Solution for Advent of Code 2018 - Day 12: Subterranean Sustainability

Link to the puzzle text

Part 1

In this puzzle we have an initial state of several plants and a list of rules how the plants change over time. This state is in the form of a list of currently alive plants, while the rules look at the plants surrounding each individual plant to determine the liveness in the next generation. This is basically a 1D cellular automaton where we look at the two neighbors to each side. We are asked to find the sum of all plants still alive after 20 generations.

We first simplified by only keeping track of the currently alive plants in each generation. The rule set was similarly changed to only include the neighbors sets where the plant is alive. The implementation of the cellular rules was straight forward:

def calc_new_state(state):
    new_state = []
    min_border = min(state) - 4
    max_border = max(state) + 4
    for k in range(min_border, max_border+1):
        surroundings = get_neighbors(state, k)
        if surroundings in survival_rules:
            new_state.append(k)
    return new_state

After running the function 20 times, we got a list of all still alive plants. Summing up the indices gave us the answer.

Part 2 

In part 2, we should run the process for 50 billion generations instead.

Just increasing the number of loops was not enough, since the iterations are not quick enough. Letting the process run for a bit and observing of sum of alive cells yielded a better solution. After a while, the plants were in a stable formation where each generation was just one cell to the right of its previous position. This means the sum will forever just increase by a constant each generation.

We kept track of the differences to the last sum and once these differences were constant for 10 generations we increased the current sum by the number of remaining generations.

if len(set(diffs[-10:])) == 1:
    return sum(state) + diffs[-1] * (50*10**9 - current_loop)

Link to my solutions