Happy Numbers, Kata in Lua

by EEVa

For my first kata, I picked Happy Numbers at Coding Kata and decided to play with Lua, which I don’t know well.

The user-story is as follows :

You are dead (yes, again). You see a long queue leading up to what you belief must be heaven’s gate. You get in line. After a few minutes of waiting you reach the gate. Suddenly you hear loud sirens, balloons and confetti rain from above.

The gate keeper says that you are the 6666th visitor today! As a reward you get to choose your reincarnation form. Cool! You think for a moment and come to the conclusion that after an unhappy life as a math teacher you want to be happy – so you decide to become a happy number!

Which one will you pick ?

The mathematical definition for happy numbers can naturally be found on wikipedia.

The point is to implement the function isHappy() which takes a number and returns true if the number is happy.

/**
 * Check if a number is a 'happy number'
 *
 * @param number    number to be checked
 * @return          true if parameter is a happy number
 */
boolean isHappy (long number);

I extended the rule slightly by making isHappy() return false when the number is not happy.

So, to get started, I prepared my unit testing environment with luaunit, a simple unit test environment. This is my minimal, single test, test suite that fails and the whole file as well:

 function isHappy(number)
 end
 -- Unit Testing
 require('luaunit')
 TestHappiness = {} -- new class
     function TestHappiness:testFunctionReturnsBoolean()
         result = isHappy(198)
         assertEquals( type(result), 'boolean' )
     end
 -- End of TestHappiness
 LuaUnit:run()

Well, for now isHappy() won’t return anything, so there’s no chance it’s a boolean.

The simplest modification for the test to succeed one could do is to return a boolean.

function isHappy(number)
    return false
end

Let’s mess this up without waiting:

function TestHappiness:testOneIsHappy()
    result = isHappy(1)
    assertEquals( result, true )
end

What comes to my mind is just to return true, and it is fixed. Next simple failing test is to check whether to is not happy.

function TestHappiness:testTwoIsNotHappy()
    result = isHappy(2)
    assertEquals( result, false )
end

Let’s make a fake, either the number is 2 and the function returns false, else it returns true.

 function isHappy(number)
     if number == 2 then
         return false
     else
         return true
     end
 end

If we test for non-happy number 6, it breaks.

Fixing this simply amounts to decide that either the number is odd (like 1) and the function returns true or the given number is even (like 2) and the funcction returns false. This is implemented in the following snipet:

function isHappy(number)
    if number % 2 == 0 then
        return false
    else
        return true
    end
end

Now, it starts to look like an automated way to determine whether a number is happy. Yet, it is still easily breakable: take 10, an happy even number !

I fixed my code by breaking this number into digits, and use the same test on every digit:

function isHappy(number)
    number = tostring(number)
    for c in number:gmatch"." do
        if c ~= 0 then
            if c % 2 == 0 then
                return false
            else
                return true
            end
        end
    end
end

This being immediately broken when testing for non-happy number 11, it is then modified this way:

function isHappy(number)
    number_str = tostring(number)
    if #number_str == 1 then
        if number % 2 == 0 then
            return false
        else
            return true
        end
    else
        for c in number_str:gmatch"." do
            c = tonumber(c)
            if c ~= 0 then
                return isHappy(c)
            end
        end
    end
end

Now, there are two parts: the first one is the exit test, on condition that number is of length 1 (note the length operator # in Lua 5.1) then if it is even exit with false, otherwise exit with true.
The second part breaks the number into digits, and calls recursively isHappy() in order to find the proper exit state.

Fortunately, it is not the end as test for 12 (non-happy) breaks the program. I fixed it by summing each digit to the power of two (it is closer to definition, and I’m not sure that is the right choice here). So the modified for loop now looks like :

        sum = 0
        for c in number_str:gmatch"." do
            c = tonumber(c)
            sum = sum + (c * c)
        end
        return isHappy(sum)

I realized then that I could simply test for 1 instead of parity:

     if #number_str == 1 then
-        if number % 2 == 0 then
-            return false
-        else
+        if number == 1 then
             return true
+        else
+            return false
         end
     else

We’re almost there. Last thing that came to consider was : what happens if a happy number of length one is given, the only one is 7, so let’s test.

function TestHappiness:test7IsHappy()
    result = isHappy(7)
    assertEquals( result, true )
end

It fails of course. The last simple fix I did was (and this is for now the final function) :

function isHappy(number)
    number_str = tostring(number)
    if #number_str == 1 then
        if number == 1 or number == 7 then
            return true
        else
            return false
        end
    else
        sum = 0
        for c in number_str:gmatch"." do
            c = tonumber(c)
            sum = sum + (c * c)
        end
        return isHappy(sum)
    end
end

Afterword

I realized, while writing the details of this kata, that I didn’t always take the simplest way, for instance testing for 7 in the last resort instead of the beginning.

Second, although I’m not fully convinced of the solution I gave, it seems that non-happy numbers tend to loop and at some point come back to digits that are different from 1 and 7, that’s why it may be possible to exclude them and return false. Happy numbers on the contrary that lead to 7 are happy, because the course of action from 7 to 1 is proven (see wikipedia about happy numbers if you doubt it).

Anyone that could help proving these wild guesses statements right (or wrong) is welcome to do so in the comments.

Advertisements