Games for Programmers: Jotto

The next in an irregular series of board game recommendations for programmers. Of course, you don't have to be a programmer to enjoy these games, but if you are a programmer, then I think there's a pretty good chance that you'll like them.

However, you might not want to play this particular game with your spouse. Here's why...

“End. E-N-D”, she guessed. “One”, I replied.
“Cab. C-A-B”, I guessed. “One”, she replied.

We were driving to a campground in Massachusetts. My wife and I were in the front seats of the minivan; our daughter was in the middle seat, watching a DVD; and our son and his friend were chatting in the back seat.

We had been on the road for several hours, and I was feeling a bit tired. I needed to do something to help keep me alert. “Jotto?”, I suggested to my wife. “Ok.“

“Icy. I-C-Y”, she guessed. “Zero”, I replied.
“Fed. F-E-D”, I guessed. “One”, she replied.

Jotto is a two-player deduction game, kind of like Mastermind but with words. In fairness, I should say that Mastermind is like Jotto but with colors, since Jotto is older than Mastermind.

Each player secretly chooses a five-letter word with no duplicate letters. The usual restrictions apply—no proper nouns, etc.

The players take turns guessing each other's words. For each guess, you tell the player how many letters were correct. Unlike Mastermind, it doesn't matter whether the letter is in the right position or not. For example, if you guessed BOARD and got one letter right, the answer might be PLAYS (the A matches, in the same place) but it could just as easily be GAMES (the A matches, not in the right place).

“Map. M-A-P”, she guessed. “One”, I replied.
“Jig. J-I-G”, I guessed. “Zero”, she replied.

Jotto is a favorite game for situations where it would not be feasible to set up a board or deal out cards. For example, you can easily play it in a restaurant, or waiting in line, or on a long drive. All you need is two pencils and two pieces of paper.

“Age. A-G-E”, she guessed. “Two”, I replied.
“Out. O-U-T”, I guessed. “Zero”, she replied.

In fact, you don't even need the pencil and paper! Most of the time, we play it in our heads with three-letter words instead of five. This is a great variation that allows the driver to play in the car. It also lets you play in situations where you are moving too much to be able to take notes comfortably, such as jogging or hiking.

For this game, I picked AXE as my word.

“Axe. A-X-E”, she guessed. “Got it. Dang that was fast!”, I replied.
“Men. M-E-N”, I guessed. “One”, she replied.

I started playing Jotto this way with my son when he was 10. We still enjoy it and play it often, but it has become kind of a running joke, because we almost always finish within one guess of each other. This is the first time I have played mental Jotto with my wife, and she's killing me! She got it in five guesses, and I'm not even close!

Ok, with ones for both FED and MEN, I guess that it probably has an E. Next, I want to figure out which letter from CAB was correct. I'll try the A, and I'll also throw one of the other letters from FED to help confirm that it really was the E.

“Far. F-A-R”, I guessed. “One”, she replied.

Good. It probably really was the A. What has an E and an A?

“Sea. S-E-A”, I guessed. “Two”, she replied.

Now I'm getting somewhere. It looks like the E-A is correct. What else has an E-A?

“Pea. P-E-A”, I guessed. “Two”, she replied.

Hmm. I'm nearly certain now that the E-A are correct. What else has an E-A? It can't be TEA because I already got a zero for OUT. What if it's A-E instead of E-A?

Wait a minute. No way. No, she couldn't possibly have picked...

“Axe. A-X-E”, I guessed. “Got it”, she laughed.

Oh, man. We really have been married too long.

Originally written as a session report for BoardGameGeek.

Creativity

I recently stumbled across the TED video by Ken Robinson (via Joshua Gans). This video is almost two years old, so I'm getting to it rather late.

Robinson describes the increasing importance of creativity in the modern world, and bashes the education system for “educating people out of their creativity”. He contends that “creativity now is as important in education as literacy and we should treat it with the same status”. Robinson is an entertaining speaker, and I quite enjoyed his video. However, as I thought about it later, I become more dissatisfied.

I agree that creativity is important, and that the education system is doing a terrible job nurturing creativity. My problem with his talk is that he equates creativity with the arts: drawing, drama, dance, etc. I would hate to see some school administrator be inspired by the talk and attempt to “solve” the problem by simply adding an extra art class to the curriculum.

