Eleven years
of puzzles

Project Euler, one problem at a time.

Vikas Munshi

Add up every number below 1,000 that is a multiple of 3 or 5.

Problem 1. Take thirty seconds.

The obvious way stops working

Counting one by oneThe clever way

Project Euler: 1,013 puzzles and one rule

Problem 1: Multiples of 3 or 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1,000.

Answer:

  • Maths puzzles that need a computer to finish, a new one most weeks.
  • Every answer is a single number, and the site checks it.
  • The rule: solve it yourself, and share answers only for the first 100.
  • Problem 1 has been solved by 853,325 people. Problem 0, by 0.

On 2 July 2015, I solved my first one.

It took ten years to reach 100, and twelve months to go from 100 to 300.

2015 0 solved
EasierHarder

Harder problems, fewer people

The higher the level, the fewer I've solved

How many people have solved it?

Every problem with a difficulty rating, one dot each; mine in colour. The newest have no rating yet.

Two long pauses, then a surge

What changed:
I built a framework

The story behind the solver

Every feature began as a problem I ran into.

  1. Keep private solutions private, in a public repository

    Encrypted strings in the codeneeded its own loader Encrypted .enc fileschecked out, checked back in A git filterplain text at work, ciphertext in git
  2. Keep the key safe, and don't lose it (I did, more than once)

    Every machine holds its own sealed copy, and any holder can pass it on, whole or in two halves.

  3. Do the old solutions still work after an update?

    Each keeps its test cases and answer; one line re-checks them all: loop {solved}: eval {loop.number}

  4. A new machine: GitHub holds the code, not the setup

    One command builds the rest: make install-all, from system packages to git hooks.

  5. Code that stays right, and can be rewritten

    mypy and flake8 on every commit, docs generated from the code; each time the framework changed shape, code transformers rewrote every solution.

  6. Turn solutions into knowledge

    An explanation beside every solution, tags by technique, articles linking problems, and a website to read them.

From problem to solution

  1. 1Fetchsummary
  2. 2Set upnew 7
  3. 3Writesolve()
  4. 4Checkeval 7
  5. 5Measurebenchmark 7
  6. 6Keepgit-commit 7

Crossing out: the sieve

Counting without walking

Working from the bottom up

A simple rule, a wild ride

Too big for a calculator

Too many to try

Deduce first, guess last

An honour code, backed by a vault


      
One master key
Sealed copyMy laptop
Sealed copyMy web shell
Sealed copyA collaborator

Each copy opens only with its holder's own key.

Working with AI

What it helps with

  • Writing the explanation beside each solution
  • Translating a Python solution into C
  • Reviewing my work for mistakes
  • Drafting the blog articles

What it doesn't do

  • Publish anything I haven't read
  • Decide when an answer is right: the tests and the site do
  • Push its own work: it stops at a local commit, and I take it from there

Problem 15, solved by hand in 2019, before any AI

Its explanation, written later together with AI

