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

はじめに

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

まずは入力例で考えます

sample_input = "2333133121414131402"

入力はデータ使用領域の数と空き領域の数を交互に表しています

データ使用領域に 0 から連番の ID を振り、空き領域の ID を nil として領域ブロックの配列を作りましょう

交互になっているので、 2 で割った余りで使用領域か否かを判定でき、 ID は 2 で割った結果になります

後で使いたいので、ついでに空き領域のブロック数もカウントしておきます

get_blocks = fn input ->
  input
  |> String.codepoints()
  |> Enum.with_index()
  |> Enum.reduce({[], 0}, fn {num, index}, {acc_list, acc_num_blanck} ->
    num = String.to_integer(num)

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

    {
      acc_list ++ List.duplicate(id, num),
      acc_num_blanck + num_blanck
    }
  end)
end

{blocks, num_blank} = get_blocks.(sample_input)

実行結果

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

空き状態のブロック（nil になっている箇所）に後ろから順にファイルで使用いているブロックを詰めていきます

最大でも、ブロックの交換回数は今ある空きブロックの数です

操作しやすいようにブロックを逆順にして、交換先の空きブロックを探し、使用ブロックの ID で埋めていきます

空きブロックと交換するので、先頭（元の末尾）のブロックは不要となるため、 tl() で先頭以外を取り出します

空きブロックがなくなったら処理を終了させます

最後に、逆順にしていたのを元に戻します

compact = fn blocks, num_blank ->
  1..num_blank
  |> Enum.reduce_while(Enum.reverse(blocks), fn _, acc_blocks ->
    case acc_blocks |> Enum.reverse() |> Enum.find_index(&(is_nil(&1))) do
      nil ->
        {:halt, acc_blocks}
      index ->
        blank_index = length(acc_blocks) - 1 - index
  
        {
          :cont,
          acc_blocks
          |> List.update_at(blank_index, fn _ -> hd(acc_blocks) end)
          |> tl()
        }
    end
  end)
  |> Enum.reverse()
end

compacted_blocks = compact.(blocks, num_blank)

実行結果

[0, 0, 9, 9, 8, 1, 1, 1, 8, 8, 8, 2, 7, 7, 7, 3, 3, 3, 6, 4, 4, 6, 5, 5, 5, 5, 6, 6]

このブロックについて、チェックサムを計算します

get_checksum = fn blocks ->
  blocks
  |> Enum.with_index()
  |> Enum.map(fn {num, index} ->
    num * index
  end)
  |> Enum.sum()
end

get_checksum.(compacted_blocks)

実行結果

1928

これを実際の入力に対して行えば答えが出ます

{blocks, num_blank} = get_blocks.(puzzle_input)

compacted_blocks = compact.(blocks, num_blank)

get_checksum.(compacted_blocks)

まとめ

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

ブロックを一個一個交換する手順にしたため、結構実行時間が長くなってしまいました

Part 2 は全く違う構造で解いています