Project-Euler

For fun I picked one of the Euler algorithms I had played with before and rewrote it in Go. Instead of carrying over the nested-loop search, this version first eliminates c using the fixed sum and solves the Pythagorean equation for b. Only a remains to search.

package main

import (
	"fmt"
	"os"
)

func main() {
	const sum = 1000

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

		if numerator%denominator != 0 {
			continue
		}

		b := numerator / denominator
		c := sum - a - b
		if a < b && b < c {
			fmt.Println(a * b * c)
			return
		}
	}

	fmt.Fprintln(os.Stderr, "no solution")
	os.Exit(1)
}

The divisibility check rejects values of a that would produce a fractional b. The program uses constant space, examines fewer than sum / 3 candidates, and prints 31875000.

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