lab/recherche_de_carre/board.js

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// fonctions utilitaires
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


function min(a,b) {
    return a<b ? a : b;
}

function col_to_str(col,the_board) {
    var col_str="";
    for(var i_lines=0;i_lines<the_board.rows.length;i_lines++) {
        col_str+=the_board.rows[i_lines][col];
    }
    return col_str;
}

function set_char_at(index,chr,str) {
    if(index > str.length-1) return str;
    return str.substring(0,index) + chr + str.substring(index+1);
}

function get_random_char(str) {
    return str[Math.floor(Math.random() * str.length)];
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// fonctions métier
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// génération d'un board aléttoire
function generate_board(rows,cols) {
    var occurences = "...............o.";
    var board={rows:[]};
    for(i=0;i<cols;i++) {
        str = "";
        for(j=0;j<rows;j++) {
            str += get_random_char(occurences);
        }
        board.rows[i]=str;
    }
    return board;
}


// chercher la plus grande distance possible avant un o ou la fin de la chaine / la valeur d'arrêt
function get_distance_to_blocking_o(start,stop,str) {
    //console.log("get_distance_to_blocking_o",start,stop,str);
    //start+stop-1, -1 parce que le char est compté dans la la dimension du stop
    var last_char_to_check = (stop < 0  ? str.length : min(start+stop-1,str.length));
    //var tmp_str=set_char_at(start,"|",str);
    //var tmp_str2=set_char_at(last_char_to_check-1,"|",tmp_str);
    //console.log("get_distance_to_blocking_o",start,last_char_to_check,tmp_str2);

    for(var i_char=start;i_char<last_char_to_check;i_char++) {
        if(str[i_char]=="o") {
            return(i_char-start);
        }
    }
    return(last_char_to_check-start);
}

// chercher le plus grand carré possible depuis un point (vers le bas / la droite)
function get_biggest_square_on_board_at(row,col,the_board,current_max_width=-1) {
    // console.log("starting at ",row,col,current_max_width);
    // si il n'y a pas de ligne row, ou pas de colonne col, on renvoie 0
    if(row >= the_board.rows.length || col >= the_board.rows[0].length) {
        // console.log("out of bounds");
        return 0;
    }
    // si on est sur un o on renvoie 0 
    if(the_board.rows[row][col] == "o") {
        // console.log("got an o");
        return 0;
    }
    // on commence en se disant qu'on peut faire tout le reste du board en partant de notre position
    // on cherche à la position actuelle jusqu'ou on peut aller en longeur et en largeur
    // la longeur max est jusqu'au premier o qu'on trouve
    var max_width = get_distance_to_blocking_o(col,current_max_width,the_board.rows[row]);
    // console.log("max w",max_width);
    // la hauter maximum est jusqu'au premier o qu'on trouve, pas besoin de chercher plus loin que la largeur max
    // console.log("col : ",col," => ",col_to_str(col,the_board));
    var max_height = get_distance_to_blocking_o(row,current_max_width,col_to_str(col,the_board));
    // console.log("max h",max_height);
    // la dimension max est le min des deux.
    current_max_width = min(max_width,max_height);
    // console.log(max_width,",",max_height, "=>",current_max_width);
    // si c'est plus de 1, c'est à dire le plus petit carré possible, alors
    // la dimension max est donc 1 + la dimension max de ce quon peut faire en descendant en diagonale dans le sous carré
    if(current_max_width > 1) {
       return 1 + get_biggest_square_on_board_at(row+1,col+1,the_board,current_max_width);
    }
    // sinon on est est soit à la fin de ce qu'on peut chercher (dimensions du tableau ou on est tombé sur un o)
    return current_max_width;
}

// chercher le plus grand carré possible pour une ligne
function get_biggest_square_for_row(row,the_board) {
    var biggest_for_row = {width:0};
    var current_width = 0;
    for(var i_col=0;i_col<the_board.rows[row].length;i_col++) {
        current_width = get_biggest_square_on_board_at(row,i_col,the_board);
        // console.log("at row ",row,", col ",i_col," => ",current_width);
        if(current_width > biggest_for_row.width) {
            biggest_for_row.row = row;
            biggest_for_row.col = i_col;
            biggest_for_row.width = current_width;
        }
    }
    return biggest_for_row;
}

//chercher le plus grand carré pour un tableau
function get_biggest_square_for_board(the_board) {
    var biggest_in_board_for_now = {width:0};
    //console.log("biggest : ",biggest);
    for(var i_row=0; i_row<the_board.rows.length; i_row++) {
        current_square = get_biggest_square_for_row(i_row,the_board);
        if(current_square.width > biggest_in_board_for_now.width) {
            biggest_in_board_for_now = current_square;
        }
    }
    return(biggest_in_board_for_now);
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// déclarations de tableaux
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

board1 = {
    rows: [
        ".....o..........",
        ".....o.....o....",
        "................",
        "....o...........",
        "..........o.....",
        "................",
        "....o...o.......",
        "................",
        ".............o.."
    ]
}

board2 = {
    rows: [
        "o....o..........",
        "...........o....",
        "................",
        "....o...........",
        "..........o.....",
        "................",
        "....o...o.......",
        "................",
        ".............o.."
    ]
}


board3 = {
    rows: [
        "................",
        "................",
        "................",
        "................",
        "................",
        "................",
        "................",
        "................",
        "................"
    ]
}

board4 = {
    rows: [
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo"
    ]
}

board5 = {
    rows: [
        "................",
        "................",
        "................",
    ]
}

board6 = {
    rows: [
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
        "oooooooooooooooo",
    ]
}

board7 = {
    rows: [
        "o....o..........",
        "...........o....",
        "................",
        "....o...........",
        "..........o.....",
        "................",
        "....o...o.......",
        "................",
        "................",
        "................",
        "................",
        ".............o.."
    ]
}

board8 = {
    rows: [
        "o....o.........................",
        "..........................o....",
        "..............o................",
        "....o........ooo...............",
        "..............o..........o.....",
        "...............o...............",
        "....o..................o.......",
        "o..............................",
        "...............................",
        ".....................o.........",
        ".....................o.........",
        ".....................o.........",
        ".........ooo...................",
        "................o..............",
        "..................o............",
        "....................o..........",
        "...............................",
        "............................o.."
    ]
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// TESTS
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// console.log('board1 0,0 ',get_biggest_square_on_board_at(0,0,board1));
// console.log('board2 0,0 ',get_biggest_square_on_board_at(0,0,board2));
// console.log('board3 0,0 ',get_biggest_square_on_board_at(0,0,board3));
// console.log('board4 0,0 ',get_biggest_square_on_board_at(0,0,board4));
// console.log('board5 0,0 ',get_biggest_square_on_board_at(0,0,board5));
// console.log('board6 0,0 ',get_biggest_square_on_board_at(0,0,board6));
// console.log('board1 5,0 ',get_biggest_square_on_board_at(5,0,board1));
// console.log('board1 0,5 ',get_biggest_square_on_board_at(0,5,board1));
// console.log('board1 6,0 ',get_biggest_square_on_board_at(6,0,board1));
// console.log('board1 0,6 ',get_biggest_square_on_board_at(0,6,board1));
//console.log('board1 1,12 ',get_biggest_square_on_board_at(1,12,board1));
//console.log(get_distance_to_blocking_o(12,-1,"...........o...."));
//console.log('board1 1,6 ',get_biggest_square_on_board_at(1,6,board1));
//console.log('board1 1,12 ',get_biggest_square_on_board_at(1,12,board1));
//console.log('board1 1,5 ',get_biggest_square_on_board_at(1,5,board1));
//console.log('board1 0 ',get_biggest_square_for_row(0,board1));
//console.log('board2 0 ',get_biggest_square_for_row(0,board2));
//console.log('board3 0 ',get_biggest_square_for_row(0,board3));
//console.log('board4 0 ',get_biggest_square_for_row(0,board4));
//console.log('board5 0 ',get_biggest_square_for_row(0,board5));
//console.log('board6 0 ',get_biggest_square_for_row(0,board6));
//console.log('board1 1 ',get_biggest_square_for_row(1,board1));
//console.log('board1 1 ',get_biggest_square_for_row(2,board1));
//console.log('board2 0 ',get_biggest_square_for_row(0,board2));

for(i_board=1;i_board<9;i_board++) {
    console.log('board'+i_board+' ',eval("board"+i_board),get_biggest_square_for_board(eval("board"+i_board)));
}

var new_board = generate_board(100,100);
console.log("generated_board ",new_board,get_biggest_square_for_board(new_board));