[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ではファイルサイズ以上)そこに可能な限りどんどん移動していく、という操作になる。あとはそれをどう実現していくか、というところで工夫の仕方を考える。
実際に各サイズの領域を持つ配列を作る代わりに、各ファイル・各空き容量がどのindexから開始するか、を保持する配列を作っておく。例からだと `[0, 2, 5, 8, 11, 12, 15, ...]` という感じ。
それを使えばchecksumの計算は容易になる。
ファイルの移動は可能な箇所が見つかれば `min(移動元ファイル容量, 移動先空き領域容量)` だけ移す。
- 移動したものは移動先のindexを使ってchecksumを計算
- 移動した量だけ移動元のファイルサイズを減らす
- 移動した量だけ移動先の空き容量を減らす
- 移動した量だけ移動先の開始indexを増やす
- 移動できるものが無く残ったものはそのままの位置でchecksumを計算
という操作の繰り返しで合計値を算出できる。
移動可能な位置の検索に毎回左端から探すのは非効率でheapなどを使うことで効率化できそうではあるが、実際の入力で都度検索していてもそこまで時間はかからないので手抜きしても問題なさそうではある。
## 実装
### Rust
共通の処理で、part1とpart2では空き領域の検索条件だけが変わることになる。
```rust
struct Solution {
disk_map: Vec<usize>,
}
impl Solution {
fn resulting_checksum(&self, move_whole: bool) -> usize {
let mut disk_map = self.disk_map.clone();
let mut offsets = vec![0; disk_map.len()];
for i in 1..disk_map.len() {
offsets[i] = offsets[i - 1] + disk_map[i - 1];
}
let mut sum = 0;
for i in (0..self.disk_map.len()).step_by(2).rev() {
while let Some(j) = (1..i)
.step_by(2)
.find(|j| disk_map[*j] > if move_whole { disk_map[i] - 1 } else { 0 })
{
for _ in 0..disk_map[i].min(disk_map[j]) {
sum += i / 2 * offsets[j];
offsets[j] += 1;
disk_map[i] -= 1;
disk_map[j] -= 1;
}
if disk_map[i] == 0 {
break;
}
}
for j in 0..disk_map[i] {
sum += i / 2 * (offsets[i] + j);
}
}
sum
}
fn new<R>(r: R) -> Result<Self, Error>
where
R: Read,
{
let mut buf = String::new();
BufReader::new(r).read_to_string(&mut buf)?;
Ok(Self {
disk_map: buf.trim().bytes().map(|u| usize::from(u - b'0')).collect(),
})
}
fn part1(&self) -> usize {
self.resulting_checksum(false)
}
fn part2(&self) -> usize {
self.resulting_checksum(true)
}
}
```