Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 17, 2016 02:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/8f17d6582ce6335af33e952450d255a3 to your computer and use it in GitHub Desktop.
Save jianminchen/8f17d6582ce6335af33e952450d255a3 to your computer and use it in GitHub Desktop.
Connected Cell In a Grid - very good structured JavaScript code - use prototype, and ===, adjacent - neighbor nodes - an array
function toNumber(value){
return parseInt(value.trim());
}
function Node(val, row, col){
this.val = val;
this.row = row;
this.col = col;
this.adjacent = [];
}
Node.prototype = {
isAdjacent : function (node){
var duplicates = this.adjacent.filter(function(adjacent){
return adjacent === node;
});
return !!duplicates.length;
},
addAdjacent : function(node){
if (!this.isAdjacent(node)){
this.adjacent.push(node);
}
}
};
function Graph(data){
this.data = data || [];
}
Graph.prototype = {
addNode : function(node){
this.data.push(node);
},
getNodesBy: function(condition){
return this.data.filter(function(node){
return condition(node);
});
}
};
function traverse(node){
var count = 1;
node.visited = true;
node.adjacent.forEach(function(adjacent){
if (!adjacent.visited){
count += traverse(adjacent);
}
});
return count;
}
function processData(input) {
var lines = input.split("\n");
var rows = toNumber(lines.shift());
var cols = toNumber(lines.shift());
var graph = new Graph();
var rowStr = lines.slice(0, rows);
var results = [];
rowStr.forEach(function(val, row){
val.trim().split(" ").slice(0, cols).forEach(function(val, col){
if (toNumber(val) === 0){
return;
}
var active = new Node(val, row, col);
var neighbors = graph.getNodesBy(function(node){
if (Math.abs(node.row - active.row) < 2 &&
Math.abs(node.col - active.col) < 2) {
return true;
}
});
neighbors.forEach(function(node){
active.code = node.code = node.code || active.code || Math.random() * 9999;
node.addAdjacent(active);
active.addAdjacent(node);
});
graph.addNode(active);
});
});
graph.data.forEach(function(node){
if (!node.visited){
results.push(traverse(node));
}
});
console.log(results.reduce(function(a, b){
return a > b ? a : b;
}));
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment