profile

Rodrigo Girão Serrão

🐍📝 mathematics is a powerful weapon

published4 months ago
9 min read

Hey there, how are you doing?

In this issue of the Mathspp Insider we will finish our analysis of the integer spiral challenge by taking a look at a very elegant mathematical solution.


Remote Python workshops

In case you missed it last week, 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

As a quick reminder, the challenge was to create a function that accepted a grid size n and then produced a square grid with that side length. The grid must be filled with the integers from 1 to n², in a spiral pattern starting at the top left and ending at the centre.

Here is an example for n = 5:

>>> 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

Last week I went over a couple of solutions and I decided to devote today's issue to the mathematical solution that follows:

A mathematical solution

def f(n, i, j):
    k = min(2 * (n - max(n - 1 - i, j)) - 1, 2 * (n - max(i, n - 1 - j)))
    return k * (2 * n - k + 1) - (i + j + 1) if k % 2 == 0 else (k - 1) * (2 * n - k) + i + j + 1

def involute(n):
    return [[f(n, i, j) for j in range(n)] for i in range(n)]

Doesn't this code look crazy? Don't worry, because it is not. It looks a bit intimidating, but thankfully, the person that shared it also included a nice explanation of how it works and, more importantly, why it works. You can find the original explanation/proof on Twitter, and I will rehash it with my own words below.

If you go through this whole explanation, I will leave a little Python reward for you at the end.

The tweet with the posted solution

twitter profile avatar
Vinícius
Twitter Logo
@ViniciusBitM
@mathsppblog pic.twitter.com/rQkHsURgCD
Video or Gif
twitter profile avatar
Rodrigo 🐍📝
@mathsppblog
Here is a Python 🐍 algorithm challenge for you. Your task is to implement a function `involute` that produces the pattern shown below. It's the pattern of a “spiral of integers” 👇 Reply with your code and then I'll write a comparison of all submissions. pic.twitter.com/6Wybp1CDhn
August 11th 2022
0
Retweets
9
Likes

The explanation

Go grab a cup or two of your favourite drink, a piece of paper, and something to write with. This is a lovely exercise but you may need your time to process everything.

Layers

The first thing that Vinícius does is think of the spiral as being composed of several layers. A nice figure really explains what Vinícius meant:

A layer represents a column and a row of the grid. If you remove one layer, you get a smaller grid. If you remove another layer, you get an even smaller grid. And so on and so forth.

Vinícius decided to number the layers inwards, so the longer layer (which is blue) is layer 1, the yellow layer is layer 2, etc. Here are the layers, numbered:

In Vinícius's code, the layer number is represented by k, and I will also use k to refer to the layer number throughout.

Layer size

The next thing to understand is how the size of each layer relates to the layer number. The layer sizes are odd numbers that go down from 2n - 1 to 1. In the grid above, n = 5, so the layer lengths are 9, 7, 5, 3, and 1. Given k, how can we know the layer length? Give it some thought...

The formula is k → 2(n - k) + 1. For example, if k = 1, then 2(n - k) + 1 = 2(5 - 1) + 1 = 9.

The last number of each layer

Looking at the figure above, what are the last numbers of each layer?

  1. 9
  2. 16
  3. 21
  4. 24
  5. 25

Can we write a formula for this? Depending on your maths knowledge, this might be easier or harder for you. You can even ask WolframAlpha, who is going to say that the formula is k → 10k - k²...

But the formula k → 10k - k² only works because the grid size is n = 5. What if it were n = 4, n = 6, or any other value of n?

The general formula is k → k(2×n - k), and you can get there by realising that you are summing a series of consecutive odd numbers, and these odd numbers are the sizes of the layers, which we saw earlier. Either way, here is how you can compute the final number of each layer k:

  1. 9 = 9
  2. 9 + 7 = 16
  3. 9 + 7 + 5 = 21
  4. 9 + 7 + 5 +3 = 24
  5. 9 + 7 + 5 + 3 + 1 = 25

Finding odd layers

Given an index (i, j) for the row and column, how can we know in which layer the index is? In a grid that is 5 × 5, these are all the positions and their layer number:

1 1 1 1 1
2 3 3 3 1
2 4 5 3 1
2 4 4 3 1
2 2 2 2 1

But how can we know that the index (3, 1) belongs to the layer k = 4, or that the index (3, 3) belongs to the layer k = 3?

To determine this, Vinícius came up with a really interesting solution.

Let us focus on the odd layers k = 1, 3, 5, and on the lower left corner of the grid:

1 1 1 1 1
. 3 3 3 1
. . 5 3 1
. . . 3 1
X . . . 1

You may have heard of the Manhattan distance (also called taxicab distance), where the distance between two points is the sum of the horizontal and vertical distances. Here, we want to use something similar, called the Chebyshev distance, where the distance between two points in a grid is the largest of the horizontal and vertical distances.

So, let us go back to the previous grid, and let me write down the Chebyshev distance of every point in the grid to the lower left corner:

4 4 4 4 4
3 3 3 3 4
2 2 2 3 4
1 1 2 3 4
X 1 2 3 4

How can you compute the Chebyshev distance of a grid point to the lower left corner? It is the maximum between the distance to the left and the distance to the bottom. The distance to the left is already the column index, which is just j. The distance to the bottom is the largest row index (n - 1) minus the current row we are at (i), so it is n - 1 - i.

