Another cellular automata! Out comes TensorFlow again, though admittedly there are other ways to solve this efficiently without. The addition of hex tiles also introduces a little challenge.

Fortunately, I've dealt with hex tiles in game dev before, so have seen the math involved already. The title image was from a hex-tile based game I was working on, and below is an animation from in-game, though this is not the data from today's challenge.

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

This part of the challenge is one involving vectors and geometry. The challenge asks you to parse lines consisting of directions (six directions: e, se, sw, w, nw, and ne) corresponding to the six neighbours of a tile in a hexagonal grid.

Here's three lines from the example:

sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse

This is hard to read, but it starts with se, se, nw ... Luckily since there is no s, we know that every time we see an se there's no confusion with an s followed by an e.

Importing the data

Since every token ends in either an e or a w, we can easily delimit it by adding a separator after those characters:

raw = open("input.txt").read().replace("e", "e,").replace("w", "w,").splitlines()

This causes our output to look like:

['se,se,nw,ne,ne,ne,w,se,e,sw,w,sw,sw,w,ne,ne,w,se,w,sw,',
 'ne,e,e,ne,se,nw,nw,w,sw,ne,ne,w,nw,w,se,w,ne,nw,se,sw,e,sw,',
 'se,sw,ne,sw,sw,se,nw,w,nw,se,',
...

Which we can proceed to split using the , character when we come to parsing the data

The coordinate system

There are a few different coordinate systems in use for hex tiles, Red Blob Games' blog has an amazingly helpful page on this geared at game developers, which I used previously. Each of the six directions map to a vector in cartesian space, and adding together any combination of these six vectors lets you traverse the hex grid.

Screenshot from Red Blob Games' blog:

Complex numbers

Python supports complex numbers. And while complex numbers have some hocus pocus to do with imaginary numbers, the important thing for us is that the real and imaginary components of the complex number are orthogonal - they don't interact during addition/subtraction, so we can ignore the fact that it contains imaginary numbers, and just use the complex numbers as a 2-element vector that we can add together without using numpy.

We create a lookup for the six vectors from the above coordinate system, expressed in complex numbers:

vecs = {
    "e":   1 + 0j ,
    "se":  0 + 1j ,
    "sw": -1 + 1j ,
    "w":  -1 + 0j ,
    "nw":  0 - 1j ,
    "ne":  1 - 1j ,
}

Applying this to all our data (this is where that .split(",") comes in, we also need to ignore the last empty entry as well because our strings end in , now):

data = [map(vecs.__getitem__, line[:-1].split(",")) for line in raw]

The result is a list of list of vectors. For example, the first entry (sesenwnenenewseeswwswswwnenewsewsw) is now:

[1j, 1j, -1j, (1-1j), (1-1j), (1-1j), (-1+0j), 1j, (1+0j), (-1+1j), (-1+0j), (-1+1j), (-1+1j), (-1+0j), (1-1j), (1-1j), (-1+0j), 1j, (-1+0j), (-1+1j)]

Sum the vectors

Each vector in the list represents a move from the start tile. We want to know where the move ends up, so we can simply sum the vectors in this list. Since it's actually just a list of numbers (albeit complex ones), we can do this with sum()

The each line in the challenge leads to a particular tile, and for each line, that targeted tile is flipped. A given tile can be flipped multiple times, so we have to resolve the target tile for each of the lines of input, and work out how many times that tile has been flipped.

To do this, we use an XOR to do the flipping, and a defaultdict that contains a bool. False is an unflipped (white) tile, and True is a flipped (black) tile:

from collections import defaultdict
tiles_flipped = defaultdict(bool)
for line in data:
    tiles_flipped[sum(line)] ^= True

This yields us a dict of tiles that were landed on, and their flipped state. This is the output for the demo data:

defaultdict(bool,
            {(-3+2j): True,
             (1-3j): False,
             (-3+3j): True,
             (2-2j): False,
             (1-2j): False,
             (-1+0j): False,
             (-2+0j): True,
             -1j: True,
             (-2+1j): True,
             -2j: False,
             (3-3j): True,
             2j: True,
             0j: True,
             (2+0j): True,
             (-1-1j): True})

Finally, we want to know how many black tiles, so we can just sum the values:

print("sum", sum(tiles_flipped.values()))

The full code for Part 1:

from collections import defaultdict

vecs = {
    "e":   1 + 0j ,
    "se":  0 + 1j ,
    "sw": -1 + 1j ,
    "w":  -1 + 0j ,
    "nw":  0 - 1j ,
    "ne":  1 - 1j ,
}
raw = open("input.txt").read().replace("e", "e,").replace("w", "w,").splitlines()
data = [list(map(vecs.__getitem__, line[:-1].split(","))) for line in raw]

tiles_flipped = defaultdict(bool)
for line in data:
    tiles_flipped[sum(line)] ^= True
print("sum", sum(tiles_flipped.values()))

The Challenge Part 2

In the second part of the challenge, we encounter a cellular automata again. The rules are fairly basic:

• black tiles flip to white if they are surrounded by 0 or more than 2 black tiles
• white tiles flip to black if they are surrounded by 2 black tiles

TensorFlow

Without hesitation, the TensorFlow code comes out again. TensorFlow allows us to calculate these grids with a lot of efficiency since it can parallelize the operations. We're not really using it for any machine learning, just its parallel matrix/tensor handling capabilities.

A with before, rather than grow the grid size, I just give it a "big enough" grid to play in. Since we have 100 steps, then 100 in either direction, give or take a few, should be enough - the grid can't grow faster than 1 tile per round.

The following code sets up our grid with the data, using the coords found from last step, and setting 0, 0 to be in the middle of the big grid.

import numpy as np
import tensorflow as tf

big_enough = 200
grid = np.zeros([big_enough,big_enough])
xdim, ydim = grid.shape

for coord, colour in tiles_flipped.items():
    gc = coord + (1+1j)*big_enough/2
    grid[int(gc.real), int(gc.imag)] = colour

Convolution filter

A slight difference here is what our convolution filter looks like. since we're on a hex grid, we have six neighbors instead of eight. We need the correct six neighbors though, and it's the six that we can reach using the six vectors defined previously. While we could calculate it by applying the vectors, for now it's quicker to just bake it in by hand.

padding = tf.constant([[1, 1], [1, 1]])
neighbors_filt = tf.constant([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])
conv_filt = tf.reshape(tf.cast(neighbors_filt, tf.float32),  [3, 3, 1, 1])

Karnaugh maps

We have to translate our rules into a logical operation. The rules say:

• black tiles flip to white if they are surrounded by 0 or more than 2 black tiles
• white tiles flip to black if they are surrounded by 2 black tiles

We can create two rules like this:

• Rule W: Tiles that are surrounded by 0 or more than 2 black tiles
• Rule B: Tiles that are surrounded by 2 black tiles

And then we can say: If it's black and Rule W applies, it becomes white. If it's white and rule B applies, it becomes black. In boolean logic: Q' = (Q & W) | (!Q & B)

Can we simplify this expression? Yes, we can either do some boolean algebra, or, use a graphical method I picked up from digital electronics called Karnaugh Maps. I won't go too much into it, but the following Karnaugh map generated from the truth table I want to achieve shows that we can reduce the expression down to: Q' = B | (Q & !W)

We can easily re-write our first rule as !W to save another operation.

The end result is:

@tf.function
def generate(this_gen):
    padded = tf.pad(this_gen, padding)
    padded = tf.reshape(padded, [1, ydim+2, xdim+2, 1]) # need for tf.nn.convolution

    convolved = tf.nn.convolution(tf.cast(padded, tf.float32), conv_filt)
    neighbors = tf.reshape(convolved, [xdim, ydim])

    rule_nw = tf.math.logical_or(neighbors == 1, neighbors == 2)
    rule_b = (neighbors == 2)

    return tf.math.logical_or(tf.math.logical_and(this_gen, rule_nw), rule_b)

Running it

Same code as before:

generation = init_data
for _ in range(100):
    generation = generate(generation)
print("total", tf.math.reduce_sum(tf.cast(generation, tf.int32)))

The full code for this part (including part 1 code needed):

from collections import defaultdict
import numpy as np
import tensorflow as tf

vecs = {
    "e":   1 + 0j ,
    "se":  0 + 1j ,
    "sw": -1 + 1j ,
    "w":  -1 + 0j ,
    "nw":  0 - 1j ,
    "ne":  1 - 1j ,
}
raw = open("input.txt").read().replace("e", "e,").replace("w", "w,").splitlines()
data = [list(map(vecs.__getitem__, line[:-1].split(","))) for line in raw]

tiles_flipped = defaultdict(bool)
for line in data:
    tiles_flipped[sum(line)] ^= True
print("sum", sum(tiles_flipped.values()))

big_enough = 200
grid = np.zeros([big_enough,big_enough])
xdim, ydim = grid.shape

for coord, colour in tiles_flipped.items():
    gc = coord + (1+1j)*big_enough/2
    grid[int(gc.real), int(gc.imag)] = colour

padding = tf.constant([[1, 1], [1, 1]])
neighbors_filt = tf.constant([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])
conv_filt = tf.reshape(tf.cast(neighbors_filt, tf.float32),  [3, 3, 1, 1])

init_data = tf.cast(grid, tf.bool)

@tf.function
def generate(this_gen):
    padded = tf.pad(this_gen, padding)
    padded = tf.reshape(padded, [1, ydim+2, xdim+2, 1]) # need for tf.nn.convolution

    convolved = tf.nn.convolution(tf.cast(padded, tf.float32), conv_filt)
    neighbors = tf.reshape(convolved, [xdim, ydim])

    rule_nw = tf.math.logical_or(neighbors == 1, neighbors == 2)
    rule_b = (neighbors == 2)

    next_gen = tf.math.logical_or(tf.math.logical_and(this_gen, rule_nw), rule_b)
    return next_gen

generation = init_data
for _ in range(100):
    generation = generate(generation)
print("total", tf.math.reduce_sum(tf.cast(generation, tf.int32)))

Happy Holidays!