After a summer hiatus, it’s time again for the Friday Fragment: our programming-related puzzle.
This Week’s Fragment
During the sabbatical, so many devious ideas came to mind: Sudoku solvers, quines, LOLCODE, you name it. But discretion prevailed; after all, this is about code fragments: small, often elegant solutions that can be written relatively quickly, or used to try new languages and compare their merits. And since this is such a happy day (with a sunny, happy daytime high), we’ll take on happy numbers.
A happy number is a positive integer which you can replace by the sum of the squares of its digits and repeat the process until you get to 1. For example, 7 is a happy number because its series ends at 1: 72 = 49, 42 + 92 = 97, 92 + 72 = 130, 12 + 32 + 02 = 10, 12 + 02 = 1. So:
Write code to compute happy numbers starting at 1. To eventually get your computer back, you can stop at some high limit: whatever makes you happy.
Of course, this is a common math puzzle, so there are likely many implementations on the web. But no peeking. Try it for yourself and aim for something interesting: least amount of code, a new (to you) or unusual language, best use of recursion or induction, best performance, etc.
To “play along”, post the solution as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post.
Last Week’s Fragment?
There wasn’t one! The Friday Fragment was on summer break, and what a break it was! But with the advent of fall, watch this space for new puzzles and solutions.
Here’s my Ruby solution; see the Oct 8 Friday Fragment for details.
# Extensions to Integer to determine if it’s happy.
class Integer
@@cache = Hash.new
def is_happy
return @@cache[self] if @@cache.include?(self)
@@cache[self] = false
result = case
when self == 1 then true
when self < 1 then false else self.digits.inject(0) { | sum, ea | (ea * ea) + sum }.is_happy end @@cache[self] = result return result end def digits a = Array.new; num = self while num > 0 do
a.unshift(num % 10)
num = num / 10
end
return a
end
end
500.times { |i| puts i if i.is_happy }
I gave this some serious thought last week, but was never satisfied enough (or had the time) to post any solutions.
I’m not conversant in Ruby, so I’m laboring to understand the code above. Does this algorithm conclusively prove that an unhappy number is unhappy? What I’m getting at is, how do we know that we won’t find that an iteration comes to 10eSOMETHING_REALLY_BIG after some HUGE number of cycles?
I’ve done some research and I see now that this doesn’t happen: large numbers will tend to “collapse” to smaller numbers. I’m still unclear how we know that your code terminates for, say, 2. Is this value pre-cached in the hash?
That’s correct, Joel: large numbers do quickly “collapse” to smaller ones and these smaller numbers are either happy or they fall into the same unhappy cycle: 42, 20, 4, 16, 37, 58, 89, 145. The unhappy cycle gets cached pretty quickly and leads to a quick conclusion as it hands out a series of falses while the stack unwinds and the loop completes.
It’s easy enough to demonstrate that and show how it terminates just by adding tracing: a simple “puts self” at the top if is_happy. With this, we see the series:
2.is_happy – 2 4 16 37 58 89 145 42 20 4
500.is_happy – 500 25 29 85 89 145 42 20 4 16 37 58 89
123456789.is_happy – 123456789 285 93 90 81 65 61 37 58 89 145 42 20 4 16 37
13631208577813.is_happy – 13631208577813 321 14 17 50 25 29 85 89 145 42 20 4 16 37 58 89
And since that last number is the current size of the US debt, it’s doubly unhappy.
Happy numbers avoid the unhappy cycle but also collapse quickly; for example:
13456789298765431.is_happy – 13456789298765431 566 97 130 10 1
1034567892987654301.is_happy – 1034567892987654301 566 97 130 10 1
There’s nothing pre-cached, but, of course, adding a global cache to an Integer extension is poor design (among other things, it’s not thread-safe). I just did it for brevity. A better solution would be to create a new class with an ivar for the cache.