////////////////////////////////////////////////////////////////

// Board as linear array.

////////////////////////////////////////////////////////////////

/* Create board on linear array.

 * Extract data from 'brd' (which is 2d array) if present. */

function BoardArr(brd) {

    this.brd = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];

    if (brd) {

        for (var i = 0; i < 4; i++)

            for (var j = 0; j < 4; j++)

                this.brd[4*i + j] = brd[i][j];

    }

}

/* Doesn't designed to be efficient. */

BoardArr.prototype.get = function(i, j) {

    return this.brd[4*i + j];

}

/* Doesn't designed to be efficient. */

BoardArr.prototype.set = function(i, j, val) {

    this.brd[4*i + j] = val;

}

/* Return and optionally fill 2d board.

 * Doesn't designed to be efficient. */

BoardArr.prototype.exportTo = function(brd) {

    brd = brd || [[],[],[],[]];

    for (var i = 0; i < 4; i++)

        for (var j = 0; j < 4; j++)

            brd[i][j] = this.brd[4*i + j];

    return brd;

}

BoardArr.prototype.copy = function(brd) {

    brd = brd || new BoardArr();

    for (var i = 0; i < 16; i++)

        brd.brd[i] = this.brd[i];

    return brd;

}

////////////////////////////////////////////////////////////////

// Board as 2d array.

////////////////////////////////////////////////////////////////

/* Create board on 2d array.

 * Extract data from brd (which is 2d array) if present. */

function BoardArr2d(brd) {

    this.brd = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]];

    if (brd) {

        for (var i = 0; i < 4; i++)

            for (var j = 0; j < 4; j++)

                this.brd[i][j] = brd[i][j];

    }

}

BoardArr2d.prototype.get = function(i, j) {

    return this.brd[i][j];

}

BoardArr2d.prototype.set = function(i, j, val) {

    this.brd[i][j] = val;

}

BoardArr2d.prototype.equals_loop = function(brd) {

    for (var i = 0; i < 4; i++)

        for (var j = 0; j < 4; j++)

            if (this.brd[i][j] !== brd.brd[i][j])

                return false;

    return true;

}

BoardArr2d.prototype.equals_unrolled = function(brd) {

    var x0 = this.brd[0], x1 = this.brd[1], x2 = this.brd[2], x3 = this.brd[3]

    var y0 = brd.brd[0], y1 = brd.brd[1], y2 = brd.brd[2], y3 = brd.brd[3];

    // More often corners differ, check it first.

    return x0[0] === y0[0] && x0[3] === y0[3] && x3[0] === y3[0] && x3[3] === y3[3]

        && x0[1] === y0[1] && x0[2] === y0[2]

        && x3[1] === y3[1] && x3[2] === y3[2]

        && x1[0] === y1[0] && x1[1] === y1[1] && x1[2] === y1[2] && x1[3] === y1[3]

        && x2[0] === y2[0] && x2[1] === y2[1] && x2[2] === y2[2] && x2[3] === y2[3];

}

BoardArr2d.prototype.equals = BoardArr2d.prototype.equals_unrolled;

/* Return and optionally fill 2d board. */

BoardArr2d.prototype.exportTo = function(brd) {

    brd = brd || [[],[],[],[]];

    for (var i = 0; i < 4; i++)

        for (var j = 0; j < 4; j++)

            brd[i][j] = this.brd[i][j];

    return brd;

}

BoardArr2d.prototype.copy = function(brd) {

    brd = brd || new BoardArr2d();

    for (var i = 0; i < 4; i++)

        for (var j = 0; j < 4; j++)

            brd.brd[i][j] = this.brd[i][j];

    return brd;

}

BoardArr2d.prototype.free = function() {

    var cnt = 0;

    for (var i = 0; i < 4; i++)

        for (var j = 0; j < 4; j++)

            if (this.brd[i][j] === 0)

                cnt++;

    return cnt;

}

BoardArr2d.prototype.score = function() {

    var score = 0;

    for (var i = 0; i < 4; i++) {

        for (var j = 0; j < 4; j++) {

            var v = this.brd[i][j];

            if (v > 0)

                score += (v-1)*Math.pow(2, v);

        }

    }

    return score;

}

