Count isolated regions in a table

count_regions.js

'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()