I'm not anti-arts. I'm not saying that art classes are bad. I am saying that giving students one art class in which to be creative, while systematically sucking the creativity out of them in every other class, is not going to solve the problem.

Instead, we need to recognize that other disciplines outside the arts also require creativity, and teach them that way. For example, mathematics is often taught in a way that brooks no creativity whatsoever, whereas the practice of actually doing real mathematics is highly creative. See Paul Lockhart's essay (pdf) for a wonderful discussion about creativity in mathematics education.

I think people often view technical subjects as having no place for creativity. You don't want a student getting creative when multiplying two numbers. I certainly don't want my programming students getting creative about indentation. In fact, in many technical subjects, the very word creative is often used as a synonym for wrong or mistaken (or sometimes unethical, as in “creative accounting”).

For example, I just said that you don't want a student getting creative when multiplying two numbers. But that's only because, in that context, “getting creative” would usually be interpreted as getting the wrong answer. In reality, I'd be thrilled if my grade-schooler, when faced with a multiplication problem like 37x999, rejected long multiplication and instead said, “Hmm. 999 is almost 1000. 37x1000 is 37000. Then take away 37 to get 36963.” That's creativity!

Perhaps the biggest difference between creativity in the arts and in technical subjects has to do with constraints. In the arts, you tend to have fewer constraints, and those constraints are often flexible. In technical subjects, you tend to have more constraints, and those constraints are often non-negotiable. Think of the scene from Apollo 13: “We've got to find a way to make this...fit into the hole for this...using nothing but that.” Or the t-shirt about the speed of light that says “300,000 kilometers per second: It's not just a good idea, IT'S THE LAW!”

Common perception is that, the more constraints you have, the less creativity is involved. I don't think that's true. In fact, as Marissa Mayer of Google fame says, creativity loves constraints. Of course, sometimes the creativity lies in figuring out which constraints are real, and which aren't.

Immortality

Last week, I wrote about one of my more spectacular failures, which involved a progression that began 1, 2, 4, 8, 16, 32, but then rather than continuing sensibly as 64, 128, ..., instead exploded into 273, 65569, 4294967361, and 1.5x10⁸². The next term is a little over 2⁶⁵⁵⁶⁹ and the term after that a little over 2^4294967361, which has about a billion digits when written out in full.

Joshua Zucker suggested that I submit this to the On-Line Encyclopedia of Integer Sequences, which I did. So I've now been immortalized in Sequence A137181. I can see my tombstone now: “He failed...BIG.”

