Project Euler 8

Going through Project Euler I am comparing my solutions to the ones here.

For question 8 my code produces the correct answer (confirmed via the check sum on the website) 23514624000.

module Main where

import Data.List

main = do
    print $ last (sort eulerEight)


eulerEight = doCalc [ x | x <- toDigits 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450]
    where
        doCalc (_:[]) = []
        doCalc (x:xs) = if 0 `notElem` take 13 (x:xs) && length (x:xs) > 12
                then product (take 13 (x:xs)) : doCalc xs
                else doCalc xs

toDigits n 
 | n < 1 = []
 | otherwise = toDigits (n `div` 10) ++ [n `mod` 10]

I realised this could be a lot better to so checked the solution here and it doesn't seem to be correct.

import Data.Char (digitToInt)
import Data.List

problem_8 = do
        str <- readFile "number.txt"
        -- This line just converts our str(ing) to a list of 1000 Ints
        let number = map digitToInt (concat $ lines str)
        print $ maximum $ map (product . take 13) (tails number)

I've changed the value of take 5 to take 13 as per the question on the Project Euler site, however the code above produces an incorrect answer of 2091059712. I've checked the number in number.txt is correct and that it has the full 1000 digits for both examples. Can anybody shed light on why the outputs are different? ( im thinking maybe to do with the fact it uses tails and not tail , but im not sure)

---

发生的事情是， digitToInt返回一个Int ，在32位系统上，当5增加到13时，它太短而无法保存测试数字。将其更改为(fromIntegral . digitToInt)并且它工作正常。

---

The problem was already identified as an Int overflow, but the wiki code itself is incorrect. It doesn't truncate the list properly, and might produce incorrect result, depending on input data (ie it produces the correct result here by a lucky chance).

Imagine a string of digits which ends in a 0 followed by 12 9 s. The code will take 9^12 into consideration incorrectly, when calculating the maximum value. Even simpler, for a 1000 zeroes it will produce 1 as an answer.

We can achieve an automagical truncation, due to the properties of zipping:

import Data.Char
import Data.List

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

Your code though is correct, but has some issues:

[x | x <- xs] [x | x <- xs] is just xs

last (sort xs) is just maximum xs , which is faster

appending on the right of a recursive call is a known source for inefficiency. it is better even to append on the left and reverse in the end, but the following transformation is more Haskellian:

toDigits n xs  -- to be called as `toDigits n []`
 | n < 1 = xs
 | otherwise = toDigits (n `div` 10) ((n `mod` 10) : xs)

链接地址: http://www.djcxy.com/p/80430.html

上一篇: 在内部，什么是存储在堆栈和堆？

下一篇: 欧拉项目8