Go to Qiita Advent Calendar 2024 Top
LoginSignup
5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ElixirAdvent Calendar 2024

Day 6
@RyoWakabayashi(若林 諒)in株式会社オーイーシー

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

Last updated at Posted at 2024-12-19

はじめに

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

スクリーンショット 2024-12-19 16.00.15.png

私の答え

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

回答

入力例で考えます

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

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

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

{map, directions} = parse_map.(small_sample_input)

実行結果

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

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

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

robot_point = get_robot_point.(map)

実行結果

{2, 2}

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

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

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

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

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

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

  • .@ -> @.
  • .OO@ -> OO@.

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

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

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

map_size = Robot.get_map_size(map)

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

実行結果

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

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

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

実行結果

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

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

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

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

実行結果

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

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

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

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

実行結果

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

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

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

{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..#
########

想定通り動きました

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

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

get_gps_coordinate.(moved_map)

実行結果

2028

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

{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#
##########

get_gps_coordinate.(moved_map)

実行結果

10092

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

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

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

まとめ

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

aoc2024_day15_1.png

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

Part 2 はこちら

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?