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

はじめに

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

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

問題文を噛み砕くと、約数の合計 * 10 がパズル入力値以上になる最小の家番号を探索することになります

そのため、まず約数の取得処理を実装してみます

例えば 1 から 9 の各約数を求める場合、単純に考えると以下のような実装になります

1..9
|> Enum.map(fn house_number ->
  1..house_number
  |> Enum.filter(fn x ->
    rem(house_number, x) == 0
  end)
end)

しかし、これだと 1,000,000 の約数を求める場合、 1,000,000 回計算しないといけません

1 から 1,000,000 の各約数を求める場合の計算量は 1000000 * 1000000 / 2 で膨大になります

そこで、少しでも計算量を減らすため、以下のように変更します

1..9
|> Enum.map(fn house_number ->
  limit = :math.sqrt(house_number) |> floor()

  1..limit
  |> Enum.filter(fn x ->
    rem(house_number, x) == 0
  end)
  |> Enum.flat_map(fn x ->
    [x, div(house_number, x)]
  end)
  |> Enum.uniq()
  |> Enum.sort()
end)

A が X の約数である場合、 X = A * B （B も X の約数）となります

条件として A <= B とすると、　A の最大値は A = B のとき、つまり X = A ^ 2 のときです

したがって、 A は 1 から X の平方根の範囲で探索すれば良いことになります

全ての A を探索したのち、各 A に対応する B を追加し、重複を排除すれば全ての約数が取得できます

これを利用して解いてみましょう

入力を数値に変換します

target_number = String.to_integer(puzzle_input)

1 から 1,000,000 の範囲で探索すれば発見できます

1..1000000
|> Enum.find(fn house_number ->
  limit = house_number |> :math.sqrt() |> floor()

  1..limit
  |> Enum.filter(fn x ->
    rem(house_number, x) == 0
  end)
  |> Enum.flat_map(fn x ->
    [x, div(house_number, x)]
  end)
  |> Enum.uniq()
  |> Enum.map(fn num -> num * 10 end)
  |> Enum.sum()
  |> Kernel.>=(target_number)
end)

Part 2

回答

約数のうち、 50 以下とかけるものだけを使用します

（X = A * B のとき、 B <= 50 となる A のみ）

1..1000000
|> Enum.find(fn house_number ->
  limit = house_number |> :math.sqrt() |> floor()

  1..limit
  |> Enum.filter(fn x ->
    rem(house_number, x) == 0
  end)
  |> Enum.flat_map(fn x -> 
    [x, div(house_number, x)]
  end)
  |> Enum.uniq()
  |> Enum.filter(fn num -> div(house_number, num) <= 50 end)
  |> Enum.sum()
  |> Kernel.>=(target_number / 11)
end)

まとめ

計算量を少なくするための工夫が必要でした（工夫しないと終わりません）