A program to solve WORDLE

WORDLE is a popular word (English vocabulary) and logical game. If you haven't given it a try yet, may be you should do now. It's quick, simple, interesting and beneficial.

Ever since I started playing it, I wanted to write a program to solve it and compare my personal performance against the program. I had an idea how to do that (from my earlier experience in writing a program to solve the similar but way more popular board game, Mastermind) but had to wait until I find a time and after that another long wait until I find a time to write about it. 

Anyway, here goes.... 

WORDLE game uses 5 letter meaningful English words. Some dictionaries give more than 150 000 such words. However, WORDLE use their answers from a selected list of 2309 words.

Once the system selects a random word, our task is to guess it in as fewer attempts as possible. For every attempt, the system will provide us more information by marking the letters in our attempted by green or yellow. Green if that letter is there in the chosen word in the exact place, yellow if the letter is present but in a different place. Following is an example, here we have taken 5 attempts to guess the word correctly.

So how to get a computer program to logically arrive at the correct word ? We have to feed it all permissible words first of course. Then we need an efficient algorithm in applying some deductive reasoning. Can you come up with an approximate quick solution for starters ? 

Think a bit, take few minutes may be...

....

....

Ok, here a clumsy but a working try. Starting by all 2309 words (problem space), we can :

1) select a word in random from the problem space and put that as an attempt

2) gather given information (green and yellow) on our attempt

3) Use that information to calculate which words within the problem space can be eliminated

4) Clear the problem space by removing words which can be eliminated by the step 3 above.

5) Go back to step 1 for the next attempt.

This will surely work, but no guarantee whether we arrive at the solution in the fastest manner possible, perhaps we can even exceed the given limit of 6 attempts. 

How to improve on this ? Take few more minutes/hours may be..

....

....

....

In the first solution, we chose a word by random. Obviously that's a place we can find some improvisation. Instead of randomly select a word, we can find the word which could give us maximum useful information. 

In the first solution, we managed to eliminate some words from the problem space using the information we got for our attempt. We can count the words which can be eliminated for a given input for a given attempt. 

Ex: in the image above we have the attempt 'ARISE' for which we have got the input of 3 yellows.Using the step 3 of the first solution, we can calculate how many words we can eliminate from the problem space for the input of 3 yellows. More importantly, we can calculate this for all other possible inputs as well! That is : number of words which can be eliminated if we get the input of 2 yellows, or if we get 1 green and 1 yellow etc. 

By the way, what are all possible inputs ? 5 greens of course is the end condition. 4 greens and 1 yellow is just not possible. We are left with following:

[4 green 0 yellow]

[3 greens 0 yellow], [3 greens 1 yellow], [3 greens 2 yellow].

[2 greens 0 yellow], [2 greens 1 yellow], [2 greens 2 yellow], [2 greens 3 yellow].

[1 green 0 yellow], [1 green 1 yellow], [1 green 2 yellow], [1 green 3 yellow], [1 green 4 yellow].

[0 green 0 yellow], [0 green 1 yellow], [0 green 2 yellow], [0 green 3 yellow], [0 green 4 yellow], [0 green 5 yellow].

That's it! 19 possible inputs in all.

For any given possible attempt we can find the number of words which can be eliminated for each of these inputs. Then we can find the worst case, which is the input which will result in eliminating the least number of words from the problem space. This worst case count can be used as a measure for a given attempt. 

Now we do the same for another word in the problem space. Find it's worst case, then do this for another word etc. We do this for all the words in the problem space. In the end we can find which word has the best worst case count. This word can be our next attempt.