はじめに
Advent of code 2023 Day 13 の Part 1 と Part 2 を解きます
去年、 Day 12 が難しくて挫折したため、スキップして Day 13 をやりました
問題文はこちら
実装したノートブックはこちら
セットアップ
Kino AOC をインストールします
行列演算をするため、 Nx もインストールします
Mix.install([
{:kino_aoc, "~> 0.1"},
{:nx, "~> 0.9.2"}
])
Kino AOC の使い方はこちらを参照
入力の取得
"Advent of Code Helper" スマートセルを追加し、 Day 13 の入力を取得します
私の答え
私の答えです。
折りたたんでおきます。
▶を押して開いてください。
Part 1
回答
まず問題を理解するために一つの例で考えてみます
以下のような行列を用意します
block =
Nx.tensor([
[1, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 1, 1, 0, 1]
])
実行結果
#Nx.Tensor<
s32[7][7]
[
[1, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 1, 1, 0, 1]
]
>
行列の行数と列数を取得します
{num_rows, num_cols} = Nx.shape(block)
実行結果
{7, 7}
まず、行について考えます
7 行を 0 行目と 1 行目の間で分けた場合、上 1 行、下 6 行に分かれます
鏡写しになっているかどうかをチェックする場合、上下のうち少ない方の行数分比較すれば良いことになります
鏡写しで同じになるかを判定するため、下側を上下に反転させます
これを 0 行目から 5 行目までの 6 回繰り返します
0..(num_rows - 2)
|> Enum.map(fn row_index ->
range = min(row_index + 1, num_rows - row_index - 1)
{
Nx.slice_along_axis(block, row_index - range + 1, range, axis: 0),
Nx.slice_along_axis(block, row_index + 1, range, axis: 0) |> Nx.reverse(axes: [0])
}
end)
実行結果
[
{#Nx.Tensor<
s32[1][7]
[
[1, 0, 0, 0, 0, 1, 0]
]
>,
#Nx.Tensor<
s32[1][7]
[
[1, 0, 0, 0, 0, 1, 1]
]
>},
{#Nx.Tensor<
s32[2][7]
[
[1, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1]
]
>,
#Nx.Tensor<
s32[2][7]
[
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0]
]
>},
...
]
Nx.equal で上下の各位置が同じ値であれば 1 、違う値であれば 0 とします
全ての位置が 1 の行を探索します
0..(num_rows - 2)
|> Enum.find(fn row_index ->
range = min(row_index + 1, num_rows - row_index - 1)
Nx.equal(
Nx.slice_along_axis(block, row_index - range + 1, range, axis: 0),
Nx.slice_along_axis(block, row_index + 1, range, axis: 0) |> Nx.reverse(axes: [0])
)
|> Nx.all()
|> Nx.to_number()
|> Kernel.==(1)
end)
実行結果
nil
結果が nil なので、行で鏡写しになっているものは存在しませんでした
同じことを列で行います
0..(num_cols - 2)
|> Enum.find(fn col_index ->
range = min(col_index + 1, num_cols - col_index - 1)
Nx.equal(
Nx.slice_along_axis(block, col_index - range + 1, range, axis: 1),
Nx.slice_along_axis(block, col_index + 1, range, axis: 1) |> Nx.reverse(axes: [1])
)
|> Nx.all()
|> Nx.to_number()
|> Kernel.==(1)
end)
実行結果
2
2 列目と 3 列目の間で鏡写しになっています
行方向は axis: 0 で列方向は axis: 1 なので、以下のようにすれば行列を繰り返しで処理できます
0..1
|> Enum.map(fn axis ->
num = Nx.shape(block) |> elem(axis)
0..(num - 2)
|> Enum.find(fn index ->
range = min(index + 1, num - index - 1)
Nx.equal(
Nx.slice_along_axis(block, index - range + 1, range, axis: axis),
Nx.slice_along_axis(block, index + 1, range, axis: axis) |> Nx.reverse(axes: [axis])
)
|> Nx.all()
|> Nx.to_number()
|> Kernel.==(1)
end)
end)
実行結果
[nil, 2]
あとはこれを全ての入力に対して行えば良いだけです
入力を全て行列に変換します
blocks =
puzzle_input
|> String.split("\n\n")
|> Enum.map(fn block ->
block
|> String.split("\n")
|> Enum.map(fn row ->
String.codepoints(row)
|> Enum.map(fn tile -> if tile == "#", do: 1, else: 0 end)
end)
|> Nx.tensor()
end)
実行結果
[
#Nx.Tensor<
s32[7][7]
[
[1, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 1, 1, 0, 1]
]
>,
#Nx.Tensor<
s32[15][15]
[
[0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1],
[0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 1, 0, ...],
...
]
>,
...
]
全ての入力について鏡写しの行番号、列番号を取得し、行は 100 倍、列はそのまま足し合わせます
blocks
|> Enum.map(fn block ->
0..1
|> Enum.map(fn axis ->
num = Nx.shape(block) |> elem(axis)
0..(num - 2)
|> Enum.find(fn index ->
range = min(index + 1, num - index - 1)
Nx.equal(
Nx.slice_along_axis(block, index - range + 1, range, axis: axis),
Nx.slice_along_axis(block, index + 1, range, axis: axis) |> Nx.reverse(axes: [axis])
)
|> Nx.all()
|> Nx.to_number()
|> Kernel.==(1)
end)
|> then(fn index -> if is_nil(index), do: 0, else: index + 1 end)
|> then(fn num -> if axis == 0, do: num * 100, else: num end)
end)
|> Enum.sum()
end)
|> Enum.sum()
Part 2
回答
1ヶ所だけ反転して鏡写しになる = 鏡写しで異なっている箇所が 1 つだけ存在するということです
Nx.not_equal で異なっている位置だけ 1 にして、異なった箇所の合計が 1 の場合、該当します
Part 1 の Nx.equal を Nx.not_equal に変えて、 Nx.all を Nx.sum に変えただけで解けました
blocks
|> Enum.map(fn block ->
0..1
|> Enum.map(fn axis ->
num = Nx.shape(block) |> elem(axis)
0..(num - 2)
|> Enum.find(fn index ->
range = min(index + 1, num - index - 1)
Nx.not_equal(
Nx.slice_along_axis(block, index - range + 1, range, axis: axis),
Nx.slice_along_axis(block, index + 1, range, axis: axis) |> Nx.reverse(axes: [axis])
)
|> Nx.sum()
|> Nx.to_number()
|> Kernel.==(1)
end)
|> then(fn index -> if is_nil(index), do: 0, else: index + 1 end)
|> then(fn num -> if axis == 0, do: num * 100, else: num end)
end)
|> Enum.sum()
end)
|> Enum.sum()
まとめ
Nx の行列演算でとてもキレイに解けました
気持ちが良いですね