profile

Rodrigo Girão Serrão

🐍📝 snail grid algorithmic challenge

published4 months ago
10 min read

Hey there, how are you doing?

In this issue of the Mathspp Insider we will go over a couple of Python solutions to an algorithmic challenge, and in the process learn a lot about grids and itertools.


Remote Python workshops

I am preparing one or two remote workshops for September. I have some ideas that would make for great workshop topics, but I would like to hear from you too!

If you are potentially interested in a remote Python workshop, help me decide what are the best topics. I prepared a 3 minute survey with 3 questions for you. You can fill out the survey here. Thank you for your input!


Snail grid challenge

A couple of days ago, I posted a challenge on Twitter:

twitter profile avatar
Rodrigo 🐍📝
Twitter Logo
@mathsppblog
August 11th 2022
36
Retweets
211
Likes

Now, I will go over the solutions that people submitted and I will explain how they work. I will start with the naive solution I wrote down before posting the challenge, and then we will do a deep dive into the other submissions.

The challenge

Just to make sure we are on the same page, the challenge was to define a function that produce a square grid of integers. If the grid had side length n, the numbers would go from 1 to n². The number 1 goes on the top left, then the numbers should define a spiral that goes clockwise and inwards. Here is an example:

>>> print_grid(involute(5))
 1,  2,  3,  4,  5
16, 17, 18, 19,  6
15, 24, 25, 20,  7
14, 23, 22, 21,  8
13, 12, 11, 10,  9

The output grid

In the challenge specification, I said that the output could be a NumPy square matrix or a Python “matrix” as a list of lists. So, in actuality, my function returns a list of lists:

>>> involute(5)
[[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

Then, I defined an auxiliary function to print the grid nicely:

def print_grid(grid):
    width = len(str(len(grid) ** 2))
    print("\n".join(", ".join(f"{v:{width}}" for v in row) for row in grid))

This auxiliary function was taken from my ebook “Comprehending Comprehensions” and it goes over the whole grid, turning rows into printable lines, and then putting everything together.

A naive solution

The naive algorithm to solve this challenge is as follows:

  1. create an “empty” grid with the final size;
  2. go over the grid in the spiral pattern, filling up the numbers; and
  3. to make sure you do not go outside the grid, check the boundaries and the numbers we already filled up.

With this idea in mind, I came up with this piece of code:

from itertools import cycle

def involute(n):
    grid = [[None for _ in range(n)] for _ in range(n)]
    directions = cycle([(0, 1), (1, 0), (0, -1), (-1, 0)])
    dr, dc = next(directions)
    r, c = 0, 0
    for v in range(n * n):
        grid[r][c] = v + 1
        r_, c_ = r + dr, c + dc
        if r_ >= n or r_ < 0 or c_ >= n or c_ < 0 or grid[r_][c_]:
            dr, dc = next(directions)
        r, c = r + dr, c + dc
    return grid

Here is a code breakdown for you:

grid = [[None for _ in range(n)] for _ in range(n)]
from functools import cycle
# ...
    directions = cycle([(0, 1), (1, 0), (0, -1), (-1, 0)])
  • this creates an infinite cyclical iterable that goes through the four possible directions, always in the same order. We start with (0, 1), then we go to (1, 0), then (0, -1), then (-1, 0), and then we start over. These pairs represent, respectively, the row and column shifts that represent going to the right (0, 1), then down (1, 0), then left (0, -1), then up (-1, 0);
dr, dc = next(directions)
r, c = 0, 0
  • this initialises the direction we are going in, which is stored in dr and dc. dr is the direction for the variable r, and dc is the direction for the variable c. The variables r and c are the row and column indices, respectively;
for v in range(n * n):
    grid[r][c] = v + 1
    r_, c_ = r + dr, c + dc
    if r_ >= n or r_ < 0 or c_ >= n or c_ < 0 or grid[r_][c_]:
        dr, dc = next(directions)
    r, c = r + dr, c + dc
  • this loop goes around the grid, filling it in as we go;
grid[r][c] = v + 1
  • this fills the current position with the correct number;
r_, c_ = r + dr, c + dc
if r_ >= n or r_ < 0 or c_ >= n or c_ < 0 or grid[r_][c_]:
    dr, dc = next(directions)
  • this computes the next row and column indices, but then verifies if they are valid! That is because if we leave the grid, or if we go over a position that was already filled in before, we need to update the direction we are going in before taking another step in that direction;
r, c = r + dr, c + dc
  • finally, after adjusting the direction (dr and dc) if needed, we take another step in the direction that we should.

Naive solution without cycle

itertools.cycle is a lovely tool, but not everyone knows it. That is why someone else submitted a pretty similar solution, but using two dictionaries to encode the directions and the direction shift.

The essence of their solution is as follows:

def involute2(n):
    grid = [[None for _ in range(n)] for _ in range(n)]
    # We do not use itertools.cycle here:
    directions = {"right": (0, 1), "leftt": (0, -1), "up": (-1, 0), "down": (1, 0)}
    next_direction = {"right": "down", "down": "left", "left": "up", "up": "right"}
    current_direction = "right"
    dr, dc = directions[current_direction]
    r, c = 0, 0
    for v in range(n * n):
        grid[r][c] = v + 1
        r_, c_ = r + dr, c + dc
        if r_ >= n or r_ < 0 or c_ >= n or c_ < 0 or grid[r_][c_]:
            current_direction = next_direction[current_direction]
            dr, dc = directions[current_direction]
        r, c = r + dr, c + dc
    return grid

The dictionary next_direction is what allows you to cycle through the four different directions indirectly. Everything else is pretty much the same.

Rotations and collations

Someone else submitted a solution that is also driven by the visual pattern that this spiral creates. It is a recursive solution that works with the fact that the grid of size n can be built by adding a new row and a new column to the grid of size n - 1.

For example, here is the grid of size 3:

1, 2, 3
8, 9, 4
7, 6, 5

Here is the same grid, after rotating it twice:

5, 6, 7
4, 9, 8
3, 2, 1

Now, let me add a new row of Xs on top of that and a new column of Xs to the right of that:

X, X, X, X
5, 6, 7, X
4, 9, 8, X
3, 2, 1, X

Notice that we can go around the grid, and the numbers are all in order! And that grid is very similar to the grid of size 4, except the numbers are too small...

Here is the grid from above, but after replacing the Xs with the first few numbers of the grid of size 4:

1, 2, 3, 4
5, 6, 7, 5
4, 9, 8, 6
3, 2, 1, 7

Notice how we go from 1 to 7 in the correct order (in the top row and rightmost column), and then we go down to 1 again when we start to go left because that inner part was already there: it was the grid of size 3. However, if we could increment all the numbers in that inner part by 7, then the numbering would become correct. So, that is what we do. In short, the recursive solution is as follows:

  • recursively create the smaller grid for the previous size (so, to create the grid of size n, create the grid of size n - 1);
  • rotate the smaller grid 180 degrees;
  • increment the values of the smaller grid by 2 * n - 1; and
  • add the top row and the right column.

This is the idea behind the solution that follows, and that makes use of NumPy because NumPy makes it really easy to rotate matrices (“grids”) and to add the top row/right column:

import numpy as np

def involute3(n):
    if n <= 1:
        return np.array([1]).reshape(1, 1)
    previous = np.rot90(involute(n - 1), 2) + (n * 2 - 1)
    top = np.arange(1, n)
    right = np.arange(n, n * 2)
    return np.c_[np.r_[[top], previous], right]

I find this to be a really fun solution because it really exploits the geometry of the problem, but this is not a very efficient solution because the repeated rotations of the matrix are not very efficient.

itertools to the rescue

The solution that we will explore now is the fastest solution of the four. I will start by showing you the code, and then we will see what the code is doing. Here it is:

from itertools import accumulate, chain, cycle, tee

def add(x, y):
    return x[0] + y[0], x[1] + y[1]

def involute4(n):
    M = [[None]*n for _ in range(n)]
    directions = cycle(((0, 1), (1, 0), (0, -1), (-1, 0)))
    repeats = chain([n-1], *zip(*tee(range(n-1, 0, -1), 2)))
    moves = chain.from_iterable([d]*r for d, r in zip(directions, repeats))
    int2idx = enumerate(accumulate(moves, add, initial=(0, 0)), start=1)
    for v, (i, j) in int2idx: M[i][j] = v
    return M

The function add is responsible for adding two tuples together, but that is just an auxiliary function. The juicy parts are in the function involute4, and that is what I will cover now. The main idea behind this code isn't very different from what we have seen in the first naive solution, but this makes use of itertools to do computations, instead of using a conditional to determine whether we need to make a turn to continue the spiral grid.

  • just like in the initial solutions, we start by creating an empty grid and defining the four directions (right, down, left, and up, respectively);
  • the variable repeats will contain the number of moves in a given direction before we have to turn. Assuming we want to create a grid of size 4, this is what the value of the variable repeats is:
>>> from itertools import chain, tee
>>> n = 4
>>> list(chain([n - 1], *zip(*tee(range(n-1, 0, -1), 2))))
[3, 3, 3, 2, 2, 1, 1]

These match the spiral pattern for a grid of size 4:

 X →1 →2 →3
↑2 →1 →2 ↓1
↑1 ←1 ↓1 ↓2
←3 ←2 ←1 ↓3

So, the variable repeats tells you for how long you can go in a direction before you have to turn.

  • then, we use that information to create a long list of the moves that we will make, in terms of directions that we take. That is what the variable moves is for:
>>> moves = list(chain.from_iterable([d]*r for d, r in zip(directions, repeats)))
>>> moves
[
    (0, 1), (0, 1), (0, 1),     # go right
    (1, 0), (1, 0), (1, 0),     # go down
    (0, -1), (0, -1), (0, -1),  # go left
    (-1, 0), (-1, 0),           # go up
    (0, 1), (0, 1),             # go right
    (1, 0),                     # go down
    (0, -1)                     # go left
]

In essence, the variable moves contains each consecutive direction repeated as many times as the variable repeats says so, which we do with a generator expression inside the call to chain.from_iterable:

([d]*r for d, r in zip(directions, repeats)

Then, we use chain.from_iterable to flatten that into a single iterable. (If you are not familiar with generator expressions, you should check my ebook “Comprehending Comprehensions” because I devote a chapter to that topic.)

  • after we have the variable moves, we compute the grid index to which each move applies to. To do that, we use accumulate with a custom function that knows how to add tuples. The idea is that we go through the grid, according to the arrow pattern I showed above (the pattern that is set by the variable moves) and we compute all the indices along the way:
>>> moves
[
    (0, 1), (0, 1), (0, 1),     # go right
    (1, 0), (1, 0), (1, 0),     # go down
    (0, -1), (0, -1), (0, -1),  # go left
    (-1, 0), (-1, 0),           # go up
    (0, 1), (0, 1),             # go right
    (1, 0),                     # go down
    (0, -1)                     # go left
]
>>> list(accumulate(moves, add, initial=(0, 0)))
[
    (0, 0),                  # start
    (0, 1), (0, 2), (0, 3),  # go right
    (1, 3), (2, 3), (3, 3),  # go down
    (3, 2), (3, 1), (3, 0),  # go left
    (2, 0), (1, 0),          # go up
    (1, 1), (1, 2),          # go right
    (2, 2),                  # go down
    (2, 1)                   # go left
]

However, the solution wraps that call to accumulate with a call to enumerate, which produces the correct value associated with each index as we go through the grid. To achieve this effect, the solution uses the not-very-well-known keyword argument “start” of enumerate.

  • finally, the solution goes over that enumeration of the indices to index into the grid and assign the correct value to that position.
int2idx = enumerate(accumulate(moves, add, initial=(0, 0)), start=1)
for v, (i, j) in int2idx: M[i][j] = v
return M

In one word: brilliant.

This might feel like a lot of work, but this is approximately twice as fast as the naive solution with the for loop that checks when to make a turn in the spiral.

A closed formula for the spiral values

If you were impressed by this itertools solution, then prepare to have your socks blown off with what I will be showing you next week... I got two solutions that were very maths-based, and I will discuss those two as well! One of them, which is the most impressive solution of all (in my opinion), makes use of a closed formula to compute the values of the spiral.

You have a week to think about this! Then, I'll share that solution and write about how it works. If you come up with a different solution, and especially if you come up with a maths-based solution or a closed formula, reply to this email and I'll write about your solution as well!


Thanks for reading, and I'll see you next time!

Rodrigo.

P.S. Don't forget to let me know what topics would be interesting for remote workshops in September!