島探し (paizaランク S 相当) を妙な方法で解く

問題

昨夜投稿した際にこの企画を知って、

これを面白そうと思ってしまったので、
まあ被らないだろうと思った方法で解いてみました。

行×列のデータ構造とか使いませんよ。

説明

コードにも大体説明が書いてあるので、合わせて読むなりしてくださればと思います。

最初の行

行数と列数が書いてあるらしいですが使いません。捨てます。

列挙の仕方

これは普通に、1行ずつ、左から順番に見ます。

データ構造

データは以下のような構造です。リンク形式のリストで、1行分の情報を繋げて持ちます。

{ start:開始位置, end:終了位置, id:島ごとのユニーク値, next: 次の構造 } → { start: ... } ...

「0」の場合

何もしません。飛ばします。

「1」の場合

とりあえず他の行のことは気にせず、左隣が「1」だったかどうかで、

• 直前の構造のendの位置を直すか
• 新たに構造を作るか
  を行います。

前の行と隣接している場合

1行前のリストを見て、隣接しているか判定します。
隣接していたとしても、idが同じ(＝島が同じ)場合は何もしません。

隣接していてidが異なる場合は接続処理となります。
idを若い方に合わせて置換するのですが、変更する側は、その行のすべての構造のidを確認して同時に置換します。

データはどこまで覚えておくか

1行前のリストは必要なので覚えておきます。
それより前の行のことは忘れてください。

何をもって島の数とするか

「構造を生成した回数」と「前の行と接続した回数」の差が島の数となります。

コード

search-island.js

// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the CC0 1.0 Universal license.
'use strict';

let first     = true; // 先頭行を飛ばす用
let before    = null; // 前行の先頭(一番左)の陸地
let created   = 0   ; // 生成した陸地の数
let connected = 0   ; // 接続した回数
let id        = 0   ; // 島ごとに割り振る値

require('node:readline').createInterface({ input: process.stdin }).on('line', line => { // 1行ごと
	if (first) { first = false; return; } // 先頭行は破棄
	
	let current = null; // 現在の行の先頭を記憶
	let left    = null; // 現在位置の左側にある陸地
	
	line.split(' ').forEach((bit, i) => { // 1行の0,1を列挙  bit:'0'or'1' i:この行における位置
		if (bit === '0') { return; } // '0'は何もしない
		
		let land = null; // 今回の陸地
		
		if (left && (left.end === (i - 1))) {
			// 左隣と陸続きの場合
			left.end = i; // endを訂正するだけ
			land = left;
		} else {
			// 新しい陸地 (前行のことは考えずに一旦生成する)
			land = { start: i, end: i, id: id++, next: null }; created++; // 生成してカウント
			if (!current) { current = land; } // この行の最初の陸地だった場合は記憶
			if (left) { left.next = land; } // 左の陸地がある場合はnextで辿れるようにしておく
			left = land; // 次のleftとして今回の陸地を設定しておく
		}
		
		while (before && (before.end < i)) { before = before.next; } // 前行で過ぎてしまった構造は飛ばす
		
		// 前行と陸続きかどうか、それが異なるID(島)か判定
		if (before && (before.start <= i) && (i <= before.end) && (before.id !== land.id)) {
			// 接続処理
			connected++; // 接続した回数をカウント
			
			// 片方の列のIDを置換する処理
			function replace(target, old_id, new_id) {
				for (; target; target = target.next) { if (target.id === old_id) { target.id = new_id; } }
			}
			// 若い方のIDに合わせる
			if (before.id < land.id) { replace(current, land.id  , before.id); } // 前行の方がIDが若い場合
			else                     { replace(before , before.id, land.id  ); } // 現在の行の方がIDが若い場合
		}
	});
	
	before = current; // 現在の行を次の前行とする
})
.on('close', () => { console.log(created - connected); }); // 「生成回数 - 接続回数」が島の数

感想

このロジックで厄介だったのはID合わせの部分でした。
若い方に合わせる点、まだ参照される可能性のある構造も全部置換しないといけない点が気づきにくく、何度か修正しました。
もう少しスマートな区別方法があるかもしれないですね。