wild·3The algorithms that run the internet

Type a word into a search box and a ranking of the web comes back before your finger leaves the key. Visit a page and your browser has already checked it against millions of known-bad addresses without asking anyone. Commit a file and version control names the exact two lines you touched. Click a pixel and a whole region fills. This last room of the gallery opens those four lids: the census that decides which page matters by simulating a bored surfer clicking forever, the sixteen-bit bouncer that answers definitely-not or probably-yes, the grid that finds the skeleton two files share so the leftovers are exactly your edit, and the fill that is breadth-first search wearing a paint costume. Every number on this page came out of a real run on Python 3.12.7 — including the false positive staged in plain sight and the RecursionError that kills the naive paint bucket. Then the gallery closes, and the course takes you back to the thinking that picks the tool.

01The random surfer who built a search empire

Start with the failure that made the idea necessary. Word-counting search ranks text, and text is authored by the one party with every incentive to lie: the page itself. Any signal the author controls, the author will saturate — that is not cynicism, it is just what happened, within months, everywhere. The 1998 reframe moves the signal to something no single author controls: the link graph. A link from page q to page p is q spending a little of its own credibility vouching for p. But that only pushes the question back — how much is q's vouching worth? As much as q's own rank, which depends on who links to q… and the definition has swallowed its own tail. The escape is to stop treating the circularity as a paradox and start treating it as an equation: rank is whatever assignment of numbers makes the whole circular story consistent at once. Such an assignment exists, it is essentially unique, and — this is the practical miracle — you find it by the dumbest imaginable method: guess evenly, then iterate the flow until it stops moving.

Here is the flow, and it is worth seeing as plumbing. Rank is a conserved fluid: the whole web holds exactly 1.0 of it, always. Each round, every page deals its current rank out along its outgoing links in equal shares — a page with one link hands its entire balance to one neighbour; a page with ten links splits itself ten ways. Then the damping: only 85% of each page's balance travels the links; the other 15% is sprinkled evenly over all pages — the surfer's teleport. And one honest complication the textbook diagram hides: a dead end, a page with no outgoing links, would simply swallow whatever reaches it, and the run below shows the entire web's rank draining to 0.0000 in four rounds when we let that happen. The fix is part of the model: a dead end's balance is spread over every page, as if the surfer, stranded, always teleports. With both fixes in place the total stays 1.0 forever, and one page can rise only by another falling.

The widget's six-page web is rigged to stage the algorithm's signature upset. Page E collects three incoming links. Page F collects one. Count links — the pre-1998 instinct — and E wins in a walk. Run the census and F finishes at .326, more than double E's .162, because F's single link comes from A, the page the whole web cites, and A has only that one link to give — F inherits A's entire fortune every round. E's three links come from B, C and D, paupers living on teleport money, each splitting their pittance in half. Watch the max delta meter as you step: the disagreement between successive rounds shrinks by roughly ×0.85 per round — the damping factor is literally the decay rate of the sloshing — until at round 27 no page moves by even a millionth and the census stands still.

Now the same census with nothing hidden: the full trace, the convergence, and then the demolition — the same web with the teleport deleted, so you can watch the dead end drain the world. The two-line summary of the run: one link from a heavyweight outranks three links from paupers, and without the teleport there is no ranking at all.

you type
$ python pagerank.py

LINKS = {                  # a six-page web: page -> the pages it links to
    "A": ["F"],            # the heavyweight hands its whole vote to F
    "B": ["A", "E"],
    "C": ["A", "E"],
    "D": ["A", "E"],
    "E": ["A"],
    "F": [],               # a dead end: everyone reads it, it links nowhere
}
PAGES = sorted(LINKS)
N = len(PAGES)


def step(rank, d):
    # the bored surfer: with probability d follow a random link on the
    # current page; otherwise teleport anywhere. A dead end teleports always.
    sink = sum(rank[p] for p in PAGES if not LINKS[p])
    new = {}
    for p in PAGES:
        flow = sum(rank[q] / len(LINKS[q]) for q in PAGES if p in LINKS[q])
        new[p] = (1 - d) / N + d * (flow + sink / N)
    return new


