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

はじめに

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

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

まず入力例で考えます

sample_input =
  """
  ....#.....
  .........#
  ..........
  ..#.......
  .......#..
  ..........
  .#..^.....
  ........#.
  #.........
  ......#...
  """
  |> String.trim()

Kino.Text.new(sample_input, terminal: true)

回転関数は Part 1 と同じです

turn = fn input ->
  input
  |> String.replace("^", "<")
  |> String.split("\n")
  |> Enum.map(&String.codepoints(&1))
  |> Enum.zip()
  |> Enum.map(fn col -> col |> Tuple.to_list() |> Enum.join() end)
  |> Enum.reverse()
  |> Enum.join("\n")
end

ただし、繰り返すときに経路のループを判定し、繰り返しを終了するようにします

経路のループは「同じ場所で同じ向きに曲がったか」です

そのため、向きを保持しておき、曲がった位置と向きを記録していきます

round = fn input ->
  Enum.reduce_while(1..1000, {input, [], :up}, fn _, {acc_input, tuened_points, direction} ->
    turned_input = turn.(acc_input)
    direction =
      case direction do
        :up -> :right
        :right -> :down
        :down -> :left
        :left -> :up
      end

    case Regex.scan(~r/#[^\n#]*</, turned_input) do
      [[route]] ->
        [[{point, _}]] = Regex.scan(~r/#[^\n#]*</, turned_input, return: :index)
        turned_point = {direction, point}
        turned_input =
          String.replace(
            turned_input,
            route,
            "#^" <> String.duplicate("X", String.length(route) - 2)
          )

        if Enum.member?(tuened_points, turned_point) do
          {
            :halt,
            { 
              turned_input,
              direction,
              true
            }
          }
        else
          {
            :cont,
            { 
              turned_input,
              [turned_point | tuened_points],
              direction
            }
          }
        end

      _ ->
        route =
          Regex.scan(~r/\.[^\n]*</, turned_input)
          |> hd()
          |> hd()

        {
          :halt,
          {
            String.replace(
              turned_input,
              route,
              String.duplicate("X", String.length(route))
            ),
            direction,
            false
          }
        }
    end
  end)
end

極小さなループを含むマップで試してみます

{rounded, _, looped} =
  """
  ..#...
  .....#
  ..^...
  .#....
  ....#.
  """
  |> String.trim()
  |> round.()

IO.inspect(looped, label: "looped")

Kino.Text.new(rounded, terminal: true)

標準出力

looped: true

実行結果

.#...
.XXX#
.X.X.
#^XX.
...#.
.....

ループしたことを判定できています

まず、入力例を普通に回転して脱出するまで経路を辿らせます

脱出後、元の向きと同じになるように回転させます

{rounded, direction, looped} = round.(sample_input)

IO.inspect(looped, label: "looped")

rounded =
  case direction do
    :up ->
      rounded
    :right ->
      rounded
      |> turn.()
      |> turn.()
      |> turn.()
    :down ->
      rounded
      |> turn.()
      |> turn.()
    :left ->
      turn.(rounded)
  end

Kino.Text.new(rounded, terminal: true)

標準出力

looped: false

実行結果

....#.....
....XXXXX#
....X...X.
..#.X...X.
..XXXXX#X.
..X.X.X.X.
.#XXXXXXX.
.XXXXXXX#.
#XXXXXXX..
......#X..

左上から最初に見つかった X の位置を元の入力で # に変更してみます

replaced =
  Regex.scan(~r/X/, rounded, return: :index)
  |> hd()
  |> then(fn [{index, _}] ->
    String.slice(sample_input, 0..(index - 1)) <>
      "#" <> String.slice(sample_input, (index + 1)..-1//1)
  end)

Kino.Text.new(replaced, terminal: true)

実行結果

....#.....
....#....#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

この地図に沿って移動したとき、ループしているか判定すれば良いことになります

{rounded_replaced, direction, looped} = round.(replaced)

IO.inspect(looped, label: "looped")

Kino.Text.new(rounded_replaced, terminal: true)

標準出力

looped: false

実行結果

...#......
.........#
.#........
.....X..#.
.....X....
..#..X....
.....X.#..
XXXXXX....
#....#....
.....#....

この場合はループせずに脱出しています

これを全ての X に対して実行することで、障害物が増えたときにループさせられる場所がわかります

Regex.scan(~r/X/, rounded, return: :index)
|> Enum.reduce(0, fn [{index, _}], loop_count ->
  if String.at(sample_input, index) == "^" do
    loop_count
  else
    replaced =
      String.slice(sample_input, 0..(index - 1)) <>
        "#" <> String.slice(sample_input, (index + 1)..-1//1)

    {_, _, looped} = round.(replaced)

    loop_count + if looped, do: 1, else: 0
  end
end)

実行結果

6

実際の入力に対しても同じ操作をすれば答えが出ます

{rounded, direction, _} = round.(puzzle_input)

rounded =
  case direction do
    :up ->
      rounded
    :right ->
      rounded
      |> turn.()
      |> turn.()
      |> turn.()
    :down ->
      rounded
      |> turn.()
      |> turn.()
    :left ->
      turn.(rounded)
  end

Regex.scan(~r/X/, rounded, return: :index)
|> Enum.reduce(0, fn [{index, _}], loop_count ->
  if String.at(puzzle_input, index) == "^" do
    loop_count
  else
    replaced =
      String.slice(puzzle_input, 0..(index - 1)) <>
        "#" <> String.slice(puzzle_input, (index + 1)..-1//1)

    {_, _, looped} = round.(replaced)

    loop_count + if looped, do: 1, else: 0
  end
end)

まとめ

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

処理にすごく時間がかかるので最適解ではないですが、何とか解くことができました