BoardArr2d.prototype.max = function() {

    var max = 0;

    for (var i = 0; i < 4; i++) {

        for (var j = 0; j < 4; j++) {

            max = Math.max(max, this.brd[i][j]);

        }

    }

    return max;

}

BoardArr2d.prototype.find = function(val) {

    var xy = [];

    for (var i = 0; i < 4; i++) {

        for (var j = 0; j < 4; j++) {

            if (this.brd[i][j] === val)

            xy.push([i,j]);

        }

    }

    return xy;

}

BoardArr2d.prototype.atEdge = function(val) {

    var brd = this.brd;

    return (brd[0][0] === val) || (brd[0][1] === val) || (brd[0][2] === val) || (brd[0][3] === val)

        || (brd[1][0] === val) || (brd[1][3] === val)

        || (brd[2][0] === val) || (brd[2][3] === val)

        || (brd[3][0] === val) || (brd[3][1] === val) || (brd[3][2] === val) || (brd[3][3] === val);

}

BoardArr2d.prototype.atCorner = function(val) {

    var brd = this.brd;

    return (brd[0][0] === val) || (brd[0][3] === val) || (brd[3][0] === val) || (brd[3][3] === val);

}

BoardArr2d.prototype.canRight = function() {

    for (var i = 0; i < 4; i++) {

        var f0 = this.brd[i][0], f1 = this.brd[i][1], f2 = this.brd[i][2], f3 = this.brd[i][3];

        if (f2 > 0 && (f2 === f3 || f3 === 0))

            return true;

        if (f1 > 0 && (f1 === f2 || f2 === 0))

            return true;

        if (f0 > 0 && (f0 === f1 || f1 === 0))

            return true;

    }

    return false;

}

BoardArr2d.prototype.canLeft = function() {

    for (var i = 0; i < 4; i++) {

        var f0 = this.brd[i][0], f1 = this.brd[i][1], f2 = this.brd[i][2], f3 = this.brd[i][3];

        if (f1 > 0 && (f1 === f0 || f0 === 0))

            return true;

        if (f2 > 0 && (f2 === f1 || f1 === 0))

            return true;

        if (f3 > 0 && (f3 === f2 || f2 === 0))

            return true;

    }

    return false;

}

BoardArr2d.prototype.canUp = function() {

    for (var j = 0; j < 4; j++) {

        var f0 = this.brd[0][j], f1 = this.brd[1][j], f2 = this.brd[2][j], f3 = this.brd[3][j];

        if (f1 > 0 && (f1 === f0 || f0 === 0))

            return true;

        if (f2 > 0 && (f2 === f1 || f1 === 0))

            return true;

        if (f3 > 0 && (f3 === f2 || f2 === 0))

            return true;

    }

    return false;

}

BoardArr2d.prototype.canDown = function() {

    for (var j = 0; j < 4; j++) {

        var f0 = this.brd[0][j], f1 = this.brd[1][j], f2 = this.brd[2][j], f3 = this.brd[3][j];

        if (f2 > 0 && (f2 === f3 || f3 === 0))

            return true;

        if (f1 > 0 && (f1 === f2 || f2 === 0))

            return true;

        if (f0 > 0 && (f0 === f1 || f1 === 0))

            return true;

    }

    return false;

}

