Long-haired programmer; loves cats and dogs but doesn't have any.

- Production rules for search (and lex ordering)
- Analogy problems
- Estimating debugging
- Paper and pencil collaborators
- Trying to work
- Linkdump
- Empowerment
- Understanding Ceu using Shenzhen I/O
- Pólya urn
- Little interpreters
- No Man's Sky
- The Secretary Problem
- Newsvendor problem
- Survival games
- Ego lens
- Elm Architecture in C++
- Mission and Space
- A little story engine
- Yet another coupon collector's problem blog post
- Reification
- Spreadsheets
- Underdrawing
- Linkdump
- Race games
- Links that I thought were interesting
- Links that I thought were interesting
- Modeling Shmups in Machinations and Ceu
- Modeling Pipe Dream in Machinations and Ceu
- Context Free Grammars for Learning
- SPSC.py howto
- Viva Pajaro and Wardley Mapping
- Where do objects come from? III
- Where do objects come from? II
- Meta II by Val Schorre
- Citations, Elisions, and Arguments
- Where do objects come from?
- Protocol Buffers
- Dataflow Bench in Java
- Abstract nonsense continued
- Abstract nonsense
- A Douche-Free bio
- Wiring Idiom in C++
- Dataflow Bench in C
- Visitor Pattern Generator in C++
- First Post
- Elm Architecture in C++

This is a silly game, but anyway.

We assume you have a graph (nodes and edges) explicitly on a piece of paper (printed out or something), and it’s small enough that you can comprehend it visually, and you don’t mind marking it up.

You will need blank index cards and a writing implement.

Decide on locations for four spots for index cards: the blank ones, the “TODO” stack, the “FOCUS” stack, and the “DONE” stack.

Create an index card for the starting node, put it in the FOCUS stack, and cross off the starting node in the graph.

- If both the FOCUS spot is empty and the TODO spot is empty, then you’re done!
- If the FOCUS spot is empty, but the TODO spot is not, move the top card from the TODO stack into the FOCUS spot.
- If the FOCUS spot is non-empty, and the corresponding node in the graph has a neighbor that has not been crossed off, create a new card for that neighbor, put it on the top of the TODO stack, and cross off the neighbor on the graph.
- If the FOCUS spot is non-empty, and every neighbor of the corresponding node in the graph is crossed off, put the card in the FOCUS spot into DONE.

Why does this game terminate? Let’s try to use Lex ordering to prove it.

Lex ordering is dictionary ordering, generalized to tuples of numbers. For example, in lex ordering (a, b, c) is bigger than another tuple (d, e, f) if a is bigger than d in the usual way, or if a is equal to d and b is bigger than e. If a equals d and b equals e then we fall back to comparing c to f.

Let’s use this 4-tuple: (unmarked non-neighbors, unmarked neighbors, number of items in TODO, number of items in FOCUS)

When we focus using rule 2, then we change the set of neighbors. In principle, switching focus could increase the number of unmarked non-neighbors, if we had some unmarked neighbors before the switch. However, because we always mark all of the neighbors before switching focus, Rule 2 never increases the number of unmarked non-neighbors, and sometimes unmarked non-neighbors become unmarked neighbors, decreasing the number of unmarked non-neighbors.

Also, when we focus using rule 2, we decrease the number of items in TODO. We increase the number of items in FOCUS, but we don’t mind that.

When we mark a neighbor with rule 3, we decrease the number of unmarked neighbors (and increase the number of items in TODO, but we don’t mind that), but we never increase the number of unmarked non-neighbors.

When we unfocus using rule 4, we decrease the number of items in FOCUS, and we don’t increase any other quality.

So in every case, we go downward in lex ordering.

Note: I am not certain that this argument is ironclad.

Opinions expressed are solely my own and do not express the views or opinions of my employer.