Solution for Advent of Code 2018 - Day 18: Settlers of The North Pole

Link to the puzzle text

Part 1

In this puzzle we have a 2D-grid of cells containg one out of lumberyard, trees and open ground each. Each time step, the content of the cells changes depending on the neighbouring cells, similar to the game of life. We are asked to simulate 10 steps and calculate the answer from the number of trees and lumberyards.

 

We implemented this similar to the game of life. Each time step, we copy the current grid and update each cells depending on the neighbours in the previous grid. Finally we count the cells containing the symbol for lumberyards and for trees and multiply them for the answer.

Part 2

In part 2, we should repeat the previously simulation for 1000000000 time steps.

Since this is too much for a straight forwards solution, we tried a different approach. After running the simulation for longer, it became clear the states repeat themselves. Once a grid state repeats, all following grid states are also repeating. So we ran the simulation again keeping a copy of each grid state seen until now. Once we find the first copy of a state, we can calculate which index the final state will be a copy of:

first_occurence = grid_history.index(grid)
repeats_every = t - first_occurence - 1
final_index = first_occurence + (1000000000 - first_occurence) % repeats_every - 1
final_grid = grid_history[final_index]

On this final grid, we can again count the number of lumberyards and trees for the final answer.

Link to my solutions