Skip to content

Instantly share code, notes, and snippets.

@mvasilkov
Last active February 19, 2020 20:10
Show Gist options
  • Save mvasilkov/46e1329e74bcfc7e1f2793f21d32a324 to your computer and use it in GitHub Desktop.
Save mvasilkov/46e1329e74bcfc7e1f2793f21d32a324 to your computer and use it in GitHub Desktop.
Count isolated regions in a table
'use strict'
// The following table has 6 connected regions:
const tab = `
111100000000000000000
111000000001110011000
110000000000011111100
000000000111111100000
110000011111000000000
111100000110000000011
011111000000000011111
000110000011111111111
000000000111100001111
000000011110000100011
000011111111110001111
000000000111111111111
001110000000111111000
000000000000001100000
`
// Prepare the table (array of arrays)
.split('\n').filter(a => !!a).map(a => a.split('').map(a => +a))
const WIDTH = tab[0].length
const HEIGHT = tab.length
/**
* Flood fill
*/
function flood(x, y) {
tab[y][x] = 2
// Left
if (x > 0 && tab[y][x - 1] == 1)
flood(x - 1, y)
// Right
if (x + 1 < WIDTH && tab[y][x + 1] == 1)
flood(x + 1, y)
// Up
if (y > 0 && tab[y - 1][x] == 1)
flood(x, y - 1)
// Down
if (y + 1 < HEIGHT && tab[y + 1][x] == 1)
flood(x, y + 1)
}
function countFlood() {
let count = 0
for (let y = 0; y < HEIGHT; ++y) {
for (let x = 0; x < WIDTH; ++x) {
if (tab[y][x] == 1) {
++count
flood(x, y)
}
}
}
console.log(`Flood fill: found ${count} regions`)
}
countFlood()
/**
* Better solution
*/
// A line from x=start to x=end (inclusive)
class Line {
constructor(start, end) {
this.start = start
this.end = end
this.succ = false // Has a successor
}
// Check if this line is touching other line
touches(other) {
return this.start <= other.end && this.end >= other.start
}
}
const NIL = -1
// Get lines on a table row y
function getLines(y) {
const result = []
let start = NIL
for (let x = 0; x < WIDTH; ++x) {
if (start == NIL && tab[y][x] != 0) {
start = x
continue
}
if (start != NIL && tab[y][x] == 0) {
result.push(new Line(start, x - 1))
start = NIL
}
}
if (start != NIL) result.push(new Line(start, WIDTH - 1))
return result
}
// Propagate down
function copySerial(prevLines, lines) {
prevLines.forEach(prev => {
lines.forEach(line => {
if (prev.touches(line)) prev.succ = true
})
})
}
// Hello world
function countBetter() {
let prevLines = []
let lines
let count = 0
for (let y = 0; y < HEIGHT; ++y) {
lines = getLines(y)
copySerial(prevLines, lines)
// Count lines with no successor
count += prevLines.reduce((a, b) => b.succ ? a : a + 1, 0)
prevLines = lines
}
count += prevLines.length
console.log(`Better solution: found ${count} regions`)
}
countBetter()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment