Please help me speed up this mahjong algorithm

Question

I am writing some mahjong-related functions in JavaScript.

Here is what I have below, with code for test cases.

Note that mahjong hands are represented by arrays, with:

• element 0 being the total number of tiles in the hand
• elements 1 through 34 being the number of tiles of each type in the hand
  • first craks, then dots, then bams, then winds, and finally dragons

The function to find waits runs really slow. How can I speed it up?

// tiles are indexed as follows:
// 1..9 = 1 crak .. 9 crak
// 10..18 = 1 dot .. 9 dot
// 19..27 = 1 bam .. 9 bam
// 28..34 = east, south, west, north, white, green, red

var wall = new Array();
set_up_wall();

function set_up_wall() {
  for (var i=1; i<=34; i++) wall[i] = 4;
  wall[0]=136;
}

// draw tile from wall
function draw() {
  var fudge = 1-(1e-14);
  var n = Math.floor(Math.random()*wall[0]*fudge);
  var i = 1;
  while (n>=wall[i]) n-=wall[i++];
  wall[i]--;
  wall[0]--;
  return i;
}

// get number of a tile (or 0 if honor)
// e.g. 8 bams = 8
function tilenum(i) {
  if (i>27) return 0;
  if (i%9==0) return 9;
  return i%9;
}

// get suit of a tile (or 0 if honor)
function tilesuit(i) {
  var eps = 1e-10;
  return Math.ceil(i/9-eps)%4;
}

// is this a well-formed hand?
function well_formed(h) {
  // this function is recursive
  if (h[0]==2) return only_pairs(h);
  if (h[0]==14) {
    if (only_pairs(h)) return true;
    if (thirteen_orphans(h)) return true;
  }
  if (h[0]%3 != 2) return false; // wrong no. of tiles in hand
  // now we start splitting up the hand
  // look for three of a kind
  for (var i=1; i<=34; i++) {
    if (h[i]>=3) {
      // create new hand minus the three of a kind
      hh = new Array();
      for (var j=0; j<=34; j++) hh[j]=h[j];
      hh[0]-=3;
      hh[i]-=3;
      if (well_formed(hh)) return true;
    }
  }
  // look for a run of three
  for (var i=1; i<=25; i++) {
    if (tilenum(i)<=7) {
      if (h[i]>=1 && h[i+1]>=1 && h[i+2]>=1) {
      // create new hand minus the run
      hh = new Array();
      for (var j=0; j<=34; j++) hh[j]=h[j];
      hh[0]-=3;
      hh[i]--; hh[i+1]--; hh[i+2]--;
      if (well_formed(hh)) return true;
      }
    }
  }
  // if we reach here, we have exhausted all possibilities
  return false;
}

// is this hand all pairs?
function only_pairs(h) {
  for (var i=1; i<=34; i++) if (h[i]==1 || h[i]>=3) return false;
  return true;
}

// thirteen orphans?
function thirteen_orphans(h) {
  var d=0;
  var c=new Array(14, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1);
  for (var i=0; i<=34; i++) {
    if (c[i]==0 && h[i]>0) return false;
    if (h[i]!=c[i]) d++;
  }
  return d==1;
}

// this is inefficient
function waits(h) {
  var w=new Array();
  for (var j=0; j<=34; j++) w[j]=false;  
  if (h[0]%3!=1) return w; // wrong no. of tiles in hand
  // so we don't destroy h
  var hh = new Array();
  for (var j=0; j<=34; j++) hh[j]=h[j];
  for (var i=1; i<=34; i++) {
    // add the tile we are trying to test
    hh[0]++; hh[i]++;
    if (hh[i]<5) { // exclude hands waiting for a nonexistent fifth tile
      if (well_formed(hh)) {
        w[0] = true;
        w[i] = true;
      }
    }
    hh[0]--; hh[i]--;
  }
  return w;
}

function tiles_to_string(t) { // strictly for testing purposes
  var n;
  var ss="";
  var s = "x 1c 2c 3c 4c 5c 6c 7c 8c 9c 1d 2d 3d 4d 5d 6d 7d 8d 9d ";
  s += "1b 2b 3b 4b 5b 6b 7b 8b 9b Ew Sw Ww Nw Wd Gd Rd";
  s=s.split(" ");
  for (var i=1; i<=34; i++) {
    n=t[i]*1; // kludge
    while (n--) ss+=(" "+s[i]);
  }
  return ss;
}

