Whoops! Looks like I may have spoken too soon yesterday when I mentioned Conway's Game of Life.
On Day 12, we're actually implementing a variation on Conway's Game of Life... Plant Life, that is. Whether or not a plant is around for the next generation depends on what the plant-life around it looks like on the previous generation.
I will give 100 internet points to anyone who submits a cool animation with their solution! I will also award 5 bonus internet points for each plant pun we get along the way. Good luck! I'm rooting for you!
Top comments (14)
Kotlin Solution
This one was similar to a previous year's problem, but it's thankfully in 2d.
Part 1
"Just" make a map of the rules, chunk the input into 5 char seedlings and map them to the rules.
Oh wait... it can grow left and right... better add some padding.
Part 2
This one seemed like it might be hard, but then I realized that part1 was fast enough that I could just do the first couple hundred and watch for loops.
I didn't get a loop, but I did see a consistency! I made a quick function to seek for that and voila! (That's French, for 'voila!')
Bonus Content
Single line:
Multi line:
Actual GIF output from AWT:
EDIT: FORGOT PLANT PUNS:
Um... hopefully this one isn't leaving you out in the weeds?
Er... put the petal to the metal?
Uh... Orange you glad I didn't say banana? (Does fruit count?)
Haha, love your visualisations! Always fascinating how such simple things can create such complexity.
(Slightly off-topic, but I once came across these "meta-pixel" in Conway's Game of Life which literally gave me goose bumps: youtube.com/watch?v=xP5-iIeKXE8)
GET. OUT. This is amazing. Thank you.
Full marks + animations + bonus plant puns! Checking for loops was a good idea. I didn't think of that until I cheated and looked at the discussion here :/
Python.
Part 1
Part 2
Part 1 would be easy for anyone who has ever coded Game of Life (I somehow managed to leave out last line on the input so I spent unreasonable amount of time debugging).
For part 2 after seeing that even 10k generations take a lot I started to look for a pattern and came up with a formula to calculate value for any generation bigger than ~160 (that's when it starts to loop).
php
readFile.php
Part 1 was easy. I used regular expressions to match the rules against the pots, and I needed to keep a record at what position the current pattern starts.
Running it for many more than 20 steps I discovered the pattern stays the same, only moving to the right. So I printed its value for two different numbers, the rest was just two equations:
Ahhh, a one-dimensional Conway's Game of Life.
Part 1 is easy enough - the tricky part is that the space is unbounded. I modelled the row of plants as a boolean array where the first and last are always true (i.e. the left and rightmost plants) and the position of the leftmost plant is stored separately. Thus if the row grows to the right the array gets longer and the origin stays the same, and if it grows to the left the array also gets longer but the origin decreases.
At first I translated the rules into a map of
BooleanArray
toBoolean
but the lookups seemed to have trouble so I converted the five bits of a rule's left hand side to an integer and used that as the key:The use of
&&
and||
for logic andand
andor
for boolean operations in Kotlin seems the wrong way round. Yes you want to bring C / Java programmers with you when you introduce a new language, but in this case I'd have gone for Python's readability.Parsing
Parsing the input data of course uses JParsec. It's just so much easier not to have to deal with questions like "did I find all the parts?" or "does the rule have exactly 5 positions on the left" etc. It either parses or it throws an error and tells you the line and column where the parsing failed.
Part 1
Running one generation of the game involves:
Sequence
so the memory footprint is sequential rather than all at once.Part 1 is just doing that 20 times.
Part 2
At first you read part 2 and think "oh, just up the iteration count to 50 billion".
No.
The secret is that the rules inevitably lead to a repeating pattern. Work out where the loop is, work out how many loops occur in 50 billion iterations, then you only need to run the loop once. The tricky part in this puzzle is that the same pattern of plants may occur with a different origin. Conway's original Game of Life is famous for its walker structures that move across the 2D space, replicating themselves perfectly.
I built a map keyed by a string representation of the plant pattern. When the current state already exists in the map, we have detected a loop. The value stored in the map describes the start of the loop. Then it's just a matter of determining the number of loops, the length of the last incomplete loop (if present), assemble the state at the end of the final loop and finish the sequence. All while avoiding 50 billion opportunities for an off-by-one error.
In my case the loop was only one iteration long, but I suspect that's not true for everyone. My
lastState
calculation's else branch is therefore never taken so I don't have full confidence that's the correct logic.I should also point out I took eight attempts to submit the right answer, constantly tweaking my code before realising I was doing 5 billion iterations, not 50 billion. I should have used the underscore syntax for the big number earlier.
Part B, so sneaky! Part A is uncommented, Part B commented.
A python solution.
Here is currently my Python code for today. Took me some time because I did not understand that we had to sum the indeces of the pots(!).
For part 2 I am looking for loops in the evolution, so that if we reach a plant state (regardless of the indeces) that we have reached before, we loop over those same circular steps without recalculation until reaching to the end.
I could clean up a little, especially the code that cleans up the borders. Maybe if I find time I will do it, but I first hope to later make a Golang solution based on my Python code.
Here is the Golang code. I don't think this is the best way of doing it in Golang, but it does the job!
JavaScript solution
I'm gonna omit reader.js which is the same as the other solutions, but you can find it at github.com/themindfuldev/advent-of...
12-common.js
12a.js
12b.js
I got part 1 done, but couldn't figure out how I could possibly do that big of a number of generations. So, I peeked (a little) here and, without seeing anyone explicitly giving it away -- but reading enough of the responses to get ideas -- I figured out the trick.