Spiral Memory

Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated 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---> ...

Input



In [1]:

    
puzzle_input = 312051

Part 1



In [149]:

    
import numpy as np

def number_to_coordinates(n):
    
    q = int(np.sqrt(n))
    r = n - q ** 2
    if q % 2 != 0:
        x = (q - 1) // 2 + min(1, r) + min(q - r + 1, 0)
        y = - (q - 1) // 2 + min(max(r - 1, 0), q)
    else:
        x = 1 - (q // 2) - min(1, r) - min(q - r + 1, 0)
        y = q // 2 - min(max(r - 1, 0), q)
    return x, y

def spiral_manhattan(n):
    x, y = number_to_coordinates(n)
    return abs(x) + abs(y)

Tests



In [152]:

    
spiral_manhattan(1)









    Out[152]:





0



In [153]:

    
spiral_manhattan(12)









    Out[153]:





3



In [156]:

    
spiral_manhattan(23)









    Out[156]:





2



In [155]:

    
spiral_manhattan(1024)









    Out[155]:





31

Solution



In [157]:

    
spiral_manhattan(puzzle_input)









    Out[157]:





430

Part 2

Square 1 starts with the value 1. Square 2 has only one adjacent filled square (with value 1), so it also stores 1. Square 3 has both of the above squares as neighbors and stores the sum of their values, 2. Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4. Square 5 only has the first and fourth squares as neighbors, so it gets the value 5. Once a square is written, its value does not change. Therefore, the first few squares would receive the following values: 147 142 133 122 59 304 5 4 2 57 330 10 1 1 54 351 11 23 25 26 362 747 806---> ...



In [178]:

    
from collections import defaultdict

def spiral_coordinates():
    n = 0
    while n >= 0:
        n += 1
        yield number_to_coordinates(n)

def first_larger(bound):
    values = defaultdict(int)
    g = spiral_coordinates()
    x, y = next(g)
    values[(x, y)] = 1
    while values[(x, y)] <= bound:
        x, y = next(g)
        values[(x, y)] = sum([values[(x + i, y + j)] for i in {-1, 0, 1} for j in {-1 , 0, 1} if (i != 0) or (j != 0)])
    return values[(x, y)]



In [186]:

    
first_larger(puzzle_input)









    Out[186]:





312453