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

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

Сперва необходимо было сделать прототип, чтобы понять, насколько задача поиска слов на поле выполнима с имеющимися на да данный момент вычислительными мощностями (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, распределенной памятью, семафорами и блекджеком.

Исходник
Словарь

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

Автор: iAlexey