Advent of code 2024 Day 9 Part 2 を Livebook で楽しむ

## はじめに

Advent of code 2024 Day 9 の Part 1 を解きます

問題文はこちら

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

実装したノートブックはこちら

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2024/2024_day9_part2.livemd

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/88bd1a5c32596af990b0

## セットアップ

Kino AOC をインストールします

```elixir
Mix.install([
  {:kino_aoc, "~> 0.1"}
])
```

Kino AOC の使い方はこちらを参照

https://qiita.com/RyoWakabayashi/items/3d3abcf9134cee4dff05

## 入力の取得

"Advent of Code Helper" スマートセルを追加し、 Day 9 の入力を取得します

![スクリーンショット 2024-12-11 13.35.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/f8bdc212-bcd1-4638-2138-4dfd9382c17d.png)

## 私の答え

私の答えです。
折りたたんでおきます。
▶を押して開いてください。

<details><summary>回答</summary>

まずは入力例で考えます

```elixir
sample_input = "2333133121414131402"
```

一つのファイル単位（同一の ID を持っているブロックの塊）に空きブロックを埋めていくので、入力を `{<ID>, <ブロック数>}` というファイル単位のタプル配列に変換します

```elixir
get_blocks = fn input ->
  input
  |> String.codepoints()
  |> Enum.with_index()
  |> Enum.map(fn {num, index} ->
    num = String.to_integer(num)

    id =
      case rem(index, 2) do
        0 ->
          div(index, 2)
        _ ->
          nil
      end

    {id, num}
  end)
end
```

```elixir
blocks = get_blocks.(sample_input)
```

実行結果

```elixir
[
  {0, 2},
  {nil, 3},
  {1, 3},
  {nil, 3},
  {2, 1},
  {nil, 3},
  {3, 3},
  {nil, 1},
  {4, 2},
  {nil, 1},
  {5, 4},
  {nil, 1},
  {6, 4},
  {nil, 1},
  {7, 3},
  {nil, 1},
  {8, 4},
  {nil, 0},
  {9, 2}
]
```

後ろからファイル毎に処理するため、繰り返し回数はブロック数の半分になります（使用ブロックと空きブロックが交互に並んでいるため）

交換対象のファイルは、交換後の状態と関係なしに常に後ろから順に選択していきます

空きファイル（`is_nil(id)`）かつ空きが十分（`num >= target_num`）な空き領域を探し、見つかれば位置を交換します

交換するときの位置はここまでの繰り返しの影響を受けるため、改めて位置を取得し直します

交換先が交換元よりも左にある場合のみ、交換します（`taregt_index > target_blank_index`）

交換によってピッタリ空きが埋まらなかった場合、隙間にできた新しい空き領域を追加します

空き領域が連続している場合、それらを一つの空き領域としてまとめます

```elixir
compact = fn blocks ->
  0..(blocks |> length() |> div(2) |> Kernel.-(1))
  |> Enum.reduce(blocks, fn index, acc_blocks ->
    taregt_index = length(blocks) - 1 - index * 2
    {target_id, target_num} = Enum.at(blocks, taregt_index)

    acc_blocks
    |> Enum.find_index(fn {id, num} ->
      is_nil(id) && num >= target_num
    end)
    |> case do
      nil ->
        acc_blocks

      target_blank_index ->
        {_, num} = Enum.at(acc_blocks, target_blank_index)
        taregt_index = Enum.find_index(acc_blocks, fn {id, _} -> id == target_id end)

        if taregt_index > target_blank_index do
          # 空き領域と使用領域を交換
          acc_blocks =
            acc_blocks
            |> List.update_at(target_blank_index, fn _ ->
              {target_id, target_num}
            end)
            |> List.update_at(taregt_index, fn _ ->
              {nil, target_num}
            end)

          if num == target_num do
            acc_blocks
          else
            # 隙間の空き領域を追加
            List.insert_at(acc_blocks, target_blank_index + 1, {nil, num - target_num})
          end
          |> Enum.reduce({[], nil}, fn {id, num} = new, {acc_acc_blocks, pre_block} ->
            # 連続する空き領域を一つにまとめる
            case {pre_block, id} do
              {{nil, pre_num}, nil} ->
                merged = {nil, num + pre_num}
                {[merged | tl(acc_acc_blocks)], merged}
              _ ->
                {[new | acc_acc_blocks], new}
            end
          end)
          |> elem(0)
          |> Enum.reverse()
        else
          acc_blocks
        end
    end
  end)
end
```

```elixir
compacted_blocks = compact.(blocks)
```

実行結果

```elixir
[
  {0, 2},
  {9, 2},
  {2, 1},
  {1, 3},
  {7, 3},
  {nil, 1},
  {4, 2},
  {nil, 1},
  {3, 3},
  {nil, 4},
  {5, 4},
  {nil, 1},
  {6, 4},
  {nil, 5},
  {8, 4},
  {nil, 2}
]
```

ID とブロック数のタプルになっていたブロックを ID の配列として展開し、チェックサムを計算します

ID が `nil` の場合（空き領域の場合）、 0 として計算します

```elixir
get_checksum = fn blocks ->
  blocks
  |> Enum.flat_map(fn {id, num} ->
    List.duplicate(id, num)
  end)
  |> Enum.with_index()
  |> Enum.map(fn {num, index} ->
    case num do
      nil -> 0
      _ -> num * index
    end
  end)
  |> Enum.sum()
end
```

```elixir
get_checksum.(compacted_blocks)
```

実行結果

```elixir
2858
```

同じことを実際の入力に対して実行します

```elixir
blocks = get_blocks.(puzzle_input)
```

```elixir
compacted_blocks = compact.(blocks)
```

```elixir
get_checksum.(compacted_blocks)
```

</details>

## まとめ

問題文から ChatGPT に画像を生成してもらいました

![aoc2024_day9_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/d13e3763-19a3-0275-6338-e097911892e4.png)

ややこしくはあるものの、考えやすい問題でした