Solution for Advent of Code 2016 - Day 18: Like a Rogue

Link to the puzzle text

Part 1

In this puzzle we are asked to find safe tiles in a tile pattern. Only the first row is explicitly given, the next rows are computed from the previous by a simple rule. The state of each tile in the next row depends on the state in the current row and the neighbors. The answer are the number of safe fields in a field with 40 rows.

This pattern is basically a cellular automata, specifically rule 90. We can generate each row by using a sliding window over the previous row and checking for one of the states which turn a field into a trap.

def generate_next_row(row):
    new_row = ""
    for i in range(1, len(row) - 1):
        char = "."
        if row[i-1:i+2] in ["^^.", ".^^", "..^", "^.."]:
            char = "^"
        new_row += char
    return new_row

We then call this function 39 times (we already have the first row given) and count the number of "." character appearing.

Part 2

In part 2, we should count the number of safe fields in 400000 rows.

The function above is reasonably fast, so we can reuse the previous code and just increase the number of iterations.

Link to my solutions