[Advent of Code 2024] Day 14: Restroom Redoubt

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

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

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

------

前の日: [[Advent of Code 2024] Day 13: Claw Contraption](https://qiita.com/mae616/items/aa4619b1b71d52ba2df4)

# 今日のお題

https://adventofcode.com/

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

# 14日目の物語
> ■ 14日目：トイレの要塞
> 歴史学者の一人がトイレに行きたがっている。幸いなことに、まだ行ったことのない場所リストの中にトイレが近くにあることがわかっているので、全員一緒に『イースターバニー本部』のロビーに瞬時に転送される。
>
> しかし、残念ながら『イースターバニー本部』は前回の訪問後、トイレのセキュリティをまた「強化」しているようだ。トイレの外にはロボットがうじゃうじゃいる！

『イースターバニー本部』は advent of Code 2016 で訪れてるみたいですね。
トイレのセキュリティ...なんかすごいですね ꉂꉂ( ᐛ )

> 歴史学者を無事にトイレに送り届けるためには、ロボットが未来にどこにいるかを予測する方法が必要だ。幸い、ロボットたちはタイルの床の上を予測可能な直線で動いているようだ。
>
> ロボットたちの現在位置( `p` )と速度( `v` )をリストにまとめる（パズルの入力）。

よし。レッツゴー！٩( ᐛ )و

# 1問目
> 例:
> ```
> p=0,4 v=3,-3
> p=6,3 v=-1,-3
> p=10,3 v=-1,2
> p=2,0 v=2,-1
> p=0,0 v=1,3
> p=3,0 v=-2,-2
> p=7,6 v=-1,-3
> p=3,0 v=-1,-2
> p=9,3 v=2,3
> p=7,3 v=-1,2
> p=2,4 v=2,-3
> p=9,5 v=-3,-3
> ```
>
> 各ロボットの位置は `p=x,y` で示され、`x` はロボットが左壁から何タイル離れているか、`y` は上壁から何タイル離れているかを表している（上から見たとき）。
> つまり、`p=0,0` の位置はロボットが左上隅にいることを意味する。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/f94abf41-9858-8926-0ef1-58b3c1c3b1e8.png" width=400>

> 各ロボットの速度は `v=x,y` で示され、`x` と `y` は秒あたりの移動タイル数で表される。`x` が正の数ならロボットは `右` に動き、`y` が正の数ならロボットは `下` に動く。例えば、`v=1,-2` という速度は、ロボットが `1` 秒ごとに `右` に `1` タイル、`上` に `2` タイル動くことを意味する。

ここからロビーの広さの話になります。

> 実際のトイレの外にいるロボットたちは、幅 `101` タイル、高さ `103` タイルの空間にいる（上から見たとき）。しかし、この例ではロボットたちは幅 `11` タイル、高さ `7` タイルの空間にいる。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/12f6642a-d72a-9314-9d48-50dba20f30f8.png" width=500>

ここからロボットの動きの話です。

> ロボットたちはお互いを上や下でうまく交差して動ける。なので同じタイルに重なってもお互いに干渉しない。この例では、各タイルにいるロボットの数は次のように見える。
> 
> ```
> 1.12....... (11 列)
> ...........
> ...........
> ......11.11
> 1.1........
> .........1.
> .......1...
> (7 行)
> ```
※ `p=3,0` にはロボットが `2` 体いる。それ以外は `1` 体。

> これらのロボットには最大のトイレセキュリティを確保するためのユニークな機能がある。それは、<INS>テレポートができる</INS>ということだ。ロボットがいる空間の端にぶつかると、ロボットはそのまま反対側にテレポートし、実質的に端を越えて回り込む。
>
> 例えば、ロボット `p=2,4` `v=2,-3` は最初の数秒間でこんな動きをする：
> ```
> Initial state:
> ...........
> ...........
> ...........
> ...........
> ..1........
> ...........
> ...........
> ```
初期位置 `p=2,4`

> ```
> After 1 second:
> ...........
> ....1......
> ...........
> ...........
> ...........
> ...........
> ...........
> ```
1秒後
初期位置 `p=2,4` から `v=2,-3` (右 `2` , 上 `3` ) 移動
移動位置 `p=4,1`

> ```
> After 2 seconds:
> ...........
> ...........
> ...........
> ...........
> ...........
> ......1....
> ...........
> ```
2秒後
1秒後位置 `p=4,1` から `v=2,-3` (右 `2` , 上 `3` ) 移動
上へ `2` 移動したら、<INS>上の端を超え一番下( `y = 6` )にテレポート</INS>。 上へ `3` 移動なので、さらに `1` 上に移動
移動位置 `p=6,5`

> ```
> After 3 seconds:
> ...........
> ...........
> ........1..
> ...........
> ...........
> ...........
> ...........
> ```
3秒後
2秒後位置 `p=6,5` から `v=2,-3` (右 `2` , 上 `3` ) 移動
移動位置 `p=8,2`

> ```
> After 4 seconds:
> ...........
> ...........
> ...........
> ...........
> ...........
> ...........
> ..........1
> ```
4秒後
3秒後位置 `p=8,2` から `v=2,-3` (右 `2` , 上 `3` ) 移動
上へ `3` 移動したら、<INS>上の端を超え一番下( `y = 6` )にテレポート</INS>
移動位置 `p=10,6`

> ```
> After 5 seconds:
> ...........
> ...........
> ...........
> .1.........
> ...........
> ...........
> ...........
> ```
5秒後
4秒後位置 `p=10,6` から `v=2,-3` (右 `2` , 上 `3` ) 移動
右へ `1` 移動したら、<INS>右の端を超え一番左( `x = 0` )にテレポート</INS>。 右へ `2` 移動なので、さらに `1` 右に移動
移動位置 `p=1,3`

> 歴史学者はこれ以上待てないので、ロボットを長時間シミュレートする必要はありません。`100` 秒後、ロボットたちはどこにいるでしょうか？

> 上の例では、`100` 秒が経過した後の各タイルにいるロボットの数はこんな感じになります:
> ```
> ......2..1.
> ...........
> 1..........
> .11........
> .....1.....
> ...12......
> .1....1....
> ```
>
> 安全なエリアを決めるためには、`100` 秒後のロビーを4等分し各エリアにいるロボットの数を数えます。<INS>ちょうど中央（水平または垂直）にいるロボットはどのエリアにも含まれない</INS>ので、関連するロボットは次の通りです:
> ```
> ..... 2..1.
> ..... .....
> 1.... .....
>            
> ..... .....
> ...12 .....
> .1... 1....
> ```
> この例では、4等分した各エリアにはそれぞれ `1`、`3 = (2 + 1)`、`4 = (1 + 1 + 2)`、`1` 体のロボットがいます。
> それらを掛け合わせると、安全係数は`12` ( `= 1 * 3 * 4 * 1` ) になります。
>
> `101` タイルの幅と `103` タイルの高さを持つ空間で、リスト内のロボットの動きを予測してください。
> `100` 秒経過した後の安全係数は何になりますか？

さて、やってみましょう٩( ᐛ )و

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

  const w = 101;
  const h = 103;
  const afterSeconds = 100;

  const wh = Math.trunc(w / 2);
  const hh = Math.trunc(h / 2);

  const sumArea = [
    { sum: 0, start: { x: 0, y: 0 }, end: { x: wh - 1, y: hh - 1 } },
    { sum: 0, start: { x: wh + 1, y: 0 }, end: { x: w - 1, y: hh - 1 } },
    { sum: 0, start: { x: 0, y: hh + 1 }, end: { x: wh - 1, y: h - 1 } },
    { sum: 0, start: { x: wh + 1, y: hh + 1 }, end: { x: w - 1, y: h - 1 } },
  ];

  // 読み込み
  const robots = [];
  for (const arg of args) {
    if (arg === "") continue;
    const [px, py, mx, my] = arg.match(/-?\d+/g).map(Number);
    robots.push({
      position: { x: px, y: py },
      move: { x: mx, y: my },
    });
  }

  // 安全係数を求める
  for (const robot of robots) {
    let x = (robot.position.x + robot.move.x * afterSeconds) % w;
    let y = (robot.position.y + robot.move.y * afterSeconds) % h;
    if (x < 0) x += w;
    if (y < 0) y += h;

    for (const area of sumArea) {
      if (
        area.start.x <= x &&
        x <= area.end.x &&
        area.start.y <= y &&
        y <= area.end.y
      ) {
        area.sum++;
      }
    }
  }
  console.log(sumArea.reduce((prev, current) => prev * current.sum, 1));
}

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

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

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

