0

Haskell でプロジェクト Euler ( here )の「正方形のアナグラム単語ペア」の問題を解決しようとしていますが、行き詰まっています...

問題は次のとおりです（私はそれを短くしました）：

  • 「CARE」とそのアナグラムの 1 つ、たとえば「RACE」と言う 1 つの単語を取ります。
  • 「CARE」の各文字を一意の数字に置き換えます。たとえば、C = 1、A = 2、R = 9、E = 6 です。たまたま 1296 であり、平方数です。
  • 同じ置換ポリシーに従ってアナグラムの文字 (「RACE」) を置換すると、これも平方数である 9216 が生成されます。

単語のリストが与えられたとき、そのようなペアのメンバーによって形成される最大の平方数は何ですか?

ファイルからすべてのアナグラムのペアを抽出することができ、それらを [(String,String)] 形式、つまり [("CARE","RACE")..] にしました。

次のステップ (map anasquare) では、単語のペアごとに、[(9216,"CARE","RACE")..] のようになるように、生成できる最大の平方数をリンクします。

まあ、ブルート フォース アプローチを回避するためのトリック (あるに違いない!) がありますが、これまでのところ、私はそれを見つけられませんでした.すべての文字 -> 数字の変換。Haskellでそれを行う方法がわかりません。疲れているのかもしれませんが、これを前にしてはただの唖然としています。それを書くための簡潔でエレガントでありながらあまりにも曖昧ではない方法があるに違いありません.誰かがアイデアを持っていますか?

アナグラム検索とファイル解析機能は割愛します。

-- Read the file -> store the content into a list -> work on that list -> print the output
result98 = do contents <- readFile ".\\resources\\98.txt"
              putStrLn $ (process.words.format) contents

-- Find anagram pairs -> Find corresponding square number -> get the biggest one
process::[String]->String
process = toString . maximum . map anasquare . anagrams
    where toString (a,b,c) = "Yay ! the result is " ++ show a

-- Generate the maximum square number possible, 0 when none exist
anasquare::(String,String)->(Integer,String,String)
anasquare (x,y) = (anasquareValue,x,y)
    where anasquareValue = 0 -- TODO
4

2 に答える 2

2

数学的洞察は、

  1. 平方数の最後のn桁は、ルートの最後のn桁によって完全に決定されます。と
  2. n桁のすべてのシーケンスが平方数の最後のn桁として表示されるわけではありません。

Haskell の 1 行で、どの桁が平方数の最後の桁になり得るかを判断します (そのうち 6 桁あります)。したがって、あなたの例では、Eは任意の数字ではなく、これらの 6 桁のいずれかでなければならないことがわかります。これにより、回答をブルート フォースする時間が 40% 短縮されます。

同様に、どの数字のペアが平方数の最後の 2 桁になるかを判断するのも Haskell の 1 行です。10 桁の可能性は 1 桁に依存することに注意してください。たとえば、最後の桁が 6 として選択された場合、最後から 2 番目の桁は1のみである可能性があり、最後の桁が6として選択された場合、最後から2 番目の桁は4のみである可能性があります。数字は1、4、または9です。

コードでこのルックアップ テーブルを生成する方法を考えてみてください。それを格納するのに適切なデータ構造は何でしょうか? 正方形の長さが何桁になるかを事前に指定する必要がありますか、それとも遅延を有利に利用できますか?

于 2012-09-28T09:25:08.283 に答える
0

数学的洞察は役に立ちますが (特にプロジェクト euler では)、「ハウツー」部分に関する知識が不足していたため、あまり役に立ちませんでした。

詳細に入るまでもなく、1 つのソリューション パスは、アナグラムの単語("CARE","RACE")を(1234,4213). 簡単なもの。平方数のペアで同様のパターンが検出された場合、一致があります。

于 2012-10-15T09:26:17.503 に答える