Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
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?

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

Advent of code 2023 Day 14 Part 2 を Livebook で楽しむ

Last updated at Posted at 2024-12-04

はじめに

Advent of code 2023 Day 14 の Part 2 を解きます

問題文はこちら

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

Part 1 はこちら

セットアップ

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

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

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

入力の取得

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

スクリーンショット 2024-12-04 9.01.19.png

私の答え

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

回答

Part 2 もまずは小さい入力例で解いてみます

map =
  """
  O....#....
  O.OO#....#
  .....##...
  OO.#O....O
  .O.....O#.
  O.#..O.#.#
  ..O..#O..O
  .......O..
  #....###..
  #OO..#....
  """
  |> String.trim()
  |> String.split("\n")
  |> Enum.map(fn row ->
    String.codepoints(row)
  end)

Part 1 のモジュールに逆回転の関数と、 1 回転の関数を追加しています

defmodule Rock do
  def turn(map) do
    map
    |> Enum.zip()
    |> Enum.map(fn col ->
      Tuple.to_list(col)
    end)
    |> Enum.reverse()
  end

  def turn_back(map) do
    map
    |> Enum.zip()
    |> Enum.map(fn col ->
      col
      |> Tuple.to_list()
      |> Enum.reverse()
    end)
  end

  def slide(map) do
    Enum.map(map, fn row ->
      slide(row, length(row) - 1)
    end)
  end
  
  def slide(row, 0), do: row
  def slide(row, current_index) do
    current_block = Enum.at(row, current_index)
    next_block = Enum.at(row, current_index - 1)

    case {current_block, next_block} do
      {"O", "."} ->
        row
        |> List.update_at(current_index, fn _ -> "." end)
        |> List.update_at(current_index - 1, fn _ -> "O" end)
        |> slide(length(row) - 1)
      _ ->
        slide(row, current_index - 1)
    end
  end

  def cycle(map) do
    map
    |> Rock.turn()
    |> Rock.slide()
    |> Rock.turn_back()
    |> Rock.slide()
    |> Rock.turn_back()
    |> Rock.slide()
    |> Rock.turn_back()
    |> Rock.slide()
    |> Rock.turn()
    |> Rock.turn()
  end

  def sum_load(map) do
    map
    |> Enum.map(fn row ->
      row
      |> Enum.reverse()
      |> Enum.with_index(1)
      |> Enum.map(fn {mark, index} ->
        case mark do
          "O" -> index
          _ -> 0
        end
      end)
      |> Enum.sum()
    end)
    |> Enum.sum()
  end
end

まず、北方向のスライドを見てみましょう

Part 1 の方法では 90 度回転してからスライドしていたため、スライド後に逆回転して元の角度に戻します

map
|> Rock.turn()
|> Rock.slide()
|> Rock.turn_back()

実行結果

