Happy Numbers

README.md

Implementations of Happy Numbers

Haskell

Simple recursive version that stores the previous steps in the sequence in an array, and checks for duplicates to detect cycles.

Can get up to 250,000,000 numbers in ~5s, with no memoisation:

$ time ./happy_numbers 350000000
"Cycle at 89"

real	0m5.752s
user	0m5.506s
sys	0m0.171s

I tricked Haskell into evaluating the map by asking for the last element. Seems pretty linear:

$ time ./happy_numbers 1
user	0m0.001s

$ time ./happy_numbers 10
user	0m0.002s

$ time ./happy_numbers 100
user	0m0.002s

$ time ./happy_numbers 1000
user	0m0.001s

$ time ./happy_numbers 10000
user	0m0.002s

$ time ./happy_numbers 100000
user	0m0.003s

$ time ./happy_numbers 1000000
user	0m0.020s

$ time ./happy_numbers 10000000
user	0m0.171s

$ time ./happy_numbers 100000000
user	0m1.550s

$ time ./happy_numbers 1000000000
user	0m14.969s

Ruby

Er, right. Less code, less performance ;) Detect cycles with a Hash of value to _ (ie. whatever). Performance was basically the same using Set.

Can get up to ~100,000 in ~5s with no memoisation, with simple memoisation in a hash can get around 250,000.

With memoisation, Falls over badly I assume for GC reasons at 1,000,000 elements, or perhaps it's just demonstrating that the runtime complexity is exponential!

$ time ruby happy_numbers.rb 1
user	0m0.012s

$ time ruby happy_numbers.rb 10
user	0m0.011s

$ time ruby happy_numbers.rb 100
user	0m0.014s

$ time ruby happy_numbers.rb 1000
user	0m0.017s

$ time ruby happy_numbers.rb 10000
user	0m0.091s

$ time ruby happy_numbers.rb 100000
user	0m1.243s

$ time ruby happy_numbers.rb 1000000
user	0m47.519s

Update

Golfed the Ruby version a bit, prompted by a comment on the original blog post

I’d be really interested if anyone can avoid conditionals.

happy_golf.rb

def step x
  x.to_s.split("").map { |y| y.to_i ** 2 }.inject(:+)
end

def happy x, map = { 1 => :happy }
  map[x] ||= :cycle
  y = step x
  map[y] || happy(y, map)
end

count = ARGV.first.to_i

count.times { |x| happy(x + 1) }

happy_numbers.hs

import System.Environment
import Data.Char

digits :: Int -> [Int]
digits = (map digitToInt) . show

sq :: Int -> Int
sq = flip (^) $ 2

sqDigits x = map sq $ digits x

step x = foldl (+) 0 $ sqDigits x

happy :: [Int] -> Int -> (String, Int)
happy _ 1 = "happy"
happy xs x
  | x `elem` xs = "Cycle at " ++ show x
  | otherwise = happy (x:xs) (step x) 

main :: IO ()
main = do arg <- getArgs
          let count = read $ arg !! 0
           in print $ last (map (happy []) [1..count])
               

happy_numbers.rb

def step x
  x.to_s.split("").map { |y| y.to_i ** 2 }.inject(:+)
end

def happy x, map = {}
  if x == 1
    "happy"
  elsif map.key?(x)
    "cycle at #{x}"
  else
    map[x] = true
    happy step(x), map
  end
end

count = ARGV.first.to_i
memoize = !!ARGV[1]
map = {}

# For no memoisation, don't pass map to #happy here.
count.times { |x| happy x + 1, map }