Bashni.org game solver

(function() {
  var spendingLimit, solutionExpectation;

  var firstWaveLevelLimit = 6;

  //solutionExpectation = 90;
  //spendingLimit = 16;

  var totalVariantsLimit = 7000000;
  var statStep = 100000;

  var startTime = new Date();

  var colors = [
    {value: 'rgb(0, 150, 150)', name: 'azure'},
    {value: 'rgb(208, 0, 0)', name: 'red'},
    {value: 'rgb(0, 51, 153)', name: 'blue'},
    {value: 'rgb(150, 100, 0)', name: 'brown'},
    {value: 'rgb(0, 102, 0)', name: 'green'},
    {value: 'rgb(198, 0, 149)', name: 'purple'},
    {value: 'rgb(248, 128, 0)', name: 'orange'},
    {value: 'rgb(182, 219, 222)', name: 'white'},
    {value: 'rgb(231, 243, 162)', name: 'yellow'},
    {value: 'rgb(102, 51, 0)', name: 'chocolate'}
  ];

  var GetColorByValue = function(value) {
    for(var i = 0; i < colors.length; i++)
      if(colors[i].value == value) return i;
  }

  //Get matrix
  var matrix = [];
  var table = $('table.bigcell');
  $('dd', table).each(function(){
    var id = this.id.split('_');
    if(!(id[2] in matrix)) matrix[id[2]] = [];

    if(this.className == 'bricks') {
      var num = parseInt(this.innerHTML) || 0;
      //Block format - [colorIndex, topNum, bottomNum]
      matrix[id[2]][id[1]] = [GetColorByValue(this.style.backgroundColor), num, num];
    }
  });

  //Normalize
  for(var i = 0; i < matrix.length; i++) {
    var column = matrix[i];

    for(var n = 0; n < column.length; n++) {
      var block = column[n];

      //Concat sibling blocks
      if(n > 0) {
        var prev = column[n-1];
        if(block[0] == prev[0] && prev[1] - block[2] == 1) {
          prev[1]--;
          column.splice(n, 1);
          n--;
        }
      }
    }
  }

  var emptyFunction = function(){};

  var solution = null;
  var matrixHash = {};
  var queue = [];

  //History
  var history = {
    length: 0,
    spending: 0,

    add: function(value) {
      if(!(value.status == 2 || (value.status == 0 && value.block[2] == 6 && value.sourceSnap)))
        this.spending++;
      this[this.length++] = value;
    },

    statusList: {
      0: 'empty column',
      1: 'move',
      2: 'siblings'
    },

    show: function() {
      for(var i = 0; i < this.length; i++) {
        var row = this[i];
        var block = '[' + colors[row.block[0]].name + ' ' + row.block[1] + ' - ' + row.block[2] + ']';
        console.log((i + 1) + '\t' + block + '\tfrom ' + (row.from + 1) + ' to ' + (row.to + 1)
          + '\t(' + this.statusList[row.status] + ')');
      }
    },

    checkCycling: function() {
      if(this.length > 1) {
        var last = this[this.length - 1];
        for(var n = this.length - 1; n--;) {
          var row = this[n];

          if(row.block[0] == last.block[0] && row.block[2] == last.block[2]) {
            //Check previous moving
            if(n == this.length - 2) return false;
            else {
              //Check block returns (exlude empty columns)
              if(last.targetSnap == row.sourceSnap && last.targetSnap != '') return false;
            }
          }
        }
      }

      return true;
    },

    price: function() {
      return this.length - this.spending;
    },

    proto: function() {
      emptyFunction.prototype = this;
      return new emptyFunction();
    }
  }

  var totalCounter = 0;
  var varCounter = 0;
  var varReadyCounter = 0;

  var variant = function(matrix, history, moving) {
    //First solution cap check
    if(solution && (history.length >= solution.length - 1 || history.spending >= solution.spending))
      return this;

    totalCounter++;

    if(totalCounter > totalVariantsLimit) return this;

    if(totalCounter%statStep == 0) ShowStat('Pending');

    this.history = history.proto();

    //Clone matrix
    this.matrix = [];
    for(var i = 0; i < matrix.length; i++) {
      this.matrix[i] = matrix[i].slice(0);
    }

    //Apply moving
    if(moving) {
      this.moveBlock.apply(this, moving);
      if(!this.history.checkCycling()) return this;
    }

    //Check siblings
    this.checkSiblings();

    //Second solution cap check (after moving and siblings)
    if(solution && this.history.length >= solution.length) return this;

    //Check spending limit
    if(spendingLimit && this.history.spending > spendingLimit) return this;

    //Check matrix hash
    var hash = [];
    for(var i = 0; i < this.matrix.length; i++) hash.push(this.matrix[i].toString());
    hash = hash.join('|');

    var price = this.history.spending;
    if(matrixHash[hash] !== undefined && price >= matrixHash[hash]) return this;
    else matrixHash[hash] = price;

    varCounter++;

    //Check ready
    if(this.checkReady()) {
      solution = this.history;
      console.log('Solution found: ' + this.history.length);

      varReadyCounter++;
      return this;
    }

    this.prepared = true;
  }
  variant.prototype = {
    findVariants: function() {
      varReadyCounter++;

      for(var i = 0; i < this.matrix.length; i++) {
        var column = this.matrix[i];
        if(column.length == 0) continue;

        var block = column[column.length - 1];
        if(block[2] == 6 && column.length == 1) continue; //skip 6-bottom single block

        for(var n = 0; n < this.matrix.length; n++) {
          if(i == n) continue;

          var status = this.checkMove(block, n);
          if(status == 0 && column.length == 1) continue; //skip moving between empty columns

          if(status >= 0) {
            var branch = new variant(this.matrix, this.history, [block, i, n, status]);
            if(branch.prepared) {
              if(branch.history.spending < firstWaveLevelLimit) branch.findVariants();
              else {
                var price = branch.history.price();
                if(!queue[price]) queue[price] = [];
                queue[price].push(branch);
              }
            }
          }
        }
      }
    },

    checkReady: function() {
      var emptyCount = 0;
      for(var i = 0; i < this.matrix.length; i++) {
        if(this.matrix[i].length > 1) return false;
        if(this.matrix[i].length == 0) emptyCount++;
      }

      return emptyCount == 2;
    },

    checkSiblings: function() {
      var movingsCount = 0;

      main:for(var i = 0; i < this.matrix.length; i++) {
        var column = this.matrix[i];

        if(column.length > 0) {
          var block = column[column.length - 1];

          for(var n = 0; n < this.matrix.length; n++) {
            if(n == i) continue;

            if(this.checkMove(block, n) == 2 && block[1] <= 1) {
              this.moveBlock(block, i, n, 2);
              movingsCount++;
              continue main;
            }
          }
        }
      }

      if(movingsCount > 0) arguments.callee.call(this);
    },

    moveBlock: function(block, sourceColumnIndex, targetColumnIndex, status) {
      var sourceColumn = this.matrix[sourceColumnIndex];
      var targetColumn = this.matrix[targetColumnIndex];

      sourceColumn.length--;

      var targetSnap = targetColumn.toString();

      if(status == 2) {
        var last = targetColumn[targetColumn.length - 1];
        targetColumn[targetColumn.length - 1] = [last[0], block[1], last[2]];
      }
      else targetColumn.push(block);

      this.history.add({
        block: block,
        from: sourceColumnIndex,
        to: targetColumnIndex,
        status: status,
        sourceSnap: sourceColumn.toString(),
        targetSnap: targetSnap
      });
    },

    // 0 - empty column, -1 - can't move, 1 - can move, 2 - siblings
    checkMove: function(block, targetColumnIndex) {
      var targetColumn = this.matrix[targetColumnIndex];

      if(targetColumn.length == 0) return 0;

      var last = targetColumn[targetColumn.length - 1];
      if(block[0] == last[0] && block[2] < last[1])
        return (block[2] == last[1] - 1) ? 2 : 1;

      return -1;
    },
  };

  function FormatNumber(num) {
    var num = num.toString();
    var result = [];
    for(var l = num.length; l--; ) {
      result.push(num.charAt(l));
      if((num.length - l)%3 == 0 && l > 0) result.push(' ');
    }
    return result.reverse().join('');
  }

  function ShowStat(text) {
    console.log(text
      + ' || Created variants total: ' + FormatNumber(totalCounter)
      + ', useful: ' + FormatNumber(varCounter)
      + ', processed: ' + FormatNumber(varReadyCounter)
      + ', queue size: ' + FormatNumber(varCounter - varReadyCounter)
    );
  }

  console.log('Start solving');

  //Run first wave
  var root = new variant(matrix, history);
  root.findVariants();

  ShowStat('Initial wave');

  if(!solution) {
    var i = 100000000;
    while(i--) {
      if(solutionExpectation && solution && solution.length <= solutionExpectation) {
        ShowStat('Solution with the expected length was found');
        break;
      }

      var n = queue.length;
      if(n == 0) {
        ShowStat('Queue is over');
        break;
      }

      while(n--) {
        var row = queue[n];
        if(row && row.length) {
          row.shift().findVariants();
          break;
        }
        else queue.length--;
      }
    }
  }

  var totalTime = (new Date() - startTime) / 1000;
  console.log('Total time: ' + Math.round(totalTime / 60) + 'm ' + Math.round(totalTime % 60) + 's');

  //Help GC to free the memory
  matrixHash = null;
  queue = null;

  if(solution) {
    solution.show();

    if(confirm('Run solution: ' + solution.length + '?')) {
      var area = $('table.bigcell tr:first');

      var i = 0;
      var solver = function() {
        var step = solution[i];

        $('td:nth-child(' + (parseInt(step.from) + 1) + ') dd', area).trigger('click');
        $('td:nth-child(' + (parseInt(step.to) + 1) + ') dd', area).trigger('click');

        if(i < solution.length - 1) {
          i++;
          setTimeout(solver, 500);
        }
      }

      solver();
    }
  }
})();