Numbers Game - Part 5 - Oops

A couple days ago, when watching the Letters and Numbers show on SBS, I used my Javascript program to check some of the numbers games. To my embarrassment, I found a serious flaw in my algorithm - the checkNumbers() function only checks expressions that are strictly from left to right - i.e. it does not cover scenarios like '(a+b)*(c-d)'. Notice that the calculation is not strictly left to right due to the brackets. So today, I set out to fix the problem.

Looking at an array of numbers - e.g. [n1, n2, n3, n4, n5, n6], they can be broken down to left and right sub-arrays using various lengths combinations - e.g. 2 elements in array 1, 4 elements in array 2; 3 elements each;, etc. So it's a matter of iterating the different array lengths to generate all possible 'brackets' scenarios.

function genExprs(numbers) {
 var len=numbers.length, exprs=[];

 if(len==1)
  exprs.push(numbers[0]);

 else if(len==2) {
  var n1=numbers[0], n2=numbers[1];
  exprs.push('('+n1+'+'+n2+')');
  exprs.push('('+n1+'-'+n2+')');
  exprs.push('('+n1+'*'+n2+')');
  if(n1/n2%1==0)
   exprs.push('('+n1+'/'+n2+')');
 } else {
  len=numbers.length-1;
  for(var i=2; i<=len; i++){
   var left=genExprs(numbers.slice(0,i));
   var right=genExprs(numbers.slice(i));
   for(lexpr of left) {
    for (rexpr of right) {
     exprs.push('('+lexpr+'+'+rexpr+')');
     exprs.push('('+lexpr+'-'+rexpr+')');
     exprs.push('('+lexpr+'*'+rexpr+')');
     var expr='('+lexpr+'/'+rexpr+')';
     if(eval(expr)%1===0)
      exprs.push(expr);
    }
   }
  }
 }
 //console.log("genExprs returning: "+exprs);
 return exprs;
}

This function generates all possible expressions with different brackets groups. It returns an array of expressions in the form of strings. So in order to check which expressions have the right answer I would have to use eval() to evaluate each expression. Because eval() has to process strings, it makes it at least 10 times slower than calculating directly. To fix this, I need to return the expression string as well as the evaluation result of the expression. A JSON object with 2 fields will suffice - one to contain the expression string; the other to store the current answer (i.e. the evaluation) of the expression. An improved version of genExprs() was born.

function genExprs2(numbers) {
 var len=numbers.length, results=[];

 if(len==1)
  results.push({expr:numbers[0], currAnswer:numbers[0]});

 else if(len==2) {
  var n1=numbers[0], n2=numbers[1];
  results.push({expr:'('+n1+'+'+n2+')', currAnswer: n1+n2});
  results.push({expr:'('+n1+'-'+n2+')', currAnswer: n1-n2});
  results.push({expr:'('+n1+'*'+n2+')', currAnswer: n1*n2});
  var currAnswer=n1/n2;
  if(currAnswer%1==0)
   results.push({expr:'('+n1+'/'+n2+')', currAnswer: currAnswer});
 } else {
  len=numbers.length-1;
  for(var i=2; i<=len; i++){
   var left=genExprs2(numbers.slice(0,i));
   var right=genExprs2(numbers.slice(i));
   for(lexpr of left) {
    for (rexpr of right) {
     results.push({ expr:'('+lexpr.expr+'+'+rexpr.expr+')', currAnswer: lexpr.currAnswer+rexpr.currAnswer});
     results.push({ expr:'('+lexpr.expr+'-'+rexpr.expr+')', currAnswer: lexpr.currAnswer-rexpr.currAnswer});
     results.push({ expr:'('+lexpr.expr+'*'+rexpr.expr+')', currAnswer: lexpr.currAnswer*rexpr.currAnswer});
     var currAnswer=lexpr.currAnswer/rexpr.currAnswer;
     if(currAnswer%1===0)
      results.push({ expr:'('+lexpr.expr+'/'+rexpr.expr+')', currAnswer: currAnswer});
    }
   }
  }
 }
 //console.log("genExprs returning: "+exprs);
 return results;
}
/*
 * length of numbers array must be greater than 3
 */
function checkNumberArray(numbers, answer) {
 var solutions=[];
 if(numbers.length<4)
  return checkNumbers(numbers.slice(1), answer, numbers[0], numbers[0]+'');

 for(expr of genExprs2(numbers)) {
  //console.log("expression="+expr);
  var currAnswer=expr.currAnswer;
  if(currAnswer===answer && !checkDup(solutions, expr.expr))
   solutions.push(expr.expr.slice(1, expr.expr.length-1)); // strip the first (open) and last (close) brackets
 }
 //console.log("checkNumberArray solutions="+solutions);
 return solutions;

}

