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…

The Lion's Lair

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?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s