Euler Problem 104

There are two solutions below. One is written by me and another from haskell wiki.

They look quite similar and I can not figure out why the wiki solution can solve problem but not mine. (Actually mine take more than 15 minutes)

• My Solution

│ main = print $ snd $ head $
│   │   │dropWhile (\ (x,y) -> (not . isLastNinePandigit "123456789") x)
│   │   │   │   │  (zip fibs [1..])
│   │   │   │   │
│ bothNinePandigit digits n =  isFirstNinePandigit digits n
│   │   │   │   │   │   │   │  && isLastNinePandigit digits n
│   │   │   │   │   │   │   │
│ isLastNinePandigit  digits = (== digits) . sort . lastDigits 9
│ isFirstNinePandigit digits = (== digits) . sort . firstDigits 9
│
│ firstDigits k n = take k (show n)
│ lastDigits  k n = show (n `mod` 10^k)

• Haskell Wiki solution¹

│
│ fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
│
│ isFibPan n =
│   let a = n `mod` 1000000000
│   │   b = sort (show a)
│   │   c = sort $ take 9 $ show n
│   in  b == "123456789" && c == "123456789"
│
│ ex_104 = snd $ head $
│   │   │  dropWhile (\(x,y) -> (not . isFibPan) x) (zip fibs [1..])

The key point here is should test start nine digits first or test end nine digits.

Two concerns here:

1. show function is (relatively) slow which used in test first 9 digits function.
2. quite few numbers are end in digits 1..9 in the first 329000 numbers

Therefore test last 9 digits first make great performance improvement.

Thanks Brent² explanation this sneaky thing very comprehensively in haskell-beginner.

What help to identify is the GHC profiling tool.

Several options used here are

• prof: for basic time and allocation profiling
• auto-all: auto insert cost centers on all top level functions. “cost center” is a location in the program like to collect statistics about and GHC will generate code to compute the cost of evalutating the expression at each location. e.g.

│   mean  s = {-# SCC "mean" #-} sum  s / fromIntegral (length s)

• caf-all: function with no parameters only computed once. CAF means constant applicative forms which used for calculate that once time evaluation.
• fforce-recomp: force full recompilation.

More details could go to chapter 25³ of [Real World Haskell] and GHC user guider chapter 5⁴.

│ # build with prof option on
│ ghc --make -O2 -prof -auto-all -rtsopts p104.hs
│
│ # then run
│ ./p104 +RTS -p -RTS

1. Chapter 25 in Real Work Haskell about profile