/**
 * onetoughpuzzle.js
 *
 * The model and puzzle solving functionality for finding solutions to
 * the One Tough Puzzle toys distributed by Great American Puzzle Factory
 *
 * Copyright (C) 2011 Jimmy Theis
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// Constants for interlocks
var PositiveHeartInterlock = '+H';
var PositiveSpadeInterlock = '+S';
var PositiveDiamondInterlock = '+D';
var PositiveClubInterlock = '+C';
var NegativeHeartInterlock = '-H';
var NegativeSpadeInterlock = '-S';
var NegativeDiamondInterlock = '-D';
var NegativeClubInterlock = '-C';

// Aggregate list of interlocks
var interlockMatches = {}
interlockMatches[PositiveHeartInterlock] = NegativeHeartInterlock;
interlockMatches[PositiveSpadeInterlock] = NegativeSpadeInterlock;
interlockMatches[PositiveDiamondInterlock] = NegativeDiamondInterlock;
interlockMatches[PositiveClubInterlock] = NegativeClubInterlock;
interlockMatches[NegativeHeartInterlock] = PositiveHeartInterlock;
interlockMatches[NegativeSpadeInterlock] = PositiveSpadeInterlock;
interlockMatches[NegativeDiamondInterlock] = PositiveDiamondInterlock;
interlockMatches[NegativeClubInterlock] = PositiveClubInterlock;

/**
 * Model for a single puzzle piece.
 */
var Piece = function(topInterlock, rightInterlock, bottomInterlock, leftInterlock) {
    this.rotations = 0;
    this.topInterlock = topInterlock;
    this.rightInterlock = rightInterlock;
    this.bottomInterlock = bottomInterlock;
    this.leftInterlock = leftInterlock;

    /**
     * Set all of this piece's interlocks at once.
     */
    this.setInterlocks = function(topInterlock, rightInterlock, bottomInterlock, leftInterlock) {
        this.topInterlock = topInterlock;
        this.rightInterlock = rightInterlock;
        this.bottomInterlock = bottomInterlock;
        this.leftInterlock = leftInterlock;
        this.wasFlipped = false;
    }

    /**
     * Whether or not this piece has any of its interlocks set.
     */
    this.isEmpty = function() {
        return this.topInterlock == null &&
            this.rightInterlock == null &&
            this.bottomInterlock == null &&
            this.leftInterlock == null;
    };

    /**
     * Create a clockwise rotated copy of this piece without
     * affecting the original.
     */
    this.rotated = function() {
        var result = new Piece();
        result.setInterlocks(this.leftInterlock, this.topInterlock,
                this.rightInterlock, this.bottomInterlock);
        result.rotations = this.rotations + 1;
        result.wasFlipped = this.wasFlipped;
        return result;
    }

    /**
     * Create a flipped copy of this piece without affecting the original
     */
    this.flipped = function() {
        var result = new Piece();
        result.setInterlocks(this.bottomInterlock, this.rightInterlock, this.topInterlock, this.leftInterlock);
        result.rotations = this.rotations;
        result.wasFlipped = true;
        return result;
    }
}

/**
 * Model for entire puzzle "board".
 */
