Sunday, September 26, 2010

Happy number

As reminder, a happy number is the number where the sequence of the sum of the squares of the digits equal 1.
For example, 1 is happy number because 12 = 1. 


7 is  a happy number because 
  72 = 49
  42 + 92 = 97
  92 + 72 = 130
  12 + 32 + 02 = 10
  12 + 02 = 1.


4 is not a happy number because

  42 = 16
  12 + 62 = 37
  32 + 72 = 58
  52 + 82  = 89
  82 + 92 = 145
  12 + 4+ 52  = 42
  4+ 2 = 20
  2+ 0 = 4








that yields an infinite loop digit sum of squares.
Here is my attempt to write happy number in Scala way.
First, I need to define sumOfSquares function, implemented as follow:

 1 def sumOfSquares(n: Int): Int = {
 2   def sumOfSquares(n: Int, powOf10: Int, acc: Int): Int = {
 3     if ( n / powOf10 == 0) {
 4       acc
 5     }
 6     else {
 7       val digit = (n / powOf10) % 10
 8       val result = acc + digit * digit 
 9       sumOfSquares(n, powOf10 * 10, result)
10     }
11   }
12   sumOfSquares(n, 1, 0)
13 }
14     

The function calls an inner method sumOfSquares that is a recursive function, taking into account that the sumOfSquares of an integer is the square of its last digit + the sumOfSquares the rest of the digits. 
The isHappyNumber function is then defined as follow:



14
15 def isHappyNumber(n: Int) = {
16   def isHappyNumberList(n: Int, lst: Set[Int]): Boolean = {
17     sumOfSquares(n) match {
18       case 1 => true
19       case sum => !lst.contains(sum) && isHappyNumberList(sum, lst + n)  
20     }
21   }
22   isHappyNumberList(n, Set.empty)
23 }
24 


That is, if the sum of squares of n is 1, then n is a happy number, otherwise n is a happy number when its sum of squares is a happy number given the sequence of the sum of squares does not yield an infinite loop.
To detect an infinite loop, a set of calculated sum of squares is kept and for each new generated sum, the program verifies that the number is not in the set already.

Monday, September 20, 2010

Get all supertypes of a class/interface (Scala)

01  def getSuperTypes(c: Class[_]) : Seq[Class[_]] = {
02      val sc = c.getSuperclass
03      val ifaces = c.getInterfaces
04      (sc, ifaces.length) match {
05          case (null, 0) => Nil
06            
07          case (null, _) => 
08            ifaces ++ ifaces.flatMap(getSuperTypes(_))
09            
10          case (_, 0) =>  sc +: getSuperTypes(sc)
11           
12          case (_, x) =>  sc +: (getSuperTypes(sc) ++ 
13                              ifaces.flatMap(getSuperTypes(_)))
14            
15        }
16    }