[
  ["O", "O", "O", "O", ".", "#", ".", "O", ".", "."],
  ["O", "O", ".", ".", "#", ".", ".", ".", ".", "#"],
  ["O", "O", ".", ".", "O", "#", "#", ".", ".", "O"],
  ["O", ".", ".", "#", ".", "O", "O", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "#", "."],
  [".", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
  [".", ".", "O", ".", ".", "#", ".", "O", ".", "O"],
  [".", ".", "O", ".", ".", ".", ".", ".", ".", "."],
  ["#", ".", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", ".", ".", ".", ".", "#", ".", ".", ".", "."]
]

実際、上に全ての丸岩がスライドできています

続いて西にスライドしますが、西は左方向なのでこのままスライドさせればよいだけです

map
|> Rock.turn()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()

実行結果

[
  ["O", "O", "O", "O", ".", "#", "O", ".", ".", "."],
  ["O", "O", ".", ".", "#", ".", ".", ".", ".", "#"],
  ["O", "O", "O", ".", ".", "#", "#", "O", ".", "."],
  ["O", ".", ".", "#", "O", "O", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "#", "."],
  [".", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
  ["O", ".", ".", ".", ".", "#", "O", "O", ".", "."],
  ["O", ".", ".", ".", ".", ".", ".", ".", ".", "."],
  ["#", ".", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", ".", ".", ".", ".", "#", ".", ".", ".", "."]
]

南へスライドさせるために逆回転してスライドし、元の角度に戻してみます

map
|> Rock.turn()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()
|> Rock.turn()

実行結果

[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", "O", ".", ".", "#"],
  ["O", ".", ".", "O", ".", "#", "#", ".", ".", "."],
  ["O", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  ["O", ".", "O", ".", ".", ".", ".", "O", "#", "."],
  ["O", ".", "#", ".", ".", "O", ".", "#", ".", "#"],
  ["O", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "O", "O", ".", "."],
  ["#", "O", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", "O", ".", ".", "O", "#", ".", ".", ".", "."]
]

最後に東に動かすので、南に動かしたあと、さらに逆回転してからスライドし、元の角度に戻すため 180 度回転します

map
|> Rock.turn()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()
|> Rock.turn_back()
|> Rock.slide()
|> Rock.turn()
|> Rock.turn()

実行結果

[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", "O", "O", "#", "#", ".", ".", "."],
  [".", "O", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "O", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "."],
  ["#", ".", ".", "O", "O", "#", ".", ".", ".", "."]
]

ここまでの 1 回転の操作を Rock.cycle に定義しています

Rock.cycle(map)

実行結果

[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", "O", "O", "#", "#", ".", ".", "."],
  [".", "O", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "O", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "."],
  ["#", ".", ".", "O", "O", "#", ".", ".", ".", "."]
]

問題文内の 1 回転後の状態と一致します

2 回転してみます

map
|> Rock.cycle()
|> Rock.cycle()

実行結果

[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", ".", ".", "#", "#", ".", ".", "."],
  [".", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "O"],
  [".", ".", ".", ".", ".", ".", ".", "O", "O", "O"],
  ["#", ".", ".", "O", "O", "#", "#", "#", ".", "."],
  ["#", ".", "O", "O", "O", "#", ".", ".", ".", "O"]
]

map
|> Rock.cycle()
|> Rock.cycle()
|> Rock.cycle()

実行結果

[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", ".", ".", "#", "#", ".", ".", "."],
  [".", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "O"],
  [".", ".", ".", ".", ".", ".", ".", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "O"],
  ["#", ".", "O", "O", "O", "#", ".", ".", ".", "O"]
]

2 回転、 3 回転も一致しました

問題では 100000000 回転 = 1 億回転すると書いてありますが、実際に 1 億回転するのは時間がかかりすぎます

回転していると同じ配置に戻ることが考えられます

同じ配置に戻れば以降はループするだけなので、どこからどこまででループしているのかを取得します

{loop_end, loop_start} =
  1..1000000000
  |> Enum.reduce_while({map, %{}}, fn index, {acc_map, memo} ->
    acc_map = Rock.cycle(acc_map)

    case Map.get(memo, acc_map) do
      nil ->
        {:cont, {acc_map, Map.put(memo, acc_map, index)}}
      exists_index ->
        {:halt, {index, exists_index}}
    end
  end)

実行結果

{10, 3}

ループの開始回転数、終了回転数から、1 億回転と同じ状態になる回転数を求めます

same_loop = rem(1000000000 - loop_start, loop_end - loop_start) + loop_start

実行結果

6

6 回転したときと 1 億回転したときの配置は同じなので、6回転だけ回して、最後に 90 度回転してから（列番号 = 重量の影響度にするため）重量の合計影響値を取得します

1..same_loop
|> Enum.reduce(map, fn _, acc_map ->
  Rock.cycle(acc_map)
end)
|> Rock.turn()
|> Rock.sum_load()

実行結果

64

問題文の結果と一致しました

あとは実際の入力で同じことをするだけです

map =
  puzzle_input
  |> String.split("\n")
  |> Enum.map(fn row ->
    String.codepoints(row)
  end)

{loop_end, loop_start} =
  1..1000000000
  |> Enum.reduce_while({map, %{}}, fn index, {acc_map, memo} ->
    acc_map = Rock.cycle(acc_map)

    case Map.get(memo, acc_map) do
      nil ->
        {:cont, {acc_map, Map.put(memo, acc_map, index)}}
      exists_index ->
        {:halt, {index, exists_index}}
    end
  end)

same_loop = rem(1000000000 - loop_start, loop_end - loop_start) + loop_start

1..same_loop
|> Enum.reduce(map, fn _, acc_map ->
  Rock.cycle(acc_map)
end)
|> Rock.turn()
|> Rock.sum_load()

まとめ

回転とループに気付けば解ける問題でした

Elixir Forum や Reddit を見るともっとスマートな回答がたくさんあり、感心しました

2
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
2
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?