The happy numbers kata

This weekend my 9 year old son was given the following homework:

Choose a two-digit number (eg. 23), square each digit and add them together. Keep repeating this until you reach 1 or the cycle carries on in a continuous loop. If you reach 1 then the number you started with is a “happy number”.

Can you find all the happy numbers between 1 and 100?

For example, 31 is happy because

31 => 32 + 12 => 10 => 12 + 02 => 1

But 4 is not happy because

4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4

and we have a cycle.

I thought this might make an interesting code kata, so while he beavered away with pencil and paper I set to writing a little program to do the job. Why not give it a try yourself?

  • What tests, if any, did you write? How many times did your stack overflow? What data structure(s) do you need?
  • Did you use recursion? Or loops? Or filters? Or something else?
  • Did you manage to eliminate all of the duplication? Can you eliminate all of the conditionals? Is any of this altered by your choice of programming language?
  • How long does it take to run? At what range size (eg. 1-100, 1-1000, 1-10000) does it take more than, say, 5 seconds to run? Does it run in linear time? Polynomial time? What mathematical tricks can you find to speed it up?
  • What will you do differently next time?

First time through, I wrote no tests. My stack overflowed three times. I used a dictionary to hold the results, with a simple array for cycle detection and a recursive algorithm. I made no attempt to eliminate either duplication or conditionals, and I used none of the arithmetic tricks that my son found while doing the exercise by hand.

Next time, however, will be different…

Supplementary (for the mathematicians among you):

Are there any numbers for which the series neither terminates at 1 nor eventually repeats forever?

Advertisements

7 thoughts on “The happy numbers kata

  1. I’m sure I never had homework that tricky when I was 9!

    I didn’t write any tests. I was writing Erlang and using the REPL for feedback instead. Thanks to tail call elimination my stack never overflowed, but I did have to abort one of my early experiments that was taking too long due to a mistake in my cycle detection!

    I used recursion because in Erlang there is no alternative. There are two conditionals in my code, not sure how I would get rid of them. I don’t think there is any duplication, but its late and I could be missing something!

    5 seconds seems to take me up to a range of about 1-550000. I’m not too hot on time complexity, the results from my tests looked roughly linear, though I didn’t think that would be the case. I think I can think of one trick to speed it up, I might give it a try tomorrow :)

    Fun problem, though thanks! Makes me want to revisit Project Euler

  2. Nice question.

    The answer to your final “for the mathematicians” question simplifies things enormously, and a little bit of experimentation on top gives a near-trivial loop detection algorithm. Nonetheless I hit an infinite loop with my first go!

    The only data structure I used was a simple array. I used Haskell’s lazy evaluation to populate it, which probably counts as recursion. I have no duplication to speak of but there are, so far, still conditionals. In 5 seconds I get to 12447609. I suspect the complexity is something like O(n log n) in time – it’s definitely O(1) in space.

    Cheers

  3. Pingback: Happy numbers again: spoilers | silk and spinach

  4. Thanks for the fun kata! I tried it in C#, using recursion. I can get to about 3.3 million in 5 seconds, but the code is now messier due to caching of previous results to short-circuit the calculation.
    I haven’t hit any stack overflows yet, despite the fact that it’s probably not emitting the tail call opcode.
    I’d be really interested if anyone can avoid conditionals.
    Looking forward to trying it in other languages…

  5. Great idea for a kata, thanks!

    I threw together a Ruby version that could do ~250k in 5 seconds, and a Haskell version that could do 250,000,000 (!). To be honest I’m not 100% confident that the Haskell version is actually evaluating the whole solution ;)

    gunn_’s comment

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

    prompted me to rewrite my Ruby version a bit , do `||=` or `||` count as a conditional? ;)

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