Snappers

snappers.js

//queue is an array of functions
//board is a 2D array
//grid is a 2D array of numbers
//progression is B-O-G-R
//grid values
//Red = 1
//Green = 2
//Orange = 3
//Blue = 4
//Empty = 0
var board1 = [["-","R","R","R","-"],
             ["G","B","R","B","G"],
             ["-","-","-","-","-"],
             ["B","-","R","-","B"],
             ["R","-","-","-","R"],
             ["O","-","R","-","O"]];

var board2 = [["-","-","B","-","-"],
              ["G","-","G","-","G"],
              ["G","-","G","-","G"],
              ["R","-","-","-","R"],
              ["O","-","G","-","O"],
              ["R","-","R","-","R"]];

var board3 = [["G","-","-","R","B"],
              ["-","-","-","G","-"],
              ["R","R","-","G","-"],
              ["R","R","-","-","-"],
              ["-","O","-","B","G"],
              ["R","O","-","-","G"]];

var grid = [];

var maxCol = 5;
var maxRow = 6;

function drawBoard(row,column,gc,level){

    var content = $("#board");
    content.append("<span> level:" + level +  "</span>");
    content.append("<span> result of tap:" + row + "," + column +  "</span>");
    for(var i = 0; i < gc.length; i++){
        var div =  $("<div/>");
        for(var j = 0; j < gc[i].length; j++){
            div.append("<span>" + gc[i][j] + "</span>");  
        }
        content.append(div); 
    }
    content.append($("<br/>"));
}

function convertBoardToGrid(board){
    for(var i = 0; i < board.length; i++){
        var row = [];
        for(var j = 0; j < board[i].length; j++){
            var val = board[i][j];
            if(val == "-"){
                row.push(0);
            }
            else if(val == "R"){
                row.push(1);
            }
            else if(val == "G"){
                row.push(2);
            }
            else if(val == "O"){
                row.push(3);
            }
            else if(val == "B"){
                row.push(4);
            }
        }
        grid.push(row);
    }
}

function playIteration(row, column, gc){
    var queue = [];
    tap(row,column,queue, gc);
    var actions = 0;
    while(queue.length > 0){
        var op = queue.shift();
        op();
        actions++;
    }
    //drawBoard(row,column, gc);
    return gc;
}

//returns score of row/colum
function getScore(row, column){
    var score = 0;
    //score -= grid[row][column];
    for(var i = 0; i < maxRow; i++){
        var val = grid[i][column];
        if(val > 0){
            score += (5 - val);
        }
    }
    for(var j = 0; j < maxCol; j++){
        var val = grid[row][j];
        if(val > 0){
            score += (5 - val);   
        } 
    }
   return score; 
}

//returns array of {row,column,score}
function scoreGrid(gc){
    var scoreArray = [];
    for(var i = 0; i < maxRow; i++){
        for(var j = 0; j < maxCol; j++){
            var val = gc[i][j];
            if(val > 0){
                var s = getScore(i,j);
                scoreArray.push({
                    row: i,
                    column: j,
                    score: s 
                });
            } 
        } 
    }
    return scoreArray; 
}

function sortScores(scoreArray){
    scoreArray.sort(function(a,b){
       return b.score - a.score; 
    });
    return scoreArray;  
}

function tap(row,column,queue,gc){
    var val = gc[row][column];
    if(val == 1){
        queue.push(function(){
            explode(row,column,queue,gc);
        });
    }
    else if(val > 1){
        gc[row][column] = val-1;
    }
}


function left(row, column, queue, gc){
    if(column - 1 >= 0){
        var val = gc[row][column-1];
        if(val == 0){
            queue.push(function(){
                left(row,column-1,queue,gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row,column-1,queue,gc);
            });
        }
        else if(val > 1){
            gc[row][column-1] = val - 1;
        }
    }
}  

function up(row, column, queue, gc){
    if(row - 1 >= 0){
        var val = gc[row-1][column];
        if(val == 0){
            queue.push(function(){
                up(row-1,column,queue,gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row-1,column,queue,gc);
            });
        }
        else if(val > 1){
            gc[row-1][column] = val - 1;
        }
    }
}
  
function right(row, column, queue, gc){
    if(column + 1 < maxCol){
        var val = gc[row][column+1];
        if(val == 0){
            queue.push(function(){
                right(row,column+1,queue,gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row,column+1,queue,gc);
            });
        }
        else if(val > 1){
            gc[row][column+1] = val - 1;
        }
    }
}  
  
function down(row, column, queue,gc){
    if(row + 1 < maxRow){
        var val = gc[row+1][column];
        if(val == 0){
            queue.push(function(){
                down(row+1,column,queue,gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row+1,column,queue,gc);
            });
        }
        else if(val > 1){
            gc[row+1][column] = val - 1;
        }
    }
}

