Advent of code 2024 Day 15 Part 1 を Livebook で楽しむ

## はじめに

Advent of code 2024 Day 15 の Part 1 を解きます

問題文はこちら

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

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

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

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-12-19 16.00.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/8ce4994f-3769-0803-ab1a-d966612c8280.png)

## 私の答え

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

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

入力例で考えます

```elixir
small_sample_input =
  """
  ########
  #..O.O.#
  ##@.O..#
  #...O..#
  #.#.O..#
  #...O..#
  #......#
  ########
  
  <^^>>>vv<v>>v<<
  """
  |> String.trim()
```

まず、入力を地図と移動方向配列として読み込みます

```elixir
parse_map = fn input ->
  [map_rows, direction_rows] = String.split(input, "\n\n")

  map =
    map_rows
    |> String.split("\n")
    |> Enum.with_index()
    |> Enum.flat_map(fn {row, row_index} ->
      row
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {mark, col_index} ->
        {{col_index, row_index}, mark}
      end)
    end)
    |> Enum.into(%{})

  directions =
    direction_rows
    |> String.replace("\n", "")
    |> String.codepoints()

  {map, directions}
end
```

```elixir
{map, directions} = parse_map.(small_sample_input)
```

実行結果

```elixir
{%{
   {1, 3} => "#",
   {1, 1} => "#",
   {1, 5} => "#",
   ...
 }, ["<", "v", "v", "<", "<", "^", "^", "<", "<", "^", "^"]}
```

ロボットの初期位置（"@" の座標）を取得します

```elixir
get_robot_point = fn map ->
  map
  |> Enum.find(fn {_, mark} -> mark == "@" end)
  |> elem(0)
end
```

```elixir
robot_point = get_robot_point.(map)
```

実行結果

```elixir
{2, 2}
```

ロボットの移動用モジュールを用意します

移動する前に、指定された方向に向かって "#" （壁）か "." （空白）が見つかるまで探索します（`search_end_point` 関数）

以下のような判断をするためです

- `#@` の場合は動くことができない
- `#OO@` の場合も動くことができない
- `.@` は動くことができる
- `.OO@` は動くことができる

つまり、移動方向に進めるかどうか、間に "O" （箱）がいくつあるかが分かります

移動方向の先に "#" がある場合は地図を更新せず、 "." がある場合は以下のように地図を更新します

- `.@` -> `@.`
- `.OO@` -> `OO@.`

地図の更新を全ての移動方向に対して実行すれば、最終的な状態が分かります

```elixir
defmodule Robot do
  def move({map, robot_point}, direction) do
    moving_points = search_end_point(robot_point, direction, map, [])
    end_point_mark = moving_points |> hd |> elem(1)

    case end_point_mark do
      "#" ->
        {map, robot_point}

      "." ->
        {  
          go_next(robot_point, moving_points, map),
          get_next_point(robot_point, direction)
        }
    end
  end

  defp go_next(robot_point, moving_points, map) do
    moving_points
    |> Enum.reverse()
    |> Enum.with_index()
    |> Enum.reduce(map, fn {moving_point, index}, acc_map ->
      mark =
        case index do
          0 -> "@"
          _ -> "O"
        end

      Map.put(acc_map, elem(moving_point, 0), mark)
    end)
    |> Map.put(robot_point, ".")
  end

  def search_end_point(robot_point, direction, map, acc) do
    next_point = get_next_point(robot_point, direction)

    next_point_mark = Map.get(map, next_point)
    next_acc = [{next_point, next_point_mark} | acc]

    case next_point_mark do
      nil -> acc
      "#" -> next_acc
      "." -> next_acc
      "O" -> search_end_point(next_point, direction, map, next_acc)
    end
  end

  defp get_next_point({px, py}, direction) do
    case direction do
      "^" -> {px, py - 1}
      "v" -> {px, py + 1}
      "<" -> {px - 1, py}
      ">" -> {px + 1, py}
    end
  end

  def get_map_size(map) do
    {
      map |> Enum.map(fn {{x, _}, _} -> x end) |> Enum.max() |> Kernel.+(1),
      map |> Enum.map(fn {{_, y}, _} -> y end) |> Enum.max() |> Kernel.+(1)
    }
  end

  def display_map(map, {tx, ty}) do
    0..(ty - 1)
    |> Enum.map(fn y ->
      0..(tx - 1)
      |> Enum.map(fn x ->
        Map.get(map, {x, y})
      end)
      |> Enum.join()
    end)
    |> Enum.join("\n")
  end
end
```

まず、初期状態を視覚化してみましょう

```elixir
map_size = Robot.get_map_size(map)
```

```elixir
map
|> Robot.display_map(map_size)
|> Kino.Text.new(terminal: true)
```

実行結果

```
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########
```

座標 `{2, 2}` から左に動くときの行き先を確認します

```elixir
Robot.search_end_point({2, 2}, "<", map, [])
```