@runner.main
def solve(*args: str) -> str:
    lattice_size = runner.parse_int(args[0])
    return str(math.factorial(2 * lattice_size)
               // math.factorial(lattice_size) ** 2)

“The crucial observation is that the geometry of the grid is irrelevant to the count: any valid path consists of exactly 2n unit steps, of which n must go right and n must go down. A path is fully determined by the order in which we interleave these two kinds of moves.”

Live: pick a problem

?

  1. Call out a number from 1 to 100, or press Space to draw one.
  2. I open it on the website and run it.
  3. The answer and its timing appear there, not on this slide.

Small puzzles add up.

Start with Problem 1 at projecteuler.net.

Under the hood

For the developers in the room: how the framework is built.

~/euler ❯ solver

A solution is one function

p0007_s0.py

@runner.main
def solve(*args: str) -> str:
    """Sieve of Sundaram over [1, n·ln n] …"""
    n = runner.parse_int(args[0])
    if n == 1:
        return str(2)
    max_expected_value = int(n * math.log(n))
    numbers = list(range(0, max_expected_value + 1))
    for i in numbers[1:]:
        for j in range(i, max_expected_value + 1):
            try:
                numbers[i + j + 2 * i * j] = 0
            except IndexError:
                break
    return str(2 * [i for i in numbers if i != 0][n - 2] + 1)

p0007_s0.c

#include "runner.h"

const char *solve(int argc, char *argv[]) {
    static char _answer[32];
    int n = parse_int(argv[1]);
    …
    for (int i = 1; i <= max_expected_value; i++) {
        if (numbers[i] == 0) continue;
        for (int j = i; ; j++) {
            long long idx = (long long)i + j + 2LL * i * j;
            if (idx > max_expected_value) break;
            numbers[idx] = 0;
        }
    }
    …
    snprintf(_answer, sizeof _answer, "%lld", result);
    return _answer;
}

The runner owns everything else: the arguments, --runs=N timing, a consistency check, and one output line, <runs> <seconds> <answer>. Python and C share the contract, so either runs under the same eval and benchmark.

Benchmarks that don't lie

packages/solver/solver/runners/runner.py, the timed loop

for _ in range(runs):
    _start, _result, _stop = perf_counter(), solve(*args), perf_counter()
    elapsed.append(_stop - _start)
    if result is not None and _result != result:
        errors.append(f"Expected consistent result, got {_result} …")
    result = _result
…
print(f'{runs} {average} {result}')
  • --runs=N repeats solve() and reports the average.
  • Every run must return the same answer, or the exit code says so.

The warm-cache trap

# Built once, at import: free on every timed run after the first
PRIMES = primes_below(10**7)

@runner.main
def solve(*args: str) -> str:
    n = runner.parse_int(args[0])
    …
@runner.main
def solve(*args: str) -> str:
    n = runner.parse_int(args[0])
    # Built inside solve(), sized to the input: timed on every run
    primes = primes_below(bound_for(n))
    …

A small command language

What you type

What the lexer normalises it to

One decorator per command

packages/solver/solver/core/git.py

@register(requires='contributor', aliases=('commit',),
          quietable=True)
def git_commit(
    problem: Problem,
    *targets: Literal['solution', 'solutions', 'docs',
                      'blogs', 'update'],
    message: Annotated[str, Ask('Message', when=_is_not_amend,
                                multiline=True)] = '',
    amend: bool = False,
    reset: bool = False,
) -> int:
    """Stage and commit the named targets — the one commit verb."""
  • git_commit becomes git-commit; requires sets the lowest profile allowed.
  • problem: Problem takes a bare number or {next}, remembers it as the current problem, and fills it in when left out.
  • *targets: Literal[…]: any number of choices, checked and tab-completed.
  • Annotated[str, Ask(…)]: left out, the shell asks for it, but only when it applies (an amend keeps its message).
  • A bool becomes a flag; the return value is the exit code.

docs/commands-index.md, generated by update-docs

#### Command: `git-commit` (`commit`)

Stage and commit the named targets — the one commit verb.

* ⚑ needs contributor or above.
* ❏ uses/sets current problem.
* ✎ asks for anything you leave out.
* » supports --silent to suppress output.

**usage**
git-commit
[problem=<n>] (default current)
[solution|solutions|docs|blogs|update ...]
[message=<str>] (asked)
[amend=true|--amend]
[reset=true|--reset]
[silent=true|--silent]
  • Generated, never written: update-docs builds this index, the command catalogue, the package layout and the tooling reference from the live code.
  • Every full release reruns it, so the reference says what the code does now.

One shell, three packages

euler_webshellthe web shell, the per-user service, the PTY, the message spool, solver-host
↓ imports
euler_sitethe content site and the auth service
↓ imports
solverthe solver shell: standalone, no web code at all
  • Dependencies point one way. layers.py fails any import that points up, on every commit.
  • A fourth package, euler_content, is data: the public tree the signed-out site serves.

packages/webshell/euler_webshell/shell/overlays.toml

[git-sync]          # after it returns, nudge the page:
emit = ["git"]      # OSC 5379 → the header's git chip

[summary]           # problems.json changed
emit = ["progress", "git"]

[show]              # swap the left pane, not a browser tab
replace = "euler_webshell.shell.viewer:show"
  • The web shell is the solver shell plus an Extension: more commands, a ticket for identity, and these overlays.
  • The solver shell never imports it, and never knows it is in a browser.

Encrypted at rest, plaintext at work

Working treeplaintext, as you edit it
clean: encrypt →← smudge: decrypt
Git objectsciphertext, as pushed
solutions/private/** filter=solver-crypt -text -diff
your passwordproven by SRP at sign-in, never sent derives PKArgon2id with the SRP salt, in the browser; it opens the vault unlocks ~/.euler/idthis machine's X25519 key, encrypted at rest unwraps enc-key.jsonthe master key, sealed to this machine gives AES-256 master keywhich decrypts every file
PasswordyouAccount page or vault change-password: a new SRP verifier and a new vault key, then every session signs out. A forgotten one is reset by mail, and the vault goes with it.
Private keyyouuser --regen (the account page's Regen): the master key moves to the new key, or a maintainer re-authorizes it.
Vault keyyour password changeReplaced on every password change, with the secrets re-encrypted under it; a reset destroys it.
Master keyan adminkey-rekey, the only revocation: every private file re-encrypted, the new key re-issued to each registered public key.

Deterministic: each file's nonce is an HMAC of its plaintext, so an unchanged file encrypts to the same bytes and git sees no change, while different text never reuses a nonce.

One service per collaborator

BrowserSRP-6a login: the password never leaves it
↓ TLS: a Let's Encrypt certificate over DNS-01, checked for renewal daily · dynamic DNS every 5 minutes
Caddystrips identity headers; signed-out reads go to the public site, everything else asks the auth service, then routes by X-User-Slug
↓ unix sockets under /run/euler
euler-sitethe public site: the packaged public tree, read-only, nothing private
euler-user@aliceown uid, home, clone, branch and vault; pages and the /ws terminal
euler-user@bobsame shape, fully separate
auth · messages · maileach on its own uid
↓ the only way out
Squid domain allowlist + per-uid nftableseach service reaches only what it needs

Defence in depth

Login
SRP-6a: the password never crosses the wire; the server keeps only a verifier, made slow to guess with Argon2id. Reset and invite forms cost a proof of work.
Identity
The edge strips client identity headers; only the auth service sets them, and each service checks which uid is calling. A web shell starts from a single-use ticket.
Isolation
One uid, home, clone and branch per collaborator, behind sockets no other collaborator can open; every service in a systemd sandbox.
Secrets
Each user's keys in a password-derived vault (Argon2id, AES-GCM); private solutions ciphertext in git.
The way out
A domain allowlist and per-uid firewall rules, loopback included; mail through a relay holding its own credentials.
The page
A Content-Security-Policy with a fresh nonce per response: only the site's own scripts run, nothing from a CDN. The terminal obeys only its own shell's signals.

Shipping it

Conventional Commitsfeat:, fix:, docs: …
→
make releasebumps version.py, commits, tags, pushes
→
make redeploy-webrefuses unless the tag is on origin

Every commit

  • No whitespace errors or conflict markers
  • No build artifacts, gitignored or unencrypted private files
  • shellcheck on staged scripts; flake8; mypy, tests included
  • The layering check: no import points up

Every push, and on demand

  • The encryption and binary audits, on exactly the blobs pushed
  • flake8, mypy, and shellcheck over every tracked script
  • The full unit test suite, when code, scripts or tests change
  • make audit: the whole tree, on demand

Designs I built and threw away

Brokers for secrets
Services that held the API and git keys on behalf of a shared web user. One was built and working. Dropped once giving every collaborator their own user removed the need.
A checkout lock
A second lock on top of the workspace's own. It worked as designed and confused everyone, so it was reverted.
One shared key file
Every machine's sealed key in one tracked file: a long run of merge conflicts. Now each machine keeps its own.
Versions from git tags
Build-time version detection from git. Replaced by one tracked version.py that only the release script writes.

Thank you. Questions?

Ask about the puzzles, the maths, or the machinery.

Vikas Munshi. This deck lives in the project, at docs/presentation.