Advent of code 2015 Day 24 Part 1 & Part 2 を Livebook で楽しむ

はじめに

Advent of code 2024 の準備として、過去回の Advent of code 2015 を Livebook で楽しみます

本記事では Day 24 の Part 1 と Part 2 を解きます

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

入力例を使って解いてみましょう

packages = Enum.to_list(1..5) ++ Enum.to_list(7..11)

実行結果

[1, 2, 3, 4, 5, 7, 8, 9, 10, 11]

3 つのコンテナに分けて同じ重量になるので、一つのコンテナの重量は全重量の 1/3 です

target_weight = packages |> Enum.sum() |> div(3)

実行結果

20

コンテナ内の荷物数を最小にするため、とりあえず二つだとして、全ての組み合わせのうち、合計が目標の重量になるものを抽出します

量子もつれは重量の総積で、そのうちの最小値を求めます

for num_a <- packages,
    num_b <- packages,
    num_a < num_b,
    num_a + num_b == target_weight do
  [num_a, num_b]
end
|> Enum.uniq()
|> Enum.filter(&(&1 != []))
|> Enum.map(&Enum.product(&1))
|> Enum.min()

実行結果

99

実際の入力を取得します

packages =
  puzzle_input
  |> String.split("\n")
  |> Enum.map(&String.to_integer(&1))

実行結果

[1, 3, 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

目標重量を求めます

target_weight = packages |> Enum.sum() |> div(3)

実行結果

508

入力例と同じことを行えば良いのですが、実際には最小の荷物数が何個なのか分かりません

そのため、 Day 21 で使ったのと同じ、組み合わせ生成モジュールを使用し、目標重量ができるまで徐々に増やしていきます

defmodule Combinations do
  def all(_, 0), do: [[]]
  def all([], _), do: []
  def all(list, n) when length(list) == n, do: [list]

  def all([head | tail], n) do
    with_head = for combo <- all(tail, n - 1), do: [head | combo]
    without_head = all(tail, n)
    with_head ++ without_head
  end
end

1..length(packages)
|> Enum.reduce_while(nil, fn size, _ ->
  packages
  |> Combinations.all(size)
  |> Enum.filter(fn combo ->
    Enum.sum(combo) == target_weight
  end)
  |> case do
    [] ->
      {:cont, []}

    valid_combinations ->
      {:halt, valid_combinations}
  end
end)
|> Enum.map(&Enum.product(&1))
|> Enum.min()

Part 2

回答

コンテナが 4 つになるので、目標重量の計算が変わります

以上です

target_weight = packages |> Enum.sum() |> div(4)

まとめ

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

全てのコンテナを考える必要はない、ということに気づけば簡単な問題でした

あと 1 日で AOC 2015 はコンプリートです！