Words Finder

This page is about the www.wordsfinder.co.uk website. I am still editing this page if you are looking to solve your 4 pics 1 word puzzle check the wordsfinder webpage.

About this Project

          Everything started with CS50 and “This is CS50”. CS50 is a Computer Science course taught in recent years by David J. Malan at Harvard University. I “took” the Fall 2011 edition of CS50 during fall-winter of 2012. But this days there is a CS50x Course available for which you can register and follow along. To register check out the CS50x website.

          I have to admit that it’s been a pleasure to watch all the material (lectures, sections, walkthroughs). Watching the lectures is like having fun,  everything seams so easy and so achievable. Of course the fun, kind of disappears when you read through the psets :). Unfortunately, at least in my case there is no achievement without hard work and this meant that I had to do the psets as well. But slowly, with help from sections, walktrhoughs and some effort you dig through the problem set, and  by the end of each pset the fun part returns, as you are testing your work.4Pics1Word

          But “long story short” I knew that in order to  get the most out of this course, I had to do a sort of final project.  I was wandering for a while what project should I do. When one day  my good lady comes home with a new app on her phone. It was the 4 Pics one Word app. These days there are several variants of this app out there but the one she had at that time was from LOTUM GmbH. In this game each puzzle contains 4 pictures and the goal is to find a word common to all 4 pictures.  There are 12 letters provided to chose from, and the length of the required word is known. 4p1wOverkill

           As you can imagine not before long I was involved as well, initially it was fun, as we were able to figure out the words, but we got stuck at one at the right. So after a while I realized that I should be able to solve this puzzle by using my new CS50 programming skills. I had everything, the dictionary from pset 6, the javascript examples and google, but to be honest I didn’t quite knew how to put the things together. Anyway the good thing was that now I had an idea for my “final project”.

           The attempt was to design a sort of program with the following requirements:

  1. To take as input a string of characters and a required word length.
  2. To produce as output all dictionary words of the required length that can be maid up with characters from the provided string of characters.
  3. To run in a reasonably amount of time.
  4. To run preferably on a mobile device as well.

           I decided that the best approach would be to use a web page based design and to  implement the word puzzle solver in JavaScript. The main advantage of this approach is that the solver is accessible by anybody from anywhere. You wold only need a device whit a web browser and access to internet. One of the disadvantage of this implementation is the processing speed as the solver is executed by the browser.

           I started by putting together the index page with two inputs, one for the string of letters and one for the required word length. I also had an output area for the dictionary words.  Now I “just” needed a script which would take the two inputs and would find the words.

           I started with a very simple algorithm (and very inefficient algorithm as it turned out later but this was what I knew how to do at that time). I took the the input string of characters (always 12 for this game) and made all possible x letter combinations. Where x was the required word length. For example in the above puzzle there are 12 characters for the input string namely “icmleklvcorg” and the required word length is 8. After I had all combinations for each combination I computed each possible permutation. In this way I ended up with any possible arrangement of x letter long strings out of the provided characters. Now, I had every possible x letter long string. The only thing left to do was to take each string and check if whatever is or isn’t in the dictionary. If a string was matched with a string in the dictionary it meant that it is a word. Of course each bit of this algorithm was a challenge to implement and connect together. I took some parts of the algorithm form forums as for example the part to do the recursive combinations and the part to do the permutations.

          After I connected everything together it was “working” at list on my set of test inputs. For example with the character string of “word” and with the required word length of 3 was producing the expected result: dor, dow, rod, row. But when I tried the input for the puzzle that we got stuck on “icmleklvcorg” with a word length of 8 my PC seamed to freeze when I had a closer look with the task manager I noticed that processor resources are allocated to the browser which was running my script. I said myself it will take slightly longer so I took a brake and I vent to get a drink. But  15 minutes later nothing changed. So I sat down and did the math to try to understand why is it tacking so long. I compared the two examples in the firs case the string “word” (4 characters) with a required word length of 3 there are 4 combinations and for each combination there are 6 permutations. In total 24 strings to be checked if exist or not in the dictionary. Now for the second case the string “icmleklvcorg” (12 characters) with a required word length of 8 there are 495 combinations and for each there are 40320 permutations. In total 19.958.400 to be checked in the dictionary. This meant that there were 831.600 times more dictionary searches to do than before. I didn’t knew how to use firebug to check the speed of my script at that time and it was already very late in the night so I decided to let the PC on overnight and check again in the morning. I was astonished to see that 6-7 hours later it still working on the problem. I said myself gee this must be really slow. Anyway I had to go to work so I left the PC running for another 8 hours. When I returned home first thing I checked my solver and finally there were two words displayed on my screen “overkill” and “microgel”. Overkill was the answer for our puzzle.

        I set some breakepoints throughout my code and I figured out that the search part took the longest to run. Although the dictionary was already sorted I initially implemented a linear search algorithm. It is obvious now that to linearly search through 140k words 19.958k times it is a time consuming operation. I initially improved my code by implementing a quadratic search it was nice to see how now my code was able to solve the same problem not in 6-14 hours but in aprox 30 min (if I remember well). It was a huge improvement and now I could fill the difference between the two searching algorithms. I was happy. Than one day I realized that I don’t even need to compute the permutations if I “sort” the dictionary even better (if the letters of every word would be sorted). This was a huge improvement because now there were only 495 strings that had to be checked if they existed or not in the dictionary. This substantially cut the running time. This wasn’t really true for any input. For example a large input string with a small  requested word length resulted in a large number of combinations. But with time I got better and better, I even figured out that there is no need to compute the combinations at all.

          In my opinion the current algorithm implemented on the Schlezinger’s Words Finder webpage is very fast. For example for the “icmleklvcorg” input string with a required word length of 8 it takes around 23 ms (except for the first 8 letter word length run; timed with firebug on my PC) to find the two words microgel and overkill. Or for a large input string like “aabbcdeefghiijklmnopqrstuvwxyz” (30 characters) with a requested word length of 8 all the 7711 dictionary words are found in around 200 ms. If the input string is keep the same and the required word length is changed to 3 than all the 1136 dictionary words are found in around 20 ms. All time measurements were taken with firebug (in firefox) on my PC. You are welcome test the Words Finder performances on your device, but please note that the first run with a new required word length will take longer, this is because the all the words with the specified word length have to be imported form the dictionary. This is done only once when an unused word length is required. I implemented it this way to cut the web page loading time. With this running times I had no dough that this application will run smoothly on any mobile device as well.

           This is the sort version of the story behind the Words Finder webpage and bellow are some print screens. 

WFiPhonePSLoading WFiPhonePSsdrow

          As you can notice in the left side printscreen the webpage will download a 1.4MB file on your device. This my be an issue for users with low data allowance or with a slow internet connection.

          On the other hand once the page is loaded there is no internet connection required at all. This my be attractive for users without permanent connection to the internet or on the move.

         The http://www.wordsfnder.co.uk webpage may be down form time to time or my not load as fast as you would like this may be because the Words Finder webpage is currently hosted with a free host () is curently hosted with a free webhost http://www.zymic.com/

I’m still working on this page. Tanks for the visit.

%d bloggers like this: