C
C was the last language that I picked up in my first year in Imperial College London, during this time, I worked as part of a group in order to develop an emulator and assembler for ARMV8 processor.
Alongside this, we also developed an extension project, for this, we chose to create a text-based version of wordle alongside an algorithm to solve wordles with a high success rate.
Currently, the wordle algorithm that we are using has not failed us, meaning that it has solved all of its tested wordles in under 6 tries.
I am not able to host this code on github, so I shall explain it in further detail below.
What is wordle
Wordle is a game currently owned by the New York Times, the game revolved around the user guessing a 5 letter word, with 6 guesses per game.
For each guess, you are told the state of a letter, which can be one of 3 kinds:
Green - The letter is in the word and in the correct position
Yellow - The letter is in the word and in the incorrect position
Grey - The letter is not in the word at all
By using this information, the user is usually able to progress towards a solution, but this is not always the case. My group project was created in order to almost always guarantee a correct wordle, and to do so in as few attempts as possible.
By using this information, the user is usually able to progress towards a solution, but this is not always the case. My group project was created in order to almost always guarantee a correct wordle, and to do so in as few attempts as possible.
How does the wordle solver work
The wordle solver revolves around a trie data structure, this is a tree that contains may contain a child for each letter of the alphabet.
For my project, the existence of a child is solely dependant on whether it is a substring (starting at position 0) of a word that is found in the uk dictionary, this is done by reading a text file containing a vast number of 5-letter words.
The program will go through each word, traversing the trie and creating the node if needed, the lowest-level node will then have two flags set.
One of the flags will signal that node will generate a word, which is set to true only if that word exists in the trie.
The other flag will signal if that node will generate a word that can pass off as a solution.
For a word to pass off as a solution, a few conditions must be met:The word must not contain any of the currently existing gray letters
The word must contain green letters in their given positions
The word must not contain yellow letters in their given position
The user is asked to enter the word that they wish to enter into their game of wordle and then we ask them to enter an expression for each of the letters to tell us about its state. When we receive this information, we update the trie by deleting elements.For green letters, we traverse the trie recursively, deleting any node that has not got the green letter at a given level
For yellow letters, we traverse the trie again, but this time we delete any node that has got the yellow letter at those given positions
For grey letters, we delete all children that contain that letter
Then we traverse the trie in pre-order traversal to print of up to 10 possible solutions for the user to enter. This repeats until the user enters 'done' or if the user reaches their sixth attempt, to which the program will output all possible solutions.
For a word to pass off as a solution, a few conditions must be met:
The user is asked to enter the word that they wish to enter into their game of wordle and then we ask them to enter an expression for each of the letters to tell us about its state. When we receive this information, we update the trie by deleting elements.
Then we traverse the trie in pre-order traversal to print of up to 10 possible solutions for the user to enter. This repeats until the user enters 'done' or if the user reaches their sixth attempt, to which the program will output all possible solutions.
Criticisms of the project
I believe that the lack of a graphical user interface negatively impacts the user's experience, I believe that this is a consideration that needs to be taken in further group projects.
This improvement was not able to be implemented in our project due to time constraints.
I also believe that the algorithm could be further optimised with regards to the yellow letters, by only selecting words that contain those yellow letters (since this was not in the algorithm at the time of submission). Another potential optimisation would be to restrict the wordset to a given website (since there are multiple sites that have wordle games online). If a word set is available online, we could restrict the words in the trie, meaning that we would get the solution in fewer turns, this also improves the runtime of the algorithm as well as the size of the project since the trie will be smaller.
I also believe that the algorithm could be further optimised with regards to the yellow letters, by only selecting words that contain those yellow letters (since this was not in the algorithm at the time of submission). Another potential optimisation would be to restrict the wordset to a given website (since there are multiple sites that have wordle games online). If a word set is available online, we could restrict the words in the trie, meaning that we would get the solution in fewer turns, this also improves the runtime of the algorithm as well as the size of the project since the trie will be smaller.
