[Day 9: Disk Fragmenter](https://adventofcode.com/2024/day/9) デフラグ！ 配列をどう扱うかが問われ、これまた色々な解法がありそうだ ## 例 ``` 2333133121414131402 ``` 1桁ずつ交互に、それぞれファイルのサイズと空き領域のサイズを表す。ので実際には ``` 00...111...2...333.44.5555.6666.777.888899 ``` という内容。これを右から順番に左端の空き領域に詰め替えていく。最終的には ``` 0099811188827773336446555566.............. ``` となり、この状態のchecksum(各ブロックのインデックス * ファイルID) は **`1928`** `(= 0 * 0 + 1 * 0 + 2 * 9 + 3 * 9 + ....)` となる。 part2ではファイルID降順に見ていって、ファイル全体を動かせる領域が左にあれば丸ごと移動する、という操作に。この例では最終的に ``` 00992111777.44.333....5555.6666.....8888.. ``` となり、checksumは **`2858`** となる。 ## 方針 基本的にはIDの大きいファイルから降順に見ていって、その場所よりも左に空いているスペースがあれば(part1では1以上あれば、part2ではファイルサイズ以上)そこに可能な限りどんどん移動していく、という操作になる。あとはそれをどう実現していくか、というところで工夫の仕方を考える。 ファイル群ではそれぞれ `ID`, 開始位置, サイズ を保持しておく。 空き容量は探索のためにサイズ(`0..9`)ごとのバケットを用意して開始位置を用意しておくと効率的。 ファイル配列を逆順に見ていって、移動したいサイズを決定 (part1 なら`1`、part2ならファイルサイズ)。そのサイズ**以上**のバケットそれぞれで最も左のものを探すことで移動先を決定できる。 従って、各サイズのバケットでは優先度付きキューのようなデータ構造で保持しておくと速い。 移動先が見つかれば、その移動可能サイズ分だけファイルから移す。つまり残りのファイルサイズが減り、移動先のバケットからはその開始位置値が消えて 残った空きスペースのバケットに移る操作をする。 まだファイルの残りサイズがあって同様の操作ができる限り繰り返す。移動先が見つからなかったら据え置きとなる。 それぞれ 移動したものも動かなかったものも `id * (pos + pos + len - 1) * len / 2` でchecksumの値を計算できるので、都度加算しながら上記の処理をしていけば良い。 ## 実装 ### Rust 共通の処理で、part1とpart2では空き領域の検索条件だけが変わることになる。 サイズ`10`の`collections::BinaryHeap`配列を使って効率的に探索できる。 ### Perl こちらは優先度付きキューのようなものはcoreモジュールには存在しないので、配列で持っておいて追加されるたびに `sort` して毎回先頭を見ることで実装した。多少遅くなるが、サイズ`0`のものは無視(どうせ選ばれることは無いので)することで高速化すると十分高速に解ける。