Как найти список возможных слов из буквенной матрицы [Boggle Solver]

Question

В последнее время я играю в игру на своем iPhone под названием Scramble. Некоторые из вас могут знать эту игру как Boggle. По сути, когда игра начинается, вы получаете матрицу букв примерно так:

F X I E
A M L O
E W B X
A S T U

Цель игры - найти как можно больше слов, которые можно составить, объединяя буквы. Вы можете начать с любой буквы, и все буквы, которые ее окружают, являются честной игрой, а затем, как только вы перейдете к следующей букве, все буквы, которые окружают эту букву, являются честной игрой, , за исключением любых ранее использованных букв . Так, например, в приведенной выше таблице я мог бы найти слова LOB, TUX, SEA, FAME и т. Д. Слова должны содержать не менее 3 символов и не более NxN символов, что было бы 16 в этой игре, но может варьироваться в некоторых реализациях. Хотя эта игра веселая и затягивающая, я, видимо, не очень хорош в этом, и я хотел немного обмануть, создав программу, которая дала бы мне наилучшие возможные слова (чем длиннее слово, тем больше очков вы получите).

_{(источник: boggled.org )}

Я, к сожалению, не очень хорош с алгоритмами или их эффективностью и так далее. Моя первая попытка использует словарь , такой как этот (~ 2.3MB), и выполняет линейный поиск, пытаясь сопоставить комбинации со словарными статьями. Для поиска возможных слов требуется очень много времени, и, поскольку вы получаете только 2 минуты за раунд, этого просто недостаточно.

Мне интересно посмотреть, могут ли какие-либо Stackoverflowers предложить более эффективные решения. Я в основном ищу решения, использующие Big 3 Ps: Python, PHP и Perl, хотя что-нибудь с Java или C ++ тоже здорово, так как скорость важна.

ТЕКУЩИЕ РЕШЕНИЯ :

• Адам Розенфилд, Питон, ~ 20 с
• Джон Фухи, Python, ~ 3 с
• Кент Фредрик, Perl, ~ 1с
• Дариус Бэкон, Питон, ~ 1с
• rvarcher, VB.NET (прямая ссылка) , ~ 1 с
• Паоло Бергантино, PHP (прямая ссылка) , ~ 5 с (~ 2 с локально)

Answer 1

Я знаю, что я опоздал, но я сделал это недавно в PHP - просто для удовольствия ...

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu Найдено 75 слов (133 балла) за 0,90108 секунд

F.........X..I..............E............... A......................................M..............................L............................O............................... E....................W............................B..........................X A..................S..................................................T.................U....

Дает некоторое представление о том, что на самом деле делает программа - каждая буква - это место, где она начинает просматривать шаблоны, а каждая '.' показывает путь, который он пытался пройти. Чем больше '.' есть дальнейшие поиски.

Дайте мне знать, если вам нужен код ... это ужасное сочетание PHP и HTML, которое никогда не предназначалось для того, чтобы увидеть свет, поэтому я не смею публиковать его здесь:

Answer 2

Сначала прочитайте, как один из разработчиков языка C # решил связанную с этим проблему: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx.

Как и он, вы можете начать со словаря и канонизировать слова, создав словарь из массива букв, отсортированных по алфавиту, в список слов, которые можно записать по этим буквам.

Затем начните создавать возможные слова на доске и искать их. Я подозреваю, что это продвинет вас довольно далеко, но, безусловно, есть и другие приемы, которые могут ускорить процесс.

Answer 3

Ваш алгоритм поиска постоянно уменьшает список слов по мере продолжения поиска?

Например, в приведенном выше поиске есть только 13 букв, с которых ваши слова могут начинаться (эффективно уменьшая вдвое меньше начальных букв).

Если вы добавите больше буквенных перестановок, это приведет к дальнейшему уменьшению доступных наборов слов, уменьшая необходимый поиск.

Я бы начал там.

Answer 4

Ради интереса я реализовал один в bash. Это не супер быстро, но разумно.

http://dev.xkyle.com/bashboggle/

Answer 5

Мне бы пришлось больше задуматься над полным решением, но в качестве удобной оптимизации мне интересно, может быть, стоит предварительно рассчитать таблицу частот диграмм и триграмм (2- и 3-буквенные комбинации) на все слова из вашего словаря, и используйте это, чтобы расставить приоритеты вашего поиска. Я бы пошел с начальными буквами слов. Поэтому, если в вашем словаре содержатся слова «Индия», «Вода», «Экстрим» и «Необыкновенный», то ваша предварительно вычисленная таблица может выглядеть следующим образом:

'IN': 1
'WA': 1
'EX': 2

Затем найдите эти диграммы в порядке общности (сначала EX, затем WA / IN)

Answer 6

Я предлагаю сделать дерево букв на основе слов. Дерево будет состоять из буквенных структур, например:

letter: char
isWord: boolean

Затем вы строите дерево, с каждой глубиной добавляя новую букву. Другими словами, на первом уровне был бы алфавит; затем с каждого из этих деревьев будет еще 26 записей и так далее, пока вы не произнесете все слова. Держитесь за это проанализированное дерево, и оно сделает все возможные ответы быстрее для поиска.

С помощью этого проанализированного дерева вы можете очень быстро найти решения. Вот псевдокод:

BEGIN: 
    For each letter:
        if the struct representing it on the current depth has isWord == true, enter it as an answer.
        Cycle through all its neighbors; if there is a child of the current node corresponding to the letter, recursively call BEGIN on it.

Это может быть ускорено с помощью небольшого динамического программирования. Например, в вашем примере два «А» находятся рядом с «Е» и «W», которые (с точки, с которой они их ударили) будут идентичны. У меня нет достаточно времени, чтобы действительно написать код для этого, но я думаю, что вы можете собрать идею.

Кроме того, я уверен, что вы найдете другие решения, если вы используете Google для "Boggle solver".

Answer 7

Я понимаю, что время этого вопроса пришло и ушло, но так как я сам работал над решателем и наткнулся на него, пока гуглял, я подумал, что должен опубликовать ссылку на свою, так как она кажется немного отличающейся от некоторых др.

Я решил использовать плоский массив для игрового поля и делать рекурсивные поиски для каждой буквы на доске, переходя от действительного соседа к действительному соседу, расширяя поиск, если текущий список букв, если действительный префикс в индекс. При прохождении понятия текущего слова используется список индексов на доске, а не буквы, составляющие слово. При проверке индекса индексы переводятся в буквы и проверка завершается.

Индекс - это словарь грубой силы, который немного похож на три, но допускает Pythonic-запросы к индексу. Если в списке есть слова «кошка» и «кошка», вы получите в словаре следующее:

   d = { 'c': ['cat','cater'],
     'ca': ['cat','cater'],
     'cat': ['cat','cater'],
     'cate': ['cater'],
     'cater': ['cater'],
   }

Таким образом, если current_word равен 'ca', вы знаете, что это действительный префикс, потому что 'ca' in d возвращает True (поэтому продолжайте обход доски). И если current_word равен 'cat', то вы знаете, что это правильное слово, потому что оно является действительным префиксом и 'cat' in d['cat'] также возвращает True.

Если это так, допускается некоторый читаемый код, который не кажется слишком медленным. Как и все остальные, затраты в этой системе на чтение / построение индекса. Решение доски довольно много шума.

Код: http://gist.github.com/268079. Он намеренно вертикальный и наивный с множеством явных проверок достоверности, потому что я хотел понять проблему, не выдавая ее за кучу магии или неизвестности.

Answer 8

Я написал свой решатель на C ++. Я реализовал пользовательскую древовидную структуру. Я не уверен, что это можно считать трий, но это похоже. Каждый узел имеет 26 ветвей, по 1 на каждую букву алфавита. Я пересекаю ветви доски сообщений параллельно веткам моего словаря. Если ветка отсутствует в словаре, я прекращаю поиск на доске Boggle. Я конвертирую все буквы на доске в целые. Так что «A» = 0. Поскольку это просто массивы, поиск всегда равен O (1). Каждый узел хранит, завершает ли он слово и сколько слов существует в его дочерних элементах. Дерево сокращается, так как слова найдены, чтобы уменьшить повторный поиск одних и тех же слов. Я считаю, что обрезка также O (1).

Процессор: Pentium SU2700 1,3 ГГц
Оперативная память: 3 ГБ

Загружает словарь из 178 590 слов за <1 секунду. <br> Решает 100x100 Boggle (boggle.txt) за 4 секунды. Найдено ~ 44 000 слов.
Решение 4x4 Boggle слишком быстро, чтобы обеспечить значимый тест. :)

