# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python [conda env:adventofcode]
#     language: python
#     name: conda-env-adventofcode-py
# ---

# # Spiral Memory

# + active=""
# 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

puzzle_input = 312051

# ## Part 1

# +
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

spiral_manhattan(1)

spiral_manhattan(12)

spiral_manhattan(23)

spiral_manhattan(1024)

# ### Solution

spiral_manhattan(puzzle_input)

# ## Part 2

# + active=""
# 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--->   ...

# +
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)]


# -

first_larger(puzzle_input)

StarcoderdataJupyterScriptsDedupFiltered