Slovomaniya - guess the words. Part 1, Ruby

When I first saw Slovenia , I crush on it very tightly, spending endless hours guessing words. The essence of the game: there is a 4x4 grid, there is a letter in each cell. The task of the player - to make words, consistently connecting the letters together.
After a certain amount of time, an idea appeared: what if to automate the process of solving words? After all, often I myself am engaged in a simple enumeration of combinations in attempts to add a word. It is obvious that the computer will cope with this task much more productively than any person. Of course, with the exception of those cases when the word is immediately “visible” on the field, but this problem has already been solved by our brain, so it was decided to engage in the division of labor between the brain and the computer, so that everyone can do what is easier for him.

First, it was necessary to make a prototype in order to understand how the task of finding words on the field is achievable with the currently available computing power (MacBook Core 2 Duo 2.2Ghz Late 2007 with 4 GB of memory and a Linode 1024 server). Since recently I have been actively developing Ruby on Rails, it was decided to take Ruby as a test environment. Obviously, our task requires large computing power, and in the case of Ruby we have a large overhead on almost every operation, so for a combat situation it is necessary to use something else (for example C, but more on that later). However, it is impossible not to take into account the undoubted plus - this is the speed of development.

So let's go. Our program will work as follows:

1. Enumerate all possible letter layout options.
2. We compare the results with the dictionary
3. If the option is found in the dictionary - the word is guessed, you can show it to the player

First of all, it was necessary to organize a dictionary on which we will rely. After a brief search, several dictionaries were found in Yandex as plain text files (there is a separate word on each line). Dictionaries are uploaded to the SQLite database. Now you can proceed directly to writing the program. I will give only the most interesting moments, links to the full source code are given at the end of the article. Please note that the program was written in the style of “make the working version as soon as possible” and not “write as beautifully as possible using all the design patterns from the GoF book”.

The following algorithm of actions took shape in my head:

1. We become a cell with coordinates (x, y) (for the origin of the coordinates, I took the lower left corner). We remember the position of the current cell in a special list of coordinates (paths).
2. We go in turn in each direction (north, south, west, east, northeast, southeast, southwest and northwest) one cell.
3. For each path create a new list of coordinates
4. According to the lists of coordinates we form words
5. Check if there are words in the dictionary (if there is, then we show the player)
6. For each new position, go to step 2 until we reach a certain word length (that is, the length of the list of coordinates). The length is determined by two factors: the maximum possible word length in the game, or our computing power.
7. Go to the next cell and start all over again.

Thus, we recursively go around the entire field, going through all possible combinations. At the same time, one should not forget that each cell can be used in each word only once, therefore in paragraph (2) it is necessary to check whether this cell is in our list of coordinates. Also, do not forget to make sure that we have not gone beyond the playing field.
And one more test: we are looking for a word in the dictionary only if its length (i.e., the length of the path) is more than two, because according to the rules of the game a word can consist of at least 3 letters.
')
Here's what it looks like:

Game grid

@@w = [ "", "", "", "" ] 

Coordinate class

 class Coord attr_accessor :x, :y def initialize(x,y) self.x = x self.y = y end end 

Bypassing Neighboring Cells

 def lookup(coords, deep) print_word coords if deep >= 3 last = coords[-1] #up lookup_next coords, Coord.new(last.x + 1, last.y), deep #up-right lookup_next coords, Coord.new(last.x + 1, last.y + 1), deep #right lookup_next coords, Coord.new(last.x, last.y + 1), deep #right-down lookup_next coords, Coord.new(last.x + 1, last.y - 1), deep #down lookup_next coords, Coord.new(last.x, last.y - 1), deep #left-down lookup_next coords, Coord.new(last.x - 1, last.y - 1), deep #left lookup_next coords, Coord.new(last.x - 1, last.y), deep #left-up lookup_next coords, Coord.new(last.x - 1, last.y + 1), deep end def lookup_next(coords, new_coord, deep) return if deep > 6 return if new_coord.x < 0 or new_coord.y < 0 or new_coord.x > 3 or new_coord.y > 3 unless coords.find{|c|cx == new_coord.x and cy == new_coord.y} lookup coords.dup + [new_coord], deep + 1 end end 

Search a word in the dictionary and print it

 def print_word coords word = "" coords.each do |c| word += @@w[3 - cy].split('')[cx] end return if @@words.include?(word) @@db.execute( "select * from words where (word)=('#{word}')" ) do |row| return if @@words.include?(word) @@words << word puts word end end 

All found words are stored in the global variable @@ words to avoid displaying identical words.

Run the search

 0.upto(3) do |x| 0.upto(3) do |y| lookup [Coord.new(x, y)], 0 end end 

One of the drawbacks of this implementation is that the search starts from the lower left corner of the grid, and the program may not have enough time to bypass the entire field, so you can search for words from the opposite corner in a separate thread:

 Thread.new { 3.downto(0) do |x| 3.downto(0) do |y| lookup [Coord.new(x, y)], 0 end end } 

Even though we use relatively slow Ruby, our program is viable and finds words perfectly. In the next article I will look at the implementation on C with ncurses, distributed memory, semaphores and blackjack.

Source code
Vocabulary

Justice triumphed: now the one with the cooler computer wins!