RuCTF PPC 400pt minesweaper

minesweaper.js

// run this at http://vuln1.quals.ructf.org/saper/www/

// https://github.com/timjb/minesweeper-solver/blob/gh-pages/solver.js
var MineSweeper = (function () {
  function repeat (el, times) {
    var arr = [];
    for (var i = 0; i < times; i++) {
      arr[i] = el;
    }
    return arr;
  }

  function randomInt (n) {
    return Math.floor(Math.random() * n);
  }

  function randomElement (arr) {
    return arr[randomInt(arr.length)];
  }

  function range (s, e) {
    var arr = [];
    while (s <= e) { arr.push(s++); }
    return arr;
  }

  function forEachNeighbor (x, y, width, height, fn) {
    function call (x, y) {
      if (x >= 0 && x < width && y >= 0 && y < height) {
        fn(x, y);
      }
    }

    call(x-1, y-1);
    call(x,   y-1);
    call(x+1, y-1);
    call(x-1, y);
    call(x+1, y);
    call(x-1, y+1);
    call(x,   y+1);
    call(x+1, y+1);
  }

  function Field (width, height, minesCount) {
    this.width = width;
    this.height = height;
    this.minesCount = minesCount;
    this.left = width*height - minesCount;

    this.mines = repeat(false, width*height);
    this.covered = repeat(true, width*height);
//    this.distributeMines(minesCount);
  }

  Field.prototype.distributmineseMines = function (n) {
    while (n > 0) {
      var i;
      do {
        i = randomInt(this.width*this.height);
      } while (this[i]);
      this.mines[i] = true;
      n--;
    }
  };

  Field.prototype.getIndex = function (x, y) {
    return y*this.width + x;
  };

  Field.prototype.isCovered = function (x, y) {
    return this.covered[this.getIndex(x, y)];
  };

  Field.prototype.blowUp = function (x, y) {
    throw new Error("KAAAWUMMMMM!");
  };

  Field.prototype.uncover = function (x, y) {
    var self = this;

    function isMine (x, y) { return self.mines[self.getIndex(x, y)]; }

    if (isMine(x, y)) {
      return this.blowUp(x, y);
    }

    var i = this.getIndex(x, y);
    if (this.covered[i]) {
      this.covered[i] = false;
      this.left--;
    }

    var count = 0;
    forEachNeighbor(x, y, this.width, this.height, function (x, y) {
      if (isMine(x, y)) { count++; }
    });
    return count;
  };


  function Solver (field) {
    this.field = field;
    this.width = field.width;
    this.height = field.height;
    this.frontier = [];
    var n = this.width*this.height;

    this.cells = [];
    for (var i = 0; i < n; i++) {
      this.cells[i] = [];
    }
    this.createConstraint(field.minesCount, range(0, n-1));
  }

  var count = 0;
  function Constraint (mines, cells) {
    this.mines = mines;
    this.cells = cells;
    this.unifiedWith = [];
    this.count = count++;
  }

  Solver.prototype.createConstraint = function (mines, cells, uncoverImmediately) {
    if (mines === 0) {
      if (uncoverImmediately) {
//        this.uncoverImmediately(cells);
      } else {
//        this.uncoverLater(cells);
      }
    }

    var constraint = new Constraint(mines, cells);
    for (var i = 0, l = cells.length; i < l; i++) {
      this.cells[cells[i]].push(constraint);
    }
    var overlapping = this.getOverlappingConstraints(constraint);
    for (i = 0, l = overlapping.length; i < l; i++) {
      if (this.unifyConstraints(constraint, overlapping[i])) { break; }
    }
  };

  Solver.prototype.removeConstraint = function (constraint) {
    for (var i = 0, l = constraint.cells.length; i < l; i++) {
      var cell = this.cells[constraint.cells[i]];
      var index = cell.indexOf(constraint);
      cell.splice(index, 1);
    }
  };

  Solver.prototype.getOverlappingConstraints = function (constraint) {
    var arr = [];
    for (var i = 0, l = constraint.cells.length; i < l; i++) {
      var cell = this.cells[constraint.cells[i]];
      for (var j = 0, k = cell.length; j < k; j++) {
        if (cell[j] !== constraint && arr.indexOf(cell[j]) === -1) {
          arr.push(cell[j]);
        }
      }
    }
    return arr;
  };

  Solver.prototype.unifyConstraints = function (a, b) {
    if (a.cells.length < b.cells.length) {
      var tmp = a;
      a = b;
      b = tmp;
    }
    a.unifiedWith.push(b);
    b.unifiedWith.push(a);

    var inA = [];
    var inB = [];
    var inAB = [];

    for (var i = 0, l = a.cells.length; i < l; i++) {
      if (b.cells.indexOf(a.cells[i]) !== -1) {
        inAB.push(a.cells[i]);
      } else {
        inA.push(a.cells[i]);
      }
    }

    for (i = 0, l = b.cells.length; i < l; i++) {
      if (inAB.indexOf(b.cells[i]) === -1) { inB.push(b.cells[i]); }
    }

    var aMore = a.mines - b.mines;
    if (aMore === inA.length) {
      this.removeConstraint(a);
      this.removeConstraint(b);
      this.createConstraint(aMore, inA);
      this.createConstraint(b.mines, inAB);
      this.createConstraint(0, inB);
      return true;
    }
    if (b.mines - a.mines === inB.length) {
      this.removeConstraint(a);
      this.removeConstraint(b);
      this.createConstraint(b.mines - a.mines, inB);
      this.createConstraint(a.mines, inAB);
      this.createConstraint(0, inA);
      return true;
    }
    if (inB.length === 0) {
      this.removeConstraint(a);
      this.removeConstraint(b);
      this.createConstraint(aMore, inA);
      // Re-add b
      this.createConstraint(b.mines, b.cells);
      return true;
    }
    if (b.mines === b.cells.length) {
      this.removeConstraint(a);
      this.removeConstraint(b);
      this.createConstraint(a.mines - inAB.length, inA);
      this.createConstraint(b.mines, b.cells);
      return true;
    }
    if (a.mines === a.cells.length) {
      this.removeConstraint(b);
      this.removeConstraint(a);
      this.createConstraint(b.mines - inAB.length, inB);
      this.createConstraint(a.mines, a.cells);
      return true;
    }
    return false;
  };

  Solver.prototype.uncoverImmediately = function (cells) {
    for (var i = 0, l = cells.length; i < l; i++) {
      var pos = this.fromIndex(cells[i]);
      var j = this.frontier.indexOf(cells[i]);
      if (j !== -1) { this.frontier.splice(j, 1); }
      this.uncover(pos[0], pos[1]);
    }
  };

  Solver.prototype.uncoverLater = function (cells) {
    for (var i = 0, l = cells.length; i < l; i++) {
      if (this.field.covered[cells[i]] && this.frontier.indexOf(cells[i]) === -1) {
        this.frontier.push(cells[i]);
      }
    }
  };

  Solver.prototype.uncover = function (x, y) {
    var mines = this.field.uncover(x, y);

    var index = this.field.getIndex(x, y);
    this.createConstraint(0, [index]);

    var neighbors = [];
    var self = this;
    forEachNeighbor(x, y, this.width, this.height, function (x, y) {
      if (self.field.isCovered(x, y)) {
        var index = self.field.getIndex(x, y);
        neighbors.push(index);
      }
    });
    this.createConstraint(mines, neighbors, mines === 0);
  };

  Solver.prototype.getProbability = function (x, y) {
    var constraints = this.cells[this.field.getIndex(x, y)];
    var p = 0;
    for (var i = 0, l = constraints.length; i < l; i++) {
      var constraint = constraints[i];
      p = Math.max(p, constraint.mines / constraint.cells.length);
    }
    return p;
  };

  Solver.prototype.guess = function () {
    var best = [], bestP = 1;
    for (var x = 0; x < this.width; x++) {
      for (var y = 0; y < this.height; y++) {
        if (this.field.isCovered(x, y)) {
          var p = this.getProbability(x, y);
          if (p === bestP) {
            best.push([x, y]);
          } else if (p < bestP) {
            bestP = p;
            best = [[x, y]];
          }
        }
      }
    }

    if (bestP !== 1) {
      for (var i=0,l=best.length*(1-bestP);i<l;++i) {
        this.uncover(best[i][0], best[i][1]);
      }
    } else {
      console.log('nothing to do...')
    }
  };

  Solver.prototype.fromIndex = function (i) {
    return [i % this.width, Math.floor(i/this.width)];
  };

  Solver.prototype.step = function () {
    if (this.frontier.length > 0) {
      var pos = this.fromIndex(this.frontier.pop());
      this.uncover(pos[0], pos[1]);
    } else {
      this.guess();
    }
  };

  Solver.prototype.solve = function () {
    while (this.field.left > 0) { this.step(); }
  };

  Solver.prototype.isFlagged = function (x, y) {
    var constraints = this.cells[this.field.getIndex(x, y)];
    for (var i = 0, l = constraints.length; i < l; i++) {
      var constraint = constraints[i];
      if (constraint.cells.length === constraint.mines) { return true; }
    }
    return false;
  };

  Solver.prototype.render = function () {
    var html = '';
    html += '<table>';
    for (var y  = 0; y < this.height; y++) {
      html += '<tr>';
      for (var x = 0; x < this.width; x++) {
        if (this.frontier.indexOf(this.field.getIndex(x, y)) !== -1) {
          html += '<td class="frontier">';
        } else {
          html += '<td>';
        }
        if (!this.field.isCovered(x, y)) {
          var mines = this.field.uncover(x, y);
          html += '<span class="mines-' + mines + '">' + mines + '</span>';
        } else if (this.isFlagged(x, y)) {
          html += '<span class="flag">F</span>';
        }
        html += '</td>';
      }
      html += '</tr>';
    }
    html += '</table>';
    return html;
  };

  Solver.prototype.renderAscii = function () {
    var str = '';
    for (var y  = 0; y < this.height; y++) {
      for (var x = 0; x < this.width; x++) {
        if (!this.field.isCovered(x, y)) {
          var mines = this.field.uncover(x, y);
          str += mines;
        } else if (this.isFlagged(x, y)) {
          str += "F";
        } else {
          str += ' ';
        }
      }
      str += '\n';
    }
    return str;
  };

  return {
    Field: Field,
    Solver: Solver
  };

})();

