BASE Meeting

Last night I attended my first BASE (Bay Area Scala Enthusiasts) meeting. Organizer Dick Wall had a nice problem to solve for the attendees. The problem was to take a list of integers, and replace each element in the list with the product of all the other elements in the list. For example, if your input was (2,4,6,8) the output should be (4*6*8, 2*6*8, 2*4*8, 2*4*6) = (192, 96, 64, 48). If you want to solve the problem yourself, stop reading and come back when you are ready to read about the solutions.

There is an "obvious" brute force solution, which would be to implement the algorithm exactly as the problem is stated. This is an O(N^2) solution, not so good. You can do better by simply taking a product of all of the elements of the original list, and then replacing each member of the list with the product divided by the element. So for the example above, the product = 2*4*6*8 = 384, and thus the output should be (384/2, 384/4 , 384/6, 384/8). This is O(N) solution, and that is much better. This is the best you can do in terms of speed and space, as you only keep around one extra integer in memory (the product.) However, it doesn't always work.

The problem is when there is a zero in the list. Then the above algorithm will lead to division by zero errors. Dick pointed this out, and pointed out that there are really three casses. If there is exactly one zero, then every element in the return list will be zero, except for the one at the same index as the lone zero from the input list. If there are two or more zeroes, then every element in the return list will be zero. With that in mind, here was my solution:

def wallify(list:List[Int]):List[BigInt] ={
  val one = BigInt.int2bigInt(1)
  val noZeroes = list.filter(_ != 0)
  if (noZeroes.length == list.length){
    val prod = list.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)}
    list.map(prod/_)
  } else if (list.length - noZeroes.length == 1){
      list.map((el) => 
        if (el == 0) 
          noZeroes.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)} 
        else 
            0
      )
  } else {
    list.map((el) => 0)
  }
}

I had to leave early, and didn't finish my code until today. Here is the code that the group, led by Bill Venners:

def wallify(input: List[Int]): List[Long] = {
  def boringCalcProduct(longInput: List[Long]): Long = {
    var product = 1L
    for (ele <- longInput) {
      product *= ele
    }
    product
  }

  def calcProduct(input: List[Long]): Long =
    // input.foldLeft(1L)(_ * _)
    (1L /: input)(_ * _)
  
  val zeroCount = input.filter(_ == 0).size
  val longInput: List[Long] = input.map(ele => ele.toLong)
  zeroCount match {
    case 0 =>
      val product = calcProduct(longInput)
      longInput.map(product / _)
    case 1 =>
      val noZero = longInput.filter(_ != 0)
      val product = calcProduct(noZero)
      longInput.map(ele => if (ele == 0) product else 0)
    case _ =>
      input.map(ele => 0L)
  }
}