Skip to content

Instantly share code, notes, and snippets.

@earlonrails
Created April 11, 2017 23:42
Show Gist options
  • Save earlonrails/aa112517529fa1ba58d9fa72a1047ee1 to your computer and use it in GitHub Desktop.
Save earlonrails/aa112517529fa1ba58d9fa72a1047ee1 to your computer and use it in GitHub Desktop.
#!/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