Thus, the Chebyshev distance from a point (i, j) to the lower left corner is (i, j) → max(j, n - 1 - i).

So, all of layer 1 has a Chebyshev distance of 4 to the lower left corner. All of layer 3 has a Chebyshev distance of 3 to the lower left corner. All of layer 5 has a Chebyshev distance of 2 to the lower left corner. So, how does that Chebyshev distance relate to the layer number? It is distance → 2×(n - distance) - 1.

Finding even layers

The prose above was relative to odd layers, but what about even layers? For even layers, we look at the Chebyshev distance between the layer and the top right corner. All the reasonings are similar, but the formulas are obviously different. My suggestion is that you try to repeat the train of thought from above for the even layers, to see if you can come up with these formulas:

  • The Chebyshev distance from a point (i, j) to the upper right corner is (i, j) → max(i, n - 1 - j); and
  • The distance can be transformed into the even layer number by distance → 2 × distance.

Picking the correct layer number

So, for each index (i, j), we can compute the odd and even layer numbers with

def odd_k(i, j):
    return 2 * max(j, n - 1 - i) - 1
    
def even_k(i, j):
    return 2 * max(i, n - 1 - j)

But if you get a grid index (i, j), how can you tell which value of k to pick?

The odd layers are on the top right part of the grid, so they are further away from the lower left corner than from the top right corner, which means their odd value of k will be smaller than their even value of k.

The even layers are on the lower left part of the grid, so they are further away from the top right corner than from the lower left corner, which means their even value of k will be smaller than their odd value of k.

Thus, given an index (i, j), its layer number k is the smallest between the even and the odd values, which explains the first line of the function f in the code Vinícius shared.


def odd_k(i, j):
    return 2 * max(j, n - 1 - i) - 1
    
def even_k(i, j):
    return 2 * max(i, n - 1 - j)
    
def f(n, i, j):
    k = min(odd_k(i, j), even_k(i, j))
    ...

The numerical value inside the layer

The only thing that is left to do is to use the grid index (i, j) and the layer number k to determine what is the integer in that position. Once more, let us focus on the odd layers, and let me display the odd layers of a grid with the sum i + j in each position:

0 1 2 3 4
. 2 3 4 5
. . 4 5 6
. . . 6 7
. . . . 8

As you can see, inside each layer, that sum grows sequentially. In layer 1, numbers go from 0 to 8. In layer 3, numbers go from 2 to 6. In layer 5, numbers go from 4 to, well, 4. The values I showed above were the values i + j. Now, let me subtract (k - 1) from each layer, so that those values start at 0:

0 1 2 3 4
. 0 1 2 5
. . 0 3 6
. . . 4 7
. . . . 8

Now,

  • layer 1 goes from 0 to 8;
  • layer 3 goes from 0 to 4; and
  • layer 5 goes from 0 to 0.

Again, the grid above shows, for odd layers, the values i + j - (k - 1). However, we also know the actual first number of each layer! Because we know the last value of each layer, the first number of the layer k is going to be 1 plus the last number of the layer k - 1. The last number of the layer k - 1 is (k - 1)×(2×n - (k - 1)) so the first number of the layer k is (k - 1)×(2×n - (k-1)) + 1.

With this information, I can recreate the grid above for the odd layers, but instead of showing just i + j - (k - 1), I can show i + j - (k - 1) plus the first number of that layer, which is (k - 1)×(2×n - (k-1)) + 1:

 1  2  3  4 5
.  17 18 19 6
.  .  25 20 7
.  .  .  21 8
.  .  .  .  9

So, the grid above shows the values i + j - (k - 1) + (k - 1)×(2×n - (k-1)) + 1 for the odd layers. Thankfully, that train can be simplified to 1 + i + j + (k - 1)×(2×n - k), which is the right part of the return statement in the code we are analysing:

def f(n, i, j):
    k = min(odd_k(i, j), even_k(i, j))
    return ... if k % 2 == 0 else (k - 1) * (2 * n - k) + i + j + 1

Notice that this is exactly the expression that runs when k is odd! But what about even values of k? You can repeat this whole train of thought, and conclude that the expression k × (2 × n - k + 1) - (i + j + 1) produces these values for the even layers:

.  .  .  .  .
16 .  .  .  .
15 24 .  .  .  
14 23 22 .  . 
13 12 11 10 .

This is what we need and is exactly the first half of the return statement:

def f(n, i, j):
    k = min(odd_k(i, j), even_k(i, j))
    return k * (2 * n - k + 1) - (i + j + 1) if k % 2 == 0 else ...

Building the grid with a nested list comprehension

Finally, Vinícius put everything together with a nested list comprehension and that was their solution!

def involute5(n):
    return [[f(n, i, j) for j in range(n)] for i in range(n)]

Why do I like this solution?

I like this solution because I am a mathematician by trade, so it really makes me happy to see a closed formula to compute the value of each number. However, there is an advantage to this solution over the other loopy solutions, and that is that this allows us to compute any value within the grid without having to know a bunch of other values.

There are situations in real life where we just need a section of a pattern and not the whole pattern. In those cases, a maths-based solution can be quite helpful.

If you have any questions regarding this solution, feel free to reply to this email! I'll do my best to help you out.

Congratulations on making it this far! As a reward, I have a little quiz for you: in how many different ways can you create a dictionary in Python? You can also email me your answer to this, if you want!


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!