// mine sweeper solver for ructf
var blockWidth = 16;
var blockHeight = 16;
var width = 480;
var height = 256;
var blockTypeMap = {
  31: 0,
  40: 1,
  65: 2,
  62: 3,
  56: 4,
  70: 5,
  76: 'a', // 爆弾ブロック
  148: 'b', //まだ空いてないブロック
  144: 'c', // 最初に空ける黒いやつ
  109: 'd' // フラグ
};
var getBlockMap = function(image, callback) {
  var canvas = document.createElement('canvas');
  canvas.width = width;
  canvas.height = height;
  var ctx = canvas.getContext('2d');
  var img = new Image();
  //img.src = 'http://vuln1.quals.ructf.org/saper/www/games/ievqhtppeqn6edud78btvuero6.png';
  img.src = image;
  img.onload = function() {
    ctx.drawImage(img, 0, 0);
    setTimeout(function() {
      var map = mapping();
      callback(map);
    }, 30);
  };

  var getBlockType = function(x, y) {
    var data = ctx.getImageData(x * blockWidth, y * blockHeight, blockWidth, blockHeight).data;
    var colorMap = [];
    for (var i=0;i<blockHeight*blockWidth;++i) {
      var red = data[i*4];
      var blue = data[i*4 + 1];
      var green = data[i*4 + 2];
      var alpha = data[i*4 + 3];
      colorMap[red*256*256 + blue*256 + green] = (colorMap[red*256*256 + blue*256 + green] || 0) + 1;
    }
    var maxCount = colorMap.sort(function(a, b){
      return b - a;
    })[0];
    return blockTypeMap[maxCount];
  };

  var mapping = function() {
    var map = [];
    for (var y=0;y<height/blockHeight;++y) {
      map[y] = [];
      for (var x=0;x<width/blockWidth;++x) {
        map[y][x] = getBlockType(x, y);
      }
    }
    return map;
  };
};

