Cheating at Word Cookies with Python

Ok, so this isn't really a Cheminformatics post, but it's kind of about combinatorial optimization, which is the sort of thing we tend to do a lot of.  Lately, my family has been obsessed with an iOS game called "Word Cookies".  The game is simple (an example is shown below), given a set of 5 letters, you have to construct a set of 3, 4 and 5 letter words.  My wife and daughters are really good at this game, I'm not.  It's funny that the hard part, at least for me, is coming up with the shorter words.  


Anyway, being a data geek, I immediately thought about how I could write a Python script to solve this puzzle.  If you think about it, it's pretty easy to just brute force a solution.  
  • Generate all 3, 4 and 5 letter permutations
  • Check each permutation to see if it's a word 
Fortunately, there are lots of useful Python libraries and we can do this in just a few lines of code.  Let's take a look. 

First off, we want to generate permutations.   This can be done easily with the itertools library.   This library contains a wealth of functions for iterating over sequences in clever ways. 

Here's how we would generate all of the 5 letter combinations of the letters above. 

import itertools 

letters = "ATSIW"
for combo in itertools.permutations(letters,5):
    word = "".join(combo)
    print(word)

This will generate 120 permutations. However, the vast majority of these combinations won't be words.  

ATSIW
ATSWI
ATISW
ATIWS
ATWSI
ATWIS
etc ...

How can we check whether a permutation is a word?  Fortunately, there is a Python library for just this task.  The enchant library is designed for spell checking, but it works nicely for our purposes. We can just add a couple of lines to our script to check whether a permutation is a word.  

The enchant library has to be installed separately, but that's as easy as 
pip install pyenchant
Here's the new version of the script. 

# we need to declare an enchant dictionaryd = enchant.Dict("en_US")

letters = "ATSIW"
for combo in itertools.permutations(letters,5):
    word = "".join(combo)
    if d.check(word):
        print(word)

Now we just get 2 words as output

WAITS
WAIST

After that, we can put together the full script to check 3,4 and 5 letter words. 

import sys
import itertools
import enchant

d = enchant.Dict("en_US")

for letter_count in [3, 4, 5]:
    res = []
    for c in itertools.permutations(list(sys.argv[1]), letter_count):
        word = "".join(c)
        if d.check(word):
            res.append(word)
    res.sort()
    for row in res:
        print(row)

Running the above script with "ATSIW" as the first argument produces this output.  The words in bold below were accepted by Word Cookies.  As you can see, enchant is a bit more forgiving than Word Cookies, but the script does come up with all of the words. 

ATS
ISA
ITS
SAT
SAW
SIT
STA
TIA
TIS - counted as an "extra word" 
TWA
WAS
WAT
WIS - counted as an "extra word"
WIT
SWAT - counted as an "extra word"
TWAS 
WAIT
WAST - counted as an "extra word"
WATS - counted as an "extra word"
WIST - counted as an "extra word"
WITS
WAIST
WAITS

Anyway, that's it.  Just a few lines of Python to cheat at Word Cookies, kind of takes the fun out of it. 

















Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Comments

Popular posts from this blog

We Need Better Benchmarks for Machine Learning in Drug Discovery

AI in Drug Discovery 2023 - A Highly Opinionated Literature Review (Part I)

Getting Real with Molecular Property Prediction