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)
  }
}

Mode Problem

I recently came across this interesting problem.

Given a list of N integers where more than half of the integers are the same, compute the mode (most common element) of the list.

When I came across the problem, the best I could immediately do was to compute the mode for any given set of numbers by putting the numbers into a heap using the frequency as the comparator. If you put the numbers in a heap like that then the mode is always at the root of the heap. It's equivalent to a heap sort, so it's a N*log(N) computation.

I knew this was not the best solution since it did not use the fact that the mode's frequency is greater than N/2. I mentioned the to my friend Chris and he figured out it was a classic Pigeonhole Principle problem.

His solution involved constructing dislike pairs of numbers. Basically you keep doing this until you can't. Eventually you won't be able to do it (because more than half of the numbers are the same) and the leftover will be the mode. Here's the code:

#include <iostream>
#include <vector>

using namespace std;

int mode(int*, int);

int main (int argc, char * const argv[]) {
    vector<int> nums;
    int n = 0;
    while (n != -999){
        cout << "Enter next number, -999 to quit" << endl;
        scanf("%d",&n);
        if (n != -999){
            nums.push_back(n);
        }
    }
    int sz = nums.size();
    int* a = new int[sz];
    for (int i=0;i<sz;i++){
        a[i] = nums[i];
    }
    cout << "Mode: " << mode(a,sz);
   
    return 0;
}

int mode(int* a, int n){
    int* b = new int[n];
    int j=0;
    for (int i=0; i<n; i++){
        if (i == j)
            b[j] = a[i];
        else if (a[i] == b[j])
            b[2*i-j] = a[i];
        else
            b[(++j)++] = a[i];
    }
    return b[j];
}

Blogged with Flock