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 を解きます

問題文はこちら

https://adventofcode.com/2015/day/9

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2015/2015_day9_part1.livemd

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2015/2015_day9_part2.livemd

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-11-23 10.43.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/c22e74c2-0ccb-90ad-7385-1c9d78d87c9f.png)

## 私の答え

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

### Part 1

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

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

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

```elixir
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` のマップにします

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

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

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

```elixir
TSP.cities(distances)
```

実行結果

```elixir
[:a, :b, :c]
```

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

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

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

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

実行結果

```elixir
[[:b, :a, :c], [:a, :c, :b], [:a, :b, :c]]
```

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

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

実行結果

```elixir
%{
  {: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 とします

```elixir
TSP.solve(distances)
```

実行結果

```elixir
605
```

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

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

実行結果

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

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

```elixir
TSP.solve(distances)
```

</details>

### Part 2

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

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

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

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

</details>

## まとめ

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

![tsp.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/1420e561-9a7a-3eb3-9a1e-71b24a28a900.jpeg)

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