Numbers Game - Part 2 - A Dog's Breakfast

Updated on 2016-01-17: note that the algorithms (or lack thereof) here have been superseded in Part 3.

Continuing from Part 1, it's time to prepare the list of arithmetic operators.

Generating Operators List

So we can generate list of numbers of various size, now we need to insert all the possible arithmetic operators between each pair of numbers. The requirement of generating operators list is a little different from numbers list: operators can be repeated - e.g. with 3 numbers in the list [n1, n2, n3] we can test n1+n2+n3 where the plus ('+') operator has been repeated in the expression.

This means that we cannot use the k_combinations() function used for numbers generation. In stead I had to tweak it a little, and call it k_com as shown below:

function k_com(set, k) {
 var i, j, combs, head, tailcombs;
 
 if (k > set.length || k <= 0) {
  return [];
 }
 
 if (k == set.length) {
  return [set];
 }
 
 if (k == 1) {
  combs = [];  
  for (i = 0; i < set.length; i++) {
   var item=[set[i]];
   if(checkDup(combs, item)==false){
    combs.push(item); 
   }    
  }  
  return combs;
 }
 
 combs = []; 
 for (i = 0; i < set.length - k + 1; i++) {
  head = set.slice(i, i+1);
  tailcombs = k_com(set, k - 1);
  for (j = 0; j < tailcombs.length; j++) {
   var item=head.concat(tailcombs[j]);
   if(checkDup(combs, item)==false) {
    combs.push(item); 
   }    
  }
 }
 
 return combs;
}
/*
 * set is [[], [], []]
 * item is just an [object]
 * checks if item is already in the set
 * returns dup=true; no dup=false 
 */
function checkDup(set, item) {
 for (var i in set) {
  var src=set[i];
  // assert.deepEqual(src, item)
  if(src.length == item.length) {
   var matched=true;
   for(var j=0; j<src.length; j++) {
    matched=matched && src[j]==item[j];
    if(!matched) break;
   }
   if (matched)
    return true;
  }
 }
 return false;
}

There are a few problems with k_com():

1. since it uses head and tail recursion approach, the last element of the array will be missed
2. since operators are repeatable, it's not just a combination algorithm, but also involves permutation
3. when there are more spaces than operators - e.g. 6 numbers require 5 operators, then this algorithm does not work.

To circumvent these problems, I  simply repeated the original operators set based on how many spaces there are - for example, if there are 3 numbers - i.e. 2 spaces (k=2), then my original operators set will be doubled as ['+', '-',  '*', '/', '+', '-',  '*', '/']; if there are 4 numbers - i.e. k=3, then my operators set will be tripled as ['+', '-',  '*', '/', '+', '-',  '*', '/', '+', '-',  '*', '/'] ...

So the getOps() function looks like below. I wish JS supports Ruby (or was it Erlang?) syntax of repeating arrays by overloading the '*' operator.

 function getOps(k) {
    var ops=["+", "-", "*", "/"];
    var i=k;
    var r=[]

    while (i--) {
        r=r.concat(ops);     
    }
    return k_com(r, k);
}

The complexity of this algorithm is probably O(n!) which is quite bad. Fortunately in Numbers Game, the maximum number for k is 5. The performance of getOps() running in V8 that came with Node.js is shown below:

> var then=new Date(); ops=getOps(2); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then)
64 takes 2 ms
undefined
> var then=new Date(); ops=getOps(4); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then)
256 takes 107 ms
undefined
> var then=new Date(); ops=getOps(5); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then)
1024 takes 4185 ms
undefined