The performance improvement of this approach is staggering - using node.js on my i5 laptop it takes around 3-5 seconds whereas the eval() version took 50 seconds or more.

See also:

• Numbers Game - Part 1 - The Journey Begins
• Numbers Game - Part 2 - A Dog's Breakfast
• Numbers Game - Part 3 - Putting Things Right
• Numbers Game - Part 4 - De-duplicate Mathematically Equivalent Expressions
• Numbers Game - Part 5 - Opps
• Numbers Game - Part 6 - AWS Lambda
• Numbers Game - Part 7 - AWS APIs

Russian Oil

My copy of a classic Russian portrait in oil.

From My Oil Painting Journey

Numbers Game - Part 4 - De-duplicate Mathematically Equivalent Expressions

In Part 3, I have completed the Numbers Game. The solveGame() function finds the shortest answer; the solveAllGames() function finds all possible solutions, if any.

There is an imperfection in solveAllGames(): it returns mathematically equivalent expressions. For example, 1+2 and 2+1 are equivalent, so we should only return one of them, not both. Therefore, in solveAllGames(), I need to check whether an equivalent expression already exists in solutions array before I append it to the array.

To check whether two expressions are mathematically equivalent is worthy of a PhD thesis and an entire math library to do. Fortunately, my problem at hand is a lot simpler since it only involves a tiny fraction of the whole mathematical expressions. Namely: my expressions are arithmetic ones only - involving only integers and four operators (+, -, *, /). By observation, I see that equivalent expressions have these properties:

1. they evaluate into the same result
2. they have the same list of integers
3. they have the same list of operators

For example, consider these expressions: 2*(1+5), (5+1)*2. They both have the same three numbers: 1, 2 and 5; they both have the same operators: + and *. 

So it's simply a matter of adding the above checks to the expression before inserting into the solutions array as highlighted lines below. I cheated a little here - since I am comparing two arrays of integers/strings only, instead of checking for deep equality (or using Node.js Assert#deepEqual() or JSON.stringify()) I just used Array#toString() to compare the two strings.

Note that this algorithm is flawed:

• it results in false positives: (25-5)+((75+50)+5)*7 and (((7+75)-50)+5)*25+5
• it results in false negatives: 5-(2-1) and 5-2+1

Alas, but it's still better than having too many duplicates in the result.

function solveAllGames (nums, answer) {
 var solutions=[];
 if(nums.indexOf(answer)>0)
  solutions.push(answer);
 else if(nums.length<2)
  return [];

 for(var i=2; i<=nums.length; i++) {
  var numbers=k_combinations(nums, i);
  for(var n of numbers) {
   var permus=permutations(n);
   for(var p of permus) {
    var expr=checkNumbers(p.slice(1), answer, p[0], ''+p[0]);
    if(expr!=-1) {
     // check if equivalant expression already in solutions
     var found=false;
     for(var sol of solutions) {
      var e1=sol.replace(/\(|\)/g, '');
      var e2=expr.replace(/\(|\)/g, '');
      if(e1.length != e2.length)
       continue;
      if(e1.split(/(\+|\-|\*|\/)/).sort().toString()==e2.split(/(\+|\-|\*|\/)/).sort().toString()) { 
       found=true;
       break;
      }
       
     }
     if(!found)
      solutions.push(expr);
    }
   }
  } 
 }
 return solutions;
}

Numbers Game - Part 3 - Putting Things Right

Continuing from Part 2.

I am really unhappy about how the operators are generated as shown in part 2 because the algorithm is not well thought through and the performance is terrible. So following Agile principle of Continuous attention to technical excellence and good design, I decided to rewrite this part.

This time, instead of generating all the possible operators combinations and permutations up front, I do it on the fly when processing each numbers array.

/*
 * generate and test nums array using all possible operators 
 * returns either -1 (no solution) or expression string
 * For example, to check numbers [n1, n2, n3, n4] against answer a,
 * pass the parameters as so:
 * checkNumbers([n2, n3, n4], a, n1, 'n1');
 */
