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

## はじめに

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

問題文はこちら

https://adventofcode.com/2023/day/14

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2023/2023_day14_part2.livemd

Part 1 はこちら

https://qiita.com/RyoWakabayashi/private/8cd2132259a24ad60ff4

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-12-04 9.01.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/3f5f78f5-7b1a-ac12-4f32-b37ecb1df815.png)

## 私の答え

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

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

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

```elixir
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 回転の関数を追加しています

```elixir
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 度回転してからスライドしていたため、スライド後に逆回転して元の角度に戻します

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

実行結果

```elixir
[
  ["O", "O", "O", "O", ".", "#", ".", "O", ".", "."],
  ["O", "O", ".", ".", "#", ".", ".", ".", ".", "#"],
  ["O", "O", ".", ".", "O", "#", "#", ".", ".", "O"],
  ["O", ".", ".", "#", ".", "O", "O", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "#", "."],
  [".", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
  [".", ".", "O", ".", ".", "#", ".", "O", ".", "O"],
  [".", ".", "O", ".", ".", ".", ".", ".", ".", "."],
  ["#", ".", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", ".", ".", ".", ".", "#", ".", ".", ".", "."]
]
```

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

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

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

実行結果

```elixir
[
  ["O", "O", "O", "O", ".", "#", "O", ".", ".", "."],
  ["O", "O", ".", ".", "#", ".", ".", ".", ".", "#"],
  ["O", "O", "O", ".", ".", "#", "#", "O", ".", "."],
  ["O", ".", ".", "#", "O", "O", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "#", "."],
  [".", ".", "#", ".", ".", ".", ".", "#", ".", "#"],
  ["O", ".", ".", ".", ".", "#", "O", "O", ".", "."],
  ["O", ".", ".", ".", ".", ".", ".", ".", ".", "."],
  ["#", ".", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", ".", ".", ".", ".", "#", ".", ".", ".", "."]
]
```

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

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

実行結果

```elixir
[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", "O", ".", ".", "#"],
  ["O", ".", ".", "O", ".", "#", "#", ".", ".", "."],
  ["O", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  ["O", ".", "O", ".", ".", ".", ".", "O", "#", "."],
  ["O", ".", "#", ".", ".", "O", ".", "#", ".", "#"],
  ["O", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  ["O", "O", ".", ".", ".", ".", "O", "O", ".", "."],
  ["#", "O", ".", ".", ".", "#", "#", "#", ".", "."],
  ["#", "O", ".", ".", "O", "#", ".", ".", ".", "."]
]
```

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

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

実行結果

```elixir
[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", "O", "O", "#", "#", ".", ".", "."],
  [".", "O", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "O", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "."],
  ["#", ".", ".", "O", "O", "#", ".", ".", ".", "."]
]
```

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

```elixir
Rock.cycle(map)
```

実行結果

```elixir
[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", "O", "O", "#", "#", ".", ".", "."],
  [".", "O", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "O", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "."],
  ["#", ".", ".", "O", "O", "#", ".", ".", ".", "."]
]
```

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

2 回転してみます

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

実行結果

```elixir
[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", ".", ".", "#", "#", ".", ".", "."],
  [".", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "O"],
  [".", ".", ".", ".", ".", ".", ".", "O", "O", "O"],
  ["#", ".", ".", "O", "O", "#", "#", "#", ".", "."],
  ["#", ".", "O", "O", "O", "#", ".", ".", ".", "O"]
]
```

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

実行結果

```elixir
[
  [".", ".", ".", ".", ".", "#", ".", ".", ".", "."],
  [".", ".", ".", ".", "#", ".", ".", ".", "O", "#"],
  [".", ".", ".", ".", ".", "#", "#", ".", ".", "."],
  [".", ".", "O", "#", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "O", "O", "O", "#", "."],
  [".", "O", "#", ".", ".", ".", "O", "#", ".", "#"],
  [".", ".", ".", ".", "O", "#", ".", ".", ".", "O"],
  [".", ".", ".", ".", ".", ".", ".", "O", "O", "O"],
  ["#", ".", ".", ".", "O", "#", "#", "#", ".", "O"],
  ["#", ".", "O", "O", "O", "#", ".", ".", ".", "O"]
]
```

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

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

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

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

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

実行結果

```elixir
{10, 3}
```

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

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

実行結果

```elixir
6
```

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

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

実行結果

```elixir
64
```

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

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

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

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

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

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

</details>

## まとめ

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

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