# 2問目
> トイレ休憩中に、誰かがこれらのロボットが北極で作られ使われているロボットと非常に似ていることに気づきます。もし同じタイプのロボットなら、ハードコードされたイースターエッグがあるはずです。それは、極めて稀に、ほとんどのロボットがクリスマスツリーの形に並ぶというものです。
> 
> ロボットがイースターエッグを表示するために、最短で何秒が経過する必要がありますか？

ん？クリスマスツリーの形に並ぶの？
あれ。これどうやったら解いたらいいんだろ ꉂꉂ( ᐛ )

クリスマスツリーの形ってどんな形のクリスマスツリーだ？ ꉂꉂ( ᐛ )

## クリスマスツリーを確認するコード
もうわからないからマンパワーです ꉂꉂ( ᐛ )

```zsh: zsh
$ npm init -y
$ npm install clivas
$ npm install keypress
```
しました。

```js: ./day14_2/main.js
const clivas = require("clivas");
const keypress = require("keypress");

keypress(process.stdin);
process.stdin.setRawMode(true);
process.stdin.resume();

const w = 101;
const h = 103;
clivas.cursor(false);
clivas.pin(h + 1);

function main(input) {
  const args = input.split("\n");

  let afterSeconds = 110607;

  // 読み込み
  const robots = [];
  for (const arg of args) {
    if (arg === "") continue;
    const [px, py, mx, my] = arg.match(/-?\d+/g).map(Number);
    robots.push({
      position: { x: px, y: py },
      move: { x: mx, y: my },
    });
  }

  const draw = () => {
    clivas.clear();

    const grids = new Array(h)
      .fill()
      .map(() => new Array(w).fill().map(() => "{2}"));
    for (const robot of robots) {
      let x = (robot.position.x + robot.move.x * afterSeconds) % w;
      let y = (robot.position.y + robot.move.y * afterSeconds) % h;
      if (x < 0) x += w;
      if (y < 0) y += h;
      grids[y][x] = "{2+green:■}";
    }
    for (const grid of grids) {
      clivas.line(grid.join(""));
    }
    clivas.line(`seconds: ${afterSeconds}`);
  };
  // キーボードでのキーを押した時
  process.stdin.on("keypress", (ch, key) => {
    // ctrl + c でゲームを終了させられるようにする
    if (key && key.ctrl && key.name === "c") {
      process.exit();
    }
    if (key.name === "up") {
      // move up
      afterSeconds += 100;
    }
    if (key.name === "left") {
      // move left
      afterSeconds--;
    }
    if (key.name === "down") {
      // move down
      afterSeconds -= 100;
    }
    if (key.name === "right") {
      // move right
      afterSeconds++;
    }
    draw();
  });

  draw();
}

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

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

下記、で実行できます。

```zsh
$ npm install
$ cd day14_2
$ node main.js
```

ひたすら → や ↑ キーを押しました。

![CleanShot 2024-12-16 at 17.33.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/f93b47de-07e0-3153-e515-830c95d44182.png)

これが出てくるみたいです ꉂꉂ( ᐛ )

ちなみにこの秒数を入れてみたのですが違いました。

## 解いたコード
クリスマスツリーが出てくる時と同じ配置になる時を求めました。

```js: ./day14_2_find/main.js
function main(input) {
  const args = input.split("\n");

  const w = 101;
  const h = 103;
  let afterSeconds = 1;
  let exampleTreeSeconds = 110607;

  // 読み込み
  const robots = [];
  for (const arg of args) {
    if (arg === "") continue;
    const [px, py, mx, my] = arg.match(/-?\d+/g).map(Number);
    robots.push({
      position: { x: px, y: py },
      move: { x: mx, y: my },
    });
  }

  const draw = (second) => {
    const grids = new Array(h)
      .fill()
      .map(() => new Array(w).fill().map(() => "."));
    for (const robot of robots) {
      let x = (robot.position.x + robot.move.x * second) % w;
      let y = (robot.position.y + robot.move.y * second) % h;
      if (x < 0) x += w;
      if (y < 0) y += h;
      grids[y][x] = "■";
    }

    const s = [];
    for (const grid of grids) {
      s.push(grid.join(""));
    }
    return s;
  };

  const isTree = draw(exampleTreeSeconds);
  let view = [];
  while (view.length === 0 || view.join("") !== isTree.join("")) {
    view = draw(afterSeconds);
    afterSeconds++;
  }
  console.log(afterSeconds - 1);
}

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

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

お疲れさまです٩( ᐛ )و

---

まだまだ海外の人に置いてかれています
https://www.reddit.com/r/adventofcode/
2問目がみんなびっくりしたみたいだけど、面白くて好評のようですね٩( ᐛ )و
2問目面白かったです ٩( ᐛ )و
(賛否はあるようです)

では、また٩( ᐛ )و