rank = {p: 1 / N for p in PAGES}
print("power iteration, d = 0.85 (the 1998 damping):")
print(" it  0:", "  ".join("%s %.4f" % (p, rank[p]) for p in PAGES))
for it in range(1, 100):
    new = step(rank, 0.85)
    delta = max(abs(new[p] - rank[p]) for p in PAGES)
    rank = new
    if it <= 4 or it % 10 == 0 or delta < 1e-6:
        print(" it %2d:" % it, "  ".join("%s %.4f" % (p, rank[p]) for p in PAGES),
              " delta %.7f" % delta)
    if delta < 1e-6:
        print("converged: no page moved by more than 1e-6 after %d rounds" % it)
        break

top = sorted(PAGES, key=rank.get, reverse=True)
inbound = {p: sum(p in LINKS[q] for q in PAGES) for p in PAGES}
print()
print("rank order:", "  ".join("%s %.4f" % (p, rank[p]) for p in top))
print("in-links  :", "  ".join("%s:%d" % (p, inbound[p]) for p in top))

print()
print("no teleport (d = 1.0), dead end left unrescued - watch the web drain:")
rank = {p: 1 / N for p in PAGES}
for it in range(1, 5):
    rank = {p: sum(rank[q] / len(LINKS[q]) for q in PAGES if p in LINKS[q])
            for p in PAGES}
    print(" it %d: total rank left in the web = %.4f" % (it, sum(rank.values())))

you see
power iteration, d = 0.85 (the 1998 damping):
 it  0: A 0.1667  B 0.1667  C 0.1667  D 0.1667  E 0.1667  F 0.1667
 it  1: A 0.4028  B 0.0486  C 0.0486  D 0.0486  E 0.2611  F 0.1903  delta 0.2361111
 it  2: A 0.3359  B 0.0520  C 0.0520  D 0.0520  E 0.1139  F 0.3943  delta 0.2040394
 it  3: A 0.2440  B 0.0809  C 0.0809  D 0.0809  E 0.1471  F 0.3664  delta 0.0919292
 it  4: A 0.3050  B 0.0769  C 0.0769  D 0.0769  E 0.1800  F 0.2843  delta 0.0821005
 it 10: A 0.2978  B 0.0715  C 0.0715  D 0.0715  E 0.1614  F 0.3264  delta 0.0020499
 it 20: A 0.2993  B 0.0711  C 0.0711  D 0.0711  E 0.1618  F 0.3255  delta 0.0000194
 it 27: A 0.2993  B 0.0711  C 0.0711  D 0.0711  E 0.1618  F 0.3255  delta 0.0000005
converged: no page moved by more than 1e-6 after 27 rounds

rank order: F 0.3255  A 0.2993  E 0.1618  B 0.0711  C 0.0711  D 0.0711
in-links  : F:1  A:4  E:3  B:0  C:0  D:0

no teleport (d = 1.0), dead end left unrescued - watch the web drain:
 it 1: total rank left in the web = 0.8333
 it 2: total rank left in the web = 0.6667
 it 3: total rank left in the web = 0.2500
 it 4: total rank left in the web = 0.0000

The census needed the whole graph in hand before your query arrived. The next algorithm answers membership questions while refusing to store the members at all →

02The bouncer who never forgets a face

Be precise about what is being refused here, because the refusal is the invention. A set — the hash table you built in Volume 4 — answers membership exactly, and pays for exactness by storing the keys: memory grows with the names, and a million URLs cost megabytes however you squeeze. The Bloom filter's opening move is to refuse to store the names at all. Sixteen bits, in this section's toy — two bytes — will remember three hostnames well enough to answer for them forever. Not perfectly. Well enough, with the imperfection all pushed into one direction, and that direction chosen on purpose: the filter may occasionally say “probably” about a stranger, but it can never, structurally, deny a name it was given. One accepted lie bought total certainty in the direction that carries the traffic.

