Skip to content

Instantly share code, notes, and snippets.

@fizbin
Created July 8, 2015 19:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fizbin/6f498ea97038b29e7abf to your computer and use it in GitHub Desktop.
Save fizbin/6f498ea97038b29e7abf to your computer and use it in GitHub Desktop.
-- SPOILER for project euler #14
-- Really, you should go do it yourself.
import Data.List
import Data.Function
import Numeric
import Data.Char (intToDigit)
data Tree = Tree {value :: Int,
branch0 :: Tree,
branch1 :: Tree}
collatzLength :: Int -> Int
collatzLength = collatzLength' where
collatzLength' 1 = 1
collatzLength' n | n `mod` 2 == 0 = 1 + lookupInCAF (n `div` 2)
collatzLength' n = 1 + lookupInCAF (3*n + 1)
lookupInCAF n =
lookupBinary (tail $ showIntAtBase 2 intToDigit n "") collatzCAF'
lookupBinary "" t = value t
lookupBinary ('0':x) t = lookupBinary x (branch0 t)
lookupBinary ('1':x) t = lookupBinary x (branch1 t)
lookupBinary _ _ = error "Not just 0 and 1"
collatzCAF' = mkTree 1
mkTree n = Tree (collatzLength' n) (mkTree (2*n)) (mkTree (1 + 2*n))
main :: IO ()
main = do
let collatzMax = maximumBy (compare `on` collatzLength) [1..999999]
print collatzMax
print $ collatzLength collatzMax
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment