Working models · Play the games!
The Children’s Playground
Everywhere else in this museum you look at code and read about it. In here the code is running, and you are allowed to push it around and see what it does.
Every machine in here is a real work from the collection, shown a second way. Underneath each one is the file it was built from, hanging on a wall in the Gallery of Methods — the same thing, written down.
I can find your number
Think of any number between 1 and 100. I will find it, and it will take me fewer guesses than you expect.
Think of a number between 1 and 100. Keep it secret — you never have to type it in.
Is it 50?
100 numbers still possible.
This is how you find a word in a dictionary without starting at A. Open it in the middle, decide which half the word is in, and throw the other half away — then do it again. A dictionary of a hundred thousand words takes seventeen goes.
The tortoise and the hare
Two runners on the same track. One is twice as fast. Watching who catches whom tells you something the runners cannot see.
Both runners start at the far left. The tortoise takes one step at a time. The hare takes two.
Nobody has moved yet.
A computer following a list of instructions can get stuck going round and round for ever. It cannot see the track from above the way you can, and remembering every step it has taken would cost too much. So it sends a second runner at twice the speed: if they ever meet, the track loops. Robert Floyd worked this out in the 1960s.
Cutting up the paper
Cut the biggest square you can off a sheet of paper. Then do it again to what is left, until there is nothing left over.
A piece of paper 24 across and 18 down. Cut the biggest square you can off the end, then do it again to whatever is left.
Nothing cut yet.
The last square you cut is the biggest one that would tile the whole sheet without a gap — which is the same as the biggest number that divides both sides exactly. Euclid wrote this down about three hundred years before the common era, and nobody has found a better way since.
Who won the vote?
Thirteen votes and one walk along the row. Find the colour that more than half of them chose, without counting anybody twice.
Thirteen votes. One token is the champion, and it has lives. Agree with it and it gains one; disagree and it loses one. On no lives, the next token takes over.
A computer counting votes could keep a tally for every colour, but that needs somewhere to put all the tallies. This needs room for one colour and one number, however many votes there are — a million, or a billion. The catch is that something always survives, so you still have to count the winner at the end to be sure it really won.
Sorting by throwing things left and right
Twelve bars in a muddle. Watch them sort themselves, one comparison at a time, and count how few it takes.
Pick a bar. Everything shorter goes to its left, everything taller to its right — then it can be dropped in the middle, and it is home for good. Do the same to each side.
Nothing looked at yet.
Try Worst case. The bars start in exactly the wrong order, so picking the last one every time peels off a single bar instead of halving the row. It still sorts — but it takes 66 looks, which is precisely what comparing every bar with every other would have cost. A muddled row takes about thirty. Quicksort is only quick when the bar it picks lands near the middle.
Tony Hoare invented this in 1959, aged twenty-five, while trying to translate Russian. It is still the sort most computers reach for first, and the reason is on the screen: the row halves, and halves again, instead of being walked end to end for every bar.
Is this shuffle fair?
One shuffle always looks random. Do it thousands of times and a badly written one gives itself away.
Six cards, shuffled 400 times. Each square shows how often a card landed in a place. If the shuffle is fair, every square is the same.
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| card 1 | ||||||
| card 2 | ||||||
| card 3 | ||||||
| card 4 | ||||||
| card 5 | ||||||
| card 6 |
This is the honest shuffle. Every square is about the same shade, because every card is equally likely to land anywhere.
This is the only machine here you cannot understand by watching it once, because nothing is wrong with any single shuffle. The fault only appears in the pattern of thousands — which is how a great many real bugs behave, and why anybody writing a shuffle should use the one that was already worked out rather than the one that seems obvious.
That is every algorithm in the Gallery of Methods, now standing in two rooms at once: here as a machine you can push around, and along the corridor as the file it was built from.