AoC 2017 Day 3: Spiraly

Source: Spiral Memory

Part 1: Create a grid in a spiral pattern like so:

17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23—> …

e>

The neat part here is using a generator to generate the coordinates of points. That way, we can run the generator until we find the point we’re looking for and cache any results for later.

I’m also using a trick I’ve used before where I’m indexing with a tuple. So we can do things like this:

>>> import lib

>>> grid = lib.SpiralGrid()

>>> grid[0, 0]
1

>>> grid[1]
(0, 0)

>>> grid[3, 4]
80

>>> grid[80]
(3, 4)

That’s pretty cool if I do say so myself1. :)

Now that we have the grid, we can get any point we want and then calculate the distance:

lib.add_argument('index')

grid = lib.SpiralGrid()

x, y = grid[lib.param('index')]
print(abs(x) + abs(y))

Coolio.

Part 2: Rather than numbering the grid 1, 2, 3..., assign each grid point a value equal to the sum of neighbors already assigned. As an example, the center of the grid would look like this:

17 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23—> …


... well that's fun. I made my cool abstract spiral, but it doesn't support this (there's no way to know specifically what order it's generating points in). We can be a bit creative though, since we do know it will generate points in order. Start with the center point and calculate our `sum_of_neighbors` ourselves.


```python
grid = lib.SpiralGrid()

values = {}
values[0, 0] = 1

for i in itertools.count(2):
    x, y = grid[i]

    # Calculate sum of neighbor values we've already calculated for the new value
    sum_of_neighbors = sum(
        values[x + xd, y + yd]
        for xd in (-1, 0, 1)
        for yd in (-1, 0, 1)
        if (not xd == yd == 0) and (x + xd, y + yd) in values
    )
    values[x, y] = sum_of_neighbors

    # As soon as we see one bigger than the given index, bail out
    if sum_of_neighbors > int(lib.param('index')):
        print(sum_of_neighbors)
        break

It’s a bit ugly, but it works.

Now I just hope we do actually use that SpiralGrid again later…2

It’s cool how quick this is for something that seems like it could be relatively complicated:

$ python3 run-all.py day-03

day-03  python3 spiraly.py 347991 --part 1      0.6469540596008301      480
day-03  python3 spiraly.py 347991 --part 2      0.0639350414276123      349975

  1. And I do. That’s pretty cool1. ↩︎

  2. Hint: We don’t. ↩︎