Slovomaniya - guess the words. Part 1, Ruby

The first time I saw Slovenia , I sunk into it very tightly, spending endless hours guessing words. The essence of the game: there is a 4x4 grid, a letter is located in each cell. The player’s task is to make up words by connecting letters together.
After an nth amount of time, an idea came up: what if we automate the process of solving words? After all, often I myself do simple enumeration of combinations in attempts to add a word. Obviously, a computer will cope with such a task much more productively than any person. Of course, with the exception of cases where the word is immediately “visible” on the field, but this problem has already been solved by our brain, so it was decided to do the division of labor between the brain and the computer, so that everyone does what is easier for him to do.

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

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

1. We sort through all the possible layout options for letters
2. Match the results with the dictionary
3. If the option was found in the dictionary - the word is guessed, you can show it to the player

The first step was to organize a dictionary on which we will rely. After a brief search in Yandex, several dictionaries were found in the form of ordinary text files (each line has a separate word). Dictionaries are uploaded to the SQLite database. Now you can proceed directly to writing the program. I will give only the most interesting points, 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 “making the working version as fast as possible”, and not “writing as beautifully as possible using all the design patterns from the GoF book”.

The following algorithm of actions developed in my head:

1. We get to the cell with the coordinates (x, y) (I took the bottom left corner for the origin). We remember the position of the current cell in a special list of coordinates (paths).
2. We take turns in each direction (north, south, west, east, northeast, southeast, southwest and northwest) one cell.
3. For each path we create a new list of coordinates
4. Using lists of coordinates we form words
5. Check if there are words in the dictionary (if any, then show the player)
6. For each new position, go to step 2 until we reach a certain word length (i.e. the length of the coordinate list). The length is determined by two factors: the maximum possible word length in the game, or our computing power.
7. We move on to the next cell and start from the very beginning.

Thus, we recursively go around the entire field, sorting through all possible combinations. At the same time, one must not forget that each cell can be involved 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 check: we look for a word in the dictionary only if its length (i.e. path length) 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 net

@@w = 
[
    "нцбь",
    "алыи",
    "етьн",
    "прет"
]

Coordinate class

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

Neighboring Bypass

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

Search for a word in a dictionary and print it

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

All found words are stored in the global variable @@ words to avoid displaying the same words on the screen.

We start 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 maybe the program does not have enough time to go around the entire field, so you can start searching for words from the opposite corner in a separate stream:

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 discuss a C implementation with ncurses, distributed memory, semaphores, and blackjack.

Source
Dictionary

Justice has triumphed: now the one with the coolest computer will win!