BoardArr2d.prototype.shiftLeft_unrolled = function(brd) {

    var from = this.brd, to = brd.brd;

    for (var i = 3; i >= 0; i--) {

        var f0 = from[i][0], f1 = from[i][1], f2 = from[i][2], f3 = from[i][3];

        if (f3 === 0) {

            to[i][0] = 0;

            if (f2 === 0) {

                to[i][1] = 0;

                if (f1 === 0) {      // a 0 0 0

                    to[i][2] = 0;

                    to[i][3] = f0;

                } else {

                    if (f0 === f1) {   // a a 0 0

                        to[i][2] = 0;

                        to[i][3] = f0 + 1;

                    } else {           // a b 0 0

                        to[i][2] = f0;

                        to[i][3] = f1;

                    }

                }

            } else {               // f2 !== 0

                if (f1 === 0) {

                    to[i][1] = 0;

                    if (f0 === f2) {   // a 0 a 0

                        to[i][3] = f2 + 1;

                        to[i][2] = 0;

                    } else {           // a 0 b 0

                        to[i][3] = f2;

                        to[i][2] = f0;

                    }

                } else {             // f1 !== 0

                    if (f1 === f2) {   // a b b 0

                        to[i][3] = f2 + 1;

                        to[i][2] = f0;

                        to[i][1] = 0;

                    } else {           // f1 !== f2

                        to[i][3] = f2;

                        if (f0 === f1) { // a a b 0

                            to[i][2] = f1 + 1;

                            to[i][1] = 0;

                        } else {         // a b c 0

                            to[i][2] = f1;

                            to[i][1] = f0;

                        }

                    }

                }

            }

        } else {                 // f3 !== 0

            if (f2 === f3) {

                to[i][3] = f2 + 1;

                to[i][0] = 0;

                if (f1 === 0) { // a 0 b b

                    to[i][2] = f0;

                    to[i][1] = 0;

                } else {

                    if (f0 === f1) { // a a b b

                        to[i][2] = f1 + 1;

                        to[i][1] = 0;

                    } else { // a b c c

                        to[i][2] = f1;

                        to[i][1] = f0;

                    }

                }

            } else { // f2 !== f3

                to[i][3] = f3;

                if (f2 === 0) {

                    to[i][0] = 0;

                    if (f1 === 0) { // a 0 0 b

                        to[i][1] = 0;

                        to[i][2] = f0;

                    } else {

                        if (f0 === f1) { // a a 0 b

                            to[i][1] = 0;

                            to[i][2] = f1 + 1;

                        } else { // a b 0 c

                            to[i][1] = f0;

                            to[i][2] = f1;

                        }

                    }

                } else { // f2 !== 0 && f2 !== f3

                    if (f1 === 0) { // a 0 b c

                        to[i][0] = 0;

                        to[i][1] = f0;

                        to[i][2] = f2;

                    } else {

                        if (f0 === f1) { // a a b c

                            to[i][0] = 0;

                            to[i][1] = f1 + 1;

                            to[i][2] = f2;

                        } else { // a b c d

                            to[i][0] = f0;

                            to[i][1] = f1;

                            to[i][2] = f2;

                        }

                    }

                }

            }

        }

    }

}

BoardArr2d.prototype.shiftRight_mostly_unrolled = function(brd) {

    var updated = false;

    var from = this.brd, to = brd.brd;

    for (var i = 0; i < 4; i++) {

        var moved = true;

        var f0 = from[i][0], f1 = from[i][1], f2 = from[i][2], f3 = from[i][3];

        if (f3 === 0) {

            if (f2 === 0) {

                if (f1 === 0) {  // a 0 0 0

                    if (f0 === 0)

                        moved = false;

                    f3 = f0;

                    f2 = 0;

                } else {         // a b 0 0

                    f3 = f1;

                    f2 = f0;

                }

                f1 = 0;

            } else {             // f2 !== 0 && f3 === 0

                if (f1 === 0) {  // a 0 b 0

                    f3 = f2;

                    f2 = f0;

                } else {         // a b c 0

                    f3 = f2;

                    f2 = f1;

                    f1 = f0;

                }

            }

            f0 = 0;

        } else {                 // f3 !== 0

            if (f2 === 0) {

                if (f1 === 0) {  // a 0 0 b

                    if (f0 === 0)

                        moved = false;

                    f2 = f0;

                } else {         // a b 0 c

                    f2 = f1;

                    f1 = f0;

                }

                f0 = 0;

            } else {             // f2 !== 0 && f3 !== 0

                if (f1 === 0) {  // a 0 b c

                    if (f0 === 0)

                        moved = false;

                    f1 = f0;

                    f0 = 0;

                } else {         // else: a b c d

                    moved = false;

                }

            }

        }

        updated = updated || moved;

        if (f2 === 0) {

            to[i][0] = 0;

            to[i][1] = 0;

            to[i][2] = 0;

            to[i][3] = f3;

            continue;

        }

        if (f1 === 0) {

            to[i][0] = 0;

            to[i][1] = 0;

            if (f2 === f3) {

                updated = true;

                to[i][2] = 0;

                to[i][3] = f3 + 1;

            } else {

                to[i][2] = f2;

                to[i][3] = f3;

            }

            continue;

        }

        if (f2 === f3) {

            updated = true;

            to[i][0] = 0;

            to[i][3] = f3 + 1;

            if (f0 === f1) {

                to[i][1] = 0;

                to[i][2] = f1 + 1;

            } else {

                to[i][1] = f0;

                to[i][2] = f1;

            }

        } else {

            to[i][3] = f3;

            if (f1 === f2) {

                updated = true;

                to[i][0] = 0;

                to[i][1] = f0;

                to[i][2] = f2 + 1;

            } else {

                if (f0 === f1) {

                    updated = true;

                    to[i][0] = 0;

                    to[i][1] = f1+1;

                    to[i][2] = f2;

                } else {

                    to[i][0] = f0;

                    to[i][1] = f1;

                    to[i][2] = f2;

                }

            }

        }

    }

    return updated;

}

