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

はじめに

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

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

まずは入力例で考えます

sample_input = "2333133121414131402"

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

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

blocks = get_blocks.(sample_input)

実行結果

[
  {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）

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

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

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

compacted_blocks = compact.(blocks)

実行結果

[
  {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 として計算します

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

get_checksum.(compacted_blocks)

実行結果

2858

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

blocks = get_blocks.(puzzle_input)

compacted_blocks = compact.(blocks)

get_checksum.(compacted_blocks)

まとめ

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

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