Number Spiral

A while back, there was a daily programming challenge that went something like this:

Make a spiral that begins with 1 and starts from the top left, going towards the right, and ends with the square of that number.

5

// ----->
1   2  3  4 5  // |
16 17 18 19 6  // |
15 24 25 20 7  // |
14 23 22 21 8  // V
13 12 11 10 9  //
// < --------


4

1   2  3  4
12 13 14  5
11 16 15  6
10  9  8  7
Bonus points for getting the spacing right.

I rather liked this problem, it was simple enough to describe, the rules were pretty simple, and writing a quick procedural solution was pretty easy. Here I will solve this problem 3 ways in python, Procedurally, OOP, and Functionally.

Procedural Solution

from itertools import cycle

def add_tuples(*pairs: tuple) -> tuple:
    return tuple(map(sum, zip(*pairs)))

def get_block(blocks, coordinates):
    y, x = coordinates
    return blocks[y][x]

def spiral(n):
    blocks = [[None for _ in range(n)] for _ in range(n) ]
    selected = (0,0)
    directions = cycle([(0,1), (1,0), (0, -1), (-1, 0)])
    current_direction = next(directions)
    for i in range(1, n**2 + 1):
        y, x = selected
        blocks[y][x] = str(i).rjust(len(str(n)) + 1)
        try:
            next_block = add_tuples(current_direction, selected)
            assert get_block(blocks, next_block) is None
        except Exception:
            current_direction = next(directions)
            next_block = add_tuples(current_direction, selected)
        finally:
            selected = next_block
    return "\n".join(map(lambda x:" ".join(x), blocks))
    
print(sprial(10))

Overall the main body is pretty simple. We are generating a list of lists, all with None of dimension size n.

We then use itertools.cycle, which returns an infinite generator that just cycles through an iterator. In our case, this represents moving left, down, right, up, in a cycle.

I have two helper methods here, one to make adding two tuples together very easy. The other to easily get the value at coordinates out. Both of these could have been put inline in the code, but I felt it was easier to read and reason about it by naming those methods and pulling them out as functions.

I also use a try except finally block to find when the direction needs to change. This is a little ugly, since it is accepting either IndexError when the next selected block is not inside the grid, and AssertionError when the next selected block is already filled in. Not the biggest fan of using exception handling to logically branch code, but it works well in this case.

Lets see how it performs

%timeit sprial(10)
277 µs ± 10 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

OOP Solution

from itertools import cycle

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __repr__(self):
        return f"Point({self.x},{self.y})"

class Spiral:
    directions = cycle([Point(0,1), Point(1,0), Point(0, -1), Point(-1, 0)])
    
    def __init__(self, n):
        self.n = n
        self.grid = dict((Point(x,y), None) for x in range(n) for y in range(n))
        self._run()

    def _get(self, point):
        return self.grid[point]
    
    def _set(self, point, value):
        self.grid[point] = value
        
    def _run(self):
        selected = Point(0,0)
        direction = next(self.directions)
        for i in range(1, self.n**2 + 1):
            self._set(selected, str(i))
            if selected + direction not in self.grid or self._get(selected + direction) is not None:
                direction = next(self.directions)
            selected += direction
    
    def __repr__(self):
        output = ""
        for x in range(self.n):
            for y in range(self.n):
                output += self._get(Point(x,y)).rjust(len(str(self.n)) + 2)
            output += '\n'
        return output
        
print(Spiral(10))

This solution is a bit different. It defines coordinates as Point, and provides some magic methods to allow us to make better use of Points. We defined __eq__ and __hash__ so that we can compare points and we can use points has keys in a dictionary. We throw in an __add__ method to make it easy to add points together.

Next we define the Sprial class. We take in the size in the __init__ method, then create a dict of type Dict[Point, Optional[str]], which allows us to store all of the points and their values flatly. This allows us to write our _get() and _set() methods using self.grid[point].

Next we call the _run() method, which will move around the grid, adding in values based on point. Because we defined Point.__add__, it was easier to check if selected + direction in self.grid than it was to use a exception handler. This not only is less lines, but much cleaner and easier to read.

Lastly we define Spiral.__repr__ to make our print() function print the final spiral. Here we simply loop around, looking up points, and returning them.

Lets see how it performs:

%timeit Spiral(10)

654 µs ± 5.58 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

A bit slower, but much more readable and easier to manipulate for sure.

Functional Solution

This problem I spent a long time trying to solve. It was a lot of fun, but how do you create a grid like this without maintaining some sort of state or mutating variables. How to I make everything pure functions? I went to a coworker who specializes in Scala and Functional programming and his answer was simply “mathematically”.

So I spent a few hours drawing out spirals, to see how each row and column related to the number n that was given. After staring at the generated number spirals for a while, I came to a realization. Each spiral was just wrapping an identical inner spiral that had all of its numbers just offset but the perimeter of that spiral. This meant I could potentially make this a recursion problem.

Here is what I came up with:

def spiral(n):
    def f(n, offset, row):
        if n == 1:
            return [offset + 1] 
        if row == 0:
            return list(range(offset + 1, offset + 1 + n))
        elif row == (n - 1):
            return list(range(offset + ((n - 1) * 4) - (row - 1), ((n - 1) * 2) + offset, -1))
        else:
            return [(n-1) * 4 - (row - 1) + offset] \
                + f((n-2), ((n-1)*4)+offset, (row - 1)) \
                + [(n + row + offset)]
    output = ""
    for i in range(n):
        output += " ".join(map(lambda x: str(x).rjust(len(str(n))+1), (f(n, 0, i))))
        output += '\n'
    return output

So this will take some explaining, lets go case by case:

if n == 1. This is either a spiral of 1, in which case the offset is zero and the spiral is just the number 1. Or it is the center of a spiral with an odd side length.

if row == 0. This is the top edge of a spiral, which is just a sequential run of numbers of length n from left to right.

if row == (n-1). This is the bottom row, which runs in reverse order. I noticed that the bottom left corner of every sprial was (n-1) * 4 - (row - 1). Then it runs that length backwards.

everything else This is where the recursion comes in, every row that isnt the first or last row is simply first and last character calculated, and a recursive call to the spiral inside of it.

Lets see how this performs.

%timeit spiral(10)
120 µs ± 3.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Much faster. In fact it is the fastest of the solutions. That is mostly to deal with not mutating any variables, and working about crawling state. Here is an example of python where the functional verison is much faster than other version, although it is practically unreadable.