项目欧拉8 - 我不明白

Question

我在Haskell中寻找第8个Euler问题的解决方案,但我不太明白.

import Data.List
import Data.Char

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails . map (fromIntegral . digitToInt)
         . concat . lines $ str

这是解决方案的链接,您可以在此处找到该任务.

任何人都可以逐一解释我的解决方案吗？

Answer 1

读数据

readFile读取文件"number.txt".如果我们在一个名为的文件中放一个小的16位数字number.txt

7316
9698
8586
1254

乳宁

euler_8 = do
   str <- readFile "number.txt"
   print $ str

结果是

"7316\n9698\n8586\n1254"

该字符串中包含额外的换行符.要删除它们,作者将字符串拆分为lines.

euler_8 = do
   str <- readFile "number.txt"
   print . lines $ str

结果不再包含任何'\n'字符,而是字符串列表.

["7316","9698","8586","1254"]

要将其转换为单个字符串,字符串将concat一起使用.

euler_8 = do
   str <- readFile "number.txt"
   print . concat . lines $ str

连接字符串是字符列表而不是数字列表

"7316969885861254"

每个字符被转换成Int通过digitToInt然后被转换为Integer通过fromInteger.在使用全尺寸的32位硬件上Integer很重要,因为13位数的乘积可能大于2^31-1.此转换适用map于列表中的每个项目.

euler_8 = do
   str <- readFile "number.txt"
   print . map (fromIntegral . digitToInt)
         . concat . lines $ str

结果列表中充满了Integers.

[7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4]

亚

作者的下一个目标是在这个整数列表中找到所有13位数的运行.tails返回列表的所有子列表,从任何位置开始并运行到列表的末尾.

euler_8 = do
   str <- readFile "number.txt"
   print . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

这导致我们的16位数示例列出了17个列表.(我添加了格式)

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
    [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
      [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
        [6,9,6,9,8,8,5,8,6,1,2,5,4],
          [9,6,9,8,8,5,8,6,1,2,5,4],
            [6,9,8,8,5,8,6,1,2,5,4],
              [9,8,8,5,8,6,1,2,5,4],
                [8,8,5,8,6,1,2,5,4],
                  [8,5,8,6,1,2,5,4],
                    [5,8,6,1,2,5,4],
                      [8,6,1,2,5,4],
                        [6,1,2,5,4],
                          [1,2,5,4],
                            [2,5,4],
                              [5,4],
                                [4],
                                 []
]

作者将在我们重新安排这些列表的过程中提取一个技巧来读取13位长的子列表.如果我们查看左对齐而不是右对齐的这些列表,我们可以看到每列中运行的子序列.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4],
  [2,5,4],
  [5,4],
  [4],
  []
]

我们只希望这些列长13位,所以我们只想要take第一13行.

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4]
]

foldr (zipWith (:)) (repeat [])转置列表列表(解释它可能属于另一个问题).它会丢弃比最短行长的行的部分.

euler_8 = do
   str <- readFile "number.txt"
   print . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

我们现在像往常一样阅读列表中的子序列

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1],
  [3,1,6,9,6,9,8,8,5,8,6,1,2],
  [1,6,9,6,9,8,8,5,8,6,1,2,5],
  [6,9,6,9,8,8,5,8,6,1,2,5,4]
]

问题

我们product通过mapping product它们来找到每个子序列.

euler_8 = do
   str <- readFile "number.txt"
   print . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

这会将列表减少为单个数字

[940584960,268738560,447897600,1791590400]

我们必须从中找到maximum.

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

答案是

1791590400