Olympiade - Moustiques

index.js

const DEBUG = false;
const MOSQITO_DENSITY = 0.1;
const MAP_HEIGHT = 200;
const MAP_WIDTH  = 120;

function randomBoolean() {
    return Math.random() < MOSQITO_DENSITY;
}

class Map {
    height = MAP_HEIGHT;
    width = MAP_WIDTH;

    constructor() {
        this.data = new Array(this.height).fill().map(row => new Array(this.width).fill().map(cell => randomBoolean()));
    }

    toString() {
        return this.data.map((row, y) => (y % 5 == 0 ? '\n' : '') + row.map((cell, x) => (x % 5 == 0 ? ' ' : '') + (cell ? '1' : '0')).join('')).join('\n');
    }
}


const map = new Map();
console.log('--------------------------------------');
console.log('Map:')
console.log(`${map}`);
console.log('');

class SimpleSolver {
    debug = DEBUG;

    log(event) {
        if (this.debug) {
            console.log(event);
        }
    }

    processMap(map) {
        let biggest = {y: null, x: null, size: 0};
        for (let y = 0; y < map.data.length; y++) {
            const row = map.data[y];
            let previousx = -1;
            for (let x = 0; x < row.length;) {
                if (previousx === x) {
                    this.log({y,x, msg: '"x" not changing'});
                    throw `Error not changing`;
                }
                previousx = x;
                if (row[x]) {
                    // Not a candidate
                    this.log({y,x, msg: 'not a candidate'});
                    x++;
                    continue;
                }
                if (y > 0 && !map.data[y-1][x]) {
                    // Already processed
                    this.log({y,x, msg: 'already processed'});
                    x++;
                    continue;
                }

                // Look-up max width at initial row
                let lastx = x;
                while (lastx < row.length && !row[lastx]) {
                    lastx++;
                }
                let size = Math.min(lastx - x, map.data.length - y);
                if (size <= biggest.size) {
                    this.log({y,x, msg: `${size} <= ${biggest.size}`});
                    x = lastx;
                    continue; // Not bigger
                }
                // Check max width on next rows
                let ny = y+1;
                while (ny < map.data.length && ny < (y+size)) {
                    if (map.data[ny][x]) {
                        // Premature end on y axis
                        this.log({y,x, msg: `Premature end on y-axis`,ny});
                        size = ny - y;
                        break;
                    }
                    for (let nx = x; nx < (x + size); nx++) {
                        if (map.data[ny][nx]) {
                            // Premature end (FIXME)
                            this.log({y,x, msg: `Shorter row on y-axis`, ny, nx});
                            size = nx - x;
                            break;
                        }
                    }
                    ny++;
                }
                if (size <= 0) {
                    this.log({y,x, msg: `Invalid size: ${size}`});
                    throw `Invalid size: ${size}`;
                }
                this.log({y,x, msg: `current: ${size} / biggest: ${biggest.size}`});
                if (size > biggest.size) {
                    biggest = { y, x, size };
                }
                x += size;
            }
        }
        return biggest;
    }
}

const solver = new SimpleSolver();
console.log('--------------------------------------');
console.log('Processing:')
const result = solver.processMap(map);
console.log('');


console.log('--------------------------------------');
console.log('Result:')
console.log(`${JSON.stringify(result)}`);
console.log('');