## Zoombinis and Lexicographic Ordering

In my last post, I said:

“The Logical Journey of Zoombinis” was a computer game first released in 1996. The aim of the game is to get your Zoombinis from Zoombini Isle to Zoombiniville via a series of logical puzzles. Coincidentally (or maybe not) Rachael and I both spent significant amounts of our childhood playing this game  – just ask our siblings! We both strongly attribute our interest in logical puzzles and maths to this game. It lead us to wonder: what maths does Zoombinis actually involve?

In this post I will describe another area of maths that arises in the Zoombinis puzzles: lexicographic ordering.

A useful thing to do is to put sequences of things in some order. For example

1. We can put numbers in size order
2. We can put letters in alphabetical order. The letters C, S, A, T go into the order A, C, S, T. But it gets more complicated if instead we want to order entire words, instead of just letters. We end up with dictionary order. We know how this works: first we order by the first letter of the word, then if two words have the same first letter we look at the second letter of the word, etc.

In maths language, this is described in the following way:

• For two words $w_1$ and $w_2$ we say $w_1 < w_2$ if $w_1$ comes before $w_2$ in the dictionary
• We can express our words in letters, for example $CATS = (C, A, T, S)$. In symbols, we have $w = (a_1, \cdots, a_n)$ for some letters $a_i$
• Consider two words $(a_1, \cdots, a_n)$ and $(b_1, \cdots, b_n)$ (which we assume to have the same number of letters). Then $(a_1, \cdots, a_n) < (b_1, \cdots, b_m)$ if $a_i = b_i$ for $1 \leq i \leq m$, for some $m$, and then $a_{m+1} < b_{m+1}$. For example $(C,A,R,S) < (C,A,T,S)$ since $C = C$ and $A = A$ and $R < T$.

The Zoombinis level “The Lion’s Lair” uses this idea: you have to put the Zoombinis in the right order. If you get the order wrong your Zoombini is transported to the right location and you lose a life. Articles about this level of the game online say that hints to the right order are written on the walls, but I have never been able to find these clues…

Instead of letters, we have features, so a Zoombini word is given by ( Hair, Nose, Feet, Eyes) and an example is (Pony tail, Red nose, Roller skates, Glasses). The player has to guess which order the features come in. Examples of the two types of things to guess are:

1. Whether you order by feet first, and then eyes or the other way around
2. What is the order of the nose colours: does red come before blue, or blue before red?

A high level of the game might ask you to put a full lexicographic order on the Zoombinis. We could ask questions such as: What is the complexity of this game? With a perfect strategy, how many guesses would we have to make to ascertain the right order for the Zoombinis?