Advent of code 2024 Day 8 Part 1 & Part 2 を Livebook で楽しむ

## はじめに

Advent of code 2024 Day 8 の Part 1 と Part 2 を解きます

問題文はこちら

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

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

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

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

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-12-08 22.14.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/0a4db20e-34d7-327e-01c9-a3515c611951.png)

## 私の答え

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

### Part 1

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

まず一番単純な例から考えます

```elixir
sample_input =
  """
  ..........
  ..........
  ..........
  ....a.....
  ..........
  .....a....
  ..........
  ..........
  ..........
  ..........
  """
  |> String.trim()
```

入力を扱いやすい形式に変換します

```elixir
parse = fn input ->
  input
  |> String.split("\n")
  |> Enum.with_index()
  |> Enum.flat_map(fn {row, row_index} ->
    row
    |> String.codepoints()
    |> Enum.with_index()
    |> Enum.map(fn {point, col_index} ->
      {{row_index, col_index}, point}
    end)
  end)
  |> Enum.into(%{})
end
```

```elixir
map = parse.(sample_input)
```

実行結果

```elixir
%{
  {1, 3} => ".",
  {9, 9} => ".",
  {1, 1} => ".",
  ...
}
```

座標と文字のマップにしています

続いて、同じ文字のペアを探索します

```elixir
find_pairs = fn map ->
  map
  |> Enum.reduce([], fn {{row_index, col_index}, point}, pairs ->
    case point do
      "." ->
        pairs

      mark ->
        map
        |> Enum.filter(fn {{pair_row_index, pair_col_index}, search_point} ->
          search_point == mark && (row_index < pair_row_index or col_index < pair_col_index)
        end)
        |> Enum.map(fn {{pair_row_index, pair_col_index}, _} ->
          {{row_index, col_index}, {pair_row_index, pair_col_index}}
        end)
        |> Kernel.++(pairs)
    end
  end)
end
```

```elixir
pairs = find_pairs.(map)
```

実行結果

```elixir
[{{3, 4}, {5, 5}}]
```

