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

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

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

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 9

      0
      > В следующей статье я рассмотрю реализацию на C с ncurses, распределенной памятью, семафорами и блекджеком.

      /usr/games/boggle что ли?
        +2
        А звонить никуда не надо?
          0
          Статья напомнила мне мой похожий проект на AppEngine + ExtJS. Я писал его под влиянием этих многочисленных телешоу, где нужно собрать слово из букв, приведенных на экране. Порылся в исходниках и нашел его. Нужно всего-лишь вписать буквы, из которых требуется составить слово, и AppEngine вернет все возможные варианты. Для моего словаря требуется примерно 10-15 секунд на поиск слов. Проект писался быстро, поэтому получился стандартный говнокод. Если немного оптимизировать, то получится сделать поиск быстрее.

          Попробовать можно тут: word-constructor.appspot.com/
            0
            Ваше приложение на любой запрос выдает «Ничего не найдено»
            0
            Наверное, тормозит в этом случае не руби, а доступ к базе. Не вижу причин не держать все слова в памяти.
              0
              Почему бы не организовать словарь в виде дерева из букв? Тогда по нему можно ходить параллельно с игровым полем и прекращать поиск в тот момент, когда нет возможных переходов по дереву.
              Работать будет знаааачительно быстрее.
                0
                Я думаю, что быстрее было бы пройтись по всем словам и проверить, подходит ли слово под сетку.
                • UFO just landed and posted this here
                    0
                    Почему бы не хранить входные данные в двумерном массиве?

                    Я тут запустил немного изменил Ваш код, запустил на таблице 100x100 и было сделано 205530 вызовов print_word — т.е. столько раз вызвался метод split. Программа работала порядка 15 минут.

                    Если хранить данные в двумерном массиве, то отрабатывает за 23 секунды.

                    Only users with full accounts can post comments. Log in, please.