[Advent of Code 2024] Day 9: Disk Fragmenter

この記事は、[mae616 Advent of Code Advent Calendar 2024](https://qiita.com/advent-calendar/2024/mae616) の9日目の記事です。

https://qiita.com/advent-calendar/2024/mae616

このアドベントカレンダーは皆勤賞のQiitaくんのぬいぐるみに惹かれて挑戦している大変ゆるい挑戦のものです。そんな感じで読んでいただければ幸いです。

Advent of Code は後半になるにつれて難しくなると聞くので、どこで難しさに打ちのめされるかな、と思っています ꉂꉂ( ᐛ )
ちなみに、何も意識せず始めたこのアドベントカレンダーの記事ですが、個人的に自分でこの記事の書き方が気に入っています。今後こういう感じで書こうかな、と思っています٩( ᐛ )و

------

前の日: [[Advent of Code 2024] Day 8: Resonant Collinearity](https://qiita.com/mae616/items/4edb1bc3d9249cddb724)
次の日: [[Advent of Code 2024] Day 10: Hoof It](https://qiita.com/mae616/items/b7819c82a31f545f95a8)

# 今日のお題

https://adventofcode.com/

https://adventofcode.com/2024/day/9

# 9日目の物語
> ■ 9日目: ディスク断片化ツール
> デバイスのボタンをもう一度押すと、あなたはまた見覚えのある『アンフィポッドたちの廊下』に移動する！みんなそれぞれ小型の潜水艦を手に入れてるから良かったね。歴史学者たちは、壁にぶつかりながらも、主任歴史学者を探してさっさと進んでいく。

『アンフィポッド』は Advent of Code 2021 と繋がっていて、んーエビみたいな形をした生き物のことなのかな？よくわからないけどそういう生き物の分類のことらしい。
小型の潜水艦はどこで手に入れたのだろう、前の年かな。

> あなたは隅っこでコンピュータに困っているアンフィポッドを見かける。彼は、ファイルを圧縮して空き領域を増やそうとしているが、プログラムがうまく動かないようだ。あなたは手伝うことを申し出る。
> 彼はすでに生成したディスクマップ（あなたのパズルの入力）を見せてくれる。

さて、今回のパズルみたいですね。レッツゴー٩( ᐛ )و

# 1問目
例:
```
2333133121414131402
```
> ディスクマップは、ディスク上のファイルと空き領域の配置を示すために、密なフォーマットを使っています。数字はファイルの長さと空き領域の長さを<INS>交互</INS>に示しています。

> 例えば、ディスクマップ `12345` は、
> * `1` ブロックのファイル
> * `2` ブロックの空き領域
> * `3` ブロックのファイル
> * `4` ブロックの空き領域
> * `5` ブロックのファイル
>
> を表します。

> ディスクマップ `90909` は、`9` ブロックのファイルが3つ並んでいる（間に空き領域なし）ことを表しています。
> * `9` ブロックのファイル
> * `0` ブロックの空き領域
> * `9` ブロックのファイル
> * `0` ブロックの空き領域
> * `9` ブロックのファイル

ここから『ブロックの形式』の話になります。
> ディスク上の各ファイルには、並べ替え前の順番に基づいてID番号が付けられ、IDは `0` から始まります。

> つまり、ディスクマップ `12345` には3つのファイルがあります。
> * `1` ブロックの<INS>ファイル</INS> ... ID: `0`
> * `2` ブロックの空き領域
> * `3` ブロックの<INS>ファイル</INS> ... ID: `1`
> * `4` ブロックの空き領域
> * `5` ブロックの<INS>ファイル</INS> ... ID: `2`
>
> 各ブロックには1文字を使い、`数字` がファイルIDを、ドット( `.` )が空き領域を示します。
> ディスクマップ `12345` は次のようにブロックを表現します。
> `0..111....22222`
> ※ `数字` や `.` の繰り返し数は、何ブロックあるかの数

ここから、『空きブロックを増やす最適化』の話に入ります。
> アンフィポッドは、ファイルブロックを1つずつディスクの端から左端の空きスペースブロックに移動したいと考えています（ファイルブロック間に隙間がなくなるまで）。
> ディスクマップ `12345`の場合、このプロセスは次のようになります：
> * 1.まず、『ブロックの形式』にします
> `0..111....22222`
> * 2.『空きブロックを増やす最適化』で `一番右端のファイル` を `一番左端の空き容量` に移動していくを繰り返します
> (1) 0<INS>.</INS>.111....2222<INS>2</INS>  →  0<INS>2</INS>.111....2222<INS>.</INS>
> (2) 02<INS>.</INS>111....222<INS>2</INS>.  →  02<INS>2</INS>111....222<INS>.</INS>.
> (3) 022111<INS>.</INS>...22<INS>2</INS>..  →  022111<INS>2</INS>...22<INS>.</INS>..
> (4) 0221112<INS>.</INS>..2<INS>2</INS>...  →  0221112<INS>2</INS>..2<INS>.</INS>...
> (5) 02211122<INS>.</INS>.<INS>2</INS>....  →  02211122<INS>2</INS>.<INS>.</INS>....
> (6) 022111222......  最適化完了

初めの例に戻りましょう。
『ブロックの形式』にすると下記になります。
```
00...111...2...333.44.5555.6666.777.888899
```

『空きブロックを増やす最適化』は下記のステップを辿ります。
```
00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............
```

パズルの答えは、最適化した結果の『ファイルシステムのチェックサム』を求めてください、てことみたいです。
最適化後のブロックは、
```
0099811188827773336446555566..............
```
です。
> チェックサムを計算するには、各ブロックの位置と、そのブロックに含まれるファイルID番号を掛け算した結果を合計します。最も左のブロックは位置0です。ブロックに空き領域が含まれている場合は、それをスキップします。

なので、左から順に
* 1文字目: インデックス `0` * ID `0` (0 * 0) = `0` 
* 2文字目: インデックス `1` * ID `0` (1 * 0) = `0` 
* 3文字目: インデックス `2` * ID `9` (2 * 9) = `18` 
* 4文字目: インデックス `3` * ID `9` (3 * 9) = `27` 
* 5文字目: インデックス `4` * ID `8` (4 * 8) = `32`
* ... (続く)

となって求めた値の合計 `(0 + 0 + 18 + 27 + 32 + ... ) = ` の `1928` が答えになります。

やってみましょう ٩( ᐛ )و



## 解いたコード
```js: ./day9_1/main.js
function main(input) {
  const args = input.split("\n");
  const s = args[0];

  // ブロック化
  let id = 0;
  let isFile = true;
  const aryFileBlock = [];
  for (let c of s) {
    if (isFile) {
      aryFileBlock.push(...new Array(Number(c)).fill(id));
      id++;
    } else {
      aryFileBlock.push(...new Array(Number(c)).fill("."));
    }
    isFile = !isFile;
  }

  // 最適化
  let blank = 0;
  let file = aryFileBlock.length - 1;
  while (blank < file) {
    if (aryFileBlock[blank] !== ".") {
      blank++;
    }
    if (aryFileBlock[file] === ".") {
      file--;
    }
    if (aryFileBlock[blank] === "." && aryFileBlock[file] !== ".") {
      [aryFileBlock[blank], aryFileBlock[file]] = [
        aryFileBlock[file],
        aryFileBlock[blank],
      ];
      blank++;
      file--;
    }
  }

  // チェックサムの計算
  let sum = 0;
  for (let i = 0; i < aryFileBlock.length; i++) {
    if (aryFileBlock[i] !== ".") {
      sum += i * Number(aryFileBlock[i]);
    }
  }
  console.log(sum);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
IDが二桁以上ある場合を考慮できなくてミスっちゃいました ꉂꉂ( ᐛ )

https://github.com/mae616/adventOfCode2024/tree/main/day9_1

下記で実行できます。
```zsh: zsh
$ cd day9_1
$ node main.js
```

# 2問目
個々のブロックを移動するのではなく、ファイル全体を移動してディスクを最適化しましょう。

あ、やっぱりそうきますよね ꉂꉂ( ᐛ )

> 今回は、ファイルが収まる左端の空き領域にファイル全体を移動することを試みます。ファイルID番号が大きいものから順に、各ファイルを1回だけ移動してみてください。もしファイルを収めるのに十分な空き領域が左側に見つからなければ、そのファイルは移動しません。

> 初めの例での今回の最適化のステップは下記になります。
> ```
> 00...111...2...333.44.5555.6666.777.888899
> 0099.111...2...333.44.5555.6666.777.8888..
> 0099.1117772...333.44.5555.6666.....8888..
> 0099.111777244.333....5555.6666.....8888..
> 00992111777.44.333....5555.6666.....8888..
> ```
> チェックサムは `2858` になります。

やってみましょう٩( ᐛ )و

## 解いたコード
```js: ./day9_2/main.js
function main(input) {
  const args = input.split("\n");
  const s = args[0];

  // ブロック化
  let id = 0;
  let isFile = true;
  const aryFileBlock = [];
  for (let c of s) {
    if (isFile) {
      aryFileBlock.push(...new Array(Number(c)).fill(id));
      id++;
    } else {
      aryFileBlock.push(...new Array(Number(c)).fill("."));
    }
    isFile = !isFile;
  }

  // 最適化
  let prevIndex = aryFileBlock.length - 1;
  let fileCount = 1;
  // 右端からfileを探す
  for (let i = aryFileBlock.length - 2; i >= 0; i--) {
    if (aryFileBlock[prevIndex] === ".") {
      prevIndex = i;
      fileCount = 1;
      continue;
    }
    if (aryFileBlock[prevIndex] === aryFileBlock[i]) {
      fileCount++;
      continue;
    }
    // 左端から空き容量を探す
    let start = 0;
    let blankCount = 0;
    for (let j = 0; j < prevIndex; j++) {
      if (aryFileBlock[j] !== ".") {
        start = j + 1;
        blankCount = 0;
        continue;
      }
      blankCount++;

      if (blankCount === fileCount) {
        const fileId = aryFileBlock[prevIndex];
        for (let k = 0; k < fileCount; k++) {
          aryFileBlock[start + k] = fileId;
          aryFileBlock[prevIndex - k] = ".";
        }
        break;
      }
    }
    prevIndex = i;
    fileCount = 1;
  }

  // チェックサムの計算
  let sum = 0;
  for (let i = 0; i < aryFileBlock.length; i++) {
    if (aryFileBlock[i] !== ".") {
      sum += i * Number(aryFileBlock[i]);
    }
  }
  console.log(sum);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
ちょっとケアレスミスしてハマっちゃいました ꉂꉂ( ᐛ )
`prevIndex` のあたりが頭の中でごちゃついちゃいました ꉂꉂ( ᐛ )

https://github.com/mae616/adventOfCode2024/tree/main/day9_2

今日は終わり。
お疲れさまです٩( ᐛ )و

---

今日の海外の人は
https://www.reddit.com/r/adventofcode/
昔のパソコンを思い出して懐かしんでますね ٩( ᐛ )و

では、また明日。