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

## はじめに

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

問題文はこちら

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

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

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

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/5d86e73950b199d0c97d

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-12-08 11.08.36.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/f1f7ae5a-2995-ab4d-86a7-e7886318625f.png)

## 私の答え

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

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

まず入力例で考えます

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

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

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

```elixir
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
```

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

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

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

```elixir
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
```

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

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

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

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

標準出力

```text
looped: true
```

実行結果

```text
.#...
.XXX#
.X.X.
#^XX.
...#.
.....
```

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

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

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

```elixir
{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)
```

標準出力

```text
looped: false
```

実行結果

```text
....#.....
....XXXXX#
....X...X.
..#.X...X.
..XXXXX#X.
..X.X.X.X.
.#XXXXXXX.
.XXXXXXX#.
#XXXXXXX..
......#X..
```

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

```elixir
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)
```

実行結果

```elixir
....#.....
....#....#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
```

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

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

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

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

標準出力

```text
looped: false
```

実行結果

```text
...#......
.........#
.#........
.....X..#.
.....X....
..#..X....
.....X.#..
XXXXXX....
#....#....
.....#....
```

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

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

```elixir
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)
```

実行結果

```elixir
6
```

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

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

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

```elixir
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)
```

</details>

## まとめ

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

![aoc2024_day6_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/d57b3b57-a36d-b35d-b0ad-acf735f7f667.png)

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