The machinery fits in a breath. Add a word: hash it into k positions — we use two, derived from one sha256 split into halves, the double-hashing idiom h1 + i·h2 — and set those k bits to 1. Check a word: compute the same k positions and read them. Any 0 → DEFINITELY NOT: had the word ever been added, that exact bit could not still be 0, because bits are never cleared. All 1s → probably — and the hedge is honest, because bits carry no signature of who set them. A stranger's probes can land, by luck, on positions other words lit; the filter sees k honest 1s and cannot know they were written by someone else. The widget stages exactly that: after three bad hostnames go in, hotel.example — never added — probes bits 13 and 8 and finds both lit, because phish.example lit that very pair.

What lifts this from trick to engineering is that the lie has a price tag you can read in advance. Load n words into m bits with k probes each and the odds a stranger finds all their probes lit is about (1 − e^−kn/m)^k — a formula with knobs, not a hope. Want a 1% false-positive rate for a million URLs? The formula tells you the bits to buy (about 9.6 per name — 1.2 bytes, versus the tens of bytes the name itself would cost) and the k to use. The run below puts the formula on trial at two sizes: 1000 names loaded, 10,000 strangers probed — measured 13.77% against a predicted 14.00%, then 1.92% against a predicted 1.96%. Theory and measurement agreeing to a third of a percent, from a structure that never stored a single character of any name it vouches for.

One more honest wrinkle before the run: step to the last beat of the widget and try to delete a word. Clearing scam.example's bits also un-remembers malware.example — the two words share bit 0, and a bit has no idea how many words are leaning on it. The attempted delete manufactures the one answer the filter promised never to give: a false negative. That is not a fixable bug; it is the compression itself. The variants that support deletion — counting filters — pay for it in bits, replacing each bit with a counter.

you type
$ python bloom.py

import hashlib
import math


def bits_for(word, m, k):
    # double hashing: one sha256, split into two 64-bit halves, k probes
    dg = hashlib.sha256(word.encode()).digest()
    h1 = int.from_bytes(dg[:8], "big")
    h2 = int.from_bytes(dg[8:16], "big") | 1     # odd, so all 16 slots reachable
    return [(h1 + i * h2) % m for i in range(k)]


M, K = 16, 2
bloom = [0] * M
for bad in ["scam.example", "phish.example", "malware.example"]:
    ps = bits_for(bad, M, K)
    for p in ps:
        bloom[p] = 1
    print("add   %-16s -> set bits %s" % (bad, sorted(ps)))
print("the filter:", "".join(map(str, bloom)), "  (bit 0 on the left)")

print()
for host in ["quebec.example", "phish.example", "hotel.example"]:
    ps = bits_for(host, M, K)
    verdict = "PROBABLY IN" if all(bloom[p] for p in ps) else "DEFINITELY NOT"
    print("check %-16s -> bits %-8s -> %s" % (host, sorted(ps), verdict))
print("hotel.example was never added; its two probes landed on phish's two")
print("bits. a false positive - the price of storing 3 names in 16 bits.")

print()
print("the real rate: add 1000 hostnames, probe 10000 strangers, twice")
for m, k in ((4096, 3), (8192, 6)):
    filt = bytearray(m)
    for i in range(1000):
        for p in bits_for("word%04d" % i, m, k):
            filt[p] = 1
    fp = sum(all(filt[p] for p in bits_for("probe%05d" % i, m, k))
             for i in range(10000))
    theory = (1 - math.exp(-k * 1000 / m)) ** k
    print("  m=%4d k=%d: measured fp %4d/10000 = %.4f   theory %.4f"
          % (m, k, fp, fp / 10000, theory))

print()
print("why you cannot delete: scam and malware SHARE bit 0")
for p in bits_for("scam.example", M, K):
    bloom[p] = 0                       # try to remove scam.example
ps = bits_for("malware.example", M, K)
verdict = "PROBABLY IN" if all(bloom[p] for p in ps) else "DEFINITELY NOT"
print("clear scam's bits %s, then check malware.example -> %s"
      % (sorted(bits_for("scam.example", M, K)), verdict))
