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

## はじめに

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

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

問題文はこちら

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

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

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

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

## セットアップ

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

また、今回も行列演算をしたいので Nx を使います

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

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

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

## 入力の取得

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

![スクリーンショット 2024-11-30 11.49.01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/73178983-1803-344e-0117-5ca39d6ba1a0.png)

## 私の答え

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

### Part 1

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

まず入力例の小さいケースから考えてみましょう

入力の文字列を行列に変換します

```elixir
lights =
  """
  .#.#.#
  ...##.
  #....#
  ..#...
  #.#..#
  ####..
  """
  |> String.trim()
  |> String.split("\n")
  |> Enum.map(fn row ->
    row
    |> String.codepoints()
    |> Enum.map(fn light -> if light == "#", do: 1, else: 0 end)
  end)
  |> Nx.tensor()
```

実行結果

```elixir
#Nx.Tensor<
  s32[6][6]
  [
    [0, 1, 0, 1, 0, 1],
    [0, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0],
    [1, 0, 1, 0, 0, 1],
    [1, 1, 1, 1, 0, 0]
  ]
>
```

「光っている周囲のライト数」を端でも数えたいので、上下左右に `0` を詰め込みます

```elixir
pad_tensor = Nx.pad(lights, 0, [{1, 1, 0}, {1, 1, 0}])
```

実行結果

```elixir
#Nx.Tensor<
  s32[8][8]
  [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 1, 0],
    [0, 1, ...],
    ...
  ]
>
```

`Nx.window_sum` で `3 * 3` の範囲の合計を計算します

また、各ライトの周辺で光っているライトだけを集計するため、各 `3 * 3` の範囲について中央のライトを引きます

```elixir
around_on =
  pad_tensor
  |> Nx.window_sum({3, 3})
  |> Nx.subtract(lights)
```

実行結果

```elixir
#Nx.Tensor<
  s32[6][6]
  [
    [1, 0, 3, 2, 4, 1],
    [2, 2, 3, 2, 4, 3],
    [0, 2, 2, 3, 3, 1],
    [2, 4, 1, 2, 2, 2],
    [2, 6, 4, 4, 2, 0],
    [2, 4, 3, 2, 2, 1]
  ]
>
```

現在光っているライトノ場合、周辺のライトが 2 以上 3 以下光っていれば、次のタイミングで光ります

```elixir
current_on_next_on =
  Nx.multiply(
    lights,
    Nx.multiply(Nx.greater_equal(around_on, 2), Nx.less_equal(around_on, 3))
  )
```

実行結果

```elixir
#Nx.Tensor<
  s32[6][6]
  [
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [1, 0, 1, 1, 0, 0]
  ]
>
```

現在光っていないライトの場合、周辺のライトが 3 個光っていれば次に光ります

```elixir
current_off_next_on =
  Nx.multiply(
    Nx.equal(lights, 0),
    Nx.equal(around_on, 3)
  )
```

実行結果

```elixir
#Nx.Tensor<
  u8[6][6]
  [
    [0, 0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 1],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
  ]
>
```

どちらかの条件に合致していれば光るので、上記二つの演算結果を足します

```elixir
next_on = Nx.add(current_on_next_on, current_off_next_on)
```

実行結果

```elixir
#Nx.Tensor<
  s32[6][6]
  [
    [0, 0, 1, 1, 0, 0],
    [0, 0, 1, 1, 0, 1],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [1, 0, 1, 1, 0, 0]
  ]
>
```

出力例で示されている値と同じになりました

上記でやってきた内容を実際の入力で実行します

```elixir
lights =
  puzzle_input
  |> String.split("\n")
  |> Enum.map(fn row ->
    row
    |> String.codepoints()
    |> Enum.map(fn light -> if light == "#", do: 1, else: 0 end)
  end)
  |> Nx.tensor()
```

100 回操作を繰り返した結果、 1 になっていた数を合計します

```elixir
1..100
|> Enum.reduce(lights, fn _, acc_lights ->
  around_on =
    acc_lights
    |> Nx.pad(0, [{1, 1, 0}, {1, 1, 0}])
    |> Nx.window_sum({3, 3})
    |> Nx.subtract(acc_lights)

  current_on_next_on =
    Nx.multiply(
      acc_lights,
      Nx.multiply(Nx.greater_equal(around_on, 2), Nx.less_equal(around_on, 3))
    )

  current_off_next_on =
    Nx.multiply(
      Nx.equal(acc_lights, 0),
      Nx.equal(around_on, 3)
    )

  Nx.add(current_on_next_on, current_off_next_on)
end)
|> Nx.sum()
```

</details>

### Part 2

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

四隅だけは常に光っているため、その配置を表す行列を作成します

```elixir
tb_lights =
  1..100
  |> Enum.map(fn index -> if index == 1 or index == 100, do: 1, else: 0 end)
  |> Nx.tensor()
  |> Nx.new_axis(1)

inner_lights = Nx.broadcast(0, {100, 98})

corner_lights =
  Nx.concatenate(
    [tb_lights, inner_lights, tb_lights],
    axis: 1
  )
```

パズル入力と四隅 1 の論理和を取ります

```elixir
lights = Nx.logical_or(lights, corner_lights)
```

各回の演算時、最後に四隅 1 との論理和を取るようにします

```elixir
1..100
|> Enum.reduce(lights, fn _, acc_lights ->
  around_on =
    acc_lights
    |> Nx.pad(0, [{1, 1, 0}, {1, 1, 0}])
    |> Nx.window_sum({3, 3})
    |> Nx.subtract(acc_lights)

  current_on_next_on =
    Nx.multiply(
      acc_lights,
      Nx.multiply(Nx.greater_equal(around_on, 2), Nx.less_equal(around_on, 3))
    )

  current_off_next_on =
    Nx.multiply(
      Nx.equal(acc_lights, 0),
      Nx.equal(around_on, 3)
    )

  Nx.add(current_on_next_on, current_off_next_on)
  |> Nx.logical_or(corner_lights)
end)
|> Nx.sum()
```

</details>

## まとめ

問題文から ChatGPT に画像を生成してもらいました

![lights.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/6253047b-af92-8b33-7147-494a27c5e626.jpeg)

行列演算で綺麗に解けるタイプの問題でした