Solution for Advent of Code 2017 - Day 3: Spiral Memory

Link to the puzzle text

Part 1

In this puzzle, there is a two-dimensional grid of numbers. The numbers are filled from the center in a spiral pattern. We are asked to find the distance from the field containing our input number to the center.

Recreating the spiral pattern is not necessary for this part, we can check if we know some fields in advance. For example, the lower right corners are always squares of odd numbers. Going backwards from that, we can find the numbers on the straights lines straight from the center. We can also find the spiral layer our input number is in:

def layer(n):
    return math.ceil((math.sqrt(n) - 1) / 2)

Once we have a few fixed points on the correct layer, we can find the minimal distance to one of those points and the total distance:

def part_1(n):
    l = layer(n)
    return l + min([abs(n - x) for x in straight_lines(l)])

Part 2

In part 2, the pattern used to fill the fields is the same. The values used to fill in are now calculated by summing up all neighboring fields, treating empty fields as 0. Once we get a value higher than our input, we should return it as answer.

We decided to just implement the filling instead of finding a better solution. In a loop, we advance to the next position and sum up the neighboring fields:

while True:
    pos_x, pos_y = next_coords(pos_x, pos_y)
    sum_values = sum([values[x, y] for x, y in get_neighbors(pos_x, pos_y)])
    values[(pos_x, pos_y)] = sum_values
    if sum_values >= n:
        return sum_values

The values could also be taken from the OEIS under the number A141481 instead of calculated.

Link to my solutions