AoC 2016 Day 18: Its A Trap

Source: Like a Rogue

Part 1: Starting with a sequence of . and ^, generate additional rows using the rules based on the three characters above the new position.

  • ^^. -> ^
  • .^^ -> ^
  • ^.. -> ^
  • ..^ -> ^
  • Otherwise -> .

How many safe tiles (.) are there after 40 generations?

This is an elementary cellular automaton. Specifically, Rule 90. I wrote a solution to these five years ago 1 with a pretty cool web based simulator. Here’s a way to do it in Python with zip though:

# If the previous row left, center, right looks like this, the next element is a trap
trap_map = {
    ('^', '^', '.'), # Its left and center tiles are traps, but its right tile is not.
    ('.', '^', '^'), # Its center and right tiles are traps, but its left tile is not.
    ('^', '.', '.'), # Only its left tile is a trap.
    ('.', '.', '^'), # Only its right tile is a trap.
}

def next(row):
    return ''.join(
        '^' if previous in trap_map else '.'
        for previous in zip('.' + row, row, row[1:] + '.')
    )

def rows(row, height):
    yield row
    for i in range(height - 1):
        row = next(row)
        yield row

safe_count = 0
trap_count = 0

for row in rows(args.initial, args.height):
    safe_count += row.count('.')
    trap_count += row.count('^')
    logging.info(row)

print('{} safe, {} trap'.format(safe_count, trap_count))

Part 2: How many safe tiles are there after 400,000 rows?

The solution doesn’t change. It’s already as memory efficient as it can be, only keeping one row at a time.


  1. I feel old now. [return]
comments powered by Disqus