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
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.
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.
-
Keep private solutions private, in a public repository
Encrypted strings in the codeneeded its own loaderEncrypted .enc fileschecked out, checked back in A git filterplain text at work, ciphertext in git -
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.
-
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} -
A new machine: GitHub holds the code, not the setup
One command builds the rest:
make install-all, from system packages to git hooks. -
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.
-
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
- 1Fetch
summary - 2Set up
new 7 - 3Write
solve() - 4Check
eval 7 - 5Measure
benchmark 7 - 6Keep
git-commit 7
Crossing out: the sieve
Counting without walking
| Grid | Routes |
|---|---|
| 2 × 2 | 6 |
| 3 × 3 | 20 |
| 4 × 4 | 70 |
| 10 × 10 | 184,756 |
| 20 × 20 | over 100 billion |
Working from the bottom up
A simple rule, a wild ride
Too big for a calculator
Too many to try
Deduce first, guess last
| Approach | Grid 01 | All fifty |
|---|---|---|
| Try every board | 5.7 × 10⁴⁶ | 2.3 × 10⁵⁶ |
| Backtrack, cell by cell | 1,605 tries | 11,011,447 tries |
| Deduce, then guess | no guesses | 28 guesses |
| Solver | C | Python |
|---|---|---|
| Backtracking, fewest candidates first | 6.4 ms | 46 ms |
| Exact cover: Dancing LinksDonald Knuth, 2000 | 1.6 ms | 54 ms |
| Constraint propagationafter Peter Norvig, 2006 | 1.0 ms | 51 ms |
An honour code, backed by a vault
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
- Call out a number from 1 to 100, or press Space to draw one.
- I open it on the website and run it.
- 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=Nrepeatssolve()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_commitbecomesgit-commit;requiressets the lowest profile allowed.problem: Problemtakes 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 onlywhenit applies (an amend keeps its message).- A
boolbecomes 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-docsbuilds 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
solver-host- Dependencies point one way.
layers.pyfails 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
solutions/private/** filter=solver-crypt -text -diff
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.user --regen (the account page's Regen): the master key moves to the new key, or a maintainer re-authorizes it.key-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
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
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.