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

## はじめに

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

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

問題文はこちら

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

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

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

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

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-11-25 23.59.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/a0edcfe0-f124-298c-c711-f9619d4fb8c9.png)

## 私の答え

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

### Part 1

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

基本的に Day 9 と同じです

https://qiita.com/RyoWakabayashi/items/f19e9796e71eebcb8bb0

入力を正規表現でパースします

```elixir
Regex.named_captures(
  ~r/(?<to>[a-zA-Z]+) would (?<sign>(gain|lose)) (?<num>[0-9]+) happiness units by sitting next to (?<from>[a-zA-Z]+)/,
  "Alice would gain 54 happiness units by sitting next to Bob."
)
```

実行結果

```elixir
%{"from" => "Bob", "num" => "54", "sign" => "gain", "to" => "Alice"}
```

`"sign"` と `"num"` で幸福変動値を計算します

Day 9 と同様、 `{from, to} => value` の幸福変動値マップとして保持しておきます

ただし、今回は向きに意味があるので反転させたりはしません

```elixir
happiness_map =
  puzzle_input
  |> String.split("\n")
  |> Enum.into(%{}, fn row ->
    Regex.named_captures(
      ~r/(?<to>[a-zA-Z]+) would (?<sign>(gain|lose)) (?<num>[0-9]+) happiness units by sitting next to (?<from>[a-zA-Z]+)/,
      row
    )
    |> then(fn %{"from" => from, "to" => to, "num" => num, "sign" => sign} ->
      num =
        case sign do
          "gain" -> String.to_integer(num)
          _ -> -1 * String.to_integer(num)
        end
    
      {{from, to}, num}
    end)
  end)
```

Day 9 と同じく、全順列を取得するためのモジュールを用意します

```elixir
defmodule Permutations do
  def get_guests(happiness_map) do
    happiness_map
    |> Map.keys()
    |> Enum.map(&Tuple.to_list(&1))
    |> Enum.concat()
    |> Enum.uniq()
  end

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

ゲストの一覧を取得します

```elixir
guests = Permutations.get_guests(happiness_map)
```

実行結果

```elixir
["Bob", "Eric", "Carol", "George", "David", "Alice", "Frank", "Mallory"]
```

順列の数は以下の公式で求められます

$$
P(n, r) = \frac{n!}{(n - r)!}
$$

8人のうち、8人を選んで並べるので $ 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 = 40320 $ 通りです

このまま計算しても良いのですが、今回は円卓に並ぶため、円順列として扱えます

円順列では、先頭が入れ替わっても単に「どこを切り取ったか」が変わるだけで同じ並びです

「ABCD」と「BCDA」は同じ並びとして扱えます

このことから、全ての円順列は以下のようにして求められます

```elixir
permutations =
  guests
  |> tl()
  |> Permutations.all()
  |> Enum.map(&[hd(guests) | &1])
```

これにより、計算量が $ n! $ から $ (n-1)! $ になります

各順列について幸福変動値の合計を計算し、最大値を求めます

両隣について幸福変動値を計算するため、 `{from, to}` と `{to, from}` の両方を足しています

```elixir
permutations
|> Enum.map(fn permutation ->
  next_permutation = tl(permutation) ++ [hd(permutation)]

  Enum.zip(permutation, next_permutation)
  |> Enum.map(fn {from, to} ->
    Map.get(happiness_map, {from, to}) + Map.get(happiness_map, {to, from})
  end)
  |> Enum.sum()
end)
|> Enum.max()
```

</details>

### Part 2

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

順列取得モジュール、ゲスト一覧取得までは Part 1 と同じです

Part 2 では `"Me"` を円順列のメンバーに加えます

```elixir
permutations =
  guests
  |> Permutations.all()
  |> Enum.map(&["Me" | &1])
```

`"Me"` は幸福変動値マップに存在していないため、マップから値が取得できなければ 0 としています

```elixir
permutations
|> Enum.map(fn permutation ->
  next_permutation = tl(permutation) ++ [hd(permutation)]

  Enum.zip(permutation, next_permutation)
  |> Enum.map(fn {from, to} ->
    Map.get(happiness_map, {from, to}, 0) + Map.get(happiness_map, {to, from}, 0)
  end)
  |> Enum.sum()
end)
|> Enum.max()
```

</details>

## まとめ

Day 9 とほぼ同じ考え方で実装できました

円順列として扱うことで計算量を抑制できたのが良かったです