0

我正在尝试解决 Haskell 中 Euler 项目（此处）的“方形字谜词对”问题，但我被困住了......

问题如下（我缩短了它）：

  • 取一个词，说“CARE”和它的字谜之一，例如“RACE”。
  • 用唯一的数字替换“CARE”的每个字母，例如 C = 1、A = 2、R = 9 和 E = 6。它恰好是 1296，是一个平方数。
  • 按照相同的替换策略替换字谜的字母（“RACE”），它会生成 9216，它也是一个平方数！

给定一个单词列表，由这样一对单词组成的最大平方数是多少？

我设法从文件中提取了所有字谜对，并将它们放在 [(String,String)] 形式中，即 [("CARE","RACE")..]。

在下一步（映射 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 的一行代码。在您的示例中，您因此知道E必须是这六个数字之一，而不是任何数字。这将暴力破解答案的时间减少了 40%。

同样地，判断哪一对数字可以是平方数的最后两位数字也是 Haskell 的一行代码。您会注意到十位数的可能性取决于个位数：例如，如果最后一个数字被选为6，倒数第二个数字可能只有1 ，如果最后一个数字被选为倒数第二个数字可能只有4数字是1、4或9。

想想你的代码如何生成这个查找表。什么是合适的数据结构来存储它？您是否需要提前指定您的方格可能有多少位数，或者您可以利用懒惰来发挥您的优势吗？

于 2012-09-28T09:25:08.283 回答
0

尽管数学洞察力很有用（尤其是在项目 euler 上），但它并没有对我有太大帮助，因为我缺少一些关于“如何做”部分的知识。

无需过多介绍细节，一个解决方案就是将一个字谜词("CARE","RACE")转换成一对，例如(1234,4213). 直截了当的东西。如果在平方数对中检测到类似的模式，则存在匹配。

于 2012-10-15T09:26:17.503 回答