各ペアの前後にできる[定常波の腹](http://www.wakariyasui.sakura.ne.jp/p/wave/housoku/teijyouha.html)を取得します

ただし、領域外に出たものは除きます

その後、腹がある箇所を重複を除いてカウントします

```elixir
crate_antinodes = fn pairs, map ->
  max_row_index =
    map
    |> Enum.map(fn {{row_index, _}, _} -> row_index end)
    |> Enum.max()

  max_col_index =
    map
    |> Enum.map(fn {{_, col_index}, _} -> col_index end)
    |> Enum.max()

  IO.inspect({max_row_index, max_col_index}, label: "map size")

  pairs
  |> Enum.flat_map(fn {{row_index, col_index}, {pair_row_index, pair_col_index}} = pair ->
    f_row = pair_row_index - row_index
    f_col = pair_col_index - col_index

    IO.puts("")
    IO.inspect(pair, label: "pair")
    IO.inspect({f_row, f_col}, label: "frequency")

    [
      {row_index - f_row, col_index - f_col},
      {pair_row_index + f_row, pair_col_index + f_col}
    ]
    |> Enum.filter(fn {r, c} ->
      r >= 0 and r <= max_row_index and c >= 0 and c <= max_col_index
    end)
    |> IO.inspect(label: "antinodes")
  end)
  |> Enum.reduce({map, 0}, fn antinode, {acc_map, acc_num} ->
    case Map.get(acc_map, antinode) do
      "#" ->
        {acc_map, acc_num}

      _ ->
        {Map.put(acc_map, antinode, "#"), acc_num + 1}
    end
  end)
end
```

```elixir
{updated_map, num} = crate_antinodes.(pairs, map)
```

実行結果

```elixir
{%{
   {1, 3} => "#",
   {9, 9} => ".",
   {1, 1} => ".",
   ...
}, 2}
```

結果を確認しやすいように整形して表示します

```elixir
plot_map = fn map ->
  max_row_index =
    map
    |> Enum.map(fn {{row_index, _}, _} -> row_index end)
    |> Enum.max()

  max_col_index =
    map
    |> Enum.map(fn {{_, col_index}, _} -> col_index end)
    |> Enum.max()

  0..max_row_index
  |> Enum.map(fn row_index ->
    0..max_col_index
    |> Enum.reduce("", fn col_index, row ->
      row <> Map.get(map, {row_index, col_index})
    end)
  end)
  |> Enum.join("\n")
end
```

```elixir
plot_map.(updated_map)
|> Kino.Text.new(terminal: true)
```

実行結果

```text
..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........
```

正しく腹が描かれています

一連の処理を繋げて関数化します

```elixir
search_antinodes = fn input ->
  map =  parse.(input)

  map
  |> find_pairs.()
  |> IO.inspect(lablel: "pairs")
  |> crate_antinodes.(map)
end
```

アンテナをもう一つ増やしたケースで実行してみます

```elixir
{updated_map, num} =
  """
  ..........
  ..........
  ..........
  ....a.....
  ........a.
  .....a....
  ..........
  ..........
  ..........
  ..........
  """
  |> String.trim()
  |> search_antinodes.()

IO.puts("")
IO.inspect(num, label: "number of antinodes")

updated_map
|> plot_map.()
|> Kino.Text.new(terminal: true)
```

標準出力

```text
...

number of antinodes: 4
```

実行結果

```text
..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........
```

ここが正直問題文からは分かりにくかったのですが、別のアンテナが立っていたとしても、そこに腹が重なって作成されます

```elixir
{updated_map, num} =
  """
  ..........
  ..........
  ..........
  ....a.....
  ........a.
  .....a....
  ..........
  ......A...
  ..........
  ..........
  """
  |> String.trim()
  |> search_antinodes.()

IO.puts("")
IO.inspect(num, label: "number of antinodes")

updated_map
|> plot_map.()
|> Kino.Text.new(terminal: true)
```

標準出力

```text
...

number of antinodes: 4
```

実行結果

```text
..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........
```

複雑な入力例に対して実行します

```elixir
{updated_map, num} =
  """
  ............
  ........0...
  .....0......
  .......0....
  ....0.......
  ......A.....
  ............
  ............
  ........A...
  .........A..
  ............
  ............
  """
  |> String.trim()
  |> search_antinodes.()

IO.puts("")
IO.inspect(num, label: "number of antinodes")

updated_map
|> plot_map.()
|> Kino.Text.new(terminal: true)
```

標準出力

```text
...

number of antinodes: 14
```

実行結果

```text
......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....#.....
...#........
#......#....
........A...
.........A..
..........#.
..........#.
```

実際の入力に対して実行すれば答えが出ます

```elixir
{updated_map, num} = search_antinodes.(puzzle_input)

num
```

</details>

### Part 2

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

アンテナ自身も含めて一直線上に一定間隔で腹が繰り返されます

そのため、腹を作る関数だけ変更します

`min(abs(div(max_row_index, f_row)), abs(div(max_col_index, f_col)))` により、縦方向と横方向のうち、繰り返せる回数が少ない方を繰り返し回数の上限とします

0 から上記回数まで前後に腹を作っていき、領域内のものだけを残します

```elixir
crate_antinodes = fn pairs, map ->
  max_row_index =
    map
    |> Enum.map(fn {{row_index, _}, _} -> row_index end)
    |> Enum.max()

  max_col_index =
    map
    |> Enum.map(fn {{_, col_index}, _} -> col_index end)
    |> Enum.max()

  IO.inspect({max_row_index, max_col_index}, label: "map size")

  pairs
  |> Enum.flat_map(fn {{row_index, col_index}, {pair_row_index, pair_col_index}} = pair ->
    f_row = pair_row_index - row_index
    f_col = pair_col_index - col_index

    IO.puts("")
    IO.inspect(pair, label: "pair")
    IO.inspect({f_row, f_col}, label: "frequency")

    0..min(abs(div(max_row_index, f_row)), abs(div(max_col_index, f_col)))
    |> Enum.flat_map(fn index ->
      [
        {row_index - index * f_row, col_index - index * f_col},
        {row_index + index * f_row, col_index + index * f_col}
      ]
    end)
    |> Enum.filter(fn {r, c} ->
      r >= 0 and r <= max_row_index and c >= 0 and c <= max_col_index
    end)
    |> Enum.uniq()
    |> IO.inspect(label: "antinodes")
  end)
  |> Enum.reduce({map, 0}, fn antinode, {acc_map, acc_num} ->
    case Map.get(acc_map, antinode) do
      "#" ->
        {acc_map, acc_num}

      _ ->
        {Map.put(acc_map, antinode, "#"), acc_num + 1}
    end
  end)
end
```

単純な例で試してみます

```elixir
sample_input =
  """
  T.........
  ...T......
  .T........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  """
  |> String.trim()

{updated_map, num} = search_antinodes.(sample_input)

IO.puts("")
IO.inspect(num, label: "number of antinodes")

plot_map.(updated_map)
|> Kino.Text.new(terminal: true)
```

標準出力

```text
...

number of antinodes: 9
```

実行結果

```text
#....#....
...#......
.#....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........
```

アンテナの場所にも腹ができるため、正しく作成できています

入力例に対して実行してみます

```elixir
{updated_map, num} =
  """
  ............
  ........0...
  .....0......
  .......0....
  ....0.......
  ......A.....
  ............
  ............
  ........A...
  .........A..
  ............
  ............
  """
  |> String.trim()
  |> search_antinodes.()

IO.puts("")
IO.inspect(num, label: "number of antinodes")

plot_map.(updated_map)
|> Kino.Text.new(terminal: true)
```

標準出力

```text
...

number of antinodes: 34
```

実行結果

```text
##....#....#
.#.#....#...
..#.##....#.
..##...#....
....#....#..
.#...##....#
...#..#.....
#....#.#....
..#.....#...
....#....#..
.#........#.
...#......##
```

実際の入力に対して実行すれば答えが出ます

```elixir
{updated_map, num} = search_antinodes.(puzzle_input)

num
```

</details>

## まとめ

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

![aoc2024_day8.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/0aaef859-0b0e-d5cb-679e-b3f7386f1a21.png)

物理学用語の「腹」が出てきたり、問題文を読み解くのが難しい問題でした