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.

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)