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