Programming

I was certain my parser spent its time converting decimal numbers. Certainty is a useful indication that I should profile before touching anything.

The tools include a real-time sampling profiler named 6prof. Despite the name, it also understands the other supported architectures. The interface is still moving, so this is a note about the weekly release on my desk rather than scripture.

I let the profiler start the real program:

$ 6prof ./logsum
  46.8%  bytes.(*Buffer).Write
  21.1%  runtime.memmove
   8.7%  parseNumber

On Linux/amd64 I can ask it to write pprof data, provided the program was linked with 6l -e:

$ 6prof -P cpu.prof ./logsum

The exact output format varies, but the result was unambiguous. My “efficient” reporting path repeatedly grew a byte buffer. Number parsing was visible and not remotely the first problem.

Preallocating a reasonable output buffer removed most growth and copies. Runtime dropped by roughly a third on the same input. Replacing the decimal parser with a clever version afterward produced noise-sized improvement, so I reverted it. Clever code that cannot beat measurement is just decorative risk.

Sampling has limits. A short run may not gather enough samples, and compiler optimization can make line attribution odd. This profiler samples threads while they are running, asleep, or waiting for I/O, so a hot entry may be telling me about waiting rather than arithmetic. I feed several seconds of representative data and repeat runs. I also keep wall-clock timing around the complete operation because users do not experience percentages.

Input matters just as much. A profile from the tiny sample used by unit tests mostly measures startup and can confidently direct optimization toward irrelevant code. I use a captured workload large enough to reach steady behavior.

The young runtime itself appears in profiles. Garbage collection, allocation, copying, and scheduler work are part of the program’s cost, even if I did not type those function names. They should not automatically be dismissed as profiler clutter. Often they point back to an allocation pattern I control.

Now I reproduce, time, profile, change one thing, and time again. This lacks the emotional satisfaction of immediately rewriting the function I dislike. Annoyingly, it makes the program faster.

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