ITA's Optimal Ghost

ITA was a startup software company that built flight scheduling software and employed some of the smartest people around until they were bought by Google in 2010. ITA was known for using Common Lisp and also for their recruitment campaign. They posted programming puzzles on the internet and in ads around the T in Boston and invited developers who wished to work at ITA to solve them.

They had two types of programming puzzles. One type were algorithmic and aimed at Computer Scientist. These are interesting. The other type were aimed at Software Engineers. However, one of the Software Engineering puzzles, Optimal Ghost dating from 2012, has enough algorithmic complexity to make it appeal me.

"In the game of Ghost two players take turns building up an English word from left to right. Each player adds one letter per turn. The goal is to not complete the spelling of a word: if you add a letter that completes a word (of 4+ letters), or if you add a letter that produces a string that cannot be extended into a word, you lose. (Bluffing plays and "challenges" may be ignored for the purpose of this puzzle.)

Write a program that allows a user to play Ghost against the computer.
The computer should play optimally given the following dictionary: WORD.LST (1.66 MB). Allow the human to play first. If the computer thinks it will win, it should play randomly among all its winning moves; if the computer thinks it will lose, it should play so as to extend the game as long as possible (choosing randomly among choices that force the maximal game length).
Your program should be written as a Java web application that provides an html-based, rich GUI for a human to play against the optimal computer player from inside the Firefox browser. The web page should access a server using JavaScript's XMLHttpRequest object, and display the results using DOM manipulation. Your GUI does not have to be complicated, but should be polished and look good.
Please submit your source code, configuration instructions, and any comments on your approach. Please also include a WAR file that we can test against Tomcat 5.5.x on Sun's J2SE 6.0. Finally, in your submission email, answer this question: if the human starts the game with 'n', and the computer plays according to the strategy above, what unique word will complete the human's victory?"

I thought it would be a fun challenge to solve using Clojure/Clojure Script, my languages of choice for building web apps.

Solving Ghost

Solving Ghost turns out to be quite simple. A trie is created containing all the words in the provided dictionary. Then a reverse post-order traverse is carried out classifying the positions into 4 states:

:completes-word if this prefix completes a word of over 4
:unable-to-move if this prefix cannot be extended to a
:winning it the next player to play can force a win
:losing if the next player to play cannot force a win

It is trivial to classify a position as :completes-word or :unable-to-move. A position is classified as :winning if there is at least one move that leads to a :losing position. Otherwise the position is classified as :losing.

Play when the computer is winning is straightforward; the computer randomly selects from all moves that leads to a :losing position. Play when the computer is losing is more complicated. The instructions state "choosing randomly among choices that force the maximal game length". However, the move that leads to the maximal game length depends on how the opponent plays. The opponent could choose to play randomly from their winning moves, but instead I have assumed that the opponent looks to complete the game as soon as possible. As part of the post-order traverse, the number of moves to the end of the game following this strategy is calculated for each position. This then enables the computer to select the 'best' losing move.

The Technical Stack

I have chosen to build a single page app in Clojurescript, React, Reagent, Reframe and Tailwind CSS with the back-end in Clojure. This meets the requirements for an AJAX app using XMLHttpRequest and DOM manipulation. The puzzle dates from around 2012 though and the technical requirements are to use Tomcat. Although my stack does allow the construction of a Tomcat compatible servlet, the modern way, especially for simple Clojure apps, is to eschew the use of a servlet container and instead use a simple embedded http server such as Jetty. I have adopted this approach.

I have build React/Reagent apps in the past, but not used Reframe which I was keen to try. Great though Reagent is, any sufficiently large Reagent apps degenerates in to a large tangle of callback functions. What is needed is a message passaging library to complement Reagent; Reframe provides this. Reframe has come in for some criticism from the Clojure community. Reframe is opinionated, a framework not a library, and to my mind takes a stricter functional approach that is more akin to Elm than Clojurescript. Nonetheless once I got over the steep learning curve, I found that Reframe worked well even for my small app.

It was also the first time I had used Tailwind CSS. In the past I have used Bootstrap and although a great framework, I did find its need to manage state grated with the stateless approach of React. But today the cool kids are using Tailwind CSS so I thought I would give if a try! It was a good experience fitting in well with the rest of the stack.

AWS

I used Elastic Beanstalk to deploy the app on AWS. It was the first time I had used it and I was impressed how it simplified AWS for a small application. Normally I would setup a load balancing group behind a load balancer and have at least 2 instances running at all times for robustness. However, as a simple demonstration application, I sought instead to optimise for cost rather than robustness and security. I instead setup a T3.nano instance in North Virginia, which was the cheapest instance I could find.

Final thoughts

The question asks if the human starts with 'n', what unique word completes the human's victory. However, I don't believe it is the case the human wins. It might be that I have misunderstood the rules or I might not have downloaded the correct dictionary for the challenge. My understanding is that if the human plays 'n', then the computer replies with 't'. The only word in the dictionary with the prefix "nt" is "nth" so the human plays 'h'. However, "nth" cannot be extended so the human loses. If, however, the computer is prevented from forcing the user to complete a 3 letter word that can't be extended, then the computer loses with the word "nyctalopia", which means night blindness.

The game as described is not at all fun for the human to play as the computer always wins! A more fun game would have difficultly levels which limit the computers vocabulary size, allow the computer to go first, have the computer randomly making mistakes and include bluffing and challenges. But the task was designed to demonstrate technical rather than build a fun game.

The source code is here