Navigating over a square spiral

Question

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.

Answer 1

I wrote my answer in c++, it might help you. On first look, our solutions are quite similar, at least from an idea standpoint.

//
// Created by Felix Crazzolara on 09.12.17.
//
#include <cstdlib>
#include <iostream>
using namespace std;
int main (int argc, char* argv[]) {
 int position = 277678;
 // Find spiral radius
 int n = 1;
 while (position > n*n)
 n += 2;
 // Find side
 int side = 4;
 int pos = n*n;
 while (side > 1 && position < (pos - n + 1)) {
 pos -= n + 1;
 --side;
 }
 int middle_point = pos - (n - 1) / 2;
 int dist = abs(position - middle_point);
 dist += (n - 1) / 2;
 cout << dist << endl;
}

Explanation:
The highest number in every spiral is the bottom right corner, that has the value \$n^2\$ if we denote the length of the sides of a spiral with \$n\$.
If a spiral has side length \$n\$ obviously the next spiral has side length \$n' = n + 2\$.

Let's assume that our point is in the spiral with side length \$n\$. There are 4 corners. Our point got to be somewhere, so we want to find a corner that is greater-equal our point. Once we got the "smallest" corner being greater-equal then our point, we know, that our point must lay on the side given by the found corner and the next smaller corner.

When starring a bit on the first numbers of the memory layout, once you'll remark that the way to go the origin is given by the way to go to the closest point being vertical/horizontal in respect to the origin, being on the current spiral, plus the way from that point to the origin.

How these ideas fit together in code, I'll leave up to you to think about.

• Daniel: You ought to explain what your code does and how it improves the original code.
• Felix Crazzolara: @Coal_ fair enough