Blog

This one isn’t even funny…

Starting in the top left corner of a $2 \times 2$ grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a $20 \times 20$ grid?

Your first thought would be to generate the routes, but for a $20 \times 20$ grid, those amount to BILLIONS and you’d try to do it recursively too! Forget it.

But if you have some CompSci-level math background, though, you’ll remember this one—reading The Art of Computer Programming, Vol. 4 also helps. It’s a matter of combinatorics and if we take $w$ for the width and $h$ for the height, all we need to calculate is:

Every path consists of exactly 20 moves right and 20 moves down. Choosing which 20 of the 40 positions are right moves uniquely determines a path, so the answer is the binomial coefficient $\binom{40}{20}$.

from math import comb

width = height = 20
print(comb(width + height, width))

math.comb computes the integer result directly, without constructing three factorials. The answer is 137846528820.

Project Euler’s problem #11 statement goes:

In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in bold.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is $26 \times 63 \times 78 \times 14 = 1\,788\,696$.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the $20 \times 20$ grid?

This one is remarkably easy but also was quite fun. I think it’s because it reminds me of the kind of work we’d do during our Algorithms classes during my first year in college. And so this one goes to my Algorithms teacher, Ricardo Vargas Dornelles—best teacher I’ve ever had too.

Only four directions are necessary: reversing any group gives the same product. Describing those directions as row and column offsets keeps one loop responsible for every case and makes the boundary check explicit.

from math import prod

grid_text = """\
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
"""

grid = [
    [int(number) for number in line.split()]
    for line in grid_text.splitlines()
]
directions = ((0, 1), (1, 0), (1, 1), (1, -1))
length = 4
rows = len(grid)
columns = len(grid[0])
largest = 0

for row in range(rows):
    for column in range(columns):
        for row_step, column_step in directions:
            end_row = row + (length - 1) * row_step
            end_column = column + (length - 1) * column_step
            if not (0 <= end_row < rows and 0 <= end_column < columns):
                continue

            product = prod(
                grid[row + offset * row_step][column + offset * column_step]
                for offset in range(length)
            )
            largest = max(largest, product)

print(largest)

Every valid group is visited exactly once. Since there are four fixed directions and four values per product, the traversal is linear in the number of grid cells. It prints 70600674.

I decided to take on Project Euler’s problem #10. Its statement goes like this:

The sum of the primes below 10 is $2 + 3 + 5 + 7 = 17$.

Find the sum of all the primes below two million.

A Sieve of Eratosthenes finds every prime below the limit together instead of running a separate divisibility test for every number. A bytearray stores one byte per candidate and supports crossing out a whole arithmetic progression at once.

from math import isqrt

limit = 2_000_000
sieve = bytearray(b"\x01") * limit
sieve[:2] = b"\x00\x00"

for prime in range(2, isqrt(limit - 1) + 1):
    if not sieve[prime]:
        continue

    start = prime * prime
    count = (limit - 1 - start) // prime + 1
    sieve[start:limit:prime] = b"\x00" * count

print(sum(number for number, is_prime in enumerate(sieve) if is_prime))

Starting at prime * prime is sufficient because smaller multiples already have a smaller prime factor. The sieve runs in $O(n\log\log n)$ time, uses $O(n)$ space, and prints 142913828922.

The language can make a brute-force search faster, but eliminating unnecessary work is better. Substituting $c = 1000 - a - b$ into the Pythagorean equation and solving for $b$ leaves only one variable to search:

#include <stdio.h>

int main(void)
{
    const int sum = 1000;

    for (int a = 1; a < sum / 3; ++a) {
        const int numerator = sum * (sum - 2 * a);
        const int denominator = 2 * (sum - a);

        if (numerator % denominator != 0)
            continue;

        const int b = numerator / denominator;
        const int c = sum - a - b;

        if (a < b && b < c) {
            printf("%d %d %d = %d\n", a, b, c, a * b * c);
            return 0;
        }
    }

    fputs("no solution\n", stderr);
    return 1;
}

The divisibility check ensures that b is an integer. This searches fewer than sum / 3 candidates in constant space and prints $200 \times 375 \times 425 = 31\,875\,000$.

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is —

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which:

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

There exists exactly one Pythagorean triplet for which $a + b + c = 1000$.

Find the product $abc$.

Using $c = 1000 - a - b$ removes one variable immediately. Substituting that into $a^2 + b^2 = c^2$ and solving for $b$ gives

That leaves only the possible values of a to search:

total = 1000

for a in range(1, total // 3):
    numerator = total * (total - 2 * a)
    denominator = 2 * (total - a)

    if numerator % denominator:
        continue

    b = numerator // denominator
    c = total - a - b
    if a < b < c:
        print(a * b * c)
        break

The divisibility check ensures that b is a natural number. The triplet is $(200, 375, 425)$, so the program prints 31875000 in linear time and constant space.