PHP謎題解算器

我正試圖找到解決方案來解決我正在處理的PHP謎題求解器。PHP謎題解算器

這是一個謎題解算器，需要填寫一個4x4網格，其中包含16個字母的4個字母的「游泳者消息」。

水平行和垂直列需要製作完整的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... 
       } 
      } 
     } 
    } 
}

來源

2015-08-08 user1104135

而不是僅僅定義問題表明你的代碼到目前爲止，我們可以幫助它更好地工作 – Orangepill

好了，這就是看到的東西我真的不知道怎麼樣去解決這個難題。我創建了一個前綴樹來快速找到可能的單詞，但我似乎無法找到解決難題的方法。 – user1104135

你從哪裏得到'$ word_array'？ – trincot

這裏是你如何能做到這一點：

預處理你的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上運行。

隨着出版here 4個字母的單詞，它發現在不到0.2秒以下解決方案：

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

......結果當然取決於的話就行了。我不得不尋找什麼OWRE意味着;-)

來源

2017-01-21 21:41:50 trincot

PHP謎題解算器

回答

相關問題