// tests

var x;
x = new Array(13, 0,0,0,0,0,1,2,2,2, 2,2,2,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0);
document.write("Hand: "+tiles_to_string(x)+"<br />");
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />");
x = new Array(13, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1);
document.write("Hand: "+tiles_to_string(x)+"<br />");
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />");
x = new Array(13, 0,0,0,0,0,0,0,0,0, 3,1,1,1,1,1,1,1,3, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0);
document.write("Hand: "+tiles_to_string(x)+"<br />");
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />");
x = new Array(13, 4,0,0,3,3,3,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0);
document.write("Hand: "+tiles_to_string(x)+"<br />");
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />");
x = new Array(13, 0,0,4,3,3,3,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0);
document.write("Hand: "+tiles_to_string(x)+"<br />");
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />");

Answer 1

You have an array to hold the contents of the hand, and then you are creating a new array to hold the contents minus a particular set of tiles each time - in a recursive function. Instead of all this array creation, create two arrays - one to hold the hand under consideration, the other to hold the tiles from the hand that you have already considered - and just pass them both around. So this:

hh = new Array();
for (var j=0; j<=34; j++) hh[j]=h[j];
hh[0]-=3;
hh[i]-=3;
if (well_formed(hh)) return true;

becomes this:

h[0]-=3;
h[i]-=3;
hc[0]+=3;
hc[i]+=3;
if (well_formed(h,hc)) return true;

You pass both h and hc around, and bear in mind that to reconstruct the whole hand, you need to add the two arrays. But this can come right at the end of considering whether or not the hnd is complete.

EDIT: Here is what I mean in more detail: EDIT: Now working I hope... typo in first attempt.

// is this a well-formed hand?
function well_formed(h) {
  hc = new Array();
  for (var i=0; i<=34; i++) hc[i]=0;
  result = well_formed_recursive(h, hc);
  for (var i=0; i<=34; i++) h[i]+=hc[i];
  return result;
}

function well_formed_recursive(h, hc) {
  // this function is recursive
  if (h[0]==2) return only_pairs(h);
  if (h[0]==14) {
    if (only_pairs(h)) return true;
    if (thirteen_orphans(h)) return true;
  }
  if (h[0]%3 != 2) return false; // wrong no. of tiles in hand
  // now we start splitting up the hand
  // look for three of a kind
  for (var i=1; i<=34; i++) {
    if (h[i]>=3) {
      h[0]-=3;
      h[i]-=3;
      hc[0]+=3;
      hc[i]+=3;
      if (well_formed_recursive(h,hc)) return true;
    }
  }
  // look for a run of three
  for (var i=1; i<=25; i++) {
    if (tilenum(i)<=7) {
      if (h[i]>=1 && h[i+1]>=1 && h[i+2]>=1) {
        h[0]-=3;
        h[i]--; h[i+1]--; h[i+2]--;
        hc[0]+=3;
        hc[i]++; hc[i+1]++; hc[i+2]++;
        if (well_formed_recursive(h,hc)) return true;
      }
    }
  }
  // if we reach here, we have exhausted all possibilities
  return false;
}

Answer 2

To duplicate an array use the concat function.

var a=[1,2,3,4];
var b=a.concat();

Answer 3

Two things wrong performance-wise, that I can see.

First is what David M has already noted: stop copying the whole array every time you recurse in well_formed(), just add in the changes before you recurse and back out the additions when you return, just as you did in your waits() function.

Second is that in well_formed() you keep rescanning the whole array every time you make a single incremental change to the hand. That's inherently inefficient, instead you should look for opportunities to keep "state counters" instead.

For instance you could easily check for only_pairs() if you always know how many pairs you had. Instead of scanning the hand() array for any non-pairs, you keep a pairs_counter as part of the array (or its associated context), whenever you add a card to hand[i] then you check if hand[i]=2 you increment the pairs counter if it's 3, you decrement it. Likewise when you remove a card, if hand[j] = 2 you increment the pairs counter, but if it equals 1 your decrement it.

There are a number of places where you can employ this strategy and it will have a big impact on your performance.