Marco Valtas

Today I was doing what ThoughtWorkers do in their spare time and got puzzled, so I decided to share this with you. If you don't know there's a web site called Programming Praxis that posts little riddles (mostly numeric ones) to be solved in any programming language. I was implementing the solution for Happy Numbers and something strange happened, first let's see my Ruby solution:

class Happy

  def initialize
    @seen = {}
  end

  def is_happy?(number)
    sum = sum_square number
    if(@seen.has_key?(1))
      initialize
      return true
    elsif(@seen.has_key?(sum))
      initialize
      return false
    else
      @seen[sum] = true
      is_happy?(sum)
    end
  end

  private
  def sum_square(number)
    sum = 0
    number.to_s.split(//).each do |d|
      sum += d.to_i ** 2
    end
    return sum
  end
end

Probably this is a naive solution (I'm not a Ruby developer) but did the job, tests worked and we are good. After that I've started implement the same solution in Java and here we go (please note the line 31):

package com.marcovaltas.happy;

import java.util.HashSet;
import java.util.Set;

public class HappyNumber {
  private Set<Integer> seen = new HashSet<Integer>();

    private int sumSquare(int number) {
        char[] digits = String.valueOf(number).toCharArray();
        int sum = 0;
        for (char d : digits) {
            sum += (int) Math.pow(Double.parseDouble(String.valueOf(d)), 2.0);
        }
        return sum;
    }

    public boolean isHappy(int number) {
        int sum = sumSquare(number);

        if (sum == 1) {
            initHash();
            return true;
        } else if (seen.contains(sum)) {
            initHash();
            return false;
        } else {
            seen.add(sum);
            isHappy(sum);
        }
        return false;
    }

    private void initHash() {
        seen = new HashSet<Integer>();
    }
}

Line 31 on the Java solution was added because the Java compiler was complaining about the possibility of this method not return, I've even tweeted that. So guess what happened? Didn't work, the tests didn't pass when I was "Uh?!". Can you answer why? Take your time.

Answer

I've started to debugging and turns out that my tweet was totally wrong. The Java compiler was right and I needed that return, the only thing is that was in the wrong place. Let's see the debugging session, if you want to try it download the code here, you can use Mercurial to download the code.

For the debugging I've used the number 7, and had a break point on line 19. So, as expected, the after the first call sum will have the value 49. The algorithm will proceed correctly until sum reach 1, then it gets interesting. Now sum == 1, so the code enters the if clause and reaches the return true; statement.

        int sum = sumSquare(number);

        if (sum == 1) {
            initHash();
            return true;
        } else if (seen.contains(sum)) {
            initHash();
            return false;
        } else {
            seen.add(sum);
            isHappy(sum);
        }
        return false;

So, what you expect to occur next? Probably, if not aware of what it happening, you will guess that the method returns. No, the call jumps to line 29.

        int sum = sumSquare(number);

        if (sum == 1) {
            initHash();
            return true;
        } else if (seen.contains(sum)) {
            initHash();
            return false;
        } else {
            seen.add(sum);
            isHappy(sum);
        }
        return false;

And then to line 31!

        int sum = sumSquare(number);

        if (sum == 1) {
            initHash();
            return true;
        } else if (seen.contains(sum)) {
            initHash();
            return false;
        } else {
            seen.add(sum);
            isHappy(sum);
        }
        return false;

After that, back to line 29, 31, 29, 31, 29, 31, 29 and finally 31, then returns false. So, why this happened? At, first I did some obscure analysis on the Java Language Specification and the book Ruby Programming Language comparing the return statements. But, as all things in life, there was a simpler explanation pointed out by Pavol Bernhauser and Luiz Ribeiro (a fellow TWer) on this blog comments. In fact still is a difference on specification, but a simpler one. For Java the value of returned from a method will be explicit informed by the return clause. So, if you follow the execution path here what is happening.

When we reach the first return true; (line 23), the control is handled back to isHappy(sum); call, the execution proceed to the next return false; (line 31), since we were in a recursion the return will handle back to the previous call of isHappy(sum); and this repeats through all intermediate numbers that made 7 a happy number (49, 97, 130 and 10). If you run on a debugger you will see the stack piling up.

The correct solution is make the call to isHappy(sum); a return call:

        int sum = sumSquare(number);

        if (sum == 1) {
            initHash();
            return true;
        } else if (seen.contains(sum)) {
            initHash();
            return false;
        } else {
            seen.add(sum);
            return isHappy(sum);
        }

But why the Ruby version worked? Well, as pointed out by Pavol and Luiz, it worked "because Ruby returns the result of last invoked statement as the result of method." in this case the is_happy? was the last statement and so will be the result. If I did the same thing I did in Java, putting a return false; on the end the Ruby version will not work too. In this case it will follow the same steps that Java took I guess.

So, in the end, was a little difference with the languages specifications, the Java compiler was right, and I, as new to Ruby, got puzzled why the Ruby version worked. Living, coding and learning.

That's it.