実行結果

```elixir
[{{1, 2}, "#"}]
```

壁に当たって移動できないことが分かります

座標 `{3, 2}` から右に動くときの行き先を確認します

```elixir
Robot.search_end_point({3, 2}, ">", map, [])
```

実行結果

```elixir
[{{5, 2}, "."}, {{4, 2}, "O"}]
```

行き先が箱を一つ挟んで空白なので、移動できます

初期位置から上に移動した状態を視覚化してみます

```elixir
{map, robot_point}
|> Robot.move("^")
|> elem(0)
|> Robot.display_map(map_size)
|> Kino.Text.new(terminal: true)
```

実行結果

```
########
#.@O.O.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########
```

確かに上に移動できています

全ての移動を実行してみます

```elixir
{moved_map, _} =
  directions
  |> Enum.reduce({map, robot_point}, fn direction, {acc_map, acc_robot_point} ->
    {acc_map, acc_robot_point} = Robot.move({acc_map, acc_robot_point}, direction)
  
    IO.puts(direction)
    acc_map |> Robot.display_map(map_size) |> IO.puts()
    IO.puts("")
    
    {acc_map, acc_robot_point}
  end)

moved_map
|> Robot.display_map(map_size)
|> Kino.Text.new(terminal: true)
```

標準出力

```
<
########
#..O.O.#
##@.O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

^
########
#.@O.O.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

^
########
#.@O.O.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

>
########
#..@OO.#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

>
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

>
########
#...@OO#
##..O..#
#...O..#
#.#.O..#
#...O..#
#......#
########

v
########
#....OO#
##..@..#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

v
########
#....OO#
##..@..#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

<
########
#....OO#
##.@...#
#...O..#
#.#.O..#
#...O..#
#...O..#
########

v
########
#....OO#
##.....#
#..@O..#
#.#.O..#
#...O..#
#...O..#
########

>
########
#....OO#
##.....#
#...@O.#
#.#.O..#
#...O..#
#...O..#
########

>
########
#....OO#
##.....#
#....@O#
#.#.O..#
#...O..#
#...O..#
########

v
########
#....OO#
##.....#
#.....O#
#.#.O@.#
#...O..#
#...O..#
########

<
########
#....OO#
##.....#
#.....O#
#.#O@..#
#...O..#
#...O..#
########

<
########
#....OO#
##.....#
#.....O#
#.#O@..#
#...O..#
#...O..#
########
```

実行結果

```
########
#....OO#
##.....#
#.....O#
#.#O@..#
#...O..#
#...O..#
########
```

想定通り動きました

最終的な箱の位置を評価して合計します

```elixir
get_gps_coordinate = fn map ->
  map
  |> Enum.map(fn {{x, y}, mark} ->
    case mark do
      "O" -> x + y * 100
      _ -> 0
    end
  end)
  |> Enum.sum()
end
```

```elixir
get_gps_coordinate.(moved_map)
```

実行結果

```elixir
2028
```

大きな入力例で実行してみます

```elixir
{map, directions} =
  """
  ##########
  #..O..O.O#
  #......O.#
  #.OO..O.O#
  #..O@..O.#
  #O#..O...#
  #O..O..O.#
  #.OO.O.OO#
  #....O...#
  ##########
  
  <vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
  vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
  ><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
  <<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
  ^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
  ^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
  >^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
  <><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
  ^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
  v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^
  """
  |> String.trim()
  |> parse_map.()

robot_point = get_robot_point.(map)
map_size = Robot.get_map_size(map)

{moved_map, _} =
  directions
  |> Enum.reduce({map, robot_point}, fn direction, {acc_map, acc_robot_point} ->
    Robot.move({acc_map, acc_robot_point}, direction)
  end)

moved_map
|> Robot.display_map(map_size)
|> Kino.Text.new(terminal: true)
```

実行結果

```
##########
#.O.O.OOO#
#........#
#OO......#
#OO@.....#
#O#.....O#
#O.....OO#
#O.....OO#
#OO....OO#
##########
```

```elixir
get_gps_coordinate.(moved_map)
```

実行結果

```elixir
10092
```

問題文と同じ結果が得られました

実際の入力に対しても同じ処理を実行します

```elixir
{map, directions} = parse_map.(puzzle_input)

robot_point = get_robot_point.(map)
map_size = Robot.get_map_size(map)

directions
|> Enum.reduce({map, robot_point}, fn direction, {acc_map, acc_robot_point} ->
  Robot.move({acc_map, acc_robot_point}, direction)
end)
|> elem(0)
|> get_gps_coordinate.()
```

</details>

## まとめ

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

![aoc2024_day15_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/006f4a97-aa87-eb4f-41e8-f6832898fa44.png)

Part 1 の時点で結構ややこしい問題でした

Part 2 はこちら

https://qiita.com/RyoWakabayashi/items/5f3dcd32e4407fc6921f