var Board = function() {
    this.contents = [new Piece(), new Piece(), new Piece(),
                     new Piece(), new Piece(), new Piece(),
                     new Piece(), new Piece(), new Piece()];

    /**
     * Whether or not this board has every space occupied by
     * a non-empty piece.
     */
    this.isFull = function() {
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].isEmpty()) return false;
        }

        return true;
    }

    /**
     * How many pieces are flipped in this board
     */
    this.numberFlipped = function() {
        var result = 0;
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].wasFlipped) result ++;
        }

        return result;
    }

    /**
     * The first available space that is currently occupied by
     * an empty piece.
     */
    this.nextEmptySpace = function() {
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].isEmpty()) return i;
        }

        return -1;
    }

    /**
     * Whether or not a piece will connect properly with the pieces
     * adjacent to the next available space.
     */
    this.canFitNextPiece = function(piece) {
        // Piece positions:
        //   0 1 2
        //   3 4 5
        //   6 7 8
        
        // Prevent more than four pieces being flipped
        if (this.numberFlipped() >= 4 && piece.wasFlipped) {
            return false;
        }

        // Helper variable to shorten the contents array name
        var c = this.contents;

        // Interlocks adjacent to each position, ordered by interlocks adjacent to top, right, bottom, left.
        // If no piece is adjacent on a side, the interlock value is null.
        var adjacency = [
            // Top row
            [null,                 c[1].leftInterlock, c[3].topInterlock, null               ],
            [null,                 c[2].leftInterlock, c[4].topInterlock, c[0].rightInterlock],
            [null,                 null,               c[5].topInterlock, c[1].rightInterlock],

            // Middle row
            [c[0].bottomInterlock, c[4].leftInterlock, c[6].topInterlock, null               ],
            [c[1].bottomInterlock, c[5].leftInterlock, c[7].topInterlock, c[3].rightInterlock],
            [c[2].bottomInterlock, null,               c[8].topInterlock, c[4].rightInterlock],

            // Bottom row
            [c[3].bottomInterlock, c[7].leftInterlock, null,              null               ],
            [c[4].bottomInterlock, c[8].leftInterlock, null,              c[6].rightInterlock],
            [c[5].bottomInterlock, null,               null,              c[7].rightInterlock]
        ];

        if (this.isFull()) return false;

        interlocks = adjacency[this.nextEmptySpace()];

        var matches = function(pieceSide, boardSide) {
            return boardSide == null || interlockMatches[pieceSide] == boardSide;
        }

        return matches(piece.topInterlock, interlocks[0]) &&
            matches(piece.rightInterlock, interlocks[1]) &&
            matches(piece.bottomInterlock, interlocks[2]) &&
            matches(piece.leftInterlock, interlocks[3]);
    }

    /**
     * Create a copy of this board with the next available space that
     * is currently occupied by an empty piece populated with the piece
     * passed to this method.
     */
    this.withNextPiece = function(piece) {
        var result = new Board();
        result.contents = this.contents.slice(0);
        
        if (result.isFull()) return result;

        result.contents[result.nextEmptySpace()] = piece;

        return result;
    }

    /**
     * Generate a string that uniquely identifies this board
     * but is the same across all rotations of this board
     */
    this.hash = function() {
        edges = [this.contents[0].topInterlock,
                 this.contents[1].topInterlock,
                 this.contents[2].topInterlock,
                 this.contents[2].rightInterlock,
                 this.contents[5].rightInterlock,
                 this.contents[8].rightInterlock,
                 this.contents[8].bottomInterlock,
                 this.contents[7].bottomInterlock,
                 this.contents[6].bottomInterlock,
                 this.contents[6].leftInterlock,
                 this.contents[3].leftInterlock,
                 this.contents[0].leftInterlock];

        var hash = edges.join();

        for (var i = 0; i < edges.length; i++) {
            edges.push(edges.shift());

            var next = edges.join();

            if (next < hash) {
                hash = next;
            }
        }

        return hash;
    }

    /**
     * Return a text representation of this board.
     * Really only works for valid and full boards.
     */
    this.toString = function() {
        var c = this.contents;

        var f = function(psn) { return c[psn].wasFlipped ? 'F' : ' '; }

        var pos = function(st) { return st[0] == '+' ? st[1] : ' '; }
        var neg = function(st) { return st[0] == '-' ? st[1] : ' '; }

        var pt = function(psn) { return pos(c[psn].topInterlock); }
        var nt = function(psn) { return neg(c[psn].topInterlock); }

        var pr = function(psn) { return pos(c[psn].rightInterlock); }
        var nr = function(psn) { return neg(c[psn].rightInterlock); }

        var pb = function(psn) { return pos(c[psn].bottomInterlock); }
        var nb = function(psn) { return neg(c[psn].bottomInterlock); }

        var pl = function(psn) { return pos(c[psn].leftInterlock); }
        var nl = function(psn) { return neg(c[psn].leftInterlock); }

        return '     '+pt(0)+'       '+pt(1)+'       ' +pt(2)+'     \n' + 
               ' +---|---+---|---+---|---+ \n' +
               ' |   '+nt(0)+'   |   '+nt(1)+'   |   '+nt(2)+'   | \n' +
               pl(0)+'-'+nl(0)+'  '+f(0)+'  '+pl(1)+'-'+pr(0)+'  '+f(1)+'  '+pl(2)+'-'+pr(1)+'  '+f(2)+'  '+nr(2)+'-'+pr(2)+'\n' +
               ' |   '+pt(3)+'   |   '+pt(4)+'   |   '+pt(5)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' + 
               ' |   '+pb(0)+'   |   '+pb(1)+'   |   '+pb(2)+'   | \n' +
               pl(3)+'-'+nl(3)+'  '+f(3)+'  '+pl(4)+'-'+pr(3)+'  '+f(4)+'  '+pl(5)+'-'+pr(4)+'  '+f(5)+'  '+nr(5)+'-'+pr(5)+'\n' +
               ' |   '+pt(6)+'   |   '+pt(7)+'   |   '+pt(8)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' + 
               ' |   '+pb(3)+'   |   '+pb(4)+'   |   '+pb(5)+'   | \n' +
               pl(6)+'-'+nl(6)+'  '+f(6)+'  '+pl(7)+'-'+pr(6)+'  '+f(7)+'  '+pl(8)+'-'+pr(7)+'  '+f(8)+'  '+nr(8)+'-'+pr(8)+'\n' +
               ' |   '+nb(6)+'   |   '+nb(7)+'   |   '+nb(8)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' +
               '     '+pb(6)+'       '+pb(7)+'       '+pb(8)+'      ';
    }
}