var solver = function(map) {
  var covered = [];
  var position = null;
  map.forEach(function(line, y) {
    line.forEach(function(point, x) {
      if (map[y][x] === 'b' || map[y][x] === 'c' || map[y][x] === 'd') {
        covered.push([x, y]);
      }
      if (point === 'c') {
        position = {
          x: x,
          y: y
        };
        clickBlock(position);
      }
    })
  });
  if (covered.length === 99) {
    console.log('clear!');

    // 残ったのが99個なら全部flagにする
    for (var i=0;i<covered.length;++i) {
      $.ajax({
        type: 'post',
        url:  'engine.php',
        data: {
          i: covered[i][1],
          j: covered[i][0],
          btn: 2
        },
        dataType: 'xml',
      });
    }
    return;
  }
  if (position) {
    return;
  }

  var field = new MineSweeper.Field(width / blockWidth, height / blockHeight, 99);
  field.isCovered = function(x, y) {
    return map[y][x] === 'b' || map[y][x] === 'c' || map[y][x] === 'd';
  };
  field.uncover = function(x, y) {
    if (!this.isCovered(x, y)) {
      return map[y][x];
    } else {
      console.log('open', x, y)
      clickBlock({
        x: x,
        y: y
      });
    }
  };
  var solver = new MineSweeper.Solver(field);
  map.forEach(function(line, y) {
    line.forEach(function(point, x) {
      if (isNaN(map[y][x])) {
        return;
      }
      solver.uncover(x, y);
    });
  });
  solver.guess();
};

var wait = 0;
var preImage;
var clickBlock = function(position) {
  ++wait;
  $.ajax({
    type: 'post',
    url:  'engine.php',
    data: {
      i: position.y,
      j: position.x,
      btn: 1
    },
    dataType: 'xml',
    success: function(data) {
      --wait;
      start_timer();
      var root = data.getElementsByTagName('root')[0];
      var img = root.getElementsByTagName('img')[0].childNodes[0];
      var status = root.getElementsByTagName('status')[0].childNodes[0].nodeValue;
      if (status === 'error') {
        console.log('error');
      }
      if (!img) {
        console.log('something wrong?');
        src = preImage;
      } else {
        src = img.nodeValue;
      }
      preImage = src;
      if (wait === 0) {
        update_screen(data);
        getBlockMap(src, solver);
      }
    }
  });
};

getBlockMap($('#click_box').attr('src'), solver);

I tried to run it using Greasmonkey, but Firefox froze or did not respond if I'm not mistaken.

Is this the correct way to run the script? Maybe I did something wrong while trying to start it.

Thank you!