PHP anagram puzzle solver

Question

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

Это анаграмма-решатель, который должен заполнить сетку 4x4 четырёхбуквенными анаграммами из 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... 
       } 
      } 
     } 
    } 
} 

Answer 1

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

• Preprocess ваш список 4-буквенных слов, так что вы их в качестве ключей (со значением 1 или что-то еще), а также каждый префикс. Поэтому, когда у вас есть ключ для «SWIM», у вас также будет один для «S», «SW» и «SWI». Это будет полезно быстро проверить, если после выбора нескольких символов есть ли возможность заполнить 4-буквенное слово.

• Предварительная обработка входной строки из 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 букв слова опубликованных here, он находит следующее решение менее чем за 0,2 секунды:

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

... результат зависит от списка слов, конечно.Мне нужно было посмотреть, что означает OWRE ;-)