/**
 * A representation of a board state, for solving
 */
var State = function(board, pieces) {
    this.board = board;
    this.pieces = pieces;
}

/**
 * Create a solved board given a list of 9 pieces
 */
var solvePuzzle = function(pieces) {
    // Helper function that removes the first element of an array, if there is one.
    var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

    var board = new Board();
    var workspace = [];

    // Push initial empty board state
    workspace.push(new State(board, pieces));

    while (true) {

        // Base case that will be triggered if a solution is not found
        if (workspace.length <= 0) return null;

        // Retrieve the top state on the workspace
        var state = workspace.pop();

        var board = state.board;
        var pieces = state.pieces;

        // Base case that will be triggered when the board is filled
        if (board.isFull()) return board;

        for (var i = 0; i < pieces.length; i++) {
            // Retrieve one of the remaining pieces
            var piece = pieces[i];

            // Strip that piece out of the pices left over
            var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

            // Generate rotations of the retrieved piece
            var piece2 = piece.rotated();
            var piece3 = piece2.rotated();
            var piece4 = piece3.rotated();

            // If any rotation of the piece fits in the next available space,
            // create the state with that piece added to the board and push
            // it onto the workspace stack
            if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
            if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
            if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
            if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));
        }
    }
}

var findAllSolutions = function(pieces) {
    // Helper function that removes the first element of an array, if there is one.
    var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

    var board = new Board();
    var workspace = [];

    results = [];

    // Push initial empty board state
    workspace.push(new State(board, pieces));

    while (true) {

        // Base case that will be triggered if a solution is not found
        if (workspace.length <= 0) return results;

        // Retrieve the top state on the workspace
        var state = workspace.pop();

        var board = state.board;
        var pieces = state.pieces;

        // Base case that will be triggered when the board is filled
        if (board.isFull()) results[board.hash()] = board;

        for (var i = 0; i < pieces.length; i++) {
            // Retrieve one of the remaining pieces
            var piece = pieces[i];

            // Strip that piece out of the pices left over
            var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

            // Generate rotations of the retrieved piece
            var piece2 = piece.rotated();
            var piece3 = piece2.rotated();
            var piece4 = piece3.rotated();

            var piece5 = piece.flipped();
            var piece6 = piece5.rotated();
            var piece7 = piece6.rotated();
            var piece8 = piece7.rotated();

            // If any rotation of the piece fits in the next available space,
            // create the state with that piece added to the board and push
            // it onto the workspace stack
            if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
            if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
            if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
            if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));

            if (board.canFitNextPiece(piece5)) workspace.push(new State(board.withNextPiece(piece5), nextPieces));
            if (board.canFitNextPiece(piece6)) workspace.push(new State(board.withNextPiece(piece6), nextPieces));
            if (board.canFitNextPiece(piece7)) workspace.push(new State(board.withNextPiece(piece7), nextPieces));
            if (board.canFitNextPiece(piece8)) workspace.push(new State(board.withNextPiece(piece8), nextPieces));
        }
    }

    return results;
}