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

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
1  from itertools import cycle 
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
1  %timeit sprial(10) 
OOP Solution
1  from itertools import cycle 
This solution is a bit different. It defines coordinates as Point
, and provides some magic methods to allow
us to make better use of Point
s. 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:
1  %timeit Spiral(10) 
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:
1  def spiral(n): 
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 == (n1)
. This is the bottom row, which runs in reverse order. I noticed that the bottom left corner of every sprial
was (n1) * 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.
1  %timeit spiral(10) 
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.