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.
data classState(valplants:BooleanArray,valorigin:Long)
At first I translated the rules into a map of BooleanArray to Boolean 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:
data classRegion(valvalue:Int){constructor(states:List<Boolean>):this(states.fold(0){v,b->(vshl1)or(if(b)1else0)})overridefuntoString():String=listOf(16,8,4,2,1).map{b->if(valueandb!=0)'#'else'.'}.joinToString("")}
The use of && and || for logic and and and or 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.
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.