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

## はじめに

Advent of code 2024 Day 13 の Part 2 を解きます

問題文はこちら

https://adventofcode.com/2024/day/13

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2024/2024_day13_part2.livemd

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/349ba425af144850065e

## セットアップ

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

また、今回は行列演算を使いたいので、 [Nx](https://github.com/elixir-nx/nx) もインストールします

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

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

https://qiita.com/RyoWakabayashi/items/3d3abcf9134cee4dff05

## 入力の取得

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

![スクリーンショット 2024-12-18 16.44.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/35f6ab86-a7b8-ebb0-31c2-42ad32b1ff36.png)

## 私の答え

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

<details><summary>回答</summary>

Part 1 の回答のままでは、組み合わせの数が多くなりすぎて終わりません

組み合わせを探索するのではなく、以下の連立方程式を解く方針にしましょう

$$
n_aa_x + n_bb_x = p_x
$$

$$
n_aa_y + n_bb_y = p_y
$$

（$n_a$ は A ボタンを押す回数、 $n_b$ は B ボタンを押す回数）

この連立方程式は行列を使うと以下のように表現できます

![expresssion.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/15b9aeee-2c87-2c5c-dcf8-b35d544166c3.png)

![expresssion (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/12957820-4419-3fbf-19f7-21209042ac32.png)

![expresssion (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/90c4d65f-5195-ca75-ee0e-264dbd9cf2a2.png)

$$
Ax=b
$$

```elixir
sample_input =
  """
  Button A: X+94, Y+34
  Button B: X+22, Y+67
  Prize: X=8400, Y=5400
  
  Button A: X+26, Y+66
  Button B: X+67, Y+21
  Prize: X=12748, Y=12176
  
  Button A: X+17, Y+86
  Button B: X+84, Y+37
  Prize: X=7870, Y=6450
  
  Button A: X+69, Y+23
  Button B: X+27, Y+71
  Prize: X=18641, Y=10279
  """
  |> String.trim()
```

クレーンゲーム機を A と b の行列で表現するように読み込みます

また、桁数が大きいため、型を `:f64` に指定します

```elixir
parse_machines = fn input ->
  input
  |> String.split("\n\n")
  |> Enum.map(fn machine_rows ->
    Regex.named_captures(
      ~r/\+(?<ax>\d+).*\+(?<ay>\d+)\n.*\+(?<bx>\d+).*\+(?<by>\d+)\n.*=(?<px>\d+).*=(?<py>\d+)/,
      machine_rows
    )
  end)
  |> Enum.map(fn %{"ax" => ax, "ay" => ay, "bx" => bx, "by" => by, "px" => px, "py" => py} ->
    %{
      A: Nx.tensor([
          [String.to_integer(ax), String.to_integer(bx)],
          [String.to_integer(ay), String.to_integer(by)]
      ], type: :f64),
      b: Nx.tensor([
        String.to_integer(px) + 10000000000000,
        String.to_integer(py) + 10000000000000
      ], type: :f64)
    }
  end)
end
```

```elixir
machines = parse_machines.(sample_input)
```

実行結果

```elixir
[
  %{
    b: #Nx.Tensor<
      f64[2]
      [10000000008400.0, 10000000005400.0]
    >,
    A: #Nx.Tensor<
      f64[2][2]
      [
        [94.0, 22.0],
        [34.0, 67.0]
      ]
    >
  },
  %{
    b: #Nx.Tensor<
      f64[2]
      [10000000012748.0, 10000000012176.0]
    >,
    A: #Nx.Tensor<
      f64[2][2]
      [
        [26.0, 67.0],
        [66.0, 21.0]
      ]
    >
  },
  %{
    b: #Nx.Tensor<
      f64[2]
      [10000000007870.0, 10000000006450.0]
    >,
    A: #Nx.Tensor<
      f64[2][2]
      [
        [17.0, 84.0],
        [86.0, 37.0]
      ]
    >
  },
  %{
    b: #Nx.Tensor<
      f64[2]
      [10000000018641.0, 10000000010279.0]
    >,
    A: #Nx.Tensor<
      f64[2][2]
      [
        [69.0, 27.0],
        [23.0, 71.0]
      ]
    >
  }
]
```

Nx には連立方程式を解くための関数が用意されています

`Nx.LinAlg.solve(A, b)` で x を求めることができます

```elixir
Nx.LinAlg.solve(
  Nx.tensor([[26, 67], [66, 21]], type: :f64),
  Nx.tensor([10000000012748, 10000000012176], type: :f64)
)
```

実行結果

```elixir
#Nx.Tensor<
  f64[2]
  [118679050709.00002, 103199174542.0]
>
```

誤差はありますが、答えがほぼ整数になっています

連立方程式が解けないケースを実行してみます

```elixir
Nx.LinAlg.solve(
  Nx.tensor([[94, 22], [34, 67]], type: :f64),
  Nx.tensor([10000000008400, 10000000005400], type: :f64)
)
```

実行結果

```elixir
#Nx.Tensor<
  f64[2]
  [81081081161.08109, 108108108148.10811]
>
```

結果が整数ではありません

このことを利用して、ある程度の誤差を許容しつつ、結果が整数であれば解けたと考えられます

```elixir
get_prize = fn %{A: a, b: b} ->
  x = Nx.LinAlg.solve(a, b)

  if x |> Nx.to_list() |> Enum.all?(&(round(&1 * 100) == round(&1) * 100)) do
    x |> Nx.to_list() |> Enum.map(&round(&1))
  else
    [0, 0]
  end
end
```

```elixir
Enum.map(machines, &get_prize.(&1))
```

実行結果

```elixir
[[0, 0], [118679050709, 103199174542], [0, 0], [102851800151, 107526881786]]
```

この結果を使ってコストを計算します

```elixir
get_cost = fn machines ->
  machines
  |> Enum.map(fn machine ->
    machine
    |> get_prize.()
    |> then(fn [num_a, num_b] ->
      num_a * 3 + num_b
    end)
  end)
  |> Enum.sum()
end
```

```elixir
get_cost.(machines)
```

実行結果

```elixir
875318608908
```

実際の入力を使えば答えが出ます

```elixir
puzzle_input
|> parse_machines.()
|> get_cost.()
```

</details>

## まとめ

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

![aoc2024_day13_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/388be0e3-68a3-deb6-a3dc-4c226aa02885.png)

Nx に連立方程式を解いてもらいました

桁数が大きすぎる場合、考慮しないといけないことが色々ありますね