print("a false negative: the one answer a plain bloom filter must never give")

you see
add   scam.example     -> set bits [0, 15]
add   phish.example    -> set bits [8, 13]
add   malware.example  -> set bits [0, 7]
the filter: 1000000110000101   (bit 0 on the left)

check quebec.example   -> bits [5, 10]  -> DEFINITELY NOT
check phish.example    -> bits [8, 13]  -> PROBABLY IN
check hotel.example    -> bits [8, 13]  -> PROBABLY IN
hotel.example was never added; its two probes landed on phish's two
bits. a false positive - the price of storing 3 names in 16 bits.

the real rate: add 1000 hostnames, probe 10000 strangers, twice
  m=4096 k=3: measured fp 1377/10000 = 0.1377   theory 0.1400
  m=8192 k=6: measured fp  192/10000 = 0.0192   theory 0.0196

why you cannot delete: scam and malware SHARE bit 0
clear scam's bits [0, 15], then check malware.example -> DEFINITELY NOT
a false negative: the one answer a plain bloom filter must never give

The bouncer answers for one name at a time. The next algorithm holds two whole files side by side — and names the two lines you touched →

03How git sees what you changed

The grid that finds the skeleton is wild 1's edit-distance table asked a different question — same family, same shape, opposite direction: edit distance wants the cheapest way to turn one sequence into the other, LCS wants the largest part that survives unchanged, and each is computable from the other. The object itself: rows for the old file's lines, columns for the new file's, and dp[i][j] holding one exact fact — the length of the longest skeleton shared by the first i old lines and the first j new lines. Row zero and column zero are free: an empty file shares nothing with anything. Every other cell is settled by looking at three already-settled neighbours, which is the entire discipline of dynamic programming: no cell is ever guessed, each is proven from proven smaller answers.

The recurrence is two cases and both are common sense. If old line i and new line j are the same text, that line extends whatever skeleton the two shorter prefixes share: diagonal + 1 — the only move in the whole table that ever grows anything. If they differ, the cell can invent nothing; it inherits the better of its two neighbours, max(up, left) — old news, carried forward. Watch the widget fill: through the four identical lines the diagonal climbs a staircase 1, 2, 3, 4; the moment it hits the changed lines, row 5 flatlines — total += int(n) matches nothing anywhere in the new file, so the row adds nothing, and the corner settles at 4. That single corner number already prices your edit before naming it: 6 − 4 = 2 removals, 6 − 4 = 2 additions.

Naming the edit is the traceback — walk from the corner back to the origin, reading each cell's story. A diagonal step is a line both files share: kept. An upward step spends an old line no skeleton wanted: print it with a “−”. A leftward step spends a new line the same way: “+”. The walk below leaves the corner on a genuine fork — up and left both read 4 — and the widget stops there to ask you what the tie means, because it is the honest subtlety of the whole method: the grid fixes the diff's size absolutely, but not its presentation. Ties are why two correct tools can print the same edit differently. This walker prefers left on ties, which groups removals above additions — the shape you have read a thousand times in a unified diff.

The run fills the same grid, walks the same traceback, and then hands the two files to difflib.unified_diff — the standard library's real tool — to check our homemade diff against the shipped one. Same four marked lines, same order.

you type
$ python diff.py

import difflib

OLD = ["import sys",
       "def main():",
       "    total = 0",
       "    for n in sys.argv[1:]:",
       "        total += int(n)",
       "    print(total)"]
NEW = ["import sys",
       "def main():",
       "    total = 0",
       "    for n in sys.argv[1:]:",
       "        total += float(n)",
       "    print(round(total, 2))"]

