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.
from itertools import cycle
Overall the main body is pretty simple. We are generating a list of lists, all with
None of dimension size
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
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
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
Points. We defined
__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
_set() methods using
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.
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
(n-1) * 4 - (row - 1). Then it runs that length backwards.
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.