PHP решатель анаграмм

Question

PHP решатель анаграмм

Я пытаюсь найти решение для решения головоломки PHP, над которым я работаю.

Это решатель анаграмм, который должен заполнить сетку 4×4 4-буквенными анаграммами из 16 букв в «Послании пловцу».

Горизонтальные строки и вертикальные столбцы должны составлять 4-буквенные анаграммы фразы. Ниже приведен желаемый результат, но моя программа должна решить его сама.

S M O G
W E R E
I T E M
M A S S

Мои попытки создать это истекают. Я пытаюсь что-то вроде этого:

foreach($word_array as $word){

$board = array();
$available = $default_array;
$row1 = $trie->run_word_check($word[0],$available);

if($row1){
echo "current row1 check: ". $row1."<br/>";
remove_from_available($row1,$available);
$board[] = $row1;
$col1 = $trie->run_word_check($row1[0],$available);

if($col1){
echo "current col1 check: ". $col1."<br/>";
remove_from_available($col1,$available);
$board[] = $col1;
$row2 = $trie->run_word_check($col1[0],$available);

if($row2){
echo "current row2 check: ". $row2."<br/>";
remove_from_available($row2,$available);
$board[] = $row2;
$col2 = $trie->run_word_check($row1[1].$row2[1],$available);

if($col2){
etc...
}
}
}
}
}

0

anagram php puzzle solver

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вот как вы можете это сделать:

Предварительно обработайте ваш список из четырехбуквенных слов, чтобы они были у вас в качестве ключей (со значением 1 или чем-то еще), а также каждый его префикс. Поэтому, когда у вас есть ключ для «SWIM», у вас также будет ключ для «S», «SW» и «SWI». Это будет полезно для быстрой проверки, если после выбора нескольких символов все еще есть возможность завершить четырехбуквенное слово.
Предварительно обработайте 16-буквенную строку ввода: сохраните отдельные буквы в качестве ключей со значением, равным количеству вхождений в этой строке. Таким образом, для «сообщения пловцу» ключ «S» будет иметь значение 3.
Поддерживать 4 горизонтальных слова и 4 вертикальных слова. Конечно, в этом есть некоторая избыточность (потому что вертикальные могут быть получены из горизонтальных), но это поможет обеспечить их быстрый доступ. Эти два массива из 4 слов будут начинаться со всех пустых строк.
Затем возьмите букву из этого второго массива (то есть доступные буквы с их количеством), чтобы использовать для позиции 0,0 в сетке, и сохраните ее как первое горизонтальное слово. а также как первое вертикальное слово. Проверьте, что есть 4-буквенные слова, которые начинаются с этого.
Если есть возможность использовать 4-буквенные слова, используйте рекурсию, чтобы взять следующую букву, чтобы поместить ее в 1,0 в сетке. Добавьте эту букву к первому горизонтальному слову (теперь оно имеет 2 символа) и поместите его во второе вертикальное слово (там будет только этот 1 символ). Сделайте проверку снова.
Повторяйте рекурсию до тех пор, пока не будут заполнены все элементы в сетке или не будет найдена буква, которая при добавлении ее к соответствующему горизонтальному и вертикальному слову дает что-то, что не может быть дополнено до соответствия 4-буквенным словам. В последнем случае вернитесь назад и попробуйте другие символы.

Выше приведено грубое описание. Вот код:

$solution = anagram("Message to swimmer", get_words());
print_r ($solution);

function index_words($word_array) {
$dict = [ '' => 1 ];
foreach ($word_array as $word) {
for ($len = 1; $len <= 4; $len++) {
$dict[substr($word, 0, $len)] = 1;
}
}
return $dict;
}

function letter_counts($available) {
$letters = [];
foreach(str_split(strtoupper($available)) as $letter) {
if (ctype_alpha($letter)) {
$letters[$letter] = isset($letters[$letter]) ? $letters[$letter]+1 : 1;
}
}
return $letters;
}

function anagram($available, $word_array) { // Main algorithm
$dict = index_words($word_array); //keys = all 4 letter words, and all their prefixes
$letters = letter_counts($available); // key = letter, value = occurrence count
$hori = ['','','','']; // store the words that are formed horizontally per row
$vert = ['','','','']; // store the words that are formed horizontally per column

$recurse = function ($row, $col)
use (&$recurse, &$letters, &$dict, &$hori, &$vert, &$limit) {
if ($row == 4) return true; // all done. backtrack out of recursion
$h = $hori[$row];
$v = $vert[$col];
foreach($letters as $letter => $count) { // for each available character
if (!$count) continue; // not available any more
$word1 = $h . $letter;
$word2 = $v . $letter;
if (isset($dict[$word1]) && isset($dict[$word2])) {
// It is still possible to form 4-letter words after placing this letter
$hori[$row] = $word1;
$vert[$col] = $word2;
$letters[$letter]--;
// use recursion to find characters for next slots in the grid
if ($recurse($row + ($col == 3 ? 1 : 0), ($col + 1) % 4)) return true;
// backtrack
$letters[$letter]++;
}
}
$hori[$row] = $h;
$vert[$col] = $v;
};
$recurse(0, 0); // start the recursive placement of letters in the grid
return $hori; // return the 4 words that were placed horizontally
}

function get_words() { // returns a comprehensive list of 4 letter words
return [
'AAHS', 'AALS', 'ABAC', 'ABAS', 'ABBA', 'ABBE', 'ABBS', 'ABED', 'ABET', 'ABID', 'ABLE',
/* etc... long list of 4-letter words ... */
'ZOOM', 'ZOON', 'ZOOS', 'ZOOT', 'ZORI', 'ZOUK', 'ZULU', 'ZUPA', 'ZURF', 'ZYGA', 'ZYME',
'ZZZS'];
}

Вы можете видеть, что это работает на eval.in.

С опубликованными 4 буквенными словами Вот, он находит следующее решение менее чем за 0,2 секунды:

M E G S
O W R E
M E A T
I S M S

… результат зависит от списка слов, конечно. Я должен был посмотреть, что значит OWRE 😉

1