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

はじめに

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

0 の場所からスタートして、高さを 1 ずつ増やしながら辿り着ける 9 の数を数えます

まずは小さい入力例で考えます

small_sample_input =
  """
  0123
  1234
  8765
  9876
  """
  |> String.trim()

入力を座標と高さのマップにパースする関数、再帰的に 1 ずつ登っていく関数、全ての 0 に対してスコアを求める関数をモジュールに定義します

defmodule Hiking do
  @next_point [
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
  ]

  def parse_map(input) do
    input
    |> String.split("\n")
    |> Enum.with_index()
    |> Enum.flat_map(fn {row, row_index} ->
      row
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {height, col_index} ->
        {{row_index, col_index}, String.to_integer(height)}
      end)
    end)
    |> Enum.into(%{})
  end

  def up(map, {cur_r, cur_c}, next_height) do
    @next_point
    |> Enum.map(fn {mov_r, move_c} ->
      next_point = {cur_r + mov_r, cur_c + move_c}

      case Map.get(map, next_point) do
        ^next_height ->
          if next_height == 9 do
            [next_point]
          else
            up(map, next_point, next_height + 1)
          end

        _ ->
          []
      end
    end)
    |> List.flatten()
    |> Enum.uniq()
  end

  def get_score(map) do
    map
    |> Enum.filter(fn {_, height} ->
      height == 0
    end)
    |> Enum.map(fn {point, _} ->
      map
      |> Hiking.up(point, 1)
      |> length()
    end)
    |> Enum.sum()
  end
end

まずは地図を読み込みます

small_map = Hiking.parse_map(small_sample_input)

実行結果

%{
  {0, 0} => 0,
  {0, 1} => 1,
  {0, 2} => 2,
  {0, 3} => 3,
  {1, 0} => 1,
  {1, 1} => 2,
  {1, 2} => 3,
  {1, 3} => 4,
  {2, 0} => 8,
  {2, 1} => 7,
  {2, 2} => 6,
  {2, 3} => 5,
  {3, 0} => 9,
  {3, 1} => 8,
  {3, 2} => 7,
  {3, 3} => 6
}

座標 {0, 0} から上下左右の座標を探し、 1 になっているところに移動します

次にその座標から上下左右の座標を探し、 2 になっているところに移動します

これを繰り返して 9 までたどり着いた場合、 9 の地点の座標を返します

Enum.uniq() によって、同じ頂点に別経路で辿り着いたケースの重複を削除します

Hiking.up(small_map, {0, 0}, 1)

実行結果

[{3, 0}]

{0, 0} から登ることができる 9 は {3, 0} の一つだけです

全ての 0 で繰り返して頂点の数を合計し、スコアを取得します

Hiking.get_score(small_map)

実行結果

1

大きい入力例に対しても実行してみます

large_sample_input =
  """
  89010123
  78121874
  87430965
  96549874
  45678903
  32019012
  01329801
  10456732
  """
  |> String.trim()

large_sample_input
|> Hiking.parse_map()
|> Hiking.get_score()

実行結果

36

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

puzzle_input
|> Hiking.parse_map()
|> Hiking.get_score()

Part 2

回答

Part 1 で重複削除していた経路をそのまま数えれば良いだけです

つまり、 Part 1 のモジュールから |> Enum.uniq() の行を消すだけでした

defmodule Hiking do
  @next_point [
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
  ]

  def parse_map(input) do
    input
    |> String.split("\n")
    |> Enum.with_index()
    |> Enum.flat_map(fn {row, row_index} ->
      row
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {height, col_index} ->
        {{row_index, col_index}, String.to_integer(height)}
      end)
    end)
    |> Enum.into(%{})
  end

  def up(map, {cur_r, cur_c}, next_height) do
    @next_point
    |> Enum.map(fn {mov_r, move_c} ->
      next_point = {cur_r + mov_r, cur_c + move_c}

      case Map.get(map, next_point) do
        ^next_height ->
          if next_height == 9 do
            [next_point]
          else
            up(map, next_point, next_height + 1)
          end

        _ ->
          []
      end
    end)
    |> List.flatten()
  end

  def get_score(map) do
    map
    |> Enum.filter(fn {_, height} ->
      height == 0
    end)
    |> Enum.map(fn {point, _} ->
      map
      |> Hiking.up(point, 1)
      |> length()
    end)
    |> Enum.sum()
  end
end

まとめ

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

Part2 の方が Part 1 より単純になってしまいました