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 を解きます

問題文はこちら

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

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

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

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

## セットアップ

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

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

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

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

## 入力の取得

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

![スクリーンショット 2024-11-25 20.25.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/60508522-07f9-8c7e-b0ac-ecab6aa46e3b.png)

## 私の答え

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

### Part 1

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

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

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

```elixir
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" を含まないこと」の条件はそのままです

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

```elixir
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
```

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

```elixir
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
```

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

```elixir
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
```

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

```elixir
find_new_password.(puzzle_input)
```

</details>

### Part 2

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

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

```elixir
puzzle_input
|> find_new_password.()
|> find_new_password.()
```

</details>

## まとめ

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

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