はじめに
Advent of code 2024 の準備として、過去回の Advent of code 2015 を Livebook で楽しみます
本記事では Day 13 の Part 1 と Part 2 を解きます
問題文はこちら
実装したノートブックはこちら
セットアップ
Kino AOC をインストールします
Mix.install([
{:kino_aoc, "~> 0.1"}
])
Kino AOC の使い方はこちらを参照
入力の取得
"Advent of Code Helper" スマートセルを追加し、 Day 13 の入力を取得します
私の答え
私の答えです。
折りたたんでおきます。
▶を押して開いてください。
Part 1
回答
基本的に Day 9 と同じです
https://qiita.com/RyoWakabayashi/items/f19e9796e71eebcb8bb0
入力を正規表現でパースします
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."
)
実行結果
%{"from" => "Bob", "num" => "54", "sign" => "gain", "to" => "Alice"}
"sign"
と "num"
で幸福変動値を計算します
Day 9 と同様、 {from, to} => value
の幸福変動値マップとして保持しておきます
ただし、今回は向きに意味があるので反転させたりはしません
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 と同じく、全順列を取得するためのモジュールを用意します
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
ゲストの一覧を取得します
guests = Permutations.get_guests(happiness_map)
実行結果
["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」は同じ並びとして扱えます
このことから、全ての円順列は以下のようにして求められます
permutations =
guests
|> tl()
|> Permutations.all()
|> Enum.map(&[hd(guests) | &1])
これにより、計算量が $ n! $ から $ (n-1)! $ になります
各順列について幸福変動値の合計を計算し、最大値を求めます
両隣について幸福変動値を計算するため、 {from, to}
と {to, from}
の両方を足しています
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()
Part 2
回答
順列取得モジュール、ゲスト一覧取得までは Part 1 と同じです
Part 2 では "Me"
を円順列のメンバーに加えます
permutations =
guests
|> Permutations.all()
|> Enum.map(&["Me" | &1])
"Me"
は幸福変動値マップに存在していないため、マップから値が取得できなければ 0 としています
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()
まとめ
Day 9 とほぼ同じ考え方で実装できました
円順列として扱うことで計算量を抑制できたのが良かったです