← All demo levels

Level 5 · Software that understands software

Ten things that read, think and translate

Level 4 reached outward to the hardware. This one goes inward — programs that read other programs, work out what they mean, and run them. This is where you stop using tools and start building them.

What changed this time Everything so far did something. These understand something first, then act on it.

A calculator that reads 2 + 3 * 4 and knows it means 14, not 20. A language you can write programs in. A spreadsheet that works out what to recalculate. A machine that runs instructions one at a time.

These are the ideas underneath every tool you use — including the editor you'll write this in.
A note on how this one was built Three demos on Level 4 shipped with real bugs in them. So the ten algorithms here live in a separate file, core.js, with 86 tests in core.test.js that run before anything is published. Every claim on this page was checked by a test first.

That's not me being careful for show — it's the actual difference between code you can change confidently and code you're afraid of.
1

A calculator that understands

What it takes to build

Medium2 daysThe foundation of everything else here~70 lines

Type into the box and watch the tree. That tree is the whole idea.

How it works — three stages:

1. Tokenise. Turn the characters 2, +, 3 into a list of meaningful pieces. Easy.

2. Parse. Turn that flat list into a tree, where the structure is the meaning. This is the clever part. 2 + 3 * 4 becomes a plus with 2 on one side and a times on the other — so the times happens first, because it's deeper in the tree.

3. Evaluate. Walk the tree from the bottom up. Three lines.

The bit that seems impossible until you see it: how does it know times binds tighter than plus? There's no rule for it anywhere. Instead you write one function per level of precedence, and each one calls the level below it. Precedence falls out of the shape of the code. Try 2 ^ 3 ^ 2 — you get 512, not 64, because powers group from the right, and that's one line of difference.

Press the broken one and watch it fail politely. Good error messages are most of what makes a language usable.

What to ask for:

Recursive descent parser for arithmetic: tokenizer, then one function per precedence level (expr calls term calls power calls primary), producing a tree, then a recursive evaluator. Right-associative exponent, unary minus, parentheses, and clear error messages naming what it expected.
2

Your own programming language

What it takes to build

HarderA weekA real language~90 lines

That box contains a working programming language. Variables, arithmetic, conditions, loops, printing, and error messages. Edit the program and run it — it's yours now.

How it works: go through the lines one at a time. Each line is matched against a few shapes: is it a print? an assignment? a while? an if? The expressions on the right-hand side get handed to the parser from demo 1 — this language is built on top of that calculator.

Loops are the only fiddly bit. When you hit while, you scan forward to find the matching end, counting nested blocks so you find the right one. Then you run everything between those two points over and over while the condition holds.

Notice the safety valve. Write a loop that never finishes and it stops with a message rather than freezing the page. Real languages do the same thing. Someone had to decide that, and it's the kind of decision that separates a toy from a tool.

This is a tree-walking interpreter — the simplest honest way to run a language. Demo 10 shows the other way.

What to ask for:

Small interpreted language: line-based, with variables, arithmetic via an expression parser, print, if/end and while/end with correct nesting by counting blocks to find the matching end, comparison operators, a step limit so infinite loops fail safely, and error messages that name the line number.
3

A spreadsheet

click a green cell to see its formula · try changing a price

What it takes to build

HarderA weekExcel's core idea~60 lines

Change a price and watch the total update. Nothing told the total to update. It worked that out.

How it works: a formula like =A2*B2 mentions other cells. To find its value you must first find theirs — which might mean finding others still. So each cell asks for what it needs, and those asks cascade outward until they hit plain numbers, then unwind.

That's lazy evaluation with memoisation: work things out only when asked, and remember each answer so it's never computed twice. It's why a spreadsheet with ten thousand formulas doesn't take ten thousand times as long.

Now press the circular reference button. It makes C2 depend on C5, which already depends on C2. A naive version would follow that loop forever and crash the page. The fix is four lines: mark each cell while you're working on it, and if you ever arrive at a cell already marked, you've gone in a circle — say so and stop.

That's exactly what Excel's "circular reference" warning is. Now you know what's behind it.

What to ask for:

Spreadsheet engine: cells hold text, numbers or =formulas referencing other cells. Resolve lazily by recursion, cache each computed value, and detect circular references with a visiting set so a loop reports an error rather than hanging. Reuse an expression parser for the formula maths.
4

