I recently found adventofcode, but when I solved Day 3 in Python, I noticed that my code isn't looking very nice. The challenge is about navigating a hypothetical memory laid out in a square spiral:
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
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---> ...
Given an input, the program should print:
- The Manhattan distance of the cell with that address to the cell with address 1 (justified by the only access port being at address 1)
For example:
- Data from square 1 is carried 0 steps, since it's at the access port.
- Data from square 12 is carried 3 steps, such as: down, left, left.
- Data from square 23 is carried only 2 steps: up twice.
Data from square 1024 must be carried 31 steps.
- The first value written to memory larger than the input during a "stress test".
As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.
- 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.
47 142 133 122 59 304 5 4 2 57 330 10 1 1 54 351 11 23 25 26 362 747 806---> ...
I'm particularly looking for tips on reducing the code repetition in the coords
function. Should I use list comprehension to sum the values? It seems quite long. Finally, is there a more Pythonic way to include a special case when a key isn't found?
from math import sqrt, floor
import itertools
# Given an address in the spiral memory, return the coordinates of that memory cell,
# where x grows when moving right, and y grows when moving down.
def coords(address):
# For a spiral of side length n, the bottom right element will have an address of n^2
# Starting from that element, the spiral goes one cell right, and then n cells up,
# n+1 cells left, n+1 cells down and n+2 cells right
# Start in the bottom right corner of the largest spiral that does not contain
# the address we are looking for.
n = floor(sqrt(address))
if n % 2 == 0:
n -= 1
# r - the radius of the spiral of side length n
r = (n - 1) // 2
address -= n ** 2
if address == 0:
return r, r
address -= 1
if address < n:
return r + 1, r - address
address -= n
if address < n + 1:
return r + 1 - address, r - n
address -= n + 1
if address < n + 1:
return r - n, r - n + address
address -= n + 1
if address < n + 2:
return r - n + address, r + 1
raise Exception("This shouldn't ever happen")
def distance(x, y):
return abs(x) + abs(y)
inp = int(input())
print(distance(*coords(inp)))
spiral = { (0, 0): 1 }
for address in itertools.count(2):
x, y = coords(address)
value = sum([spiral[(x + dx, y + dy)] for dx, dy in itertools.product([-1, 0, 1],
repeat = 2) if (x + dx, y + dy) in spiral])
spiral[(x, y)] = value
if value > inp:
print(value)
break
Note: I had to add the blockquotes in an edit because SE considers heuristics about how well an answer is formatted an absolute truth... I think something should be done about it. If I am going as far as figuring out how to unbind an event listener that doesn't let me post, it should be clear that I am certain about my formatting.