Fast Boggle Solver GitHub Repo

Answer 9

Веселое. Я чуть не опубликовал тот же вопрос несколько дней назад из-за той же чёртовой игры! Я не сделал, однако, потому что просто искал в Google для Boggle Solver Python и получил все ответы, которые я мог хотеть.

Answer 10

Для доски Boggle с N строками и M столбцами предположим следующее:

• N * M значительно больше количества возможных слов
• N * M значительно больше самого длинного слова

При этих предположениях сложность этого решения составляет O (N * M).

Я думаю, что сравнение времени работы этой одной примерной платы во многих отношениях упускает из виду, но для полноты картины это решение завершается за <0,2 с на моем современном MacBook Pro. </p>

Это решение найдет все возможные пути для каждого слова в корпусе.

#!/usr/bin/env ruby
# Example usage: ./boggle-solver --board "fxie amlo ewbx astu"

autoload :Matrix, 'matrix'
autoload :OptionParser, 'optparse'

DEFAULT_CORPUS_PATH = '/usr/share/dict/words'.freeze

# Functions

def filter_corpus(matrix, corpus, min_word_length)
  board_char_counts = Hash.new(0)
  matrix.each { |c| board_char_counts[c] += 1 }

  max_word_length = matrix.row_count * matrix.column_count
  boggleable_regex = /^[#{board_char_counts.keys.reduce(:+)}]{#{min_word_length},#{max_word_length}}$/
  corpus.select{ |w| w.match boggleable_regex }.select do |w|
    word_char_counts = Hash.new(0)
    w.each_char { |c| word_char_counts[c] += 1 }
    word_char_counts.all? { |c, count| board_char_counts[c] >= count }
  end
end

def neighbors(point, matrix)
  i, j = point
  ([i-1, 0].max .. [i+1, matrix.row_count-1].min).inject([]) do |r, new_i|
    ([j-1, 0].max .. [j+1, matrix.column_count-1].min).inject(r) do |r, new_j|
      neighbor = [new_i, new_j]
      neighbor.eql?(point) ? r : r << neighbor
    end
  end
end

def expand_path(path, word, matrix)
  return [path] if path.length == word.length

  next_char = word[path.length]
  viable_neighbors = neighbors(path[-1], matrix).select do |point|
    !path.include?(point) && matrix.element(*point).eql?(next_char)
  end

  viable_neighbors.inject([]) do |result, point|
    result + expand_path(path.dup << point, word, matrix)
  end
end

def find_paths(word, matrix)
  result = []
  matrix.each_with_index do |c, i, j|
    result += expand_path([[i, j]], word, matrix) if c.eql?(word[0])
  end
  result
end

def solve(matrix, corpus, min_word_length: 3)
  boggleable_corpus = filter_corpus(matrix, corpus, min_word_length)
  boggleable_corpus.inject({}) do |result, w|
    paths = find_paths(w, matrix)
    result[w] = paths unless paths.empty?
    result
  end
end

# Script

options = { corpus_path: DEFAULT_CORPUS_PATH }
option_parser = OptionParser.new do |opts|
  opts.banner = 'Usage: boggle-solver --board <value> [--corpus <value>]'

  opts.on('--board BOARD', String, 'The board (e.g. "fxi aml ewb ast")') do |b|
    options[:board] = b
  end

  opts.on('--corpus CORPUS_PATH', String, 'Corpus file path') do |c|
    options[:corpus_path] = c
  end

  opts.on_tail('-h', '--help', 'Shows usage') do
    STDOUT.puts opts
    exit
  end
end
option_parser.parse!

unless options[:board]
  STDERR.puts option_parser
  exit false
end

unless File.file? options[:corpus_path]
  STDERR.puts "No corpus exists - #{options[:corpus_path]}"
  exit false
end

rows = options[:board].downcase.scan(/\S+/).map{ |row| row.scan(/./) }

raw_corpus = File.readlines(options[:corpus_path])
corpus = raw_corpus.map{ |w| w.downcase.rstrip }.uniq.sort

solution = solve(Matrix.rows(rows), corpus)
solution.each_pair do |w, paths|
  STDOUT.puts w
  paths.each do |path|
    STDOUT.puts "\t" + path.map{ |point| point.inspect }.join(', ')
  end
end
STDOUT.puts "TOTAL: #{solution.count}"