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

はじめに

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

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

問題文はこちら

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

セットアップ

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

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

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

いちいち四則演算するのが面倒になってきたので、 Nx による行列演算を導入します

入力の取得

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

私の答え

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

回答

まず正規表現で入力をパースします

Regex.named_captures(
  ~r/(?<ingredient>[a-zA-Z]+): .+ (?<capacity>\-*\d+), .+ (?<durability>\-*\d+), .+ (?<flavor>\-*\d+), .+ (?<texture>\-*\d+), .+ (?<calories>\-*\d+)/,
  "Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8"
)

実行結果

%{
  "calories" => "8",
  "capacity" => "-1",
  "durability" => "-2",
  "flavor" => "6",
  "ingredient" => "Butterscotch",
  "texture" => "3"
}

入力を行列に変換する関数を用意します

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} ->
      [
        String.to_integer(capacity),
        String.to_integer(durability),
        String.to_integer(flavor),
        String.to_integer(texture)
      ]
    end)
  end)
  |> Nx.tensor()
end

入力例を使って試します

ingredients =
  [
    "Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8",
    "Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3"
  ]
  |> get_ingredients_tensor.()

実行結果

#Nx.Tensor<
  s32[2][4]
  [
    [-1, -2, 6, 3],
    [2, 3, -2, -1]
  ]
>

バタースコッチを小さじ44杯、シナモンを小さじ56杯のレシピを定義します

nums = Nx.tensor([[44, 56]])

材料とレシピの内積により、各プロパティのスコアを計算することができます

Nx.dot(nums, ingredients)

実行結果

#Nx.Tensor<
  s32[1][4]
  [
    [68, 80, 152, 76]
  ]
>

最終的なスコアは各プロパティのスコアを全てかけたものです

nums
|> Nx.dot(ingredients)
|> Nx.product(axes: [1])

実行結果

#Nx.Tensor<
  s32[1]
  [62842880]
>

出力例と同じ値になりました

パズルの入力を行列に変換します

ingredients =
  puzzle_input
  |> String.split("\n")
  |> get_ingredients_tensor.()

実行結果

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

各材料の分量が合計 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

実行結果

[
  [0, 0, 0, 100],
  [0, 0, 1, 99],
  [0, 0, 2, 98],
  [0, 0, 3, 97],
  ...
]

各組み合わせについて、プロパティ毎のスコアを計算します

all_combinations
|> Nx.tensor()
|> Nx.dot(ingredients)

実行結果

#Nx.Tensor<
  s32[176851][4]
  [
    [-100, 0, 0, 200],
    [-99, -1, 4, 198],
    [-98, -2, 8, 196],
    ...
  ]
>

スコアがマイナスになっている場合は 0 にするため、 0 と Nx.max() を取ります

all_combinations
|> Nx.tensor()
|> Nx.dot(ingredients)
|> Nx.max(0)

実行結果

#Nx.Tensor<
  s32[176851][4]
  [
    [0, 0, 0, 200],
    [0, 0, 4, 198],
    [0, 0, 8, 196],
    ...
  ]
>

各組み合わせ毎に合計スコアを計算します

all_combinations
|> Nx.tensor()
|> Nx.dot(ingredients)
|> Nx.max(0)
|> Nx.product(axes: [1])

実行結果

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

最後に最大値を求めます

all_combinations
|> Nx.tensor()
|> Nx.dot(ingredients)
|> Nx.max(0)
|> Nx.product(axes: [1])
|> Nx.reduce_max()

まとめ

いよいよ行列演算を使い出して、難易度の上昇を感じますね

Part 2 はこちら