[Advent of Code 2024] Day 8: Resonant Collinearity

この記事は、[mae616 Advent of Code Advent Calendar 2024](https://qiita.com/advent-calendar/2024/mae616) の8日目の記事です。

https://qiita.com/advent-calendar/2024/mae616

このアドベントカレンダーは皆勤賞のQiitaくんのぬいぐるみに惹かれて挑戦している大変ゆるい挑戦のものです。そんな感じで読んでいただければ幸いです。

一週間を超えて続いてますね٩( ᐛ )و
コツコツ続ければぬいぐるみいけるかとホクホクしています٩( ᐛ )و

---

前の日: [[Advent of Code 2024] Day 7: Bridge Repair](https://qiita.com/mae616/items/b1b0543695b766580c1d)
次の日: [[Advent of Code 2024] Day 9: Disk Fragmenter](https://qiita.com/mae616/items/740ec17c7b8e7d60271b)

# 今日のお題

https://adventofcode.com/

https://adventofcode.com/2024/day/8

# 8日目の物語
> ■ 8日目: 共鳴的な共線性
> あなたたちは、『極秘のイースターバニー施設の屋上』にいます。

これがまたAdvent of Code 2016と繋がっているのかな。
なんか今日はタイトルが難しいですね。"共鳴的な共線性"って何だろう。

> 歴史学者たちがそれぞれの仕事をしている間、あなたはおなじみの巨大なアンテナを見つめます。驚くべきことに、それはイースターバニーブランドの「模倣されたいまいちチョコレート」をクリスマスギフトとして購入する確率を0.1％増加させる信号を発信するように再構成されているようです！考えられません！

んー"イースターバニーブランドの「模倣されたいまいちチョコレート」"て何だろうと思ったら、"あまり魅力的でないチョコレートが「イースターバニー」ブランド名のもとで販売されていることを皮肉的に示唆している表現"らしく、要は『クリスマスプレゼントとして渡すにはちょっと魅力に欠ける商品』を買う人を増やすアンテナらしいですね。

> 街中をスキャンすると、実は同様のアンテナがたくさんあることが分かります。各アンテナは、小文字のアルファベット、大文字のアルファベット、または数字で示された特定の周波数にチューニングされています。あなたはこれらのアンテナの地図（パズルの入力）を作成します。

まあ、「イマイチなものをクリスマスギフト向けに販売してるお店が多いよ！」てことなんですかね ꉂꉂ( ᐛ )

# 1問目
例:
```
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
```

ええと、`.` 以外の文字が書かれているのがアンテナのようですね。で、書いてある文字(小文字のアルファベット、大文字のアルファベット、または数字)は同じ周波数なので共鳴し合う、ってことですかね。

んー。ちょっと問題文が難しいですね。ちょっと解読しますね。

...

要はアンテナ📡なので何かの特定の条件がそろうと、何らかの現象を引き起こすようです。

*現象1:*
* 条件: 同じ周波数(要は文字)のアンテナが2つ直線上にある時
```
..........
..........
..........
....a.....
..........
.....a....
..........
..........
..........
..........
```
* 現象: (文がちょっと難しいので誤読の可能性がありますが...) 2つのアンテナと等間隔を開けた両端にアンチノード(アンテナの共鳴において電磁波の振動が最大となる位置) `#` を作ります
```
..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........
```
*現象2:*
* 条件: *現象1* にさらに同じ周波数の第3のアンテナを追加数する
```
..........
..........
..........
....a.....
........a.
.....a....
..........
..........
..........
..........
```
* 現象: それぞれの直線上の2つのアンテナと等間隔を開けた両端にアンチノード`#` を作ります（ただしこのケースの場合は2つのアンチノードはマップ外になるため、2つだけ追加される）

実際は:
```
..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........
```
で、要は
```
..........
...#......
#.........
....a......#.
........a....
.....a......#
..#.......
......#...
..........
..........
```
マップ外に2つアンチノードは追加されるようですね（でもマップ外なので数えられない）

※ 異なる周波数のアンテナはアンチノードを作りません。`A` と `a` は異なる周波数とみなされます。しかし、アンチノードはアンテナが存在する位置に現れることがあります。

```
..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......A...
..........
..........
```
`a` のアンチノードが `A` の位置にできますね。

ええと、最初の例に戻り、その例で作られるアンチノードは下記になります。
ただ実際は `A` に1つアンチノードが重なっています。
```
......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....A..... (ここのAに注目。0のアンチノードでもある)
...#........
#......#....
........A...
.........A..
..........#.
..........#.
```

そのため、（`A` と重なっているものも含め）`14` のアンチノードが存在します。
マップの範囲内でアンチノードが存在するユニークな位置は何箇所ありますか？

...てことみたいです。
問題の解読に結構時間をかけちゃいました ꉂꉂ( ᐛ )

## 解いたコード
これあれかな。直線上ってとこに一次関数の知識が必要なのかな？
んー。ちょっと調べてみましょう。

https://alpha-katekyo.jp/tips/tips174/

んーこれでいけそう。

y = ax + b
で2点の xの差 と yの差で下記の式に当てはめる
a = (yの差) / (xの差)

で a がもとまるので、
どちらか 1点の座標 と 求めたa で bを出す。

(yの座標) = (求めたa) * (xの座標) + b
だから
(yの座標) - {(求めたa) * (xの座標) } = b
かな。

んー。算数や数学いつかはできるようになりたいですね。
大学で挫折してすっかり苦手になってしまいました ꉂꉂ( ᐛ )

ではいってみましょう。
```js: ./day8_1/main.js
function main(input) {
  const args = input.split("\n");

  const map = [];
  for (const arg of args) {
    if (arg === "") continue;
    map.push(arg.split(""));
  }
  const h = map.length;
  const w = map[0].length;

  // 読み取り
  const antennas = {};
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (map[i][j] === ".") continue;

      if (map[i][j] in antennas) {
        antennas[map[i][j]].push([i, j]);
      } else {
        antennas[map[i][j]] = [[i, j]];
      }
    }
  }

  // アンチノードを探す
  const existing = new Set();
  for (const s of Object.keys(antennas)) {
    antinode(antennas[s], existing, h, w);
  }

  // for (const exist of existing) {
  //   const [y, x] = exist.split(",").map(Number);
  //   map[y][x] = "#";
  // }
  // console.table(map);

  console.log(existing.size);
}

function antinode(aryAntenna, existing, h, w) {
  const node = (x, a, b) => {
    let y = Math.round(a * x + b); // 端数は四捨五入

    if (0 <= x && x < w && 0 <= y && y < h) {
      existing.add(`${y},${x}`);
    }
  };

  for (let i = 0; i < aryAntenna.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      const y1 = aryAntenna[j][0];
      const x1 = aryAntenna[j][1];
      const y2 = aryAntenna[i][0];
      const x2 = aryAntenna[i][1];

      const a = (y2 - y1) / (x2 - x1);
      const b = y1 - a * x1;

      node(x1 - (x2 - x1), a, b); // small
      node(x2 + (x2 - x1), a, b); // large
    }
  }
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
y を求める際に四捨五入してなくて、すごいハマってしまいました ꉂꉂ( ᐛ )
何でしょう。コンピュータの誤差なのかな。ちょっとよくわかってないです。

https://github.com/mae616/adventOfCode2024/tree/main/day8_1

下記で実行できます。
```zsh: zsh
cd day8_1
node main.js
```

# 2問目
歴史学者に計算の間違いを指摘されたらしいですね ꉂꉂ( ᐛ )
要は、2つ直線上に並んだとき、両端にアンチノードができるのでなく、同じ直線上にマップ内でいる間は等間隔 + アンテナのところに、アンチノードができるみたいですね。

下記の例だとアンチノードが `9` 個。
```
T....#....
...T......
.T....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........
```

1問目の例だと `34` 個になるらしいですね。
```
##....#....#
.#.#....0...
..#.#0....#.
..##...0....
....0....#..
.#...#A....#
...#..#.....
#....#.#....
..#.....A...
....#....A..
.#........#.
...#......##
```

んー。ちょっと変えるだけでいけるかな？
やってみましょう٩( ᐛ )و

## 解いたコード
```js: ./day8_2/main.js
function main(input) {
  const args = input.split("\n");

  const map = [];
  for (const arg of args) {
    if (arg === "") continue;
    map.push(arg.split(""));
  }
  const h = map.length;
  const w = map[0].length;

  const existing = new Set();

  // 読み取り
  const antennas = {};
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (map[i][j] === ".") continue;

      if (map[i][j] in antennas) {
        antennas[map[i][j]].push([i, j]);
      } else {
        antennas[map[i][j]] = [[i, j]];
      }
      existing.add(`${i},${j}`);
    }
  }

  // アンチノードを探す
  for (const s of Object.keys(antennas)) {
    antinode(antennas[s], existing, h, w);
  }

  // for (const exist of existing) {
  //   const [y, x] = exist.split(",").map(Number);
  //   map[y][x] = "#";
  // }
  // console.table(map);

  console.log(existing.size);
}

function antinode(aryAntenna, existing, h, w) {
  const node = (x, next, a, b) => {
    let y = 0;
    while (true) {
      x = next(x);
      y = Math.round(a * x + b); // 端数は四捨五入

      if (x < 0 || w <= x || y < 0 || h <= y) {
        return;
      }
      existing.add(`${y},${x}`);
    }
  };

  for (let i = 0; i < aryAntenna.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      const y1 = aryAntenna[j][0];
      const x1 = aryAntenna[j][1];
      const y2 = aryAntenna[i][0];
      const x2 = aryAntenna[i][1];

      const a = (y2 - y1) / (x2 - x1);
      const b = y1 - a * x1;

      node(x1, (x) => x - (x2 - x1), a, b); // small
      node(x2, (x) => x + (x2 - x1), a, b); // large
    }
  }
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```

https://github.com/mae616/adventOfCode2024/tree/main/day8_2

今日は苦戦してしまいました ꉂꉂ( ᐛ )
本当にもっと賢くなりたいですね。勉強することがたくさんです ꉂꉂ( ᐛ )

今日は終わり。
お疲れさまです٩( ᐛ )و

---

今日の海外の人は...
https://www.reddit.com/r/adventofcode/
お、これは多分、「問題は何をいってるんだ？」となった仲間がいる感じですかね ꉂꉂ( ᐛ )

では、また明日。