Skip to content

Instantly share code, notes, and snippets.

@idiomatic
Last active December 6, 2017 20:53
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 idiomatic/70a285403501a17238c968f9eda65428 to your computer and use it in GitHub Desktop.
Save idiomatic/70a285403501a17238c968f9eda65428 to your computer and use it in GitHub Desktop.
count the number of "islands" in an matrix of non-wraparound bits, where horizontally/vertically/diagonally adjacent bits are the same island
const tests = [
[0, [[0]]],
[1, [[1]]],
[1, [[1, 0], [0, 0]]],
[1, [[0, 1], [0, 0]]],
[1, [[0, 0], [1, 0]]],
[1, [[0, 0], [0, 1]]],
[1, [[1, 0], [0, 1]]],
[1, [[0, 1], [0, 1]]],
[1, [[1, 0], [1, 0]]],
[1, [[0, 1], [1, 0]]],
[1, [[1, 1], [1, 1]]],
[2, [[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 0], [0, 1, 0, 0]]],
[16, [[0, 1, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0]]]
].forEach(
([expected, map], i) =>
console.assert(countIslands(map) == expected, `test ${i} failed`)
)
function countIslands(map) {
const height = map.length
const width = map[0].length
var islands = 0
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
if (map[y][x]) {
if (!(map[y][x-1]
|| ((y > 0) &&
(map[y-1][x-1] || map[y-1][x] || map[y-1][x+1])))) {
islands++
}
}
}
}
return islands
}
exports = { countIslands }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment