test-collect-rain.ts

/*

	二维接雨水
	1. 假设存在 n * m 矩形随机山体（类似泰拉瑞亚）
	2. 雨水从山体顶部开始流动，流动到山体底部，灌满所有空腔
	3. 当雨水停止流动后，山体中的水会漏出来达到平衡
	4. 最后求出山体中的留下来的水的总量

*/
import 'colors';

enum BlockContent {
	EMPTY = 0,
	WALL = 1,
	WATER = 2,
};

type Position = readonly [number, number];

class Block {
	content: BlockContent;

	readonly hill: Hill;
	readonly position: Position;

	constructor(hill: Hill, position: Position) {
		this.content = BlockContent.EMPTY;
		this.hill = hill;
		this.position = position;
	}

	left(): Block | null { return this.hill.getBlock([this.position[0] - 1, this.position[1]]) }
	right(): Block | null { return this.hill.getBlock([this.position[0] + 1, this.position[1]]) }
	top(): Block | null { return this.hill.getBlock([this.position[0], this.position[1] - 1]) }
	bottom(): Block | null { return this.hill.getBlock([this.position[0], this.position[1] + 1]) }

	show(): string {
		return ({
			[BlockContent.EMPTY]: '  ',
			[BlockContent.WALL]: '  '.bgWhite,
			[BlockContent.WATER]: '  '.bgBlue,
		})[this.content];
	}
}

// class ConnectedArea {
// 	content: Set<Block>
// }

type InitialContent = BlockContent[][];

class Hill {
	readonly waterBlocks: Set<Block> = new Set;

	readonly width: number;
	readonly height: number;
	readonly content: ReadonlyArray<ReadonlyArray<Block>>;

	constructor(width: number, height: number, initialContent?: InitialContent) {
		this.width = width;
		this.height = height;

		this.content = (initialContent || Hill.createRandomInitialContent(width, height))
			.map((row, y) => row.map((c, x) => {
				const block = new Block(this, [x, y]);
				block.content = c;
				return block;
			}));
	}

	getBlock([x, y]: Position) {
		return this.content[y]?.[x];
	}

	show() {
		for (const row of this.content) {
			console.log('|' + row.map(b => b.show()).join('') + '|')
		}
		console.log(''.padEnd(this.width * 2 + 2, '-'))
		console.log('water: ', this.waterBlocks.size)
	}

	showSaveData() {
		console.log('[')
		console.log(this.content.map(row => `  [${row.map(b => b.content === BlockContent.WALL ? BlockContent.WALL : BlockContent.EMPTY).join(',')}]`).join(',\n'));
		console.log(']')
	}

	// 大水漫灌
	water() {
		const travel = (block: Block | null) => {
			if (!block || block.content !== BlockContent.EMPTY) {
				return;
			}
			block.content = BlockContent.WATER;
			this.waterBlocks.add(block);
			travel(block.left())
			travel(block.right())
			travel(block.top())
			travel(block.bottom())
		}

		for (const block of this.content[0]) {
			travel(block);
		}
	}

	// 雨停漏水
	leak() {
		const travel = (block: Block | null) => {
			if (!block || block.content !== BlockContent.WATER) {
				return;
			}
			block.content = BlockContent.EMPTY;
			this.waterBlocks.delete(block);
			travel(block.left())
			travel(block.right())
			travel(block.top())
		}

		for (const block of this.content[this.height - 1]) {
			travel(block);
		}
		for (const row of this.content) {
			travel(row[0]);
			travel(row[this.width - 1]);
		}
	}

	// 连通水域水位平衡
	balance() {
		const unresolvedBlocks = new Set(this.waterBlocks);

		const waterFaces = [...unresolvedBlocks].filter(b => {
			const top = b.top();
			return !top || top.content === BlockContent.EMPTY
		}).sort((a, b) => b.position[1] - a.position[1]);

		for (const waterFace of waterFaces) {
			const climbingTravel = (block: Block | null) => {
				if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
					return;
				}
				block.content = BlockContent.EMPTY;
				this.waterBlocks.delete(block);
				unresolvedBlocks.delete(block);
				climbingTravel(block.left());
				climbingTravel(block.right());
				climbingTravel(block.top());
			}
			const divingTravel = (block: Block | null) => {
				if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
					return;
				}
				unresolvedBlocks.delete(block);
				divingTravel(block.left())
				divingTravel(block.right())
				divingTravel(block.bottom())
				if (block.position[1] === waterFace.position[1]) {
					climbingTravel(block.top());
				} else {
					divingTravel(block.top());
				}
			}
			divingTravel(waterFace);
		}
	}

	collectRain() {
		this.show();
		console.log('=== water ===')
		this.water();
		this.show();
		console.log('=== leak ===')
		this.leak();
		this.show();
		console.log('=== balance ===')
		this.balance();
		this.show();
		// console.log('=== save date ===')
		// this.showSaveData();
	}

	static createRandomInitialContent(width: number, height: number): InitialContent {
		const remap = ([x0, x1]: [number, number], [y0, y1]: [number, number]) => {
			const dx = x1 - x0;
			const dy = y1 - y0;
			return function (x: number) {
				const px = (x - x0) / dx;
				return y0 + px * dy;
			};
		}
		const remapProbability = remap([0, height - 1], [0.2, 0.7]);

		return Array.from({ length: height })
			.map((_, h) => Array.from({ length: width })
				.map(_ => Math.random() > remapProbability(h) ? BlockContent.EMPTY : BlockContent.WALL));
	}

}

const hill = new Hill(20, 10);
hill.collectRain();

// cases
const cases = [
	[
		[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
		[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
		[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
		[0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
		[1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0],
		[0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1],
		[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
		[0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1],
		[0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1],
		[0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1]
	],

	[
		[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
		[0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
		[0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0],
		[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1],
		[0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
		[1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
		[0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
		[1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
		[0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1],
		[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]
	],

	[
		[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0],
		[0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0],
		[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
		[1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1],
		[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
		[1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
		[0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1],
		[0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
	],

	[
		[0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
		[0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
		[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0],
		[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0],
		[1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0],
		[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1],
		[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1],
		[1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1],
		[0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0],
		[1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1]
	],
	[
		[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0],
		[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0],
		[0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
		[1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0],
		[1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1],
		[1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1],
		[1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0],
		[1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1]
	],
	[
		[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
		[1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
		[0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0],
		[1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
		[1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1],
		[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
		[1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1],
		[1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1],
		[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
		[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0]
	],
];