m, n = len(OLD), len(NEW)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if OLD[i - 1] == NEW[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print("the LCS grid - dp[i][j] = longest skeleton of old[:i] and new[:j]")
for row in dp:
    print("  ", row)
print("corner says: the two files share a %d-line skeleton (of 6 each)" % dp[m][n])

out = []
i, j = m, n
while i > 0 or j > 0:                # walk back from the corner
    if i > 0 and j > 0 and OLD[i - 1] == NEW[j - 1]:
        out.append("  " + OLD[i - 1]); i -= 1; j -= 1      # diagonal: kept
    elif j > 0 and (i == 0 or dp[i][j - 1] >= dp[i - 1][j]):
        out.append("+ " + NEW[j - 1]); j -= 1              # left: added
    else:
        out.append("- " + OLD[i - 1]); i -= 1              # up: removed
print()
print("the traceback, read forwards - everything off the skeleton is the edit:")
for line in reversed(out):
    print("   " + line)

print()
print("difflib.unified_diff - the stdlib's real tool, same verdict:")
for line in difflib.unified_diff(OLD, NEW, "old.py", "new.py", lineterm=""):
    print("   " + line)

you see
the LCS grid - dp[i][j] = longest skeleton of old[:i] and new[:j]
   [0, 0, 0, 0, 0, 0, 0]
   [0, 1, 1, 1, 1, 1, 1]
   [0, 1, 2, 2, 2, 2, 2]
   [0, 1, 2, 3, 3, 3, 3]
   [0, 1, 2, 3, 4, 4, 4]
   [0, 1, 2, 3, 4, 4, 4]
   [0, 1, 2, 3, 4, 4, 4]
corner says: the two files share a 4-line skeleton (of 6 each)

the traceback, read forwards - everything off the skeleton is the edit:
     import sys
     def main():
         total = 0
         for n in sys.argv[1:]:
   -         total += int(n)
   -     print(total)
   +         total += float(n)
   +     print(round(total, 2))

difflib.unified_diff - the stdlib's real tool, same verdict:
   --- old.py
   +++ new.py
   @@ -2,5 +2,5 @@
    def main():
        total = 0
        for n in sys.argv[1:]:
   -        total += int(n)
   -    print(total)
   +        total += float(n)
   +    print(round(total, 2))

From comparing whole files to a single click on a pixel: the gallery closes with the algorithm you have been running since your first drawing app →

04The paint bucket you have clicked for years

There is a genuine unmasking here, so collect it in one sentence: the paint bucket — the first tool you ever clicked in a drawing program — is chapter 44's breadth-first search, unchanged. The queue is the same queue; the rings are the same rings; the never-revisit discipline is the same discipline. What changed is only the reading of the words. BFS says visit every node reachable from the source; the bucket says paint every pixel connected to the click — and “connected” just means reachable through edges, where an edge joins touching pixels of the same colour. The wall in your drawing is not special to the algorithm. It is simply pixels of a different colour, so the colour test fails there, no edge exists, and the frontier dies at the outline for the same reason ch44's ripple dies at the end of a graph: there is nowhere legal left to go.

The implementation below is chapter 52's deque doing its day job — popleft from the front, append to the back, the frontier advancing in rings — with one detail worth stealing for any BFS you ever write: pixels are painted when they join the queue, not when they leave it. Paint-on-arrival would let two frontier pixels both discover the same neighbour and queue it twice; paint-on-enqueue makes the once-ever rule structural. And one decision the loop cannot duck: the move list. N4 is up, down, left, right — edges only. N8 adds the four corner steps. Two extra tuples in a list, and they change the meaning of every region on the grid, because connectivity is a definition, not a discovery — the classic production bug is drawing a boundary that is only diagonally connected and filling with a rule that treats corners as passable: the wall is airtight under one rule and a sieve under the other.

The widget's field stages that bug in miniature. A four-pixel chamber sits sealed behind a wall — except at row 5, column 3, where two wall cells meet only at their corners, leaving a diagonal crack. Under N4 the crack is just more wall: the free cells on either side of it touch corner-to-corner, corners are not neighbours, no edge exists — the fill paints 33 pixels and the chamber survives. Under N8, the same click, the same walls: at ring 5 the paint steps corner-through-corner and the chamber floods — 37 pixels. Four pixels of difference, and they are the entire distance between “the tool selected what I meant” and “the paint went everywhere”. The run then adds the other classic failure, the one that ships to production: write the fill recursively and each deferred neighbour becomes a stack frame — on a 200×200 open field Python dies with RecursionError after 999 pixels, under 3% of the region. The deque holds the same frontier as plain data on the heap, and finishes anything that fits in memory.

The run, both rules, before and after — and then the recursive version walking into the wall Python builds at a thousand frames.

you type
$ python flood.py

from collections import deque

GRID = ["##########",
        "#........#",
        "#..####..#",
        "#..#..#..#",
        "#..#..#..#",
        "#...###..#",
        "#........#",
        "##########"]
ROWS, COLS = len(GRID), len(GRID[0])
N4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
N8 = N4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)]


