はじめに
Advent of code 2024 の準備として、過去回の Advent of code 2015 を Livebook で楽しみます
本記事では Day 18 の Part 1 と Part 2 を解きます
問題文はこちら
実装したノートブックはこちら
セットアップ
Kino AOC をインストールします
また、今回も行列演算をしたいので Nx を使います
Mix.install([
{:kino_aoc, "~> 0.1"},
{:nx, "~> 0.9.2"}
])
Kino AOC の使い方はこちらを参照
入力の取得
"Advent of Code Helper" スマートセルを追加し、 Day 18 の入力を取得します
私の答え
私の答えです。
折りたたんでおきます。
▶を押して開いてください。
Part 1
回答
まず入力例の小さいケースから考えてみましょう
入力の文字列を行列に変換します
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()
実行結果
#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 を詰め込みます
pad_tensor = Nx.pad(lights, 0, [{1, 1, 0}, {1, 1, 0}])
実行結果
#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 の範囲について中央のライトを引きます
around_on =
pad_tensor
|> Nx.window_sum({3, 3})
|> Nx.subtract(lights)
実行結果
#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 以下光っていれば、次のタイミングで光ります
current_on_next_on =
Nx.multiply(
lights,
Nx.multiply(Nx.greater_equal(around_on, 2), Nx.less_equal(around_on, 3))
)
実行結果
#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 個光っていれば次に光ります
current_off_next_on =
Nx.multiply(
Nx.equal(lights, 0),
Nx.equal(around_on, 3)
)
実行結果
#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]
]
>
どちらかの条件に合致していれば光るので、上記二つの演算結果を足します
next_on = Nx.add(current_on_next_on, current_off_next_on)
実行結果
#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]
]
>
出力例で示されている値と同じになりました
上記でやってきた内容を実際の入力で実行します
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 になっていた数を合計します
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()
Part 2
回答
四隅だけは常に光っているため、その配置を表す行列を作成します
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 の論理和を取ります
lights = Nx.logical_or(lights, corner_lights)
各回の演算時、最後に四隅 1 との論理和を取るようにします
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()
まとめ
問題文から ChatGPT に画像を生成してもらいました
行列演算で綺麗に解けるタイプの問題でした