Evil Hangman

March 15, 2020

Recently, I’ve been learning Kotlin while working on Android apps. While doing this, Kotlin’s heavy use of Lambda functions and comparator parameters began to remind me of functional programming languages like Haskell. Even though Kotlin is an imperative and object oriented language, I wanted to see just how far I could push its functional features by writing Evil Hangman.

The algorithm behind evil hangman is easy to understand. The computer starts with a dictionary of words and instead of picking a word for the player to guess, it picks a word family. A word family is a group of words that have certain letter positions in common. For example, if the player has only guessed the letter “e”, the words “more”, “care”, “have”, “love” and so on would all be in the same word family, because “e” is the fourth letter. Every time the player guesses a letter, the computer sorts all of the remaining words into word families that match the current correct guesses, then picks the family that has the most words. This is usually a family that doesn’t have the letter the player guessed, meaning most of the time they’ll be incorrect. Pure Evil.

The hard part of writing Evil Hangman is sorting the words into families efficiently. In haskell, this is pretty easy:

Put simply, the getPattern function takes a guessed letter, a word, and the current word family and returns the family the word belongs to. For example, if the guessed letter is “o”, the word is “more”, and the current word family is “_ _ _ e”, then the function returns “_ o _ e”. The wordFamilies function takes the guessed letter, the list of remaining words, and the current word family, and applies “insertWith (++)” to all words. Breaking it down a bit, “(++)” is the list concatenation operator which turns 2 values of the same type into a list of that type, and “insertWith” is a native function that accepts an operator, a key operation, and an insertion operation to create a Map. When used as shown above, we can create a list of lists of strings, where each inner list is a word family in a one line function.

Unfortunately, Kotlin doesn’t have an “insertWith” or a generic list concatenation operator, which meant I couldn’t use a similar one-liner. Instead of writing my own insertWith function, I took a more imperative approach and used a for loop:

Both of these functions accomplish the same things as their haskell counterparts. Instead of recursively checking each character, this getPattern uses kotlin’s native regex support to replace letters. The main difference is that it doesn’t incorporate the current pattern, but that doesn’t make too much of a difference since all remaining words fit into the word family of the current pattern. getWordFamily works in pretty much the same way as wordFamilies in haskell: get the family each word fits, then organize them into a map of lists of string, where the key is the pattern that corresponds to each list.

In this example, the functional features of kotlin didn’t help in finding the families, but helped elsewhere in the program. Instead of having to write a function to check each family in the map and return the largest one like you would in many other imperative languages, I was able to use kotlin’s “maxBy” function:
val largestFamily = families.keys.maxBy { families[it]!!.size }!!.

Similarly, “removeIf” also came in handy:
words.removeIf { it.length != wordLength }.
After this experiment, I think it’s safe to conclude that, for all intents and purposes, kotlin is another imperative language like Java or C(++), but with just enough functional features to be helpful.

Feel free to check out both my implementations: