Advent of code 2023 Day 13 Part 1 & Part 2 を Livebook で楽しむ

## はじめに

Advent of code 2023 Day 13 の Part 1 と Part 2 を解きます

去年、 Day 12 が難しくて挫折したため、スキップして Day 13 をやりました

問題文はこちら

https://adventofcode.com/2023/day/13

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

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2023/2023_day13_part1.livemd

https://github.com/RyoWakabayashi/elixir-learning/blob/main/livebooks/aoc/2023/2023_day13_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 13 の入力を取得します

![スクリーンショット 2024-12-03 22.20.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1485835/3665f83e-377c-4d7d-1c75-c68190af5913.png)

## 私の答え

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

### Part 1

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

まず問題を理解するために一つの例で考えてみます

以下のような行列を用意します

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

実行結果

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

行列の行数と列数を取得します

```elixir
{num_rows, num_cols} = Nx.shape(block)
```

実行結果

```elixir
{7, 7}
```

まず、行について考えます

7 行を 0 行目と 1 行目の間で分けた場合、上 1 行、下 6 行に分かれます

鏡写しになっているかどうかをチェックする場合、上下のうち少ない方の行数分比較すれば良いことになります

鏡写しで同じになるかを判定するため、下側を上下に反転させます

これを 0 行目から 5 行目までの 6 回繰り返します

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

実行結果

```elixir
[
  {#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 の行を探索します

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

実行結果

```elixir
nil
```

結果が `nil` なので、行で鏡写しになっているものは存在しませんでした

同じことを列で行います

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

実行結果

```elixir
2
```

2 列目と 3 列目の間で鏡写しになっています

行方向は `axis: 0` で列方向は `axis: 1` なので、以下のようにすれば行列を繰り返しで処理できます

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

実行結果

```elixir
[nil, 2]
```

あとはこれを全ての入力に対して行えば良いだけです

入力を全て行列に変換します

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

実行結果

```elixir
[
  #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 倍、列はそのまま足し合わせます

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

</details>

### Part 2

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

1ヶ所だけ反転して鏡写しになる = 鏡写しで異なっている箇所が 1 つだけ存在するということです

`Nx.not_equal` で異なっている位置だけ 1 にして、異なった箇所の合計が 1 の場合、該当します

Part 1 の `Nx.equal` を `Nx.not_equal` に変えて、 `Nx.all` を `Nx.sum` に変えただけで解けました

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

</details>

## まとめ

Nx の行列演算でとてもキレイに解けました

気持ちが良いですね