### 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 Manhattan Distance from that point to the origin (

`1`

)?

This same sort of structure comes up from time to time in Project Euler as well. I’m going to guess we’ll see this again. Seems like a fine contender for a library function.

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).

```
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^{1}. :)

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.

```
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
```

- And I do. That’s pretty cool
^{1}.^{[return]} - Hint: We don’t.
^{[return]}