abcdefghppp.js

function abcdefghppp(base, width, callback){
  var i;
  var cnt = 0;
  var used1 = new Array(base);
  var used2 = new Array(base);
  var sp = new Array(width);

  var table = new Array(base);
  for(i=0; i<base; i++) table[i] = new Array(base);
  var tableLen = new Array(base);

  var N = (base-2*width-1)*(base-2*width-2);
  var va = new Array(N);
  var vb = new Array(N);
  var br = new Array(N);

  // for storing candidate of digits of a and b
  var vs = new Array(base-2*width-1);

  // EXP[i] = base^i
  var EXP = new Array(width);
  EXP[0] = 1;
  for(i=1; i<width; i++) EXP[i] = base*EXP[i-1];

  // value of e
  var e = 1;
  for(i=0; i<width; i++) e = base*e+1;

  // just to make sure b has at least width digits
  var MIN=1;
  for(i=1; i<width; i++) MIN = MIN*base;

  // used-tables helpers
  function reset(used){
    for(var i=0; i<used.length; i++) used[i] = false;
    used[1] = true;
  }
  function checkWrite(used, a){
    // mutable check
    for(var i=width; i--;){
      var t = a%base;
      if( used[t] ) return false;
      used[t] = true;
      a = (a-t)/base;
    }
    return true;
  }

  // return true to break
  function generate(w,c){
    if( w === width ){
      var d = e - c;
      if( d < c ) return true;    // due to symmetry of c and d
      reset(used2);
      if( checkWrite(used2, c) && checkWrite(used2, d) ) solveAB(c);
      return false;
    }

    // left-most digit cannot start with zero and one is used
    var start = w === 0 ? 2 : 0;
    for(var i=start; i<base; i++){
      if( used1[i] ) continue;
      used1[i] = true;
      if( generate(w+1, base*c+i) ) return true;
      used1[i] = false;
    }
    return false;
  }

  function solveAB(c){
    var i,j,t;

    // possible digits in a and b
    for(i=0,j=0; i<used2.length; i++) if( !used2[i] ) vs[j++] = i;

    // clear table
    for(i=0; i<base; i++) tableLen[i] = 0;

    // O( B*B )
    t=0;
    for(i=0; i<vs.length; i++){
      for(j=i+1; j<vs.length; j++){
        var v1 = vs[i], v2 = vs[j];
        var i1 = v2-v1, i2 = base+v1-v2;

        table[i1][tableLen[i1]++] = t;
        va[t] = v2; vb[t] = v1; br[t] = 0;
        t++;

        table[i2][tableLen[i2]++] = t;
        va[t] = v1; vb[t] = v2; br[t] = 1;
        t++;
      }
    }

    function diffSearch(i, borrow, a, b){
      if( i === width ){
        if( a > b && b > MIN ){
          cnt++;
          callback(a,b,c,e-c);
        }
        return;
      }
      var di = sp[i] + borrow;
      if( di === base ) return;    // this implies that a0 = b0 = 0, so not a solution
      var vec = table[di], len = tableLen[di];
      for(var j=0; j<len; j++){
        var t = vec[j], a0 = va[t], b0 = vb[t];
        if( used2[a0] || used2[b0] ) continue;
        used2[a0] = used2[b0] = true;
        diffSearch(i+1, br[t], a+a0*EXP[i], b+b0*EXP[i]);
        used2[a0] = used2[b0] = false;
      }
    }

    for(i=0, t=c; i<width; i++, t = Math.floor(t/base) ) sp[i] = t%base;
    diffSearch(0, 0, 0, 0);
    // due to symmetry of c and d
    c = e - c;
    for(i=0, t=c; i<width; i++, t = Math.floor(t/base) ) sp[i] = t%base;
    diffSearch(0, 0, 0, 0);
  }

  reset(used1);
  generate(0,0);

  return cnt;
}

var base = 17, width = 4;
console.log('number of solution: ', abcdefghppp(base, width, function(a,b,c,d){
  var sa = a.toString(base);
  var sb = b.toString(base);
  var sc = c.toString(base);
  var sd = d.toString(base);
  var se = (a-b+d).toString(base);
  console.log([sa,'-',sb,'=',sc,', ',sc,'+',sd,'=',se].join(''));
}));