A dart thrown into the dark abstract landed on the trick that finds the value filling more than half of a stream while remembering only two numbers — a candidate and a counter — no matter how long the stream runs. Match: count up. Miss: count down. Hits zero: the next token becomes the new candidate. We show the technique live, credit who actually made it, and ask what I-13 should learn: a language that can already do the vote but has no way to be fed a stream.
THE TECHNIQUE one pass · two scalars · then verify
Walk the stream once. Hold a candidate and a counter. If the counter is 0, adopt the current token as candidate and set counter to 1. Else if the token matches the candidate, +1; if it misses, −1. The survivor is the only possible majority — but Boyer-Moore can be fooled when no majority exists, so a second pass must confirm the survivor really crosses 50%. live demo
cand = null; cnt = 0
for token in stream: // ONE pass, O(1) memory
if cnt == 0: cand = token; cnt = 1
elif token == cand: cnt += 1
else: cnt -= 1
// survivor = cand (the ONLY candidate that could be a majority)
verify: count(cand) > n/2 ? // second pass — required
candidate
—
counter
0
total memory
2 scalars — fixed (stream len irrelevant)
Press step to advance one token, or run to end.
HISTORY & CREDIT credit where it is due
The name is right and the confusion is elsewhere: this is the Boyer-Moore string search. It is not — that famous substring algorithm shares the same two authors but is a different technique. This is their lesser-known majority vote. cited
1980 · Robert S. Boyer & J Strother Moore (SRI International / later UT Austin) — devise the majority-vote algorithm while formally verifying a fault-tolerant “majority” component; write it up as a tech report circulated in 1981. The origin. 1981 · the same pair are already famous for the Boyer-Moore string-search algorithm (1977) — which is why this one is often mistaken for it. Different problem, same authors. 1982 · Jayadev Misra & David Gries — generalise it to find all items over 1/k of the stream (the Misra-Gries heavy-hitters / summary), the ancestor of modern streaming frequency estimators. 1991 · the vote finally appears in a formal, citable venue — Boyer & Moore, “MJRTY: A Fast Majority Vote Algorithm,” in Automated Reasoning: Essays in Honor of Woody Bledsoe. Ten years between invention and publication.
What is open: the algorithm is simple enough that pieces of it were surely reinvented at other desks; and because it slept unpublished from 1981 to 1991, folklore attributions drift. The solid claim: Boyer & Moore conceived it (1980–81), Misra & Gries generalised it (1982). Both are correct and independently checkable. open
RECOMMEND FOR I-13 it can compute the vote — it just can’t be fed
This one has a subtle finding. The vote’s entire runtime state is two scalars and its logic is only if, ==, +, − — every one of which I-13 already has. So unlike most darts, the compute needs nothing new. I proved it: I hand-unrolled the 7-token stream [4,4,2,4,3,4,4] into explicit declarations (the only input shape I-13 permits) and ran the full vote + verify pass on the live compiler:
i13 run vote.i13 => RUN OK · 330 steps · peak stack 4
MAJORITY = 4 (survivor of the two-scalar fold)
hits = 5 (verify pass: 5 of 7)
CONFIRMED = 1 (2*5 > 7 — true majority)
used ONLY: I decls, def, if, ==, +, - — zero new alphabet, zero new BinOp
The wall is not the vote — it is the input. Boyer-Moore is a stream algorithm; its whole point is “for token in stream” over an unknown length. I-13 has no array, no iterable, no I/O to deliver one. Proven, not asserted — three ways the stream is refused:
i13 check arr.i13 => arr.i13:1:13 E0001 unexpected character `[` (no array/sequence literal)
i13 run read.i13 => read.i13:1:8 E0202 unknown function `read` (no input primitive to pull a stream)
i13 run vararg.i13=> vararg.i13:2:8 E0203 function `f` expects 1 argument(s), provides 6 (fixed arity — can’t feed an arbitrary-length run through one call)
Recommend — and this is the honest, cheaper-than-usual finding: for the compute, add nothing. The O(1) vote already fits inside the counted 13-symbol alphabet exactly as shipped; the RUN OK above is the whole proof. Do not reach for a new BinOp here — there is nothing missing to add.
What is genuinely absent is an input story: an iterable — a sequence value plus a way to walk it (a length-indexed read, or a fold/`each` construct), or a host I/O channel that streams tokens in. That is a real capability I-13 lacks, and it is the thing standing between “can hand-unroll seven tokens” and “can process a stream.”
Tradeoff (stated plainly): an array/iterator is not a free BinOp discriminant — it is a new value kind and new control shape, and it lands squarely in I-13’s published NOT COVERED list (iteration, sequences). It costs more counted-alphabet purity than the modulo-style adds other darts proposed. So the design-respecting move is to keep the vote as-is and treat “how does a stream enter an I-13 program” as its own deliberate decision — likely a host-fed channel (as examples/core.i13 already threads explicit payloads from the HTML host) rather than a language-level array, preserving the counted alphabet while still letting real streams arrive.