Created
April 11, 2017 23:42
-
-
Save earlonrails/aa112517529fa1ba58d9fa72a1047ee1 to your computer and use it in GitHub Desktop.
https://www.careercup.com/question?id=5749882624147456 Isles question in ES6 javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env node | |
"use strict" | |
// Write a function that receives a position in 2 dimensional (x,y) array, which was initially initialized with 'o' (signals "water"), the function changes the value/state of that position to 'x' (signals "land") and returns the number of isles in the board. | |
// For example, for 3x3 board, it will initially look like the following: | |
// o o o | |
// o o o | |
// o o o | |
// After calling the function with the position (1,2), the board will look like the following: | |
// o o x | |
// o o o | |
// o o o | |
// and the functions returns 1 | |
// An isle is defined as 'x' surrounded horizontally and vertically with 'o' | |
// In the following board there is only one isle | |
// o o o | |
// o x x | |
// o x o | |
let matrix = [ | |
["o", "o", "o"], | |
["o", "o", "o"], | |
["o", "o", "o"] | |
] | |
class Grid { | |
constructor(matrix) { | |
this.loadFromMatrix(matrix) | |
} | |
loadFromMatrix(matrix) { | |
this.points = matrix.reduce((yAcc, yCurr, yIdx) => { | |
yAcc[yIdx] = yCurr.reduce((xAcc, xCurr, xIdx) => { | |
xAcc[xIdx] = new Point(xCurr, yIdx, xIdx, matrix) | |
return xAcc | |
}, {}) | |
return yAcc | |
}, {}) | |
this.islandCount = this.countIsles() | |
} | |
markIsle(x, y) { | |
var currentNode = this.points[y][x] | |
if (currentNode.value == 'x') { | |
return this.islandCount | |
} | |
if (currentNode) { | |
currentNode.value = 'x' | |
this.islandCount = this.countIsles() | |
return this.islandCount | |
} | |
return 'Error outside of graph' | |
} | |
// hasCycle | |
countIsles() { | |
let visited = {}, count = 0 | |
Object.keys(this.points).forEach((yKey) => { | |
Object.keys(this.points[yKey]).forEach((xKey) => { | |
var current = this.points[yKey][xKey] | |
if (current.value == 'x' && !visited[current.key]) { | |
this.dfs(current, visited) | |
count++ | |
} | |
}) | |
}) | |
return count | |
} | |
// dfs | |
dfs(current, visited) { | |
visited[current.key] = true | |
var neighbors = current.neighbors(this.points) | |
neighbors.forEach((neighbor, idx) => { | |
if (!neighbor) return | |
if (neighbor.value == 'x' && !visited[neighbor.key]) { | |
this.dfs(neighbor, visited) | |
} | |
}) | |
} | |
} | |
class Point { | |
constructor(value, yIdx, xIdx, matrix) { | |
this.y = yIdx | |
this.x = xIdx | |
this.key = yIdx + "," + xIdx | |
this.value = value | |
} | |
neighbors(matrix) { | |
let left, right, top, bot | |
if (matrix[this.y]) { | |
left = matrix[this.y][this.x - 1] | |
right = matrix[this.y][this.x + 1] | |
} | |
if (matrix[this.y - 1]) { | |
top = matrix[this.y - 1][this.x] | |
} | |
if (matrix[this.y + 1]) { | |
bot = matrix[this.y + 1][this.x] | |
} | |
return [left, right, top, bot] | |
} | |
} | |
console.log("matrix: ", JSON.stringify(matrix)) | |
// matrix: [["o","o","o"],["o","o","o"],["o","x","o"]] | |
var g = new Grid(matrix) | |
console.log(JSON.stringify(g)) | |
// {"points":{"0":{"0":{"y":0,"x":0,"key":"0,0","value":"o"},"1":{"y":0,"x":1,"key":"0,1","value":"o"},"2":{"y":0,"x":2,"key":"0,2","value":"o"}},"1":{"0":{"y":1,"x":0,"key":"1,0","value":"o"},"1":{"y":1,"x":1,"key":"1,1","value":"o"},"2":{"y":1,"x":2,"key":"1,2","value":"o"}},"2":{"0":{"y":2,"x":0,"key":"2,0","value":"o"},"1":{"y":2,"x":1,"key":"2,1","value":"x"},"2":{"y":2,"x":2,"key":"2,2","value":"o"}}},"islandCount":1} | |
console.log("g.markIsle(1, 2): ", g.markIsle(1, 2)) | |
// g.markIsle(1, 2): 1 | |
console.log("g.markIsle(2, 1): ", g.markIsle(2, 1)) | |
// g.markIsle(2, 1): 2 | |
console.log("g.markIsle(1, 1): ", g.markIsle(1, 1)) | |
// g.markIsle(1, 1): 1 | |
console.log("g.markIsle(0, 0): ", g.markIsle(0, 0)) | |
// g.markIsle(0, 0): 2 | |
console.log("g.points: ", g.points) | |
// g.points: { '0': | |
// { '0': Point { y: 0, x: 0, key: '0,0', value: 'x' }, | |
// '1': Point { y: 0, x: 1, key: '0,1', value: 'o' }, | |
// '2': Point { y: 0, x: 2, key: '0,2', value: 'o' } }, | |
// '1': | |
// { '0': Point { y: 1, x: 0, key: '1,0', value: 'o' }, | |
// '1': Point { y: 1, x: 1, key: '1,1', value: 'x' }, | |
// '2': Point { y: 1, x: 2, key: '1,2', value: 'x' } }, | |
// '2': | |
// { '0': Point { y: 2, x: 0, key: '2,0', value: 'o' }, | |
// '1': Point { y: 2, x: 1, key: '2,1', value: 'x' }, | |
// '2': Point { y: 2, x: 2, key: '2,2', value: 'o' } } } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment