Wordz — guess words. Part 1, Ruby

First saw Slowmanow, I had fallen for her very hard, spending endless hours guessing the word. The essence of the game: there's a 4x4 grid, each cell is a letter. The player's task — to make words, sequentially connecting the letters together.
After a certain amount of time had an idea: what if we automate the process of solving a word? Quite often I do a simple enumeration of combinations in an attempt to form a word. It is obvious that the computer will handle this task much more productive than any human. Of course, with the exception of those cases when the word is immediately "visible" on the field, but this task is already solved by our brain, so it was decided to deal with the division of labor between brain and computer, everyone to do with the fact that he is easier given.

First, it was necessary to make a prototype, to understand how the task of searching for the feasible with the available on the moment computing capacities (MacBook Core 2 Duo 2.2 Ghz Late 2007 with 4 GB of memory and the server is a Linode 1024). Since the last time I actively develop on Ruby on Rails, it was decided to take Ruby as a test environment. It is obvious that our task requires a high computing capacity, and in the case of Ruby we have a lot of overhead for almost every operation, so that a combat situation you need to use something else (like C, but more on that later). However, it is impossible not to take into account a definite plus is the speed of development.

So there you go. Our program will work as follows:

the
1. Iterate through all possible variants of layout of letters
the
2. compare the results with the dictionary
the
3. If the variant is found in the dictionary — the word is guessed, you can show it to the player

The first thing we had to organize the dictionary on which we rely. After a brief search in Yandex were found several dictionaries in plain text files (each line a single word). Dictionaries are uploaded into the database SQLite. You can now start writing the program. I will give only the most interesting moments, links to the full source code given at the end of the article. Please note that the program is written in the style of "do as quickly as possible a working version" and not "write as beautiful as you can, using all the design patterns from the GoF book".

The head has developed the following algorithm:

the
1. Be on the cell with coordinates (x,y) (the origin of coordinates, I took the lower left corner). Remember the position of the current cell in the list of coordinates (path).
the
2. Go through the queue in each direction (North, South, West, East, North-East, South-East, South-West and North-West) for one cell.
the
3. For each path, create a new list of coordinates
the
4. lists of coordinates generated by word
the
5. Check whether there are words in the dictionary (if there is, show the player)
the
6. For each new position go to step 2 as long as distinguem a certain word length (i.e. the length of the list of coordinates). Length is determined by two factors: the maximum possible length of the word in the game, or any of our computing facilities.
the
7. Go to the next cell and start all over from the beginning.

Thus, we recursively go around the whole field, going through all possible combinations. It should not be forgotten that each cell can be used in each word only once, so in paragraph (2), you need to check whether our list of the coordinates of that cell. Also, do not forget to make sure that we go beyond the playing field.
And another test: we are looking for a word in the dictionary only if its length (i.e. path length) of more than two, because the rules of the game the word can be composed of a minimum of 3 letters.

Here's how it looks:

the grid

the

@@w = 
[
"NCBI",
"alyi",
"etin",
"rushing"
]

the Class of coordinates

the

class Coord
attr_accessor :x, :y

def initialize(x,y)
self.x = x
self.y = y
end
end

Bypass neighboring cells

the

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)
deep return if > 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|c.x == new_coord.x and c.y == new_coord.y}
lookup the coords.dup + [new_coord], deep + 1
end
end

Search for words in the dictionary and print the

the

def print_word coords
word = ""
coords.each do |c|
word += @@w[3 - c.y].split(")[c.x]
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

Found words are stored in the global variable @@words to avoid displaying the same words.

Launch search

the

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 maybe the program won't have enough time to get around the entire field, so you can in a separate thread to search for words with the opposite corner:

the

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

Even despite the fact that we use relatively slow Ruby, our program is viable and perfectly finds the words. In the next article I will consider implementation in C with ncurses, distributed memory, semaphores, and blackjack.

Source
Dictionary

Justice is done: now the winner is the one who abruptly computer!

Article based on information from habrahabr.ru