function checkNumbers(nums, answer, currAnswer, currExpr) {
 var length=nums.length, num=nums[0], tail=nums.slice(1);

 if(length<1) return -1;
  
 if(length==1){
  if(currExpr.length==0)
   return num;
  // else
  if((currAnswer+num)===answer) {
   return currExpr+'+'+num;
  } else if ((currAnswer-num)===answer) {
   return currExpr+'-'+num;
  } else if ((currAnswer*num)===answer) {
   return currExpr+'*'+num;
  } else if ((currAnswer/num)===answer) {
   return currExpr+'/'+num;
  } else
   return -1;
 } 
 // try +, -, *, / one by one
 // could use eval() but chose not to due to performance concern
 var a=currAnswer+num
 if(a===answer)
  return currExpr+'+'+num;
 else {
  var result = checkNumbers(tail, answer, a, '('+currExpr+'+'+num+')');
  if(result!=-1)
   return result;
 }
 
 a=currAnswer-num; 
 if(a===answer)
  return currExpr+'-'+num;
 else {
  var result = checkNumbers(tail, answer, a, '('+currExpr+'-'+num+')');
  if(result!=-1)
   return result;
 }
 
 a=currAnswer*num;
 if(a===answer)
  return currExpr+'*'+num;
 else {
  var result = checkNumbers(tail, answer, a, currExpr+'*'+num);
  if(result!=-1)
   return result;
 }

 a=currAnswer/num;
 if(a%1 !=0)
  return -1;
 if(a===answer)
  return currExpr+'/'+num;
 else {
  var result = checkNumbers(tail, answer, a, currExpr+'/'+num);
  if(result!=-1)
   return result;
 }
 return -1;
}

Now the solveGame() becomes:

function solveGame (nums, answer) {
 if(nums.indexOf(answer)>0)
  return answer;
 if(nums.length<2)
  return -1;

 for(var i=2; i<=nums.length; i++) {
  var numbers=k_combinations(nums, i);
  for(var n of numbers) {
   var permus=permutations(n);
   for(var p of permus) {
    var expr=checkNumbers(p.slice(1), answer, p[0], ''+p[0]);
    if(expr!=-1) {
     console.log("Solved: "+expr);
     return expr;
    }
   }
  } 
 }
 console.log("Problem has no solution.")
 return -1;
}

To find all possible solutions:

function solveAllGames (nums, answer) {
 var solutions=[];
 if(nums.indexOf(answer)>0)
  solutions.push(answer);
 else if(nums.length<2)
  return [];

 for(var i=2; i<=nums.length; i++) {
  var numbers=k_combinations(nums, i);
  for(var n of numbers) {
   var permus=permutations(n);
   for(var p of permus) {
    var expr=checkNumbers(p.slice(1), answer, p[0], ''+p[0]);
    if(expr!=-1) {
     solutions.push(expr);
    }
   }
  } 
 }
 return solutions;
}

An unsolvable game (i.e. traversing all possible combinations and permutations of all numbers of all sizes using all operators) used to take about 12 seconds on V8 now takes 250ms:

c:\temp>node numsGame.js
Sun Jan 17 2016 15:23:47 GMT+1100 (AUS Eastern Daylight Time)
solving [75,25,100,50,10,10] targetting 883
Problem has no solution.
-1
Sun Jan 17 2016 15:23:48 GMT+1100 (AUS Eastern Daylight Time)
Duration: 250ms

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

Numbers Game - Part 1 - The Journey Begins

I am a fan of the Letters and Numbers game on SBS channel of Australian TV. So today I decided to try and write a javascript program to solve the games. To keep the program simple, brute force is the way to go!

Letters games should be easy. It's just a matter of generating all the combinations and permutations of the nine letters and check against a work list from MacQuarie dictionary. So I will leave this to a later date.

The numbers game is a lot trickier. The orthodox way would be to generate binary trees and put numbers into the tree leaves in different permutations. The non-leaf nodes of the tree would be permutations of five operators: plus, minus, multiply, divide and null operator (since not all numbers have to be used to get to the answer).

So the numbers game is reduced to the following main problems:

1. generate all combinations of the numbers to be put into the tree
2. generate all combinations of the operators to be put into the tree
3. evaluate the generated tree

However, I feel that implementing binary trees and arithmetic operators for such a small program are too much effort. So I decided to use arrays instead and take the lazy way out... I mean the Agile way by following one of the principles: Simplicity--the art of maximizing the amount of work not done--is essential.

1. generate all combinations and permutations of the numbers (which are non-repeatable) into arrays of different sizes (from 2 to 6) - e.g. [n1, n2], [n2, n1], [n1, n3]...[n1, n2, n3, n4, n5] and permutate each of them
2. generate all combinations and permutations of the operators (which are repeatable) into arrays of different sizes (from 1 to 5) - e.g. ['+'], ['-'], ['*'], ['/'], ['+', '+'], ['+', '-'], ... ['/', '/', '/', '/', '/']
3. walk-through all the number arrays and for each weave with the operators array of the correct size - e.g. [n1, n2] combined with ['+'], ['-'], ['*'], ['/'] to produce strings: n1+n2, n1-n2, n1*n2, n1/n2, ...
4. use eval() to evaluate the generated arithmetic expression strings and check against the answer until matched.

