Misra and Gries’s generalisation: k − 1 street corners around a plaza, each held by at most one gang,
with a counter C[y] for its members there. When all corners are held and a member of yet another gang walks in, there is a standoff:
the newcomer and one member from every corner — k members of k different gangs — all die. Every gang with more than n/k members
survives at a corner. The highlighted line of the code is the one being executed.
Boyer and Moore’s linear-time majority vote, told as a turf war: the elements of A arrive one by one as members of
colour-coded gangs; the gang holding the square is the candidate x, and c counts its members there.
Two members of different gangs who meet fight a duel that both lose; the graveyard of these mixed pairs is the whole correctness proof.
The code is the one from the slides; the highlighted line is the one being executed.
Show
Random
— / —Speed700ms
Town square
The invariant
Head count
What happens
Code
About this page — the story, the invariant, Misra–Gries, input format