Day 6: The Connected Cell in a Grid
-
Pwter 9 years ago The learning curve and pace of this contest is terrible. Day 5: const PI=Math.PI; Day 6: 2 dimensional matrix search algorithm with input handling with different whitespaces.
-
dotkim 9 years ago No kidding. They don't even explain what DP is.
-
Ayelis 9 years ago That's pretty much how I've found the learning curve on the entire HackerRank site overall. Warmup lessons? A breeze. Everything else listed as Easy? Calculate the average airspeed velocity of an unladen swallow, with nothing but these geotagged coordinates of its migration pattern and the Google Maps API to determine if it is an African or European swallow.
-
sasankadx 9 years ago Seriously they are not taking it seriously. No one can get some important subject like js,jq in 7 days only.
-
-
XiongX 9 years ago The input is not clean. Some lines ends with "\n", some lines end with "\r\n".
So use
input.split(/\r?\n/);
-
alvinlin123 9 years ago yea I got bit by that to. I use trim() to trim each row instead
-
iweizmeisk 9 years ago Use this : input.replace(/\n/g," ").split(" ");
-
-
Misfit 9 years ago My inelegant but rather easy way of solving this problem for those stuck.
function fill(arr, i, j, m, n) { // return if any of the indices is out of matrix bounds if (i < 0 || i >= m || j < 0 || j >= n) return 0; else if (arr[i][j] == 1) { // zero the element for a "visited"-like indicator, // so every connected component is recursed through // only once arr[i][j] = 0; // return 1 as the component size, adding the recursive // returns for all its possible neighbours return 1+fill(arr, i-1, j-1, m, n) +fill(arr, i-1, j, m, n) +fill(arr, i-1, j+1, m, n) +fill(arr, i, j-1, m, n) +fill(arr, i, j+1, m, n) +fill(arr, i+1, j-1, m, n) +fill(arr, i+1, j, m, n) +fill(arr, i+1, j+1, m, n); } return 0; } function processData(input) { // read and parse the input var arr = input.split(/\r?\n/); var m = arr[0], n = arr[1], chck = 0, rslt = 0; arr = arr.slice(2).map(e => e.split(' ').map(Number)); // cycle through every element of the matrix for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { // check arr[i][j] value and count its component chck = fill(arr, i, j, m, n); // compare this component size with max size yet rslt = (chck > rslt) ? chck : rslt; } } console.log(rslt); }
-
leonardofa 9 years ago Pretty nice, tks
-
PRASHANTB1984 9 years ago It is pretty nice! In the return from the fill function you could perhaps generate the 8 terms via some kind of iterator, not that it implies something significantly different.
-
emcas88 9 years ago var dx = [-1, 0, 1,-1, 1, -1, 0, 1]; var dy = [-1,-1,-1, 0, 0, +1,+1,+1];
function countCells(matrix, x, y) { var c = 0;
if (matrix[y][x] === "1") { c = 1; matrix[y][x] = "x"; for (var i = 0; i < dx.length; i++) { var nx = dx[i] + x; var ny = dy[i] + y; if (ny >= 0 && ny < matrix.length && nx >= 0 && nx < matrix[ny].length) { c += countCells(matrix, nx, ny); } } } return c;
}
-
-
-
kenrick95 9 years ago Take note that a cell is also connected if they are adjacent to each other diagonally.
-
ykurmangaliyev 9 years ago Yeah, that costed one attempt to me :(
-
vyletel 9 years ago I forgot about triangle pattern like this:
x x x 1 x 1
x x x x 1 x
It's cost me an attempt as well...
-
-
PRASHANTB1984 9 years ago Yes, its the 8-connected pixel. Thanks for sharing it with others as well.
-
Sort 50 Discussions, By:
Please Log In in order to post a comment