Advent of code 2015 Day 15 Part 2 を Livebook で楽しむ

はじめに

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

本記事では Day 15 の Part 2 を解きます

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

Nx による行列演算を導入します

入力の取得

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

私の答え

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

回答

Part 2 ではカロリーも含めて行列化します

get_ingredients_tensor = fn rows ->
  rows
  |> Enum.map(fn row ->
    Regex.named_captures(
      ~r/(?<ingredient>[a-zA-Z]+): .+ (?<capacity>\-*\d+), .+ (?<durability>\-*\d+), .+ (?<flavor>\-*\d+), .+ (?<texture>\-*\d+), .+ (?<calories>\-*\d+)/,
      row
    )
    |> then(fn %{"capacity" => capacity, "durability" => durability, "flavor" => flavor, "texture" => texture, "calories" => calories} ->
      [
        String.to_integer(capacity),
        String.to_integer(durability),
        String.to_integer(flavor),
        String.to_integer(texture),
        String.to_integer(calories)
      ]
    end)
  end)
  |> Nx.tensor()
end

カロリーは使用方法が他のプロパティとは異なるため、分離しておきます

{ingredients, calories} =
  puzzle_input
  |> String.split("\n")
  |> get_ingredients_tensor.()
  |> Nx.split(4, axis: 1)

実行結果

{#Nx.Tensor<
   s32[4][4]
   [
     [5, -1, 0, 0],
     [-1, 3, 0, 0],
     [0, -1, 4, 0],
     [-1, 0, 0, 2]
   ]
 >,
 #Nx.Tensor<
   s32[4][1]
   [
     [5],
     [1],
     [6],
     [8]
   ]
 >}

Part 1 と同じく、合計が 100 になる組み合わせを全て取得します

all_combinations =
  for sprinkles <- 0..100,
      peanut_butter <- 0..100,
      frosting <- 0..100,
      sugar <- 0..100,
      sprinkles + peanut_butter + frosting + sugar == 100 do
    [sprinkles, peanut_butter, frosting, sugar]
  end

無条件に全組み合わせの合計スコアを計算します

all_products =
  all_combinations
  |> Nx.tensor()
  |> Nx.dot(ingredients)
  |> Nx.max(0)
  |> Nx.product(axes: [1], keep_axes: true)

各組み合わせについてカロリーが 500 なら 1 、それ以外なら 0 になるカロリー条件行列を生成します

valid_calories =
  all_combinations
  |> Nx.tensor()
  |> Nx.dot(calories)
  |> Nx.equal(500)

実行結果

#Nx.Tensor<
  s32[176851][1]
  [
    [0],
    [0],
    [0],
    ...
  ]
>

合計スコアとカロリー条件行列を結合して積を求めます

カロリーが 500 の組み合わせ以外はスコアが 0 になり、条件をクリアした値のうちの最大値が求められます

Nx.concatenate([all_products, valid_calories], axis: 1)
|> Nx.product(axes: [1])
|> Nx.reduce_max()

まとめ

かなりややこしい問題ですが、 Nx の力でクリアできました