function explode(row, column, queue, gc) {
    //down
    gc[row][column] = 0;
    if (row + 1 < maxRow) {
        var val = gc[row+1][column];
        if(val == 0){
            queue.push(function() {
                down(row + 1, column, queue, gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row+1,column,queue,gc);    
            });
        }
        else if(val > 1){
            gc[row+1][column] = val-1;
        }
    }
    //right
    if (column + 1 < maxCol) {
        var val = gc[row][column+1];
        if(val == 0){
            queue.push(function() {
                right(row, column+1, queue, gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row,column+1,queue, gc);    
            });
        }
        else if(val > 1){
            gc[row][column+1] = val-1;
        }
    }
    //up
    if(row-1 >= 0){
        var val = gc[row-1][column];
        if(val == 0){
            queue.push(function() {
                up(row - 1, column, queue, gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row-1,column,queue,gc);    
            });
        }
        else if(val > 1){
            gc[row-1][column] = val-1;
        }     
    }
    //left
   if(column - 1 >= 0){
        var val = gc[row][column-1];
        if(val == 0){
            queue.push(function() {
                left(row, column-1, queue, gc);
            });
        }
        else if(val == 1){
            queue.push(function(){
                explode(row,column-1,queue,gc);    
            });
        }
        else if(val > 1){
            gc[row][column-1] = val-1;
        }  
    }
}

function printScores(scoreArray){
    var strings = [];
    for(var i = 0; i < scoreArray.length; i++){
        var s = scoreArray[i];
        var v = s.row + "," + s.column + ":" + s.score + " \n ";
        strings.push(v);
    }
    return strings; 
}

function isComplete(gc){
    var total = 0;
    for(var i = 0; i < maxRow; i++){
        for(var j = 0; j < maxCol; j++){
            total += gc[i][j];  
        }  
    }
    return total == 0;
}

function copyGrid(gc){
    var copy = [];
    for(var i = 0; i < maxRow; i++){
        var row = [];
        for(var j = 0; j < maxCol; j++){
            row.push(gc[i][j]);  
        }
        copy.push(row);  
    }
    return copy;
}

function copyPath(path){
    var copy = [];
    for(var i = 0; i < path.length; i++){
        copy.push({row:path[i].row,column:path[i].column});   
    }
    return copy; 
}

function printPath(path){    
    var p = "";
    if(path.length){
        for(var i = 0; i < path.length; i++){
            p += path[i].row + "," + path[i].column + " : ";    
        }
    }
    return p;
}

function evaluatePaths(gc, maxTaps){

    var scores = scoreGrid(gc);
    scores = sortScores(scores);
    var queue = [];
    var path = [];
    for(var i = 0; i < scores.length; i++){
        var tap = scores[i];
        queue.push({
            row : tap.row,
            column : tap.column,
            grid : copyGrid(gc),
            path : copyPath(path),
            level : 0,
            traverse : function(r,c,g,p,l){
                return followPath(g,p, {row:r,column:c}, queue, l, maxTaps); 
            }
        });   
    }
    
    var counter = 0;
    var finalPath = "";
    
    while(queue.length > 0 && counter < 1000){
        var op = queue.shift();
        //drawBoard(op.row,op.column,op.grid,op.level);

        var result = op.traverse(op.row,op.column,op.grid,op.path,op.level);
        if(result){
            finalPath = result;
            break;   
        }

        counter++;
    }
    alert(printPath(finalPath) + " : " + counter);
}

var ml = 0;
function followPath(gc, path, tap, queue, level, maxTaps){
    
    //if(level > ml){ alert("new level " + level); ml = level; }
    
    //drawBoard(-1,-1,gc);
    path.push(tap);
    gc = playIteration(tap.row,tap.column, gc);
    //drawBoard(tap.row,tap.column,gc, level);
    if(isComplete(gc)){
        //alert("board complete");
        return path;   
    }
    else if(level + 1 < maxTaps){
        var scores = scoreGrid(gc);
        scores = sortScores(scores);
        for(var i = 0; i < scores.length; i++){
            var t = scores[i];
            queue.push({
                row : t.row,
                column : t.column,
                grid : copyGrid(gc),
                path : copyPath(path),
                level : level+1,
                traverse : function(r,c,g,p,l){
                    return followPath(g, p, {row:r,column:c}, queue, l, maxTaps);
                }
            });
        }
    }
    //alert("all execution complete for " + tap.row + "," + tap.column + "," + level);
    return false;
}

$(function() {
    convertBoardToGrid(board2);
    drawBoard(-1,-1,grid);
    var maxTaps = 3;
    var taps = [];
    var turnCount = 0;
  
    var og = copyGrid(grid);
    evaluatePaths(grid, maxTaps);

});