Advent of code 2024 Day 7 Part 1 & Part 2 を Livebook で楽しむ

## はじめに

Advent of code 2024 Day 7 の Part 1 と Part 2 を解きます

問題文はこちら

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

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

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

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

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-12-08 17.20.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/eaa9e0f2-c46c-0564-3b83-89b701eac79a.png)

## 私の答え

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

### Part 1

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

まずは入力例で考えてみます

```elixir
sample_input =
  """
  190: 10 19
  3267: 81 40 27
  83: 17 5
  156: 15 6
  7290: 6 8 6 15
  161011: 16 10 13
  192: 17 8 14
  21037: 9 7 18 13
  292: 11 6 16 20
  """
  |> String.trim()
```

入力を扱いやすい形に変換します

```elixir
parse = fn input ->
  input
  |> String.split("\n")
  |> Enum.map(fn row ->
    [left, right] = String.split(row, ":")

    {
      String.to_integer(left),
      right
      |> String.trim()
      |> String.split(" ")
      |> Enum.map(&String.to_integer(&1))
    }
  end)
end
```

```elixir
equations = parse.(sample_input)
```

実行結果

```elixir
[
  {190, [10, 19]},
  {3267, ~c"Q(\e"},
  {83, [17, 5]},
  {156, [15, 6]},
  {7290, [6, 8, 6, 15]},
  {161011, [16, 10, 13]},
  {192, [17, 8, 14]},
  {21037, [9, 7, 18, 13]},
  {292, [11, 6, 16, 20]}
]
```

:::note info
一部、表示時に文字リストとして認識されています
:::

`+` と `*` を n 回重複有りで選択するための関数を用意します

```elixir
defmodule Combinations do
  def all_with_repetition(_, 0), do: [[]]

  def all_with_repetition(list, n) do
    for x <- list,
        tail <- all_with_repetition(list, n - 1) do
      [x | tail]
    end
  end
end
```

例えば、 3 回選択する場合を実行してみます

```elixir
Combinations.all_with_repetition(["+", "*"], 3)
```

実行結果

```elixir
[
  ["+", "+", "+"],
  ["+", "+", "*"],
  ["+", "*", "+"],
  ["+", "*", "*"],
  ["*", "+", "+"],
  ["*", "+", "*"],
  ["*", "*", "+"],
  ["*", "*", "*"]
]
```

全てのパターンを網羅できています

`{190: [10, 19]}` のケースで考えてみます

`10 + 19` と `10 * 190` のパターンが考えられるので、それぞれ演算子と数値で Elixir コードを作り、実行結果が `190` になればよいことが分かります

また、左から順に必ず演算していくので、先頭から順に次の数値と演算子を繰り返し計算していけばよいことになります

```elixir
nums = [10, 19]

["+", "*"]
|> Combinations.all_with_repetition(length(nums) - 1)
|> Enum.find(fn operations ->
  [tl(nums), operations]
  |> Enum.zip()
  |> Enum.reduce(hd(nums), fn {num, op}, acc ->
    Code.eval_string("#{acc} #{op} #{num}")
    |> elem(0)
  end)
  |> then(fn result -> result == 190 end)
end)
```

実行結果

```elixir
["*"]
```

正しく掛け算 1 回を選択できました

これを関数化します

```elixir
find_valid_operations = fn {left, right} ->
  ["+", "*"]
  |> Combinations.all_with_repetition(length(right) - 1)
  |> Enum.find(fn operations ->
    [tl(right), operations]
    |> Enum.zip()
    |> Enum.reduce(hd(right), fn {num, op}, acc ->
      "#{acc} #{op} #{num}"
      |> Code.eval_string()
      |> elem(0)
    end)
    |> then(fn result -> result == left end)
  end)
end
```

いくつかのパターンで検証します

```elixir
find_valid_operations.({83, [17, 5]})
```

実行結果は `nil` になり、成立するパターンが存在しないことが分かります

```elixir
find_valid_operations.({3267, [81, 40, 27]})
```

実行結果は `["+", "*"]` になります

`(81 + 40) * 27 = 3267` なので正解です

これを全ての方程式について実行し、結果が `nil` でないとき左辺を合計します

```elixir
equations
|> Enum.reduce(0, fn {left, _} = equation, acc ->
  case find_valid_operations.(equation) do
    nil -> acc
    _ -> left + acc
  end
end)
```

実行結果

```elixir
3749
```

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

```elixir
puzzle_input
|> parse.()
|> Enum.reduce(0, fn {left, _} = equation, acc ->
  case find_valid_operations.(equation) do
    nil -> acc
    _ -> left + acc
  end
end)
```

</details>

### Part 2

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

演算子が 3 種類に増えました

パターンが圧倒的に増えるため、少しでも高速化するため、 `Code.eval_string` は使わずに直接計算します

```elixir
find_valid_operations = fn {left, right} ->
  ["+", "*", "||"]
  |> Combinations.all_with_repetition(length(right) - 1)
  |> Enum.find(fn operations ->
    [tl(right), operations]
    |> Enum.zip()
    |> Enum.reduce(hd(right), fn {num, op}, acc ->
      case op do
        "+" ->
          acc + num
        "*" ->
          acc * num
        "||" ->
          String.to_integer(Integer.to_string(acc) <> Integer.to_string(num))
      end
    end)
    |> then(fn result -> result == left end)
  end)
end
```

それ以外は Part 1 と変わりません

</details>

## まとめ

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

![aoc2024_day7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/53fcf427-0b54-c698-43a3-7c68b8793fe7.png)

すごく時間がかかるので、 ETS を使ったメモ実装などをした方がいいかもしれませんが、とりあえずシンプルに解きました