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

はじめに

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

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

入力の取得

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

私の答え

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

回答

入力例で考えます
（Part 1 とは違う例です）

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

問題文に沿って、地図の幅を倍にします

spread_map = fn input ->
  input
  |> String.replace("#", "##")
  |> String.replace("O", "[]")
  |> String.replace(".", "..")
  |> String.replace("@", "@.")
end

その上で、地図と移動方向配列として読み込みます

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} =
  small_sample_input
  |> spread_map.()
  |> parse_map.()

実行結果

{%{
   {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)

実行結果

{10, 3}

Part 1 と基本的な考え方は同じですが、箱の幅がロボットの倍なので、箱が左右にはみ出し、隣の列の箱も巻き込んで進みます

動けるかどうかの判断は、移動しようとしている箱（"[" または "]"）の先に壁（"#"）があるか、で行います

例えば、以下の例では上に進むことができません

####
..[]
.[].
..[]
...@
####

逆に、以下のような配置では1回上に進めます

####
..[]
[]..
.[].
..@.
####

実装したモジュールは以下のものです

defmodule Robot do
  def move({map, robot_point}, direction) do
    moving_points = search_end_point(robot_point, direction, map, [])

    if Enum.any?(hd(moving_points), &(elem(&1, 1) == "#")) do
      {map, robot_point}
    else
      {
        go_next(robot_point, direction, moving_points, map),
        get_next_point(robot_point, direction)
      }
    end
  end

  defp go_next(robot_point, direction, moving_points, map) do
    current_points_group = Enum.reverse(moving_points)
    next_points_group = (tl(moving_points) ++ [[{robot_point, "@"}]]) |> Enum.reverse()

    current_points_group
    |> Enum.zip(next_points_group)
    |> Enum.reduce(map, fn {current_points, next_points}, acc_map ->
      current_points
      |> Enum.reduce(acc_map, fn current_point, acc_acc_map ->
        {{cx, _}, _} = current_point

        next_point =
          Enum.find(next_points, fn {{nx, _}, _} ->
            if Enum.member?(["^", "v"], direction) do
              cx == nx
            else
              true
            end
          end)

        mark =
          case next_point do
            nil -> "."
            _ -> elem(next_point, 1)
          end

        Map.put(acc_acc_map, elem(current_point, 0), mark)
      end)
    end)
    |> Map.put(robot_point, ".")
  end

  def search_end_point({rx, ry} = robot_point, direction, map, acc) do
    head =
      case acc do
        [] -> [{robot_point, "@"}]
        _ -> hd(acc)
      end

    next_points =
      head
      |> Enum.filter(fn {_, mark} -> mark != "." end)
      |> Enum.map(fn {{ax, _}, _} ->
        get_next_point({ax, ry}, direction)
      end)

    next_row =
      Enum.flat_map(next_points, fn point ->
        if Enum.member?(["^", "v"], direction) do
          case Map.get(map, point) do
            "#" ->
              [{point, Map.get(map, point)}]

            "." ->
              [{point, Map.get(map, point)}]

            "]" ->
              {px, py} = point
              [{{px - 1, py}, "["}, {point, "]"}]

            "[" ->
              {px, py} = point
              [{point, "["}, {{px + 1, py}, "]"}]
          end
        else
          [{point, Map.get(map, point)}]
        end
      end)
      |> Enum.sort()
      |> Enum.uniq()

    next_acc = [next_row | acc]

    cond do
      Enum.any?(next_points, &(Map.get(map, &1) == "#")) ->
        next_acc

      Enum.all?(next_points, &(Map.get(map, &1) == ".")) ->
        next_acc

      Enum.member?(["^", "v"], direction) ->
        robot_point = {rx, if(direction == "^", do: ry - 1, else: ry + 1)}
        search_end_point(robot_point, direction, map, next_acc)

      true ->
        robot_point = hd(next_points)
        search_end_point(robot_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)

実行結果

##############
##......##..##
##..........##
##....[][]@.##
##....[]....##
##..........##
##############

ロボットを移動させてみましょう

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

標準出力

<
##############
##......##..##
##..........##
##...[][]@..##
##....[]....##
##..........##
##############

v
##############
##......##..##
##..........##
##...[][]...##
##....[].@..##
##..........##
##############

v
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##.......@..##
##############

<
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##......@...##
##############

<
##############
##......##..##
##..........##
##...[][]...##
##....[]....##
##.....@....##
##############

^
##############
##......##..##
##...[][]...##
##....[]....##
##.....@....##
##..........##
##############

^
##############
##......##..##
##...[][]...##
##....[]....##
##.....@....##
##..........##
##############

<
##############
##......##..##
##...[][]...##
##....[]....##
##....@.....##
##..........##
##############

<
##############
##......##..##
##...[][]...##
##....[]....##
##...@......##
##..........##
##############

^
##############
##......##..##
##...[][]...##
##...@[]....##
##..........##
##..........##
##############

^
##############
##...[].##..##
##...@.[]...##
##....[]....##
##..........##
##..........##
##############

問題文と同じ移動をしています

原点により近い方は必ず　"[" なので、 "[" の座標を使って計算します

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

get_gps_coordinate.(moved_map)

実行結果

618

大きい入力例でも同様に処理してみます

まずは状態を確認します

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

map_size = Robot.get_map_size(map)

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

実行結果

####################
##....[]....[]..[]##
##............[]..##
##..[][]....[]..[]##
##....[]@.....[]..##
##[]##....[]......##
##[]....[]....[]..##
##..[][]..[]..[][]##
##........[]......##
####################

移動させてみます

robot_point = get_robot_point.(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)

実行結果

####################
##[].......[].[][]##
##[]...........[].##
##[]........[][][]##
##[]......[]....[]##
##..##......[]....##
##..[]............##
##..@......[].[][]##
##......[][]..[]..##
####################

get_gps_coordinate.(moved_map)

実行結果

9021

実際の入力に対して実行します

{map, directions} =
  puzzle_input
  |> spread_map.()
  |> parse_map.()

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 に画像を生成してもらいました

箱の幅が2倍になるだけで、かなり難しくなりました