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

はじめに

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

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

問題文はこちら

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

セットアップ

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

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

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

入力の取得

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

私の答え

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

Part 1

回答

まず、正当なパスワードの条件をチェックします

「アルファベットが順番通りに3つ並んでいる」の条件は力技で突破します

has_straight_str = fn str ->
  Regex.match?(
    ~r/(?=abc|bcd|cde|def|efg|fgh|ghi|hij|ijk|jkl|klm|lmn|mno|nop|opq|pqr|qrs|rst|stu|tuv|uvw|vwx|wxy|xyz)/,
    str
  )
end

has_straight_str.("abcd") は true 、 has_straight_str.("abdc") は false になりました

「"i" と "o" と "l" を含まないこと」の条件はそのままです

has_no_iol = fn str ->
  Regex.match?(~r/^[^iol]*$/, str)
end

「同じ文字の連続が2回以上存在する」も正規表現でチェックします

has_double_double = fn str ->
  Regex.match?(~r/(.)\1.*(.)\2/, str)
end

上記全てのチェックをクリアすれば正当なパスワードと言えます

valid_password? = fn password ->
  has_straight_str.(password) && has_no_iol.(password) && has_double_double.(password)
end

続いて、「次のパスワード」を取得します

"a" から "z" を 0 から 25 に変換し、 26 進数として計算すれば良さそうです

英字を数字に変換する関数を作ります

to_alphabet_num = fn str ->
  <<code>> = str
  code - 97
end

逆に数字を英字に変換する関数を作ります

from_alphabet_num = fn num ->
  <<(num + 97)>>
end

順番に 1 ずつ加算していくと時間がかかるので（10分ほど待てば解けますが）、少し工夫します

例えば入力の末尾が iaaa だったとき、末尾が iaaa から izzz のうちは必ず不正です（i が含まれるため）

次に正当なパスワードは末尾が jaaa になったときです

これを利用して、 "i" "o" "l" があった場合、 "j" "p" "m" + 末尾まで "a" までパスワードのループをスキップできます

skip_iol = fn password ->
  index_map =
    ["i", "o", "l"]
    |> Enum.reduce(%{}, fn char, index_map ->
      case :binary.match(password, char) do
        {index, _} -> Map.put(index_map, char, index)
        _ -> index_map
      end
    end)

  if index_map == %{} do
    password
  else
    index_map
    |> Enum.min_by(fn {_, index} -> index end)
    |> then(fn {char, index} ->
      password
      |> String.codepoints()
      |> Enum.with_index()
      |> Enum.map(fn {code, code_index} ->
        cond do
          code_index == index ->
            case char do
              "i" -> "j"
              "o" -> "p"
              "l" -> "m"
              _ -> code
            end
          code_index > index ->
            "a"
          true ->
            code
        end
      end)
      |> Enum.join()
    end)
  end
end

ここまでの関数を組み合わせて次のパスワードを求める関数を作ります

next_password = fn current ->
  current
  |> String.codepoints()
  |> Enum.reverse()
  |> Enum.with_index()
  |> Enum.reduce(0, fn {str, digit}, num ->
    num + to_alphabet_num.(str) * (26**digit)
  end)
  |> Kernel.+(1)
  |> Integer.digits(26)
  |> Enum.map(&from_alphabet_num.(&1))
  |> Enum.join()
  |> skip_iol.()
end

現在のパスワードから正当な次のパスワードを探索する関数を用意します

find_new_password = fn current_password ->
  0..10000000
  |> Enum.reduce_while(current_password, fn _, password ->
    new_password = next_password.(password)
    if valid_password?.(new_password) do
      {:halt, new_password}
    else
      {:cont, new_password}
    end
  end)
end

後は関数にかけるだけです

find_new_password.(puzzle_input)

Part 2

回答

次の次のパスワードを求めるので、関数を2回実行するだけです

puzzle_input
|> find_new_password.()
|> find_new_password.()

まとめ

全探索するとかなり計算量が多いため、工夫を施しました

いよいよ難しくなってきましたね