List of Happy Numbers in scala

Question

Definition of Happy numbers taken from Wikipedia.

A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits in base-ten, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers)

Example: 19 is happy, as the associated sequence is

1*1 + 9*9 = 82,
8*8 + 2*2 = 68,
6*6 + 8*8 = 100,
1*1 + 0*0 + 0*0 = 1.

import scala.collection.mutable.Set
object HappyNumber extends App {
 def findSquareSum(n: Int): Int =
 n.toString.foldLeft(0) { (product, num) => product + num.asDigit * num.asDigit }
 val visited = Set[Int]()
 def isHappyNumber(n: Int): Boolean = {
 n match {
 case 1 => true
 case _ =>
 if (visited contains n) false
 else {
 visited += n
 if (isHappyNumber(findSquareSum(n))) { visited -= n; true} else false
 }
 }
 }
 (1 to 247) foreach { num => if(isHappyNumber(num)) println(num) }
}

Answer 1

In findSquareSum(), what you've labelled as product is actually a sum. So that's a little confusing. The digits squared is a product but adding them together is a running sum.

I like to avoid transitions to/from String representation whenever possible, but that's mostly a style thing.

If you make the visited set a passed parameter to the isHappyNumber() method, you can

1. keep it immutable
2. avoid emptying it between runs
3. make the method tail recursive, which will be faster and more memory efficient

.

def isHappyNumber(n: Int, seen: Set[Int] = Set()): Boolean =
 if (n == 1) true
 else if (seen(n)) false
 else isHappyNumber(findSquareSum(n), seen+n)

Here I've given the Set, now called seen, a default value (empty) so it doesn't have to be specified when invoked.

(1 to 247).filter(isHappyNumber(_)).foreach(println)

---

UPDATE

Ah, I see that I've missed the point and purpose of your visited set, which is to cache unhappy numbers in order to reduce the recursive iterations in future calculations. Not a bad idea, but the obvious next question is: Why not cache all the isHappyNumber() results? You'll have quick lookups on all calculations and you won't have to back-out the happy number results.

//memoize a function of arity-2 but only cache the 1st parameter
//
def memo[A,B,R](f :(A,B)=>R): (A,B)=>R = {
 val cache = new collection.mutable.WeakHashMap[A,R]
 (a:A,b:B) => cache.getOrElseUpdate(a,f(a,b))
}
//isHappyNumer() is now a memoized function
// for quick lookup of both happy and unhappy numbers
//
val isHappyNumber :(Int, Set[Int]) => Boolean = memo { (n, seen) =>
 if (n == 1) true
 else if (seen(n)) false
 else isHappyNumber(findSquareSum(n), seen + n)
}
(1 to 24).filter(isHappyNumber(_,Set())).foreach(println)

You'll note that the scope (visibility) of the mutable hash map is kept quite small and local.

• vikrant: thanks for your comment. I am not emptying the set between runs, but just removing a HappyNumber from it. That makes this algorithm remember the previously explored "sad numbers" and makes it fast. If I pass an empty set for every number I will endup computing the set over and over again.

Answer 2

Just a nitpick about naming: the "find" in findSquareSum is meaningless, and perhaps even misleading, since it's not searching for anything. Just squareSum would be fine. Even better, call it something like sumSquaresOfDigits to be explicit about what the function does.

Answer 3

It's better to cache both happy and unhappy numbers

def squareSum(n: Int): Int = n.toString.map(_.asDigit).map(x => x * x).sum
def happyNum(n: Int, book: Set[Int], happy: Set[Int], unhappy: Set[Int]): List[Set[Int]] = {
 if(n==1 || happy.contains(n)) List(happy ++ book, unhappy)
 else if(book.contains(n) || unhappy.contains(n)) List(happy, unhappy ++ book)
 else happyNum(squareSum(n), book + n, happy, unhappy)
}
def helper(): Set[Int] = {
 var happy, unhappy = Set[Int]()
 for(i <- 1 to 1000){
 val lis: List[Set[Int]] = happyNum(i, Set(), happy, unhappy)
 happy = lis(0)
 unhappy = lis(1)
 }
 happy + 1
}
def solution(): List[Int] = helper.toList
def solution(num: Int): Boolean = helper.contains(num)

• Mast: Welcome to Code Review! Can you explain why your solution is better than the original? Alternative implementations by themselves are not reviews.