Partial solution to Advent of Code 2017 Day 4 Part 2

aoc2017day4p2.py

# Once you know the Cartesian (x, y) coordinate of spiral position i in Part 1,
# you can compute Part 2 really easily using just a map from coordinates to int.
# map[(0,0)] = 1, and then you go around the spiral. At each new coordinate, you look
# at its nine neighbors with a pair of for loops. Most of them (including the new position)
# won't be in there.

# Here's a Python implementation to show what I mean.

# Essentially a Fibonacci-style dynamic
# programming calculation but with 2-3 neighbors.
def soln2(n):
    # Keep a map of values we've computed so far.
    spiral = dict()
    # Start the recurrence with the initial value.
    spiral[spiralCoord(1)] = 1
    # Now run the recurrence forward until the input is
    # exceeded, then take the last answer.
    i = 2
    while True:
        # Where are we?
        x, y = spiralCoord(i)
        # Compute the recurrence.
        t = 0
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                dc = (x + dx, y + dy)
                if dc in spiral:
                    t += spiral[dc]
        # Is this what we were looking for?
        if t > n:
            return t
        # Save for future computation.
        spiral[(x, y)] = t
        # Next recurrence step.
        i += 1