[Advent of Code 2024] Day 6: Guard Gallivant

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

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

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

何かの絵ができるんですかね。まだよくわからないですね٩( ᐛ )و

![CleanShot 2024-12-06 at 15.00.36.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/f6c37939-024d-e114-83c7-018c6943d182.png)

---

前の日: [[Advent of Code 2024] Day 6: Guard Gallivant](https://qiita.com/mae616/items/6968f78a85acc36ca361)

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

# 今日のお題

https://adventofcode.com/

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

# 6日目の物語
> ■ 6日目: ガードの見回り
> 歴史学者たちはまたデバイスを使って、今度は『1518年の北極圏プロトタイプスーツ製造ラボ』にみんなを連れて行ってくれることに！歴史に直接アクセスできるって、歴史学者たちは本当に便利なんだな。

テレポート装置かと思ったらタイムトラベルもできるですね٩( ᐛ )و
歴史学者って何かと思ったら、いろんな歴史(年の場所)に行けるんですね。便利ですね。

> でも、タイムパラドックスには気をつけなきゃいけないから、1518年の人々には近づかないようにするのが大事だね。歴史学者たちが主任歴史学者を探している。でも、残念なことに、『ラボ』の今いるエリアには1人の警備員が見回りをしているみたい。

おお、タイムトラベルによくあるタイムパラドックスですね。素晴らしい物語です。

> もしかしたら、警備員がどこに行くか予測できるかもしれないから、歴史学者たちが安全に探せるようにしてあげられるかも？
> まずは、周辺の地図（パズルの入力）を作成するところから始めよう。

これは、自分の好きな graph 問題ですかね٩( ᐛ )و

# 1問目
例:
```
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
```
地図上の `^` が警備員を表していてマークの向きで進行方向を表しています(例は上を向いている)。障害物(箱や机など)は `#` で表されています。
1518年のラボの警備員は非常に厳格な見回りプロトコルに従っており、以下の手順を繰り返します:
* 前に何かがある場合、右に90度回転する
* それ以外の場合、1歩前進する

　
つまり、例の場合、警備員は次の動きをします。
(1) 警備員は、障害物にぶつかるまで上に進みます
```
....#.....
....^....#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...
```
(2) 障害物が前にあるため、ガードは右に回転し、新しい向きで直進を続けます
```
....#.....
........>#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...
```
(3) 別の障害物にぶつかり、ガードは再び右に回転し、下に進みます
```
....#.....
.........#
..........
..#.......
.......#..
..........
.#......v.
........#.
#.........
......#...
```
(4) 同じようなプロセスがしばらく続き、最終的に警備員は地図に表示されたエリアを出て行きます
```
....#.....
.........#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#v..
```
この例では、警備員は地図上で `41` の異なる位置を訪れることになります。

警備員の進行ルートを予測して、警備員が地図に表示されたエリアを離れる前に、いくつの異なる位置を訪れるでしょうか？

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

  const graph = [];
  for (const arg of args) {
    if (arg === "") continue;
    graph.push(arg.split(""));
  }

  const h = graph.length;
  const w = graph[0].length;

  const move = {
    top: { mark: "^", x: 0, y: -1, check: (x, y) => y > 0, turn: "right" },
    right: { mark: ">", x: 1, y: 0, check: (x, y) => x < w - 1, turn: "down" },
    down: { mark: "v", x: 0, y: 1, check: (x, y) => y < h - 1, turn: "left" },
    left: { mark: "<", x: -1, y: 0, check: (x, y) => x > 0, turn: "top" },
  };

  // ex. position = { x: 0, y: 0, direction: "down" };
  const position = (function () {
    for (let y = 0; y < h; y++) {
      for (let x = 0; x < w; x++) {
        if (graph[y][x] === "^") {
          return { x, y, direction: "top" };
        } else if (graph[y][x] === ">") {
          return { x, y, direction: "right" };
        } else if (graph[y][x] === "v") {
          return { x, y, direction: "down" };
        } else if (graph[y][x] === "<") {
          return { x, y, direction: "left" };
        }
      }
    }
  })();

  let count = 1;
  while (move[position.direction].check(position.x, position.y)) {
    if (
      graph[position.y][position.x] !== "X" &&
      graph[position.y][position.x] !== "#"
    ) {
      graph[position.y][position.x] = "X";
      count++;
    }

    const next = move[position.direction];
    const tempX = position.x + next.x;
    const tempY = position.y + next.y;

    if (graph[tempY][tempX] === "#") {
      position.direction = next.turn;
    } else {
      position.x = tempX;
      position.y = tempY;
    }
  }
  console.log(count);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
ありゃ。`move` と `position` のデータ構造だけ書いたらGitHub Copilotがほとんど書いてくれましたね。便利ですね٩( ᐛ )و

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

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

# 2問目
障害物を1つ増やすことができる。
それによって警備員の巡回をループさせられる障害物の置き場所は何個あるか？て問題のようですね。
例:
```
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
```
これでは `6` 箇所、警備員の巡回をループさせられる障害物の置き場所があるみたいですね。

難しいですね ꉂꉂ( ᐛ )
とりあえず総当たりしてみますかね ꉂꉂ( ᐛ )

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

  const graph = [];
  for (const arg of args) {
    if (arg === "") continue;
    graph.push(arg.split(""));
  }

  const h = graph.length;
  const w = graph[0].length;

  const move = {
    top: { mark: "^", x: 0, y: -1, check: (x, y) => y > 0, turn: "right" },
    right: { mark: ">", x: 1, y: 0, check: (x, y) => x < w - 1, turn: "down" },
    down: { mark: "v", x: 0, y: 1, check: (x, y) => y < h - 1, turn: "left" },
    left: { mark: "<", x: -1, y: 0, check: (x, y) => x > 0, turn: "top" },
  };

  // ex. position = { x: 0, y: 0, direction: "down" };
  const position = (function () {
    for (let y = 0; y < h; y++) {
      for (let x = 0; x < w; x++) {
        if (graph[y][x] === "^") {
          return { x, y, direction: "top" };
        } else if (graph[y][x] === ">") {
          return { x, y, direction: "right" };
        } else if (graph[y][x] === "v") {
          return { x, y, direction: "down" };
        } else if (graph[y][x] === "<") {
          return { x, y, direction: "left" };
        }
      }
    }
  })();

  const checkLoop = (graph, position) => {
    let loopCount = 0;
    let moveCount = 0;
    while (move[position.direction].check(position.x, position.y)) {
      if (graph[position.y][position.x] === "X") {
        if (moveCount < loopCount) {
          return true;
        }
        loopCount++;
      } else {
        loopCount = 0;
      }
      if (
        graph[position.y][position.x] !== "X" &&
        graph[position.y][position.x] !== "#" &&
        graph[position.y][position.x] !== "O"
      ) {
        graph[position.y][position.x] = "X";
        moveCount++;
      }

      const next = move[position.direction];
      const tempX = position.x + next.x;
      const tempY = position.y + next.y;

      if (graph[tempY][tempX] === "#" || graph[tempY][tempX] === "O") {
        position.direction = next.turn;
      } else {
        position.x = tempX;
        position.y = tempY;
      }
    }
    return false;
  };

  let count = 0;
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (graph[y][x] !== ".") continue;
      const tempGraph = structuredClone(graph);
      const tempPosition = structuredClone(position);
      tempGraph[y][x] = "O";
      if (checkLoop(tempGraph, tempPosition)) {
        count++;
      }
    }
  }
  console.log(count);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
総当たりだから実行時間かかりますね ꉂꉂ( ᐛ )
もっと賢くやらなきゃ、ですね。今後、勉強します٩( ᐛ )و

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

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

---

今日の海外の人は
https://www.reddit.com/r/adventofcode/
んー。ちょっと英語がわからないので、翻訳頼りなのですが、どうも総当たり仲間がいそう٩( ᐛ )و

ではまた明日。