rush_hour.js

'use strict';

const SIZE = 6;
const BASE = SIZE - 1;
const HORI = 0;
const VERT = 1;

const SPACE = '.';
const TARGET = '+';

class Queue {
  /* add and remove are amortized O(1) */

  constructor(size) {
    this.head = 0;
    this.last = 0;
    this.q = new Array(size || 3);
  }

  resize(size) {
    var arr = new Array(size);
    var j = 0;
    for(var i = this.head; i < this.last; i++, j++) arr[j] = this.q[i];
    this.q = arr;
    this.last = j;
    this.head = 0;
  }

  shrink(){
    var j = 0;
    for(var i = this.head; i< this.last; i++, j++) this.q[j] = this.q[i];
    this.last = j;
    this.head = 0;
  }

  add(elem) {
    if (this.last === this.q.length){
      // grow q iff half of q is occupied
      if( 2*this.length > this.q.length ) this.resize(2*this.q.length+1);
      else this.shrink();
    }
    this.q[this.last++] = elem;
  }

  peek() {
    return this.q[this.head];
  }

  remove() {
    if( this.head < this.last ) return this.q[this.head++];
  }

  get length() {
    return this.last - this.head;
  }
}

function encode(pos) {
  var n = 0;
  for (var i = pos.length; i--;) n = BASE * n + pos[i];
  return n;
}

function decode(width, n) {
  var arr = new Array(width);
  for (var i = 0; i < width; i++) {
    arr[i] = n % BASE;
    n = (n - arr[i]) / BASE;
  }
  return arr;
}

function solve(game) {
  // game board
  var targetIx;
  var nBlock = 0;
  var ixToCh = {};
  var type = [];  // block type
  var bpos = [];  // block position
  var blen = [];  // block length
  var curr = [];  // initial pos

  // for neighbors
  var tmpCanvas = new Array(SIZE);
  for (let i = 0; i < SIZE; i++) tmpCanvas[i] = new Array(SIZE);

  // for bfs
  var visited = new Set();
  var parent = new Map();
  var q = new Queue();

  function parse(mat) {
    for (var i = 0; i < SIZE; i++) {
      for (var j = 0; j < SIZE; j++) {
        var c = mat[i][j];
        if (c === SPACE) continue;

        // mark target ix
        if (c === TARGET) targetIx = nBlock;

        // block found
        ixToCh[nBlock] = c;
        nBlock += 1;
        if (mat[i][j] === mat[i][j + 1]) {
          // horizonal block
          type.push(HORI);
          bpos.push(i);
          curr.push(j);
          let len = 0;
          while (mat[i][j + len] === c) {
            mat[i][j + len] = SPACE;
            len += 1;
          }
          blen.push(len);
        }
        else if (mat[i][j] === mat[i + 1][j]) {
          // vertical block
          type.push(VERT);
          bpos.push(j);
          curr.push(i);
          let len = 0;
          while (mat[i + len][j] === c) {
            mat[i + len][j] = SPACE;
            len += 1;
          }
          blen.push(len);
        }
        else throw new Error('invalid game');
      }
    }
  }

  function render(pos) {
    var canvas = new Array(SIZE);
    for (let i = 0; i < SIZE; i++) canvas[i] = new Array(SIZE);
    for (let i = SIZE; i--;) for (var j = SIZE; j--;) canvas[i][j] = SPACE;

    for (let i = 0; i < nBlock; i++) {
      if (type[i] === HORI) {
        for (let j = 0; j < blen[i]; j++) canvas[bpos[i]][pos[i] + j] = ixToCh[i];
      }
      else if (type[i] === VERT) {
        for (let j = 0; j < blen[i]; j++) canvas[pos[i] + j][bpos[i]] = ixToCh[i];
      }
    }

    return canvas.map(row => row.join('')).join('\n');
  }


  // O(size*size)
  function neighbors(n, pos) {
    var nei = [];

    // O(size*size)
    for (let i = SIZE; i--;) for (var j = SIZE; j--;) tmpCanvas[i][j] = -1;

    // O(size*size)
    for (let i = 0; i < nBlock; i++) {
      if (type[i] === HORI) {
        for (let j = 0; j < blen[i]; j++) tmpCanvas[bpos[i]][pos[i] + j] = i;
      }
      else {
        for (let j = 0; j < blen[i]; j++) tmpCanvas[pos[i] + j][bpos[i]] = i;
      }
    }

    var read = function (i, j) {
      var pos = bpos[i];
      if (type[i] === HORI) return tmpCanvas[pos][j];
      return tmpCanvas[j][pos];
    };

    // O(nBlock)
    for (var i = 0, b = 1; i < nBlock; i++, b *= BASE) {
      var l = 1, t = n;
      while (pos[i] + blen[i] + l - 1 < SIZE && read(i, pos[i] + blen[i] + l - 1) === -1) {
        t += b;
        nei.push(t);
        l++;
      }
      l = 1;
      t = n;
      while (pos[i] - l >= 0 && read(i, pos[i] - l) === -1) {
        t -= b;
        nei.push(t);
        l++;
      }
    }

    return nei;
  }

  function bfs(init) {
    visited.add(init);
    parent.set(init, null);
    q.add(init);

    while (q.length) {
      var n = q.remove();
      var pos = decode(nBlock, n);

      if (pos[targetIx] === SIZE - blen[targetIx]) return n;

      for (var t of neighbors(n, pos)) {
        if (t === n) continue;
        if (!visited.has(t)) {
          visited.add(t);
          parent.set(t, n);
          q.add(t);
        }
      }
    }
    return -1;
  }

  // append '$' for convenient bound check
  parse((game.trim() + '\n' + '$'.repeat(SIZE)).split('\n').map(x => (x.trim() + '$').split('')));

  var last = bfs(encode(curr));

  if (last < 0) console.log('(no solution)');
  else {
    let steps = [];

    while (typeof last === 'number') {
      steps.push(last);
      last = parent.get(last);
    }

    for (var i = 0; i < steps.length; i++) {
      console.log('==== step ' + i + ' ====');
      console.log(render(decode(nBlock, steps[steps.length - 1 - i])));
    }
  }
}

// UBM free expert original 372
const game1 = `
1222.3
1.4553
++4678
.99678
...CAA
BBBC..
`;

// http://code.ulb.ac.be/dbfiles/Ser2005mastersthesis.pdf, P.83
const game2 = `
14488D
155..D
2.6++C
2.699C
..7ABB
337A..
`;

// Unblock me solutions beginner level 1
const game3 = `
..4445
.....5
++3..5
..3.66
1.3.7.
12227.
`;

// Unblock me solutions beginner level 298
const game4 = `
1344..
13.5..
1++5.A
2267.A
..6799
..6888
`;

solve(game1);