One Bit a Letter
Guess the next letter of a sentence until you get it. How far down your guesses the answer sits measures how much English you already know, in bits, and you will beat the machine.
algorithms
17 projects
- 64
deep - 50
The Collision You Did Not Expect
Fifty days in, the last one is about how soon two things land in the same place. It is much sooner than it feels.
- 45
The Best of All Triangles
Delaunay maximises the smallest angle in a mesh. I checked it exhaustively, and then noticed the maximum is dreadful.
- 44
Fair to Things You Have Forgotten
Pick six items uniformly from a stream of unknown length while holding only six. The items you threw away had exactly the same chance as the one in your hand.
- 42
One Bit Too Many
Huffman coding is provably optimal and famously within one bit of entropy. On the right source that one bit is a twelve-fold overhead.
- 40
The Shape Decides
The convex hull of n random points has far fewer than n vertices. How many fewer depends on the shape they came from, not on n.
- 36
A Filter That Lies
A Bloom filter's false-positive rate has a famous closed-form formula. The formula is right about filters in general and wrong about yours.
- 35
Which Half Matters
A Fourier transform splits an image into sizes and offsets. Throw away the sizes and you can still read it. Throw away the offsets and you cannot.
- 33
The Best Fraction
22/7 is not just close to π. Nothing with a smaller denominator is closer, and there is a machine that finds such fractions.
- 30
A Good Guess
Three searches for the same route. One is careful, one is clever, and one is fast and wrong.
- 26
The Sound Of Sorting
Four algorithms doing the same job, with their comparison counts checked against the theory that predicts them.
sound - 25
Eight Bits Of Weather
A row of cells, eight bits of rule. One draws Pascal's triangle, one makes usable random numbers, and one is powerful enough to compute anything at all.
- 23
One More Digit
Throwing darts at a circle finds π in seconds, then spends the rest of eternity finding the next decimal place.
- 17
Polite Randomness
The same number of random points twice, one following a single extra rule. Only one of them looks random.
- 10
Carve And Escape
A maze digs itself out of solid rock, then the same algorithm turns round and walks back out.
- 9
Soft Edges
Six blobs merging and splitting, their outline pulled out of a grid of numbers by a sixteen-case lookup table.
- 8
Settling Cells
Ninety scattered points, each repeatedly stepping to the middle of its own territory, discovering honeycomb.