Словомания — отгадываем слова. Часть 1, Ruby

Впервые увидев Словоманию ^[1], я запал на нее очень крепко, проводя бесконечные часы отгадывая слова. Суть игры: есть сетка 4х4, в каждой ячейке расположена буква. Задача игрока — составлять слова, последовательно соединяя буквы между собой.
После энного количества времени появилась идея: а что если автоматизировать процесс разгадывания слов? Ведь зачастую я и сам занимаюсь простым перебором комбинаций в попытках сложить слово. Очевидно, что компьютер справится с такой задачей гораздо продуктивнее любого человека. Конечно, за исключением тех случаев, когда слово сразу «видно» на поле, но эта задача уже решена нашим мозгом ^[2], так что было решено заняться разделением труда между мозгом ^[2] и компьютером, чтобы каждый занимался тем, что ему проще дается.

Сперва необходимо было сделать прототип, чтобы понять, насколько задача поиска слов на поле выполнима с имеющимися на да данный момент вычислительными мощностями (MacBook Core 2 Duo 2.2Ghz Late 2007 с 4 гб памяти и сервер Linode 1024). Поскольку в последнее время я активно занимаюсь разработкой на Ruby On Rails, то было принято решение взять Ruby в качестве тестовой среды. Очевидно, что наша задача требует больших вычислительных мощностей, а в случае с Ruby мы имеем большой оверхед почти на каждой операции, так что для боевой ситуации необходимо использовать нечто другое (например C, но об этом позже). Однако, нельзя не учитывать несомненный плюс — это скорость разработки.

Итак, поехали. Наша программа будет работать следующим образом:

1. Перебираем все возможные варианты компоновки букв
2. Сопоставляем результаты со словарем
3. Если вариант нашелся в словаре — слово угадано, можно показать его игроку

Первым делом необходимо было организовать словарь на который мы будем опираться. После недолгих поисков в Яндексе было найдено несколько словарей в виде обычных текстовых файлов (на каждой строчке отдельное слово). Словари выгружены в базу SQLite. Теперь можно приступать непосредственно к написанию программы. Я буду приводить лишь самые интересные моменты, ссылки на полный исходный код приведены в конце статьи. Прошу заметить, что программа писалась в стиле «сделать как можно быстрее рабочую версию», а не «написать как можно красивее, используя все паттерны проектирования из книги GoF».

В голове сложился следующий алгоритм действий:

1. Становимся на клетку с координатами (x,y) (за начало отсчета координат я взял левый нижний угол). Запоминаем позицию текущей клетки в специальном списке координат (пути).
2. Идем по очереди в каждую сторону (север, юг, запад, восток, северо-восток, юго-восток, юго-запад и северо-запад) на одну клетку.
3. Для каждого пути создаем новый список координат
4. По спискам координат формируем слова
5. Проверяем, есть ли слова в словаре (если есть, то показываем игроку)
6. Для каждой новой позиции переходим к пункту 2 до тех пор, пока не достингем определенной длины слова (т.е. длины списка координат). Длина определяется двумя факторами: максимально возможной длиной слова в игре, либо нашими вычислительными мощностями.
7. Переходим к следующей клетке и начинаем все с самого начала.

Таким образом мы рекурсивно обходим все поле, перебирая все возможные комбинации. При этом нужно не забывать, что каждая клетка может быть задействована в каждом слове только один раз, поэтому в пункте (2) необходимо проверить, нет ли в нашем списке координат этой клетки. Также не забываем удостовериться, что мы не ушли за пределы игрового поля.
И еще одна проверка: мы ищем слово в словаре только в том случае, если его длина (т.е. длина пути) больше двух, поскольку по правилам игры слово может состоять минимум из 3 букв.

Вот как это выглядит:

Игровая сетка

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

Класс координаты

class Coord
  attr_accessor :x, :y

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

Обход соседних клеток

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

Поиск слова в словаре и вывод его на печать

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

Все найденные слова хранятся в глобальной переменной @@words, чтобы избежать вывода на экран одинаковых слов.

Запускаем поиск

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

Одним из недостатков данной реализации является то, что поиск начинается с левого нижнего угла сетки, и возможно программе не хватит времени чтобы обойти все поле целиком, поэтому можно в отдельном потоке заняться поиском слов с противоположного угла:

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

Даже не смотря на то что мы используем относительно медленный Ruby, наша программа является жизнеспособной и отлично находит слова. В следующей статье я рассмотрю реализацию на C с ncurses, распределенной памятью, семафорами и блекджеком.

Исходник ^[3]
Словарь ^[4]

Справедливость восторжествовала: теперь победит тот, у кого круче компьютер!

Автор: iAlexey