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

はじめに

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

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

いきなりビット演算が来ました

以前 NervesLivebook でビット演算をやっていたので方法は知っています

https://qiita.com/RyoWakabayashi/items/32edd890ade613cb4e37

Elixir では Bitwise モジュールを使えばビット演算できます

import Bitwise

x = 123
y = 456

AND は &&& 演算子です

d = x &&& y

OR は ||| 演算子です

e = x ||| y

LSHIFT は <<< 演算子です

f = x <<< 2

RSHIFT は >>> 演算子です

g = y >>> 2

ややこしいのが NOT です

NOT は ~~~ 演算子ですが、単純に ~~~1 とすると、 -2　（補数）が返ってきます

16 桁でビット反転するため、以下のように実装しました

<<h::integer-size(2)-unit(8)>> = <<(~~~x)::size(16)>>

h

関数化するとこんな感じです

bit_not = fn input ->
  <<output::integer-size(2)-unit(8)>> = <<(~~~input)::size(16)>>
  output
end

i = bit_not.(y)

i

続いて、回路の接続指示をパースします

正規表現を使うことで、うまい具合にパースできます

単純な代入のパターン

Regex.named_captures(
  ~r/(?<input_a>[a-z0-9]*) *(?<op>[A-Z]*) *(?<input_b>[a-z0-9]*) -> (?<output>.+)/,
  "123 -> c"
)

実行結果

%{"input_a" => "123", "input_b" => "", "op" => "", "output" => "c"}

ビット反転のパターン

Regex.named_captures(
  ~r/(?<input_a>[a-z0-9]*) *(?<op>[A-Z]*) *(?<input_b>[a-z0-9]*) -> (?<output>.+)/,
  "NOT b -> c"
)

実行結果

%{"input_a" => "", "input_b" => "b", "op" => "NOT", "output" => "c"}

上記以外の論理演算のパターン

Regex.named_captures(
  ~r/(?<input_a>[a-z0-9]*) *(?<op>[A-Z]*) *(?<input_b>[a-z0-9]*) -> (?<output>.+)/,
  "a AND b -> c"
)

実行結果

%{"input_a" => "a", "input_b" => "b", "op" => "AND", "output" => "c"}

どのパターンでも正しくパースできています

処理が複雑なので、今回はモジュールを定義します

defmodule Solver do
  import Bitwise

  defp bit_not(input) do
    <<output::integer-size(2)-unit(8)>> = <<(~~~input)::size(16)>>
    output
  end

  defp parse_variable(nil, _), do: nil
  defp parse_variable("", _), do: nil
  defp parse_variable(variable, _) when is_integer(variable), do: variable
  defp parse_variable(variable, dict) do
    case Integer.parse(variable) do
      {number, ""} -> number
      _ -> Map.get(dict, variable, variable)
    end
  end

  defp calc("", input_a, _) when is_integer(input_a), do: input_a
  defp calc("NOT", _, input_b) when is_integer(input_b), do: bit_not(input_b)
  defp calc("AND", input_a, input_b) when (is_integer(input_a) and is_integer(input_b)) do
    input_a &&& input_b
  end
  defp calc("OR", input_a, input_b) when (is_integer(input_a) and is_integer(input_b)) do
    input_a ||| input_b
  end
  defp calc("LSHIFT", input_a, input_b) when (is_integer(input_a) and is_integer(input_b)) do
    input_a <<< input_b
  end
  defp calc("RSHIFT", input_a, input_b) when (is_integer(input_a) and is_integer(input_b)) do
    input_a >>> input_b
  end
  defp calc(_, _, _), do: nil

  defp solve(instruction, dict) do
    %{
      "input_a" => input_a,
      "input_b" => input_b,
      "op" => op,
      "output" => output
    } = instruction

    input_a = parse_variable(input_a, dict)
    input_b = parse_variable(input_b, dict)

    result = calc(op, input_a, input_b)
    solved = !is_nil(result)

    instruction = Map.put(instruction, :solved, solved)
    dict = if solved, do: Map.put(dict, output, result), else: dict

    {instruction, dict}
  end

  def parse_instraction(row) do
    Regex.named_captures(
      ~r/(?<input_a>[a-z0-9]*) *(?<op>[A-Z]*) *(?<input_b>[a-z0-9]*) -> (?<output>.+)/,
      row
    )
  end

  def cyclic_solve(%{solved: true}, instructions, dict), do: {instructions, dict}
  def cyclic_solve(new_instruction, instructions, dict) do
    {new_instruction, dict} = solve(new_instruction, dict)

    if new_instruction.solved do
      {instructions, dict} =
        instructions
        |> Enum.reduce({[], dict}, fn sub_instruction, {acc_instructions, acc_dict} ->
          cyclic_solve(sub_instruction, acc_instructions, acc_dict)
        end)

      {[new_instruction | instructions], dict}
    else
      {[new_instruction | instructions], dict}
    end
  end
end

この問題の最大にややこしいところは、入力の伝わる順序と回路の接続指示の順序が一致していないことです

上から順に値を計算していくことができません

回路の接続指示を instructions 、回路の各ワイヤーの値を dict に保持しながら、ワイヤーの値が確定するたびに未確定のワイヤーについて値の計算を試みます

cyclic_solve 関数で再帰処理することで実装しました

puzzle_input
|> String.split("\n")
|> Enum.reduce({[], %{}}, fn row, {instructions, dict} ->
  new_instruction = Solver.parse_instraction(row)
  Solver.cyclic_solve(new_instruction, instructions, dict)
end)
|> elem(1)
|> Map.get("a")

まとめ

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

Day 7 はいきなりレベルが上がった感じがします

ビット演算、ややこしいパース、再帰処理と3段階のハードルがあり、かなり時間がかかってしまいました

Part 2 はこちら