javascript - How to find a consecutive sequence of symbols in a squared matrix -
i need finding right algorithm. have 2d array, example:
var arr = [ [""," "," "," ",""], [""," "," "," ",""], [""," "," ","x",""], ["","x","x","x",""], [""," "," ","x",""]]; and want verify if array has 3 next symbols match each other in direction (horizontal or vertical, or cross), display symbols.
i'm doing this:
run through array:
for(var = 0; < arr.length; i+=1){ for(var j = 0; j < arr.length; j+=1){ then verify if match:
if(arr[i][j] == "x" && arr[i+1][j] == "x" && arr[i+2][j] == "x"){ console.log(arr[i][j]); but give error, because i+1 , i+2 behind array.
i've tried make verification if:
if(arr[i][j+1] < arr.length) but doesn't count last rows.
how can it?
you can try count successive each row, column or diagonal.
given step function count successive "x"
data = { succx = 0 }; function step (data, arr, i, j) { data.succx = arr[i][j] === "x" ? data.succx + 1 : 0; return data.succx >= 3;; } then, can iterate , step result. if step return true, might store corresponding sequence , stop searching.
iterate on each row
for (var = 0, nbrow = arr.length; < nbrow; i++) { (var j = 0, nbcol = arr[i].length; j < nbcol; j++) { data.winseq = data.winseq || step(data, arr, i, j) && [[i, j-2], [i, j-1], [i, j]]; } } data.succx = 0; iterate on each column
for (var j = 0, nbcol = arr[0].length; j < nbcol; j++) { (var = 0, nbrow = arr.length; < nbrow; i++) { data.winseq = data.winseq || step(data, arr, i, j) && [[i-2, j], [i-1, j], [i, j]]; } } iterate on each diagonal
for (var d = 0, dim = arr.length, nbdiag = dim * 2 - 1; d < nbdiag; d++) { var maxe = d >= dim ? nbdiag - d - 1 : d; (var e = 0; e <= maxe; e++) { var = math.min(d, dim -1) - e, j = math.max(0, d - dim + 1) + e; data.winseq = data.winseq || step(data, arr, i, j) && [[i, j-2], [i+1, j-1], [i+2, j]]; } data.succx = 0; } (var d = 0, dim = arr.length, nbdiag = dim * 2 - 1; d < nbdiag; d++) { var maxe = d >= dim ? nbdiag - d - 1 : d; (var e = 0; e <= maxe; e++) { var = dim - 1 -math.min(d, dim -1) + e, j = math.max(0, d - dim + 1) + e; data.winseq = data.winseq || step(data, arr, i, j) && [[i-2, j-2], [i-1, j-1], [i, j]]; } data.succx = 0; } at end, data.winseq contains either undefined or valid sequence.
you can see whole process illustrated in snippet right below.
var delay = 0; function findwinseq(arr, seqlength) { var data = { succx: 0 }; // iteration step function step (data, arr, i, j) { if (arr[i][j] === "x") { data.succx++; colorize(i, j, "validcell", delay); } else { data.succx = 0; colorize(i, j, "selectcell", delay); } var haswon = data.succx >= seqlength; delay += haswon ? 2000 : 120; return haswon; } // count each row (var = 0, nbrow = arr.length; < nbrow; i++) { (var j = 0, nbcol = arr[i].length; j < nbcol; j++) { data.winseq = data.winseq || step(data, arr, i, j) && [[i, j-2], [i, j-1], [i, j]]; } } data.succx = 0; // count each column (var j = 0, nbcol = arr[0].length; j < nbcol; j++) { (var = 0, nbrow = arr.length; < nbrow; i++) { data.winseq = data.winseq || step(data, arr, i, j) && [[i-2, j], [i-1, j], [i, j]]; } } // count each diagonal (var d = 0, dim = arr.length, nbdiag = dim * 2 - 1; d < nbdiag; d++) { var maxe = d >= dim ? nbdiag - d - 1 : d; (var e = 0; e <= maxe; e++) { var = math.min(d, dim -1) - e, j = math.max(0, d - dim + 1) + e; data.winseq = data.winseq || step(data, arr, i, j) && [[i, j-2], [i+1, j-1], [i+2, j]]; } data.succx = 0; } (var d = 0, dim = arr.length, nbdiag = dim * 2 - 1; d < nbdiag; d++) { var maxe = d >= dim ? nbdiag - d - 1 : d; (var e = 0; e <= maxe; e++) { var = dim - 1 -math.min(d, dim -1) + e, j = math.max(0, d - dim + 1) + e; data.winseq = data.winseq || step(data, arr, i, j) && [[i-2, j-2], [i-1, j-1], [i, j]]; } data.succx = 0; } return data.winseq || null; } var tests = [ [ [" "," "," "," "," "], [" ","x"," ","x"," "], [" "," ","x"," "," "], [" "," "," ","x"," "], [" ","x"," "," "," "] ], [ [" "," "," "," "," "], [" ","x"," ","x"," "], [" "," "," "," "," "], [" "," "," ","x"," "], [" ","x"," "," "," "] ], [ [" "," "," "," "," "], [" ","x"," ","x"," "], [" "," "," "," ","x"], [" "," "," ","x"," "], [" ","x","x"," "," "] ], [ [" "," "," "," "," "], [" "," "," ","x"," "], [" "," ","x","x"," "], [" "," "," ","x"," "], [" ","x"," "," "," "] ], [ [" "," "," "," "," "], ["x","x","x","x"," "], [" "," ","x"," "," "], [" "," "," ","x"," "], [" ","x"," "," "," "] ], ]; // fancy stuffs function colorize(i, j, color, delay) { function _colorize(i, j, color) { // reset first valid cell if needed if (color === "selectcell") { var cells = document.getelementsbyclassname("validcell"); for(var k = 0, cell; cell = cells[k]; k++) { cell.classname = "cell"; } } // apply color next cell var previous = document.getelementsbyclassname("selectcell")[0]; if (previous !== undefined) { previous.classname = "cell"; } document.getelementbyid([i,j].join("")).classname = color; } settimeout(_colorize, delay, i, j, color); } function buildboard (test) { var board = document.getelementbyid("board"); board.style.width = test.length * 40 + "px"; board.innerhtml = ""; (var = 0, marker, cell, dim = test.length; < dim; i++) { (var j = 0; j < dim; j++) { cell = document.createelement('div'); cell.classname = "cell"; cell.id = [i,j].join(""); if (test[i][j] === "x") { marker = document.createelement('div'); marker.classname = "marker"; cell.appendchild(marker); } board.appendchild(cell); } } } (var = 0, test; test = tests[i]; i++) { settimeout(function (test) { settimeout(function (test) { buildboard(test); }, delay, test); findwinseq(test, 3); }, 750 * i, test); }#board { padding: 0; margin: 0; font-size: 0; } .cell, .validcell, .selectcell { display: inline-block; box-sizing: border-box; border: 1px solid #888; width: 40px; height: 40px; } .validcell { background: #cdeb8b; } .selectcell { background: #ddd; } .marker { background: #888; width: 16px; height: 16px; margin: 12px 0 0 12px; }<div id="board"></div>
Comments
Post a Comment