7
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-11-26

はじめに

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 の入力を取得します

スクリーンショット 2024-11-25 23.59.49.png

私の答え

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

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 とほぼ同じ考え方で実装できました

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

7
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?