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—> …

> Given a specific index, what is the [[wiki:Manhattan Distance]]() from that point to the origin (`1`)?




This same sort of structure comes up from time to time in [Project Euler](/programming/sources/project-euler/) as well. I'm going to guess we'll see this again. Seems like a fine contender for a [library function](https://blog.jverkamp.com/2017/12/01/aoc-2017-library-functions/).

Specifically, we'll create a `SpiralGrid` class that can be used to automatically generate as large of a grid as we want lazily (it won't generate more of the grid until we need it).

```python
class SpiralGrid():
    '''
    Generate a spiral grid that looks 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---> ...

    The point (0, 0) is 1. x runs left to right, y from top to bottom. So the
    point 12 is at (2, -1).
    '''

    def __init__(self):
        self._indexes = {}
        self._points = {}

        def make_spiral():
            index = 1
            (x, y) = (0, 0)

            yield index, (x, y)

            # Build the layers outwards
            for layer in itertools.count(1):
                # Each layer starts by going right and down one (we'll go back up before yielding)
                x += 1
                y += 1

                # Go through the four sides, up then left then down then right
                # Repeat 2*layer times per side
                for xd, yd in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
                    for step in range(2 * layer):
                        index += 1
                        x += xd
                        y += yd
                        yield index, (x, y)

        self._generator = make_spiral()

    def __getitem__(self, key):
        '''
        Given an index or point return the other.

        If we're given an integer, it's an index, return the point.
        If we're given a tuple, it's a point, return the index.

        Either way, generate as much data as we need and don't have.
        '''

        if isinstance(key, int):
            field = self._indexes
        elif isinstance(key, str):
            key = int(key)
            field = self._indexes
        elif isinstance(key, tuple) and len(key) == 2:
            field = self._points
        else:
            raise ValueError

        while key not in field:
            index, point = next(self._generator)
            self._indexes[index] = point
            self._points[point] = index

        return field[key]

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 myself¹. :)

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…²

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