A coworker told me about an interview question where you’re asked to develop a hangman solver. It seemed like a fun challenge so I spent the evening working on it. Here’s how it went.
Before I design my algorithm, I needed to create a game. Fortunately, Hangman is pretty straightforward to create. However, I had to make a couple of optimizations:
- Initially, the
Gameclass didn’t have its data in a format that the
Solverclass accepted so it passed the target word to the solver which seemed really, really wrong to do.
- Once I moved the logic into the
Gameclass, I realized that there was common logic between that and the display logic for the words which helped me DRY up my code.
Once I was done with that, I was ready to create the solver.
I took a greedy approach to the algorithm. At every guess, the algorithm looks at all the words in the dictionary that have the same length as the target word and counts how many words each letter occurs in then picks the letter that occurs in the most words. The idea is that, by optimizing each guess, I’m optimizing the entire word.
One optimization that I didn’t do is doing all the processing in the beginning and creating a data structure to store the processed word data in. Right now, word length and letter occurrences are recalculated for every word which is fine for a single game but terrible for testing which repeatedly runs games.
To test my solver, I created a
Tester class that ran the solver against every word in the dictionary and calculated the percentage of words that were guessed correctly. A word is considered to have been guessed correctly if the solver doesn’t make 6 wrong guesses since, in a traditional game of Hangman, unless your friend is being lenient on you and adds extra body parts, you only get 6: head, torso, 2 arms, and 2 legs.
The solver solver was ran against 45,402 words and managed to guess 86% of the words correctly which is better than me!
This was a fun exercise that allowed me to do some algorithms which I’d missed since, unfortunately, you rarely get to write algorithms on the job despite algorithms’ prevalence in interviews.
You can find the source code here: https://github.com/LeoJweda/hangman