Programming Praxis – Happy Numbers

Today’s Programming Praxis problem is a pretty simple one, but it comes with a time limit. We have 15 minutes to write a function that finds all the happy numbers up to a given limit. The version below took me around 4 minutes. Let’s go into the explanation.

While we could write the function directly, we’ll split it up in two: one to determine if a single number is happy and one to get all the required happy numbers. We model the happy number algorithm with basic recursion. We keep a list of all previously “visited” numbers to detect loops.

isHappy :: (Read a, Integral a) => a -> Bool
isHappy = f [] where
    f _  1 = True
    f xs n = notElem n xs && f (n:xs) (sum . map (^ 2) $ digits n)
    digits = map (read . return) . show

Once we know if a single number is happy, determining all of them is just a simple matter of filtering all the numbers less than the limit.

happyUpto :: (Read a, Integral a) => a -> [a]
happyUpto n = filter isHappy [1..n - 1]

All that's left is actually running the algorithm.

main :: IO ()
main = print $ happyUpto 50

Looks like everything's working correctly. Of course, it would be somewhat embarrassing if it didn't, since this is only a fraction more complicated than FizzBuzz.

About these ads

Tags: , , , , , , , ,

One Response to “Programming Praxis – Happy Numbers”

  1. John Says:

    Far more elegant than my solution in Redcode :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: