Advent of code 2015 Day 9 Part 1 & Part 2 を Livebook で楽しむ

はじめに

Advent of code 2024 の準備として、過去回の Advent of code 2015 を Livebook で楽しみます

本記事では Day 9 の Part 1 と Part 2 を解きます

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

いわゆるセールスマン巡回問題（Traveling Salesman Problem = TSP）です

単純に全てのルートを取得し、それぞれの合計距離を計算します

defmodule TSP do
  def cities(distances) do
    distances
    |> Map.keys()
    |> Enum.map(&Tuple.to_list(&1))
    |> Enum.concat()
    |> Enum.uniq()
  end

  def all_routes([]), do: [[]]
  def all_routes(list) do
    for elem <- list,
        rest <- all_routes(list--[elem]) do
      [elem | rest]
    end
  end

  def drop_reversed(list) do
    list
    |> Enum.reduce([], fn new, acc ->
      if Enum.member?(acc, Enum.reverse(new)) do
        acc
      else
        [new | acc]
      end
    end)
  end

  def reverse_distances(distances) do
    distances
    |> Enum.into(%{}, fn {{from, to}, value} ->
      {{to, from}, value}
    end)
  end

  def get_min_distance(permutations, full_distances) do
    permutations
    |> Enum.map(fn permutation ->
      next_permutation = tl(permutation) ++ [nil]
    
      Enum.zip(permutation, next_permutation)
      |> Enum.map(fn {from, to} ->
        if is_nil(to), do: 0, else: Map.get(full_distances, {from, to})
      end)
      |> Enum.sum()
    end)
    |> Enum.min()
  end

  def solve(distances) do
    permutations =
      distances
      |> cities()
      |> all_routes()
      |> drop_reversed()

    full_distances = Map.merge(distances, reverse_distances(distances))

    get_min_distance(permutations, full_distances)
  end
end

一旦、問題を単純化して、入力を以下のような {from, to} => distance のマップにします

distances = %{
  {:a, :b} => 464,
  {:a, :c} => 518,
  {:b, :c} => 141
}

モジュールの一部を実行して、動きを確認してみましょう

まず、全てのルートを取得するために都市の一覧を取得します

TSP.cities(distances)

実行結果

[:a, :b, :c]

都市を通る全ての順列を取得し、逆順のものは距離が同じなので排除します

全ての順列を取得する処理は Elixir Forum に出ていたものを参考にしました

https://elixirforum.com/t/most-elegant-way-to-generate-all-permutations/2706

permutations =
  distances
  |> TSP.cities()
  |> TSP.all_routes()
  |> TSP.drop_reversed()

実行結果

[[:b, :a, :c], [:a, :c, :b], [:a, :b, :c]]

距離を計算する際、2都市間の距離が {from, to} でも {to, from} でも同じように取得できるよう、キーを反転したものも追加します

full_distances = Map.merge(distances, TSP.reverse_distances(distances))

実行結果

%{
  {:a, :b} => 464,
  {:a, :c} => 518,
  {:b, :a} => 464,
  {:b, :c} => 141,
  {:c, :a} => 518,
  {:c, :b} => 141
}

各順列について、合計距離を計算します

例えば [:b, :a, :c] の場合、一つずらした [:a, :c, nil] という配列を作り、 Enum.zip で組み合わせると [{:b, :a}, {:a, :c}, {:c, nil}] という {from, to} の配列ができるので、あとは単純に各距離を取得して合計するだけです

ただし、 to が nil の場合（終点の場合）は距離を 0 とします

TSP.solve(distances)

実行結果

605

実際のパズルの入力を正規表現で {from, to} => distance のマップに変換します

distances =
  puzzle_input
  |> String.split("\n")
  |> Enum.into(%{}, fn row ->
    Regex.named_captures(
      ~r/(?<from>[a-zA-Z]+) to (?<to>[a-zA-Z]+) = (?<distance>[0-9]+)/,
      row
    )
    |> then(fn %{"from" => from, "to" => to, "distance" => distance} ->
      {{from, to}, String.to_integer(distance)}
    end)
  end)

実行結果

%{
  {"AlphaCentauri", "Arbre"} => 116,
  {"AlphaCentauri", "Snowdin"} => 12,
  {"AlphaCentauri", "Straylight"} => 91,
  ...
  {"Tristram", "Snowdin"} => 103,
  {"Tristram", "Straylight"} => 97,
  {"Tristram", "Tambi"} => 49
}

あとは、用意しておいたモジュールで解くだけです

TSP.solve(distances)

Part 2

回答

最短距離だったのが最長距離になるだけでした

defmodule TSP do
  def cities(distances) do
    distances
    |> Map.keys()
    |> Enum.map(&Tuple.to_list(&1))
    |> Enum.concat()
    |> Enum.uniq()
  end

  def all_routes([]), do: [[]]
  def all_routes(list) do
    for elem <- list,
        rest <- all_routes(list--[elem]) do
      [elem | rest]
    end
  end

  def drop_reversed(list) do
    list
    |> Enum.reduce([], fn new, acc ->
      if Enum.member?(acc, Enum.reverse(new)) do
        acc
      else
        [new | acc]
      end
    end)
  end

  def reverse_distances(distances) do
    distances
    |> Enum.into(%{}, fn {{from, to}, value} ->
      {{to, from}, value}
    end)
  end

  def get_max_distance(permutations, full_distances) do
    permutations
    |> Enum.map(fn permutation ->
      next_permutation = tl(permutation) ++ [nil]
    
      Enum.zip(permutation, next_permutation)
      |> Enum.map(fn {from, to} ->
        if is_nil(to), do: 0, else: Map.get(full_distances, {from, to})
      end)
      |> Enum.sum()
    end)
    |> Enum.max()
  end

  def solve(distances) do
    permutations =
      distances
      |> cities()
      |> all_routes()
      |> drop_reversed()

    full_distances = Map.merge(distances, reverse_distances(distances))

    get_max_distance(permutations, full_distances)
  end
end

puzzle_input
|> String.split("\n")
|> Enum.into(%{}, fn row ->
  Regex.named_captures(
    ~r/(?<from>[a-zA-Z]+) to (?<to>[a-zA-Z]+) = (?<distance>[0-9]+)/,
    row
  )
  |> then(fn %{"from" => from, "to" => to, "distance" => distance} ->
    {{from, to}, String.to_integer(distance)}
  end)
end)
|> TSP.solve()

まとめ

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

都市の数が少なかったので、そんなに工夫せずとも解けました