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

Post a Comment

Popular posts from this blog

Generative Molecular Design Isn't As Easy As People Make It Look

Image
I was taken aback by a recent CNBC article entitled “ Generative AI will be designing new drugs all on its own in the near future ”.  I should know better than to pay attention to AI articles in the popular press, but I feel that even scientists working in drug discovery may have a skewed perception of what generative AI can and can’t do.  To understand exactly what’s involved, it might be instructive to walk through a typical generative molecular design workflow and point out a few things.  First, these programs are far from autonomous.  Even when presented with a well-defined problem, generative algorithms produce a tremendous amount of nonsense.  Second, domain expertise is essential when sifting through the molecules produced by a generative algorithm.  Without a significant medicinal chemistry background, one can’t make sense of the results.  Third, while a few nuggets exist in the generative modeling output, a lot of work and good old-fashioned c...
Read more

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

Image
Here’s the first part of my review of some interesting machine learning (ML) papers I read in 2023.  As with the previous editions , this shouldn’t be considered a comprehensive review.  The papers covered here reflect my research interests and biases, and I’ve certainly overlooked areas that others consider vital.  This post is pretty long, so I've split it into three parts, with parts II and III to be posted in the next couple of weeks.    I. Docking, protein structure prediction, and benchmarking II. Large Language Models, active learning, federated learning, generative models, and explainable AI III. Review articles 2023 was a bit of a mixed bag for AI in drug discovery.  Several groups reported that the deep learning methods for protein-ligand docking weren’t quite what they were initially cracked up to be.  AlphaFold2 became pervasive, and people started to investigate, with mixed success, the utility of predicted protein structures.  There...
Read more

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

Image
Picking up where we left off in Part I , this post covers several other ML in drug discovery topics that interested me in 2023.  Some areas, like large language models, are new, and most of the work is at the proof-of-concept stage.  Others, like active learning, are more mature, and several groups are starting to explore nuances of the methods.   Here’s the structure of Part II.  4. Large Language Models 5. Active Learning 6. Federated Learning 7. Generative Models 8. Explainable AI 9. Other Stuff 4. Large Language Models The emergence of GPT-4 and ChatGPT brought considerable attention to large language models (LLMs) in 2023.  In November and December, several large pharmas held “AI Day” presentations featuring LLM applications for clinical trial data analysis. Many of these groups demonstrated the ability of LLMs to ingest large bodies of unstructured clinical data and subsequently generate tables and reports based on natural language queries.  Asid...
Read more