{- 

  Euler #44 in Haskell

  """  
  Pentagonal numbers are generated by the formula, P(n)=n(3n−1)/2. 
  The first ten pentagonal numbers are:

  1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

  It can be seen that P(4) + P(7) = 22 + 70 = 92 = P(8). However, 
  their difference,  70 − 22 = 48, is not pentagonal.

  Find the pair of pentagonal numbers, P(j) and P(k), for which their sum 
  and difference is pentagonal and D = |P(k) − P(j)| is minimised; what 
  is the value of D?  
  """

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Haskell page: http://www.hakank.org/haskell/

-}


import Data.List
import qualified Data.Set as Set
-- import HakankUtils

pent :: Int -> Int
pent n = n*((3*n)-1) `div` 2

isPent x = if not $ null t then True else False
           where
              t =  [ n | n <- [1..floor $ sqrt(fromIntegral x)], pent n == x]
        
euler44a :: Int
euler44a = minimum [p2-p1 | p1 <- ps, p2 <- ps, p1 <= p2, elem (p2-p1) ps, elem (p1 + p2) ps]
           where
           ps = reverse $ map pent [1..2500]

-- Somewhat cheating
euler44b :: Int
euler44b = head [p2-p1 | p1 <- ps, p2 <- ps, p1 <= p2, elem (p2-p1) ps, elem (p1 + p2) ps]
           where
           ps = reverse $ map pent [1..2500]

-- Infinite list. Memory exhausted.
-- euler44c :: Int
-- euler44c = head [p2-p1 | p1 <- ps, p2 <- ps, p1 <= p2, elem (p2-p1) ps, elem (p1 + p2) ps]
--            where
--            ps = map pent [1..]


-- Using Data.Set
euler44d :: Int
euler44d = head [p2-p1 | p1 <- ps, p2 <- ps, p1 <= p2,  Set.member (p2-p1) pss, Set.member (p1 + p2) pss]
           where
           ps = map pent [1..2500]
           pss = Set.fromList ps

main :: IO ()
main = do
         -- print euler44a -- (55.89 secs, 651,759,096 bytes)

         -- print euler44b --(20.65 secs, 301,764,120 bytes)

         print euler44d -- (0.98 secs, 351,249,792 bytes)