There is a rule in the numbers game saying that throughout all the steps of the calculation, no fractions are allowed. For example, to get 431 from [75, 25, 50, 100, 8, 2]:

Arithmetically (75/100+50)*8+25=431. However, this is not a correct answer in the game because the step 75/100 produces fraction.

Generating Numbers List

Basically, from the array of 6 integers, say [5,6,7,8,9,0], I need to generate all its combinations into arrays of size 2, 3, 4, 5, 6:

• size 2 (with 15(=6! / (2! (6-4)!)) combinations): [[5,6],[5,7],[5,8],[5,9],[5,0],[6,7],[6,8],[6,9],[6,0],[7,8],[7,9],[7,0],[8,9],[8,0],[9,0]]
• size 3 (with 20(=6! / (3! (6-3)!)) combinations): [[5,6,7],[5,6,8],[5,6,9],[5,6,0],[5,7,8],[5,7,9],[5,7,0],[5,8,9],[5,8,0],[5,9,0],[6,7,8],[6,7,9],[6,7,0],[6,8,9],[6,8,0],[6,9,0],[7,8,9],[7,8,0],[7,9,0],[8,9,0]]
• size 4 (with 15(=6!/(4! (6-4)!)) combinations): [[5,6,7,8],[5,6,7,9],[5,6,7,0],[5,6,8,9],[5,6,8,0],[5,6,9,0],[5,7,8,9],[5,7,8,0],[5,7,9,0],[5,8,9,0],[6,7,8,9],[6,7,8,0],[6,7,9,0],[6,8,9,0],[7,8,9,0]] 
• size 5 (with 6(=6!/(5! (6-5)!)) combinations): [[5,6,7,8,9],[5,6,7,8,0],[5,6,7,9,0],[5,6,8,9,0],[5,7,8,9,0],[6,7,8,9,0]]

For each of the above arrays, we can try putting different operators between each two numbers and compute them. Note that each array also needs to be permutated - e.g. [5,6] becomes [5,6] and [6,5] so that we can try 5-6, as well as 6-5, and so on.

There is a nice little Javascript that generates combinations and k-combinations found here.
There are also plenty of permutations code, I prefer this one from crl:

function permutations(xs){
 var r=[];
 if (!xs.length)
  return [[]];
 for (var i=0;i<xs.length;i++){
  var xs_ = xs.slice();
  var x = xs_.splice(i, 1);
  var ps = permutations(xs_);
  r.splice(r.length, 0,...ps.map(psi=>x.concat(psi)))
 }
 return r;
}

So with the combinations(), k_combinations() and permutations() functions, I am well on my way to process the numbers.

Now I must stop as Letters and Numbers show is on right now! Stay tuned for Part 2.

Include a HTML File

This morning I turned on my laptop intending to quickly fill up my timesheet for the week and bugger off. However, my nerdiness toke over. I decided to improve on my work cheatsheet HTML file.

My cheatsheet is simply a static HTML file that I use as my default web page of my web browser. In the cheatsheet I put all the useful and frequently used links and information. I recently rewrote it using Javascript to dynamically update the URLs depending on whether I am on the company VPN or not. So now I have two versions of it - the new one with Javascript; and the old one in pure HTML, which has way more info than the new one. I am too lazy to migrate everything to the new one so I decided to somehow include it instead.

Since the cheatsheet is a static HTML file only, there is no web server where I can utilise the web container for including another file - e.g. the include tag in ASP/JSP or Apache web server's SSI feature... I can only rely on native HTML or Javascript.

With this constraint, I can think of basically the following approaches:
1. use iframe and this is tried and true, and simple enough to use:

<iframe src='index.htm' style="height:100%; width=100%" />

2. use XMLHttpRequest and set the xhr.responeType to "document":

        if (window.XMLHttpRequest) xhr = new XMLHttpRequest();
        else xhr = new ActiveXObject("Microsoft.XMLHTTP");
        xhr.open("GET", "file://c:/work/index.htm", true);
        xhr.responseType="document";
        xhr.onload=function(e){
            var doc=e.target.response;
            var container=document.body;
            container.appendChild(doc.querySelector('.h'));
        }    
        xhr.send();

3. use HTML5's import feature:

    if('import' in document.createElement('link')) {
        var link=document.createElement('link');
        link.rel="import";
        link.href="index.htm";
        link.onload=function(e) {
            var doc=link.import.querySelector('.h');          
            document.body.appendChild(doc.cloneNode(true));    
        };
        document.head.appendChild(link);   
    } 

Among the above methods, my preference would be HTML5, XHR and iframe, in that order. Unfortunately, XHR and HTML5 import don't allow file:// to be accessed for security reasons. So the only option left is iframe and it works well.