# Number Spiral

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

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

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

## OOP Solution

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:

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:

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.

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.