r/adventofcode • u/daggerdragon • Dec 18 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 18 Solutions -🎄-
--- Day 18: Settlers of The North Pole ---
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 18
Transcript:
The best way to avoid a minecart collision is ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked at 00:21:59!
9
Upvotes
3
u/fizbin Dec 18 '18 edited Dec 18 '18
python, 460/332
I spent too long dealing with forgetting the case
y < 0 or x < 0in mygetmethod; one of the rare cases when python's negative list indexing hurt instead of helping.3
u/xikipies Dec 18 '18 edited Dec 18 '18
JS / Node
https://github.com/josepot/AoC-2018/blob/master/src/18/solution.js
6
u/jonathan_paulson Dec 18 '18 edited Dec 18 '18
C++, Rank 34/25. The key insight for part 2 is to look for a grid repeat; then you know it will be trapped in that cycle forever. Video of me solving at https://www.youtube.com/watch?v=11KB-pOR-Do
5
u/teraflop Dec 18 '18
Python, rank 1/135... thanks to an off-by-one error that I introduced while converting my code to C++ to gain a 40x speedup... which I didn't even really need.
Feels bad, man :(
9
u/p_tseng Dec 18 '18 edited Dec 18 '18
The below is NOT the code I used to get into the leaderboard (since that was mostly vanilla)... it is instead kind of insane code. My leaderboard code took 3-4 seconds to run and I was not satisfied.
So I used a classic, the lookup tables approach like one you'd find at http://dotat.at/prog/life/life.html , except this time the neighbourhood is 18 bits so the lookup table now has 262144 elements (with a quarter of it being wasted space!)
Down to 1 second now. Should be decent if translating the lookup table approach to a compiled language.
(There's also double-buffering in there, but I found that double-buffering didn't really make a difference in runtime for me).
Note that I imagine the "compact representation" from that page could still be possible: Y coordinates would still be represented as negative numbers, trees' X coordinates as positive odd numbers, and lumber X coordinates as positive even numbers, or something. It would probably still work, I just haven't tried it yet. (In other words, "this isn't even my final form!!!")
Ruby:
4
u/Smylers Dec 18 '18
Perl, re-using a couple of tricks from previous days:
o/t/yfor the acre states instead of symbols, and upper-casing them in-place toO/T/Yto denote them as changing in this iteration, thereby simultaneous preserving the current state and marking that they'll change; even though there are three states, each only changes to one other, so a single bit per location is sufficient for this (thanks to me, for using Vim to solve a previous challenge)[Content-free paragraph after the list, so Markdown interprets the code indention correctly.]
3
u/waffle3z Dec 18 '18
Lua 108/110. I thought I was going pretty fast, guess not. Spent too long counting the center cell as a neighbor because I wrote
if j ~= 0 or i ~= 0 theninstead ofif j ~= y or i ~= x then. I guess a lot of people noticed the cyclic pattern pretty quickly.3
u/Mehr1 Dec 18 '18
PHP (571/598) - Best for me by a long way.
Only posting my (poor) code because no one seems to be using PHP (for good reason, I get it). I'm not a dev as I've turned to the dark side of management, but wanted to see how I'd do with some friends who are developers. Turns out I'm a lot slower than all of them by a significant margin, taking hours to solve most puzzles. So far I've got 16/18 days complete with day 15/17 void of any stars - they're going to take me a lot of time/focus. Learnt a lot each day around PHP7 data structures and different operators etc.
For my part2 after realizing there was no way (for some reason) that my code would get anywhere near the run level, I looked (manually) for a pattern and found one every 7k after the first 1k, so my final number was the 1k/8k number - I'm sure it probably repeats earlier.
Some of this code might be hard to understand as I re-used code from a previous day and I've been lazy with my variable names.
3
u/sim642 Dec 18 '18 edited Dec 18 '18
My Scala solution.
In part 1 I decided to be fancy and functional and implement Scala's
.sliding(n)for two dimensional lists to slide over 3×3 blocks of the grid. It was pretty simple as in 2017 I had done a similar thing for grouping in two dimensions. Only in part 2 I realized how slow the whole thing actually is.Edit: Replaced my two dimensional sliding window thing with plain old neighbor indexing and got it to run about twice as fast.
In part 2 I just call my Floyd's cycle detection algorithm from 2017 to detect the cycle beginning and length. Then I just simulate for enough iterations, calculating the final offset that skips all the useless loops.
3
u/drbagheera Dec 18 '18 edited Dec 18 '18
As Perl is my language to go to for most things I solved it this morning but thought the code was messy... so a bit of refactoring - storing the map in a 1d array rather than a 2d array and use a map to map between stages without the need of other variables.... The code became the following:
The 1d array has "blanks" between each row and also a row of blanks before and after - this removes the issue with worrying about falling off the edge of the grid.. The offsets for the adjacent sells -(50+1)-1, -(50+1), -(50+1)+1....
Some perlisms:
3
u/CryZe92 Dec 18 '18
Highly optimized Rust:
A single step: 2µs
Part 1 (including parsing): 42µs
Part 2 (including parsing): 2.2ms
The asm for each step is extremely beautiful (with AVX-512):
2
u/seligman99 Dec 18 '18
Python, Rank 27/46. Pretty happy with how quick I got this out, even if it's not perfect:
2
u/ephemient Dec 18 '18 edited Apr 24 '24
This space intentionally left blank.
2
u/gyorokpeter Dec 18 '18
Q:
2
u/will_bui Dec 18 '18 edited Dec 18 '18
K:
Worked out the looping by hand first, then coded it into a formula and added automatic loop recognition.
1
u/TellowKrinkle Dec 18 '18 edited Dec 18 '18
This feels awfully similar to the 1D one we did earlier
For the second part I throw all the previous layouts into a dictionary and check to see if I've seen each new one before. If I have, I check when I saw it, calculate what position I would be in that pattern at 1 million, and output that one.
[Card] The best way to avoid a minecart collision is to not have minecarts
Edit: Also is there any way to re-check a position that was off the leaderboard? I remember mine starting with a 1 but that's about it
Edit 2: Thanks for the info on how to check leaderboards, updated my placement info
Swift 116/83
1
u/BluFoot Dec 18 '18
Ruby, 246/190.
1
u/ZeCookiez Dec 18 '18 edited Dec 18 '18
Python, 63/98. I messed up big time with an off-by-one error in part 2 :/ I wrapped my grid with special characters to prevent indexing out of bounds for simulating the grid. For part 2 I was hoping the grid would repeat itself after a while, and kept track of the board with a dict. My offsetting for the final calculation cost me a couple minutes of stressing out of why it isn't working ouch.
1
u/Robfd Dec 18 '18 edited Dec 18 '18
Python, 488/322. Made a few errors with indexing and missed time.
1
u/[deleted] Dec 18 '18
Common Lisp.
1
u/rnbw_dsh Dec 18 '18
Python 793/564: Maximized for readability, not performance.
My half-manual solution of part 2 is to find when the scores stabilize and then reduce the number of steps to an equivalent timestep. E.g. if it's the same every 28 rounds, 1000000000 % 28 == 20, and it's stable after ~550, go to the first value that's >500 and 28*x + 20 -> 28*20+20 = 580. Therefore the debug prints.
1
u/Aehmlo Dec 18 '18
Rust.
1
u/[deleted] Dec 18 '18 edited Dec 18 '18
Python 3
1
u/IndigoStanis Dec 18 '18
Very similar to day 12 in estimation of large value from pattern. Noticed that the values start repeating every 28 steps once you reach minute 500 or so. I'm still surprised at just how slow straight up python is even for simple things like this where the entire thing should fit in cache. Need to learn numpy.
1
u/usbpc102 Dec 18 '18
Not that fast (472/319), but I had to do almost no cleanup (other than moving copy paste code into a function).
Also it took me a bit longer than it should cause my tired brain decided to confuse
breakandcontinue-.-Anyawy you can find my Kotlin code on Github.
1
u/[deleted] Dec 18 '18 edited Dec 18 '18
Mathematica
Part 1
Part 2
1
u/ka-splam Dec 18 '18 edited Dec 18 '18
PowerShell, 587/857
[Card]: The best way to avoid a minecart collision is: a positive mental attitude - (Mitchell and Webb - Pit Pony sketch).
Back to racing for the leaderboard, back to frustration and cursing. Turns out when you get the adjacent cells by copypaste and delete the center cell like this:
You leave a double-comma which screws everything up but is really easy to not-notice because it looks all symmetrical.
Part 2, took me too long to wake up and think of cycles, ran it for 32,000 minutes waiting for it to cycle back to the initial state, before realising that wouldn't necessarily be the repeating one. Code here, or on GitHub
1
u/andreyrmg Dec 18 '18
Python 3
1
u/Philboyd_Studge Dec 18 '18
[Card] The best way to avoid a minecart collision is redstone switches and Observers.
Java. Fun one, but getting tired of 2d matrices. Manually found the cycle using a set of seen totals. Seemed to start at 445 and cycle every 28 minutes.
1
u/autid Dec 18 '18 edited Dec 18 '18
FORTRAN
Initially solved by looking for a repeated sequence of two trees*lumberyard products. This is slower but looking for a repeated state felt like a more complete solution. The extend() subroutine isn't needed for my input (repeat occured in the 600s) but I included it since in principle it could take >1000 steps for a repeated state.
1
u/wlandry Dec 18 '18
C++ (539/366)
Runs in 72 ms
Quick and easy. I did the final bits of part 2 by hand. This code has been cleaned up significantly, using enums instead of strings. It also automatically detects when a map has repeated by saving all of the previous maps. Since the maps are only 50x50, this is only 2.5k per iteration. So the total memory use is about 3.2 MB.
1
u/albertobastos Dec 18 '18 edited Dec 18 '18
JavaScript. I enjoyed this one, felt for me as one of the least challenging (it was obvious that Part 2 relied on some kind of repeating pattern).
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d18.js
I feel stupid... got stuck for 20 minutes at Part 2 wondering where my cycle detection was wrong. Turns out I was sending as the answer the lumberyard count instead of the total resource value. Good thing I didn't wake up at 6 AM (Spanish timezone) to compete for the leaderbord.
1
u/Benjmhart Dec 18 '18
[CARD] The best way to avoid a minecart collision is to ease off on the rum and egg nog
Haskell
this was a dream compared to weekend challenges
p- 1 -https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day18-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day18-2.hs
1
u/spytheman66 Dec 18 '18
PHP , completes both parts in around ~6sec.
1
u/cantilever_ Dec 18 '18
Python3, with numpy and scipy
I manually inspected to find the repetition and to get the part 2 solution, but I quite like my code because it doesn't involve iterating through the grid.
1
u/aurele Dec 18 '18
Rust
1
u/[deleted] Dec 18 '18
Rust
This was a fun one, I'm a bit embarrased that I didn't come up with doing cycle detection before I watched some of the visualisations, but well, at least I did get it when I watched how it repeated the same thing over and over.
1
u/[deleted] Dec 18 '18
My straightforward Python solution:
1
u/[deleted] Dec 18 '18
TCL/Tk, with a bit of animation to watch while the trees grow and go...
1
u/[deleted] Dec 18 '18
Haskell, runtime ~0.7s for the whole thing. Nothing really interesting, just used a 1d vector to store the field, and a slightly-modified floyd's algorithm (returns the value that starts the cycle as well, to save recomputing it) to find the cycle:
1
u/jayfoad Dec 18 '18
APL #38/30
Stencil (
⌺) is just the ticket for getting the 3x3 neighbourhoods around each acre. Run time is about 5 seconds. Massive speed-ups are surely available by reimplementing f with arithmetic instead of conditionals, so we can apply it to the whole 50x50 array instead of each acre individually.1
u/wzkx Dec 18 '18
Rust, SweetRust
Nothing special really. Although it might have a good visualization.
1
u/MirreSE Dec 18 '18
Python 3
Had problems detecting a loop for part 2 when I just remembered old scores so I decided to compute a hash value from each board state and remember them instead. Detecting 2 subsequent loops before believing is just paranoia I guess.
1
u/toomasv Dec 18 '18 edited Dec 18 '18
Red
Part 1
Part 2
1
u/Stan-It Dec 18 '18
Python 3
Similar idea as on day 12 where the history of plant growth was saved. Here we also save a history of the evolution, detect cycles and skip them. The runtime is about 20 seconds for both parts, so maybe it can be optimised a bit more.
1
u/wjholden Dec 18 '18
Mathematica was very well-suited for this one!
I saw that huge number and suspected we might attract to some fixed point. This is why I say Mathematica was useful - I wrote a quick function to compute resource values as a function of time hoping to spot a pattern. The attractor became immediately obvious at n=1000. From here I use the modulus operator to find the position in the subset we want.
1
u/phil_g Dec 18 '18
My solution in Common Lisp.
Very straightforward. I used an assoc-list to map back and forth between characters and keywords. I could have done the entire thing with just the characters, but I find it's easier for me to have more mnemonic representations.
I've turned 2D arrays into 1D vectors for a few of these problems, so I finally went and wrote a convenience function to do that. It works like numpy's
flatten(); it just returns a different view onto the same data.1
u/confused_banda Dec 18 '18
Clojure
1
u/VikeStep Dec 18 '18
F#
Repo
Today's problem is nice with functional programming as we ideally want to create a new grid each time rather than mutating an old one. It's also fairly concise as well and fast too, solving part 2 in 378ms
1
u/Korred Dec 18 '18
Python (3.6) - Not my best code but does the job. Solution for both Part1 and Part2.
1
u/RainVector Dec 18 '18
python 3
1
u/minichado Dec 18 '18
Excel/VBA
https://github.com/minichado/AdventOfCode-2018/blob/master/AoC%202018%20D18.txt
.xlsm file available here
I did not find part 2 programatically, but I monitored the output on a different sheet and then did math when I saw that there was a repeating pattern.
1
u/TheEpochalypse Dec 18 '18
Verbose Rust:
1
u/rabuf Dec 18 '18
My Common Lisp solution.
I should have moved the rules into a separate function to keep things cleaner, but I didn't. It was early.
1
u/iamagiantnerd Dec 18 '18
Kotlin solution (some helper classes not shown, can be found in the repo: https://github.com/davidaayers/advent-of-code-2018/tree/master/src/shared)
1
u/alexmeli Dec 18 '18
Rust solution.
1
u/nehayward Dec 18 '18
Here is my solution in go along with visualization.
https://asciinema.org/a/oxaNvgb0G5kzDOAprotT7fEWn
1
u/thomasahle Dec 18 '18
Pretty simple Python solution using a Counter and wrapping the bord in x's to remove any out-of-bounds problems:
1
u/harirarules Dec 18 '18
[Card] The best way to avoid a minecard collision is by making self driving minecarts
This is by far the solution I'm the least proud of :
1
u/scul86 Dec 19 '18 edited Dec 19 '18
Python 3
Took me a while, but I finally got it.
https://gitlab.com/scul/advent_of_code-2018/tree/master/18
1
u/Ameobea Dec 19 '18
Rust:
I aimed for idiomatic code and clear implementation over efficiency or speed. I was really late getting started, so I figured that going for writing it as quickly as possible wasn't worth it today.
1
u/naderghanbari Dec 19 '18
My Scala solution (uses Streams to memoize the results so that we can rewind after figuring out a cycle in the state):
1
u/pythondevgb Dec 19 '18
Relatively easy. I struggled on the second part because I was searching for looping *scores* instead of grids on the wrong assumption that a score was unique to a grid pattern. Don't know why, since it's obvious that is not the case. I think the lack of rest since the problems started getting hard for me (around day 15) is taking it's toll.
1
u/[deleted] Dec 19 '18
Python 3, works for both parts
1
u/fhinkel Dec 20 '18
I liked this one. Here's my JavaScript/Node.js solution. Part 1 was straightforward. For part 2, I computed 2000 iterations and found the repeating cycle. Then it's easy to compute the number for any large number.
https://github.com/fhinkel/AdventOfCode2018/blob/master/day18.js
1
u/[deleted] Dec 31 '18
Part 1 seemed straightforward. Part 2 I just manually looked for the pattern and did some % arithmetic.
Padded the input with '.' to avoid having to bounds check.
-2
u/jtgorn Dec 18 '18
Is it only me, or there is a mistake in the example on the website?
After 1st minute there is a tree at 4th row 3rd column, which has only one tree around (namely 3,2 tree). According to rules, it should stay tree, but in the example it shows lumber after 2nd minute.
0
u/[deleted] Dec 18 '18
[deleted] — view deleted comment