LoginSignup
8
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(若林 諒)

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

Posted at

はじめに

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

スクリーンショット 2024-12-08 22.14.17.png

私の答え

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

Part 1

回答

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

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

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

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

map = parse.(sample_input)

実行結果

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

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

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

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

pairs = find_pairs.(map)

実行結果

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

各ペアの前後にできる定常波の腹を取得します

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

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

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

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

実行結果

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

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

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

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

実行結果

..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........

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

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

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

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

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

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

標準出力

...

number of antinodes: 4

実行結果

..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........

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

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

標準出力

...

number of antinodes: 4

実行結果

..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........

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

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

標準出力

...

number of antinodes: 14

実行結果

......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....#.....
...#........
#......#....
........A...
.........A..
..........#.
..........#.

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

{updated_map, num} = search_antinodes.(puzzle_input)

num

Part 2

回答

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

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

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

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

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

単純な例で試してみます

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)

標準出力

...

number of antinodes: 9

実行結果

#....#....
...#......
.#....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........

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

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

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

標準出力

...

number of antinodes: 34

実行結果

##....#....#
.#.#....#...
..#.##....#.
..##...#....
....#....#..
.#...##....#
...#..#.....
#....#.#....
..#.....#...
....#....#..
.#........#.
...#......##

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

{updated_map, num} = search_antinodes.(puzzle_input)

num

まとめ

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

aoc2024_day8.png

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

ElixirAdvent Calendar 2024

Day 16
8
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
8
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?