Several years ago I was giving a guest lecture in a colleague's Algorithms class, when I encountered immortality of a different sort. The students were asking me about how I invented “Okasaki trees”, and were dumbfounded when I didn't know what they were talking about. How could I not know about Okasaki trees when I invented them? “Well,” I told them, “I've invented a lot of different data structures, and most of them are trees of one kind or another. But I've never called any of them Okasaki trees.” After a bit more digging, it turned out that my colleague (who wasn't there that day) had been telling them the previous week about my simplification of red-black trees, and he called them Okasaki trees.

The lasting result of this is that I now have a friend at work who ribs me about Okasaki trees every chance she gets.

A Spectacular Failure

About five years ago, a mathematical puzzle occurred to me. I eventually solved the puzzle, but I don't want to talk about that solution here. Instead, I want to talk about my first attempt at solving the puzzle, which was an utter failure. A glorious, spectacular failure. Perhaps the single most impressive failure of my career. Failures are often much more interesting than successes, but for some unfathomable reason, people are often reluctant to discuss them.

The Puzzle and My “Solution”

You don't need to understand the details of the puzzle to enjoy the failure, so if you're not familiar with SK combinators and their ilk, or if you just can't be bothered, then please skip ahead to the next section.

I was playing around with SK combinators one day when a puzzle occurred to me. Could I introduce new combinators that would allow me to linearize any combinator expression? Combinator expressions are normally binary trees, and are written using parentheses to indicate the tree structure. The convention is that parentheses on the left can be omitted. For example, ((w x) y) z can be written as w x y z, but w (x (y z)) cannot be written without parentheses. I wondered if I could introduce new combinators that would allow me to rewrite any expression into an equivalent expression with no parentheses. I called such a transformation “flattening”.

One of the standard combinators in the SK family is B, which has the rewrite rule

B f g x = f (g x)Reading this rule backwards works well for flattening small expressions—for example, x (y z) can be rewritten without parentheses as B x y z—but I ran into problems using it to flatten larger expressions, so I quickly turned to a variation of B that swaps the first two arguments R f g x = g (f x) This new combinator works well for flattening expressions of the form c (c₁ c₂ ... c_N). For example,

   c (c1 c2 ... c7)
       = R (c1 c2 ... c6) c c7
       = R (c1 c2 ... c5) R c6 c c7
       = R (c1 c2 ... c4) R c5 R c6 c c7
       ...
       = R c1 R c2 R c3 R c4 R c5 R c6 c c7

Now, another combinator F works in conjunction with R to flatten more complicated expressions. F is defined as

F f g x y = f x (g y) For example, we can now rewrite c₁ c₂ c₃ (d₁ d₂ d₃) as follows:

   c1 c2 c3 (d1 d2 d3)
      = F (c1 c2) (d1 d2) c3 d3
      = R c1 F c2 (d1 d2) c3 d3
      = F (R c1 F) d1 c2 d2 c3 d3
      = R (R c1) F F d1 c2 d2 c3 d3
      = R R R c1 F F d1 c2 d2 c3 d3

The complete rules for flattening are

• flatten(c) = c
• flatten(e c) = flatten(e) c
• flatten(c1 (e c2)) = flatten(R e c1 c2)
• flatten(e1 c1 (e2 c2)) = flatten(F e1 e2 c1 c2)
• flatten(e1 e2) = flatten(flatten(e1) flatten(e2))

where each c is a simple symbol and each e is an arbitrary expression.

Not So Fast

I run my solution by hand on a few examples and it works great. So I code it up, run it on my examples and get the same answers. Yippee! Next, I run it on a larger example and.........nothing. The computer justs sits there, mocking me. Obviously, I've got a bug somewhere that is causing infinite recursion.

I stare at my program for awhile, but I'm not seeing any bugs. Hmmm. I run it on a different example and it finishes this time. I print out the result and...whoa, that's a lot of output! I wonder how big the transformed expressions are? Ok, calculating the size of the result shouldn't be too hard. I whip up another program and print out a table of the maximum output for an input of size N.

   N=1     max output=1
     2                2
     3                4
     4                8
     5                16
     6                32
     .
     .
     .
     .

Quick! Guess the next value in the table! 64, right? RIGHT?!

     .
     .
     .
     .
     .
     7                273
     .
     .
     .
     .
     .

Huh? 273? What the heck is that?

     .
     .
     .
     .
     .
     8                65,569
     .
     .
     .
     .
     .

65,569?! You're joking, right?

     .
     .
     .
     .
     .
     9                4,294,967,361
     .
     .
     .
     .
     .

4 billion? Well, that's just silly.

     .
     .
     .
     .
     .
     10      15,177,100,720,513,508,366,
            558,296,147,058,741,458,143,
            803,430,094,840,009,779,784,
            451,085,189,728,165,691,939

What do you even say to a number like that? That's 1.5x10⁸². To put that in perspective, the number of atoms in the observable universe is estimated to be about 10⁸⁰. No wonder my program was running slow! At a few billion operations a second, that calculation should only take about...um...carry the 3...dang, where's Art Benjamin when you need him?...let's just say a long time.

If you're curious, here's the function that describes the size of the biggest possible output for an input of size N:

• Biggest(N) = 2^(N-1), if N <= 6
• Biggest(N) = 2^Biggest(N-3) + 2*Biggest(N-3) + 1, if N > 6

And here's the input of size 10 that gives the absurd result above:X (X X) (X (X X) (X (X (X X))))

Once I recovered from the shock of this experience, I did eventually come up with a very nice solution to the puzzle, based on ideas from postfix languages like Forth and Postscript, but nothing quite compares with getting an answer like 1.5x10⁸².