I have been presented with the challenge of coming up with a solution to solve the following problem: Being given a start and an target word, I need to build a ladder of words starting from the start word, by changing one character between words until it reaches the target word based on a supplied word dictionary file.
To be able to solve the problem by writing down an algorithm, I must first try to solve the problem by myself. So I have taken a subset of words, paste them into Notepad++ and then tried to figure out a way to go from the start to the target word.
I immediately thought about using regular expressions to iterate over every found word's characters by replacing them with the any character pattern and then writing down every word found by that expression.
For example: having the word cast, perform the following:
- look for words in the dictionary with the pattern .ast, then c.st, then ca.t and then cas.
- Write down all the found words on every iteration
- Repeat the process for every word found and so on until the target word is found
There are 2 things we need to worry about. The first one is to avoid finding already found words so we need to ignore those as we go on. The second thing is to some how keep the connection between words so that when we find the target word we can navigate back to the start word.
- To perform the finding of the target word without knowing how many words we are going to find a long the way, we need to somehow iterate over a growing loop to avoid going into a recursive algorithm which might have slower performance. We need to iterate over the length of the array of words that are being found as we move forward.
- Next step is to iterate over the current word using regular expressions and look for every word in the dictionary except the ones that have already been found, matching the expression and finally iterate over every found word, add it to the found/ignored words. Do this until the or target word is found.
- To be able to go back to the start word, I have created a linked list structure called Word that contains the current word and a link to its parent, so that when I find the target word, I can easily navigate back to the start word.
- Coding standards are important and are present such as keeping coherence which makes code reading more easy to everybody, like for example using _variable-name for private variables, Pascal case for the name of the classes as well as using an IInterface-name for interfaces.
- Use of C# 8.0 such as initializing the using statement with a semi-comma in the end.
- I have also used a Nuget package just to help me handle the command line parameters (link available bellow).
- SOLID principles can be verified within the code and some are marked as regions with the it's abbreviation.
- TDD can also be verified in the separate project for tests.
To run the program using the command line, set the parameters like for example:
wordladder.exe -s:else -e:safe -d:"words-english.txt" -o:"c:\temp\outputfile.txt"
Or
dotnet run wordladder.csproj -s:else -e:safe -d:"words-english.txt" -o:"c:\temp\outputfile.txt"
- -s = Start word
- -e = End/Target word
- -d = Word dictionary file path
- -o = Output file name
Used Nuget packages:
- Command line helper: https://github.com/cajuncoding/CommandLineArgsHelper