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

はじめに

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

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

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()

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

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

equations = parse.(sample_input)

実行結果

[
  {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]}
]

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

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

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 回選択する場合を実行してみます

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

実行結果

[
  ["+", "+", "+"],
  ["+", "+", "*"],
  ["+", "*", "+"],
  ["+", "*", "*"],
  ["*", "+", "+"],
  ["*", "+", "*"],
  ["*", "*", "+"],
  ["*", "*", "*"]
]

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

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

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

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

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)

実行結果

["*"]

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

これを関数化します

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

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

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

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

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

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

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

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

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

実行結果

3749

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

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

Part 2

回答

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

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

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 と変わりません

まとめ

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

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