def flood(start, moves):
    grid = [list(row) for row in GRID]
    q = deque([start])                 # ch52's deque: the frontier, in a queue
    grid[start[0]][start[1]] = "o"
    filled = 1
    while q:
        r, c = q.popleft()
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == ".":
                grid[nr][nc] = "o"     # paint it - and never visit it again
                filled += 1
                q.append((nr, nc))
    return grid, filled


print("before - the chamber's wall has a diagonal crack at row 5, col 3:")
for row in GRID:
    print("   " + row)

g4, n4 = flood((1, 1), N4)
print()
print("click (1,1), 4-way fill: painted %d cells - the chamber held:" % n4)
for row in g4:
    print("   " + "".join(row))

g8, n8 = flood((1, 1), N8)
print()
print("same click, 8-way fill: painted %d cells - it leaked through:" % n8)
for row in g8:
    print("   " + "".join(row))

print()
print("the recursive version, on a 200x200 open grid:")
big = [["."] * 200 for _ in range(200)]


def rec(r, c):
    if 0 <= r < 200 and 0 <= c < 200 and big[r][c] == ".":
        big[r][c] = "o"
        rec(r + 1, c); rec(r - 1, c); rec(r, c + 1); rec(r, c - 1)


try:
    rec(0, 0)
except RecursionError:
    painted = sum(row.count("o") for row in big)
    print("  RecursionError after painting %d of 40000 cells" % painted)
    print("  every deferred neighbour became a stack frame; the deque holds")
    print("  the same frontier on the heap and never runs out of room")

you see
before - the chamber's wall has a diagonal crack at row 5, col 3:
   ##########
   #........#
   #..####..#
   #..#..#..#
   #..#..#..#
   #...###..#
   #........#
   ##########

click (1,1), 4-way fill: painted 33 cells - the chamber held:
   ##########
   #oooooooo#
   #oo####oo#
   #oo#..#oo#
   #oo#..#oo#
   #ooo###oo#
   #oooooooo#
   ##########

same click, 8-way fill: painted 37 cells - it leaked through:
   ##########
   #oooooooo#
   #oo####oo#
   #oo#oo#oo#
   #oo#oo#oo#
   #ooo###oo#
   #oooooooo#
   ##########

the recursive version, on a 200x200 open grid:
  RecursionError after painting 999 of 40000 cells
  every deferred neighbour became a stack frame; the deque holds
  the same frontier on the heap and never runs out of room

Close the gallery on the family resemblance, because after twelve algorithms it is impossible to miss. PageRank is a tiny loop plus an invariant — rank is conserved — iterated until a fixed point. The Bloom filter is two functions plus an invariant — bits never clear, so a probed zero is proof — with its one lie priced by a formula. The diff grid is a two-case recurrence plus an invariant — every cell exact before anything depends on it — and the answer read backwards along the arrows. Flood fill is ch44's loop plus an invariant — painted once, spread only through legal edges — with the visited set promoted to the product. None of the four is more than fifteen lines. What carries each one is the promise it can afford to keep on every step, and the honesty to know exactly where the promise ends: the census that link farms gamed, the bouncer's priced lie, the diff that is minimal but not unique, the region that depends on what “neighbour” means. That is what an algorithm is, seen from the metal up — and by now, you can read one cold.

That closes the gallery — twelve algorithms in the wild, from your pocket to the map to the internet. Back to the course: the thinking that picks the tool →