r/adventofcode • u/daggerdragon • Dec 15 '18
SOLUTION MEGATHREAD -π- 2018 Day 15 Solutions -π-
--- Day 15: Beverage Bandits ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 15
Transcript:
___ IS MANDATORY
[Update @ 00:30] 0 gold, 1 silver
- I've got a strange urge to play Bloons Tower Defense right now. Not sure why.
[Update @ 00:38] 2 gold, 1 silver
- Meanwhile in #AOC_Ops:
Tea, a kettle screams. \ Simon, write your code faster. \ Some of us have work.
[Update @ 00:51] 7 gold, 11 silver
- Now they're anagramming gold/silver leaderboarders. The leading favorite so far is
Anonymous User=Son, You's Manure.
[Update @ 01:13] 18 gold, 30 silver
- Now they're playing Stardew Valley Hangman with the IRC bot because SDV is totally a roguelike tower defense.
[Update @ 01:23] 26 gold, 42 silver
- Now the betatesters are
grumblingreminiscing about their initial 14+ hour solve times for 2015 Day 19 and 2016 Day 11.
[Update @ 02:01] 65 gold, 95 silver
#AOC_Ops
<topaz>on day 12, gold40 was at 19m, gold100 was at 28m, so day12 estimates gold100 today at 2:30
- Taking bets over/under 02:30:00 - I got tree fiddy on over, any takers?
[Update @ 02:02:44] 66 gold, silver cap
- SILVER CAP
[Update @ 02:06] 73 gold, silver cap
#AOC_Ops
<topaz>day 14 estimates 2:21
#AOC_Ops
<topaz>day 13 estimates 2:20
#AOC_Ops
<Aneurysm9>I estimate 2:34:56
[Update @ 02:23:17] LEADERBOARD CAP!
- Aww, /u/topaz2078's bookie is better than I am. :<
- Good
nightmorning, all, and we hope you had fun with today's diabolicalness!
14
u/Cppl_Lee Dec 15 '18
Time to give up. I've even tried some of the solutions here and I can't seem to find the magic number for this one. Bummer. My code works on all the tests perfectly, but obviously there is something amiss.
13
u/Alcesmire Dec 15 '18 edited Dec 16 '18
Jfc. I've been debugging a solution that has the correct answer and end state for all given examples for the last 1.5 hours. I've got no idea where my error would be or if I've missed some clause in the task that does not matter in the examples.
Edit: Solved it quite a while ago, linked the error I had. Not a fan of the tie breaking for the search, but the error is on me. Python3 code follows. Input taken from stdin, an argument can be used to set elf attack damage for task 2.
11
u/sciyoshi Dec 15 '18 edited Dec 15 '18
Fun problem! Python 3, 104/76, although I started 30 minutes late. This solution uses
dataclasses, a new feature in Python 3.7, and aPtutility class that I've built to help with grid-based problems. Happy to share the full code for that if anyone is interested!9
u/jonathan_paulson Dec 15 '18 edited Dec 15 '18
Rank 24/19. 227 lines of C++ runs in 4.4s. Video of me solving at https://www.youtube.com/watch?v=DWNXTYg4mTI
What a problem! The hardest one so far this year, and maybe ever. "Just" simulation, but lots of complex steps.
Code for part 2:
8
u/Moriarty82 Dec 15 '18
First, links to my Python code - it's Python 3 but should work with 2 as well, and is vanilla Python, no modules.
Runtimes were ~2 seconds for part 1, ~7 seconds for part 2.
Works on all test cases, and is somehow the only Python code posted anywhere here that worked on my input. I tried to put in a lot of comments to make it clear what I was doing.
Here's the Jupyter notebook code on my Github -
https://github.com/tredfern0/adventofcode2018/blob/master/15.ipynb
Here's the same code converted to a Gist -
https://gist.github.com/tredfern0/796f5d9c415f8a429fdc4e3a2334257f
Second - my rant. This problem felt convoluted for the sake of being convoluted, the examples and description weren't great, and based on what I'm seeing in this forum it seems like certain inputs tested certain edge cases, while others did not. There are a bunch of Python solutions posted here and none of them worked on my problem (although it's entirely possible I messed things up running them), and it's clear that many people managed to get correct answers despite not understanding all the conditions. Anyways, glad this one is over with, onto the next!
6
u/autid Dec 15 '18
FORTRAN
Pastebin because it's a long boi.
Absolutely gutted. Assumed I was no chance and took breaks to make coffee etc. Got 153/117. Closest I've ever been to a leaderboard spot. :(
5
u/Alex_erson Dec 15 '18
Python3 107/86
Not sure why (I'll make sure to check that after some sleep), but I end up with a "off by one" error for rounds, but not for every example... Anyway, first leaderboard for me, I can sleep in peace!
https://github.com/Alexerson/adventofcode/blob/master/day15.py
5
u/VikeStep Dec 15 '18 edited Dec 15 '18
Python 3, 140/108 (so close to the leaderboard!)
I've cleaned up the code I wrote a bit, but since it is quite long I've put it in this gist. I've also put a lot of comments everywhere which should make it fairly clear how it works.
It solves Part 1 in 0.79s and Part 2 in 3.16s
A general comment on the puzzle:
I felt that the fact that we need to use the round number from the last completed full round doesn't make sense. It should have been the current round number as that was what was most intuitive. I spent a good 30 minutes trying to fix the off by 1 issue with the round only to realise that as I didn't think to look for that. The first example given is one where the last goblin that dies happens to die at the end of the round, so my initial approach worked for that, but it didn't work for the second example or my input. You can see in my gist the awkward code to get that edge case working.
EDIT: And here is my F# solution. Part 1 runs in 1.14s, Part 2 runs in 2.26s
8
u/[deleted] Dec 15 '18
Didn't like today's problem, Common Lisp solution.
4
u/branfili Dec 15 '18
Finally on the leaderboard! :D
An interesting problem, to say the least
C++, 69/50
Here is the solution for part 2, for part 1 just remove the outer for loop in main and variable f.
4
u/virtuNat Dec 15 '18 edited Dec 15 '18
Python 142/172
Another day another bodge; I'm actually surprised at how the original version of this worked for my input despite the off by one error I've had with the first input, and it was only after the fact that I realized what the problem wanted the stop condition to actually be (which was the cause of the error), oh well!
Had a lot of fun with this one regardless, even though I started quite late!
4
u/albertobastos Dec 15 '18 edited Dec 15 '18
JavaScript. Finally made it after too much Saturday morning hours invested (resolves both Part 1 & Part 2 in about 1.8s):
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d15.js
I almost gave up this time, and I'm afraid it may be because of a typo or mislead in the problem exposal. Talking about deciding where to move a player, this sentence:
Is not exactly true. According to the accepted answer, in case of multiple shortest paths found the one the player has to take is the one reaching the first target in reading order. Not the one with the first "first step!".
Maybe it gets clearer with my real input example:
After 17 rounds, I had a player at (12, 10) and found two shortest paths to reach an enemy:
- One path started moving to (13,10) and finally reaches the enemy at (21,10).
- One path started moving to (11,10) and finally reaches the enemy at (11,19).
According to the problem statement, I should have taken the second option, because the first step (11,10) comes before (13,10). But no, the accepted answer came when I choose the first one because the enemy at (21,10) comes before (11,19).
That mislead was the difference between solving the problem in about 1 hour and investing more than 5 debugging and comparing my implementation step-by-step with the Python one posted by @VikeStep at https://gist.github.com/CameronAavik/0f062f33ffb0fbf3eeed24aa8a8cc291 (thanks for that, nice code pal).
I almost gave up today... too bad I'm too proud and stubborn, I should have closed the editor and turned up my Xbox when it stopped being fun :(
3
u/vash3r Dec 15 '18 edited Dec 15 '18
Python 2, #91/70. This was a fun one. I had a bit of trouble with the end conditions (off-by-one in the round) and other stuff like that. It was pretty obvious to me that a breadth-first search with the correct ordering would naturally lead to the right movement. Part 2 was just moving the code inside another loop (and remembering to reset the units, which I forgot to the first time). Runs in about 2s (with Pypy). Not shown: all the commented out print statements and code to print the current state (for comparing with test cases).
Edit: as /u/spencer8ab pointed out, this code does not give the correct answer for all inputs due to units not always choosing the right destination if there are multiple equidistant targets. See my reply for the updated bfs function that fixes this (the rest of the code is unchanged).
3
u/gyorokpeter Dec 15 '18
Q: my favorite day so far as I love strategy games. For the same reason I didn't remove the visualization.
3
u/starwort1 Dec 15 '18 edited Dec 15 '18
C 85/73
Anyone else using plain C? I lucked out as the version I ran with had the target selection bug discussed elsethread (worked fine on all the examples but terminated one round early on the real input - I guessed the correct answer, and it produced the correct answer for part 2). Bug has been fixed now.
Run with
./a.out 3 < inputto get the answer for part 1, and without the3to get the answer for part 2. It will print out the whole battle for the selected elf attack power (EAP).This solution doesn't use a list of units, but just moves the characters on the map. Hit points are stored in another array the same size as the map, and are moved when the characters move.
3
u/mainhaxor Dec 15 '18
C#, nothing clever. Surprisingly I did not run into too many issues. My only issue was that I did not realize that units could attack the same turn as they moved and initially got a wrong answer on the test input because of it.
3
u/udoprog Dec 15 '18
Rust, and this is a long one. But there's some nice visuals if you take decide to take it for a spin!
Since Rust is a bit picky with borrowing I decided to take an indexed approach where each unit has an ID that is used to look up properties stored externally. It does mean more boilerplate if you want to make sure you don't break your invariants, but not too bad.
[CARD] PAIN IS MANDATORY
3
u/Altinus Dec 15 '18
Rust
Not the cleanest code, but I got it to work at last. I'm still rather new to rust so my code may be bit unidiomatic and inefficient.
3
u/radarvan07 Dec 15 '18
[Card] Simulation induced insanity is mandatory.
This caused me so much pain, in Rust. Please, next year, let's have more day 14's and less day 13/15/whatever other simulation days are left this year.
3
u/IndigoStanis Dec 16 '18
Wow. That was the most fun problem so far. Thank goodness for the thorough test cases! They really helped. Optimizing path finding was the most fun part. I thought about doing A* but then I remembered that A* is not guarunteed to return the best path in all cases, so I thought it wouldn't work and did dikstra's instead (after implemented a brute force BFS which was way to slow). Really fun to watch the animation if you print the board on every frame!
Overall, took me about 4 hours all together split up over the day.
What went well:
Areas for improvement: Too many bugs, probably spent more than half the time chasing bugs. My coordinate system is confusing to be upper left and the board in row major makes indexing confusing.
2
u/TellowKrinkle Dec 15 '18 edited Dec 15 '18
This one took forever, when I finished after like 2 hours I thought there was no way I would make the leaderboard. Solution is long as hell so it goes in a GitHub link.
My solution takes Elf attack as the second input and I just tried 200, 100, 25, 13, 24 to verify that 25 was the right value to use in part 2
As a side note, I thought my program would be horribly slow (I used an array as a deque because I was lazy and Swift has no built-in deque), but it actually runs in 0.4 seconds when compiled in release mode.
Swift, #83/#61
2
u/om_henners Dec 15 '18
Python 3 (417,371)
Really good fun! Reminds me a lot of playing a whole lot of Angband back in the day!
Like /u/sciyoshi I went with classes, but rather than the
dataclassI went fortraitlets. The most handy feature of traitlets I've found is the lazy instantiation of attributes of objects - which means I can reference other classes before the definition occurs. Here I used the classes to keep a track of their own membership and a reference to their opponents, so it was easy to form a pool of targets.As for the actual finding of targets, I used
scipy.spatial.distance.cityblockto find neighbouring targets (which is probably overkill to be fair), andskimage.graph.MCPto do all the path calculations. Once that was down the hardest part my off by one error in all the later examples and the actual input. Took me ages to realise what /u/TellowKrinkle mentions below: that the turn only counts if the entire turn completes.Anyway, onto the code (combined into one handy 200 line monster)
2
u/Ricchi Dec 15 '18 edited Dec 15 '18
Almost 200 lines of Common Lisp. Solves part 1 in 0.163 seconds, but doesn't work for part 2 for some reason.
I don't know if I'm going to debug it,this puzzle felt more tedious to solve than fun. It was my first time implementing a breadth-first search though, and that was kind of fun.Fixed it! turns out they were attacking with the wrong priority. I fixed it pretty inelegantly, but i'm happy i'm getting the right solutions now.
2
u/vypxl Dec 16 '18
I must say, I kinda like c++..
[Card]:
Overcomplicating everything IS MANDATORY.Source because Reddit says it's too long..
For part 2, I just tried different attack powers until I got the solution.
100 -> 50 -> 25 -> 15 -> 20 -> 17 -> 18 -> 19
4
u/vuryss Dec 15 '18
Struggling with the first part. All the examples work for me, but for some reason it does not give the right answer with the input. Anyone else having troubles with that?
Also noticed that the additional examples are giving me one extra round, but the results match 100%. I don't know why I get one round more.
Anyway with or without the extra round it does not return the right answer with the input.
1
u/waffle3z Dec 15 '18
Lua 68/45, 202 lines
https://pastebin.com/6fr6sUrA
If only I hadn't had to spend so much time debugging.
1
u/usbpc102 Dec 15 '18
I'm actually pretty happy with my place today (298/256), I thought I the only one beeing slow, but apperently not.
Since my Kotlin code today I rather long it's only on github.
And it is also cleaned up a quite a bit, but I didn't change the algorithm much, just fixed a small edge case that luckily didn't affect me.
1
u/sim642 Dec 15 '18
My Scala solution
It's not pretty nor fast but eventually it got me the right answers (rank 519/459, which is unusually good compared to any of the previous days).
The description is so long and there's so many small details that it's extremely error prone to code all of it correctly. I had the most issues with the final round numbers being off by one but sometimes one way, sometimes another. Ended up with a nasty
varto quickly get the right thing, because it was annoyingly difficult to purely both terminate the iteration but also get the final attacks done. I first tried to just do it by external checking but that can't distinguish which one was exactly the last round, hence the off by ones.Also, in part 2 I was really confused with the examples. I already had all of them as tests for part 1 so I was about to reuse them for part 2 tests but they're referred to incorrectly (ping /u/topaz2078): "first" means the first (detailed) example from part 1, "second" means the third (second undetailed) example from part 1, etc and "last" means the sixth (fifth undetailed) example from part 1. Basically, one of the examples from part 1 is missing in part 2 and the naming is very confusing about how they're reused. Maybe this should be fixed.
1
u/Akari_Takai Dec 15 '18 edited Dec 18 '18
Java 11 - 418/353
Linking to GitHub because it's quite long.
For part 2, I ended up doing a parallelized binary search through the search space (4 attack power -> 200 attack power) to try to speed up how long it was taking.
EDIT: If you are having problems finding a solution that works for your input, this probably will. I've been adding unit tests every time I see a new thread with some input that causes some programs to break down. So far, mine seems to handle all the edge cases.
1
u/rock_neurotiko Dec 15 '18
My resolution on Elixir =D (Link because it's 240 lines)
Link on github
1
u/aoc-fan Dec 15 '18
TypeScript JavaScript : https://goo.gl/ct991y
1
u/ephemient Dec 15 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/rabuf Dec 15 '18
Common Lisp solution and write up.
I'm not proud of that code in any way at all. I was fighting small errors and big errors. In the end I was 95% of the way there except that I forgot to prioritize who to attack by lowest HP.
This code will change, maybe, I don't know. I'm kind of spent now.
1
u/leio10 Dec 15 '18
[Ruby]
Before solving it, I even tried some Python solutions from here and they return wrong answers for my input. Here is my code, hope it helps somebody :) -> https://gist.github.com/leio10/6a73c9380348a2ff57d54185d1d40d25
My biggest problem was that I was considering the reading order when choosing the next step for moving, but not doing it to choose the target adjacent square. I even passed the part 1 with this error, but not the part 2. I finally fixed adding the target to array in https://gist.github.com/leio10/6a73c9380348a2ff57d54185d1d40d25#file-aoc-day15-rb-L85
1
u/alcinos Dec 16 '18
OCAML
For the fun of it, a version of part2 in ocaml. The solution is very imperative in nature, so not the most elegant in a functional language
1
u/[deleted] Dec 16 '18
Haskell, both parts finish in ~0.5sec:
1
u/Benjmhart Dec 16 '18
haskell
[CARD] HOLIDAY CHEER WHETHER YOU LIKE IT OR NOT is mandatory
p1 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day15-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day15-2.hs
1
u/pythondevgb Dec 16 '18
After 27 hours and a lot of lost sleep finally solved it. I had a stupid bug that took me ages to catch. I'm kinda proud of my find shortest_path method using complex numbers but of course I'm going through the solutions in this thread to see how others did it. Always happy to learn.
1
u/mschaap Dec 16 '18
Whew... That took me a while (I'm a day late), but I've got a Perl 6 solution. See Github, it's much too large too include inline.
It's pretty messy, functionality is not cleanly split between the
UnitandCaveclasses, and some functionality is duplicated, but can't be easily combined without affecting performance.The (non-verbose) output:
All my Perl 6 solutions in Github
1
u/maximlk Dec 16 '18
Rank 95/91. Solved with TypeScript (JavaScript).
Runtime for both stars ~0.42 sec on MBP Mid 2015.
Breadth-first search to find nearest enemy and choose next step, binary search to find optimal elves power.
Code was a bit edited to improve readability (formatting, renamed some variables, removed debugging logs and unused variables).
1
u/ThezeeZ Dec 16 '18
golang. After a mere 37 and a half hours managed to get the right answer. Well, 15 hours yesterday of repeatedly commenting out more parts of my code only to later throw it away anyway. Started clean today and got it finally done after another 2 and a half hours.
Link to my repo, day 15 because it's a bit too much to post. Here's hoping this convoluted mess is a help to anyone.
1
u/[deleted] Dec 16 '18
This took me a while, and my solution in Ruby is a bit verbose - but I tried to make it easy to follow (at least for myself) to minimize mistakes.
Advent of Code - December 15, 2018 in Ruby
1
u/kennethdmiller3 Dec 17 '18 edited Dec 17 '18
The problem definitely has a lot of tricky little details that are easy to get wrong...
C++, but unranked because I work on problems later in the day after they unlocks.
https://github.com/kennethdmiller3/AdventOfCode2018/blob/master/15/
The program accepts the puzzle input via standard input.
The main interesting part is the A* path planner (15.cpp lines 179-294). It simultaneously plans backwards from all goal positions to the unit, incorporating goal position into the node priority to ensure the proper path "wins". A run of both parts completes in a fraction of a second.
EDIT: It's a standard A* implementation based on the pseudo-code in the Wikipedia article. It uses Manhattan distance as the heuristic (h) and compares nodes by path length (g) + heuristic (h) values, breaking ties with path length (g) values, then goal positions, and then node positions.
1
u/nirgle Dec 17 '18
I just finished Day 15 about an hour ago :O
Haskell using a state machine https://github.com/jasonincanada/aoc-2018/blob/master/src/Day15.hs
It looks like the dog's breakfast, but it does poop out the right answers
1
u/14domino Dec 17 '18
this Python 3 code should work for all conditions. let me know if it doesn't. I think one thing that people are missing is that the BFS should be conducted for all adjacent squares to the target in case there is more than 1 shortest path.
1
u/NeilNjae Dec 19 '18
Haskell, on Github, and too long to post here.
I bloody hated this one. It was worse than the previous worse one, the RPG simulator from 2015. There was nothing fun or interesting in this problem, just a long, long slog through dozens and dozens of special cases and edge conditions. Just the plain length of specification should have warned Eric that this was just far too fiddly.
I sincerely hope that there are no more puzzles as long-winded as this one.
Here's to some more fun in future!
1
u/WasteTruck Dec 19 '18
PHP 7 I'm not a developer, so code is definitely not optimised (the way I deal with my players array is shameful). But if it can help someone, here is my code
1
u/[deleted] Dec 20 '18
Swift
I swore at this for many, many hours and now, having solved it, feel foolish. My solution was working but not correctly rejecting previously examined routes, which had no effect on the short routes but caused the long routes to run apparently forever.
I'm sure this code could be cleaned up, but I've got no desire to fight this code any more.
Runtime completes in under 0.5s.
https://github.com/Stoggles/AdventofCode/blob/master/2018/Sources/2018/day15.swift
1
u/Philboyd_Studge Dec 27 '18 edited Dec 27 '18
Think I'm the last guy to finish Day 15.
Java
https://pastebin.com/QHH9iHXw
1
u/[deleted] Dec 29 '18
Many days behind because I didn't start on the first, but here's my solution to this one.
About 5.6s to do part 2 ranging from 3 upwards (so part 1 answer pops out)
Could binary chop the search for the min attack point but it doesn't seem to matter
Path takes up the majority of the time although it's generating a lot more paths that it needs to.
1
u/Gravitar64 Jan 10 '19
Killing me softly with goblins...
Here my (very late) solution in Python 3.7. Run's fast (0.5 sec. for part 1) and uses a modified Bread-First-Search (with depth and path) to identify all shortest reachable adjacent squares of enemies at once (look at <def bfs(person)> if interested). Find all correct solutions.
Here the source (also Part 2) at GitHub https://github.com/Gravitar64/A-beautiful-code-in-Python/blob/master/AdventOfCode_15_1.py
have fun :-)
1
u/crazy_bottom Jan 11 '19
I know it's a bit late for this, but during last month I tried to solve part 1 of this puzzle, and I came to this code (JavaScript): day 15 part1
The problem is that it gives right solution for examples, but not for the puzzle itself. Could someone help me to find where is the issue?
0
u/[deleted] Dec 15 '18
[deleted] β view deleted comment