BoardArr2d.prototype.shiftDown_mostly_unrolled = function(brd) {

    var updated = false;

    var from = this.brd, to = brd.brd;

    for (var j = 0; j < 4; j++) {

        var moved = true;

        var f0 = from[0][j], f1 = from[1][j], f2 = from[2][j], f3 = from[3][j];

        if (f3 === 0) {

            if (f2 === 0) {

                if (f1 === 0) {  // a 0 0 0

                    if (f0 === 0)

                        moved = false;

                    f3 = f0;

                    f2 = 0;

                } else {         // a b 0 0

                    f3 = f1;

                    f2 = f0;

                }

                f1 = 0;

            } else {             // f2 !== 0 && f3 === 0

                if (f1 === 0) {  // a 0 b 0

                    f3 = f2;

                    f2 = f0;

                } else {         // a b c 0

                    f3 = f2;

                    f2 = f1;

                    f1 = f0;

                }

            }

            f0 = 0;

        } else {                 // f3 !== 0

            if (f2 === 0) {

                if (f1 === 0) {  // a 0 0 b

                    if (f0 === 0)

                        moved = false;

                    f2 = f0;

                } else {         // a b 0 c

                    f2 = f1;

                    f1 = f0;

                }

                f0 = 0;

            } else {             // f2 !== 0 && f3 !== 0

                if (f1 === 0) {  // a 0 b c

                    if (f0 === 0)

                        moved = false;

                    f1 = f0;

                    f0 = 0;

                } else {         // else: a b c d

                    moved = false;

                }

            }

        }

        updated = updated || moved;

        if (f2 === 0) {

            to[0][j] = 0;

            to[1][j] = 0;

            to[2][j] = 0;

            to[3][j] = f3;

            continue;

        }

        if (f1 === 0) {

            to[0][j] = 0;

            to[1][j] = 0;

            if (f2 === f3) {

                to[2][j] = 0;

                to[3][j] = f3 + 1;

                updated = true;

            } else {

                to[2][j] = f2;

                to[3][j] = f3;

            }

            continue;

        }

        if (f2 === f3) {

            updated = true;

            to[0][j] = 0;

            to[3][j] = f3 + 1;

            if (f0 === f1) {

                to[1][j] = 0;

                to[2][j] = f1 + 1;

            } else {

                to[1][j] = f0;

                to[2][j] = f1;

            }

        } else {

            to[3][j] = f3;

            if (f1 === f2) {

                updated = true;

                to[0][j] = 0;

                to[1][j] = f0;

                to[2][j] = f2 + 1;

            } else {

                if (f0 === f1) {

                    updated = true;

                    to[0][j] = 0;

                    to[1][j] = f1+1;

                    to[2][j] = f2;

                } else {

                    to[0][j] = f0;

                    to[1][j] = f1;

                    to[2][j] = f2;

                }

            }

        }

    }

    return updated;

}