A search engine

    What it takes to build

    Medium2 daysHow Google started~40 lines

    How it works — and the first idea is the important one.

    The slow way to search is to read every document looking for the word. Instead, build the index backwards: go through everything once, and record for each word which documents contain it, and how often. Now searching is a lookup, not a hunt. That's an inverted index, and it's why search is instant on collections far too large to read.

    Then: ranking. Matching isn't enough — which match is best? The rule has two halves:

    A word matters more if it appears often in this document. And it matters more if it's rare across all documents. "The" appears everywhere, so it tells you almost nothing. "Tomatoes" appears rarely, so it's a strong signal.

    Multiply those together and you get TF-IDF. Search "the" and watch the scores collapse to almost nothing. That's the second half working.

    And the bit that makes it feel alive The first version of this only matched whole words. Type bicy and it found nothing — which is technically correct and feels completely broken, because you're still typing.

    The fix: each term also matches any indexed word that starts with it, scored a little lower than an exact hit so real matches still win. Type b, then bi, then bic and watch the results narrow.

    The scaling note: this checks every word in the index for each keystroke, which is fine for 57 words and hopeless for a million. Real engines store words in a trie — a tree where shared beginnings share a branch — so finding everything starting with "bic" costs three steps instead of a million.

    What to ask for:

    Search over a list of documents: build an inverted index from word to {docId: count}, then rank results by TF-IDF — term frequency divided by document length, times log of total documents over documents containing the term. Sort best first.
    5

    Squeezing text smaller

    What it takes to build

    Medium2 daysInside every zip file~50 lines

    How it works: normally every letter takes 8 bits, whether it's a common e or a rare z. That's wasteful. Give common letters short codes and rare ones long ones, and the total shrinks.

    Building the codes is beautifully simple. Count every letter. Repeatedly take the two rarest things and join them into a pair, which now counts as their combined total. Keep going until one tree remains. Then the path down to each letter — left is 0, right is 1 — is its code. The rarest letters ended up deepest, so they got the longest codes. Automatically.

    The problem this quietly solves: if a is 0 and b is 01, then reading 01 is ambiguous. Because every letter sits at the end of a branch, no code can ever be the start of another. It's impossible to misread. That property has a name — prefix-free — and the tree gives it to you for free.

    Type text with lots of repetition and watch the bar shrink. Type random letters and watch it barely move. Compression is just exploiting predictability — and something with no pattern can't be compressed at all.

    What to ask for:

    Huffman coding: count character frequencies, repeatedly combine the two lowest-count nodes into a parent until one tree remains, then walk it assigning 0 for left and 1 for right to get each character's code. Report original versus compressed bit counts.
    6

    Spotting what changed

    What it takes to build

    Harder3 daysWhat git does~35 lines

    Edit either box. It finds the smallest set of changes that turns one into the other.

    How it works: the trick is to flip the question. Instead of hunting for differences, find the longest sequence of lines the two have in common, in order. Everything in that sequence stayed. Everything else was added or removed. Differences are what's left over.

    Finding that longest common run looks like it needs checking every combination, which would take longer than the universe has existed for a real file. Instead you build a grid and fill it in from the bottom-right corner, where each square's answer depends only on squares you've already done. That's dynamic programming — turning an impossible search into a table you fill in once.

    Every time you see a green-and-red diff on GitHub, or your editor shows what changed, this is running underneath.

    What to ask for:

    Line diff using longest common subsequence: build the LCS length table with dynamic programming, then walk it from the start emitting keep, delete and insert operations. Handle one side being empty.
    7

    A game that thinks ahead

    What it takes to build

    Medium3 daysCannot be beaten~50 lines

    Try to win. You can't. The best available to you is a draw, every time.

    How it works: it plays out every possible continuation of the game. For each one it asks "who wins?" Then it reasons backwards: I will pick the move that leads to my best outcome, assuming you then pick the move that leads to yours.

    That mutual assumption is the whole algorithm, and it's called minimax — I maximise, you minimise, all the way down.

    Then the optimisation that makes it practical. Watch the position count after each move. Suppose you're checking a move and find it lets the opponent win. You can stop immediately — it doesn't matter how the rest of that branch plays out, you'd never choose it.

    That's alpha-beta pruning, and on an empty board the difference is:

    Positions examined
    Plain minimax549,945
    With pruning34,202

    Sixteen times less work, identical play. Chess engines use exactly this — it's the difference between looking four moves ahead and looking twenty.

    What to ask for:

    Tic-tac-toe with minimax and alpha-beta pruning. Score wins by depth so it prefers winning sooner and losing later. Count positions examined so I can compare with and without pruning, and verify both return the same move.
    8

    Light, properly

    What it takes to build

    HarderA weekHow CGI films are made~90 lines

    Look at the reflections. Each sphere contains the others, and those reflections contain reflections. Nobody drew any of that.

    How it works — and it's physics run backwards. In reality, light leaves a lamp, bounces around, and some tiny fraction reaches your eye. Simulating that would waste almost all the work on light that never arrives.

    So do it in reverse. For each pixel, fire a ray out of the camera and follow it until it hits something. Then ask two questions at that point: can the light see this spot? (if not, it's in shadow) and is this surface shiny? (if so, bounce and repeat).

    Shadows aren't drawn. They're what you get when the answer to the first question is no. Reflections aren't drawn either — they're the same function calling itself with a new direction.

    Press the bounces button. At 0 the spheres go flat and dull. At 1 they reflect each other. At 3 the reflections have reflections in them. Each step costs real time — which is why films render for hours per frame.

    Compare this with Level 4's 3D demo. That one ran on the graphics card and was instant. This runs on the processor, one pixel at a time, and you can watch it draw. Same idea, one uses the right hardware.

    What to ask for:

    CPU ray tracer on canvas: ray-sphere intersection, a directional light with shadow rays, recursive reflection up to a bounce limit, and gamma correction. Render progressively a few rows per frame so the page stays responsive.
    9

    Your own pattern matcher

    What it takes to build

    Harder4 daysA famously scary topic~80 lines

    Regular expressions have a reputation for being impenetrable. Writing one is genuinely harder than understanding how they work.

    How it works: first turn the pattern into a list of items — a letter, "any character", "a character from this set" — each optionally marked "repeat this". Then match the list against the text, one item at a time.

    The interesting part is *. When a pattern says "any number of b's", how many should it take? The answer is: as many as possible, then fewer if that fails. Grab everything, try the rest of the pattern, and if it doesn't work, give one back and try again. That's backtracking.

    Try ab*c against abbbc. The b* greedily swallows bbbc, then finds no c left, gives one back, and succeeds. That retry-with-less is the entire mechanism.

    And it's why regexes can be dangerously slow. Certain patterns make backtracking explode into millions of retries — it has taken down major websites. Now you know exactly why, because you've seen the retry loop.

    A test that passed for the wrong reason This demo shipped with ranges like [a-z] broken — the code treated it as the three characters a, - and z, so [0-9] didn't match 5, and [a-z] happily matched a dash.

    The uncomfortable part: I had a test for it, and the test passed. It checked that [0-9] doesn't match abc — which was true, but only because the pattern matched nothing at all. The test confirmed the right answer for entirely the wrong reason.

    The lesson: a test that only checks something fails isn't much of a test. You need one that checks it succeeds when it should. There are now five range tests, including one that must match sam@example.

    What to ask for:

    Small regex engine supporting literals, dot, character classes with negation, star, plus, question mark, and start and end anchors. Use recursive backtracking: for greedy repeats, take the maximum then give characters back one at a time until the rest of the pattern matches.
    10

    A computer inside the computer

    Stack
    Variables

    What it takes to build

    Medium3 daysWhat Java and Python do~50 lines

    Press Step and watch. That listing is the program from demo 2 — factorial of 5 — but with all the structure removed. No loops, no variables in the ordinary sense. Just twenty instructions and a stack.

    How it works: there's a pile of numbers called the stack. PUSH puts one on. ADD takes two off and puts the answer back. JMP moves to a different instruction. That's genuinely the whole machine.

    Look at how the loop is built. There's no while anywhere — there's a comparison, a conditional jump forward to escape, and at the bottom a jump backwards to the top. Every loop you have ever written compiles down to that.

    Why go to the trouble? Demo 2 ran a program by walking its tree, which is simple but slow. Compiling to flat instructions first is faster, and the instructions are portable — anything that can run these twenty opcodes can run your program. That's exactly how Java and Python work: your code becomes bytecode, and a virtual machine runs the bytecode.

    Demos 1, 2 and 10 are a set. Read text into a tree. Walk the tree to run it. Or flatten the tree into instructions and run those instead. That's every language implementation, in three demos.

    What to ask for:

    Stack virtual machine with PUSH, LOAD, STORE, ADD, SUB, MUL, LT, GT, JMP, JZ, PRINT and HALT. Keep a program counter, a stack and a variable map, and expose a single step function so the state can be shown after each instruction. Write a factorial program in it by hand.

    What Level 5 was really about

    Every demo here takes something written for humans and turns it into something a machine can act on.

    DemoReadsTurns it into
    CalculatorAn expressionA tree
    LanguageA programActions
    SpreadsheetFormulasA dependency order
    SearchDocumentsAn index
    CompressionTextShorter codes
    DiffTwo filesA list of changes
    Virtual machineInstructionsA running program
    The thing to take from this level You have now built, in miniature, the machinery underneath the tools you use every day. Your editor's search is demo 4. Its "what changed" panel is demo 6. Its find-and-replace is demo 9. The language you write in is demos 1, 2 and 10.

    None of it is magic, and none of it took more than a week. Tools are just programs, and you can write programs.

    Things to try

    1. Add a feature to your language. Open core.js and give it a repeat N loop, or an else. You'll need to touch the parser and the runner — which is exactly what adding a feature to a real language feels like.
    2. Break precedence on purpose. In the parser, make term() handle + and expr() handle *. Now 2 + 3 * 4 returns 20. One swap, and maths is wrong everywhere.
    3. Feed the compressor random letters. Type qwertyuiop — barely any saving. Then aaaaaaaaab — huge saving. You've just discovered why you can't zip a zip file twice.
    4. Race the pruning. Play a few moves of tic-tac-toe and watch both position counts. The gap widens as the board fills, then collapses at the end.
    5. Run the tests. In the level-5 folder: node core.test.js. Then break something in core.js on purpose and run them again. Watching a test catch your mistake is the moment testing stops feeling like homework.