[Advent of Code 2024] Day 4: Ceres Search

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

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

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

---

前の日: [[Advent of Code 2024] Day 3: Mull It Over](https://qiita.com/mae616/items/e8ec70a8a9868862238c)
次の日: [[Advent of Code 2024] Day 5: Print Queue](https://qiita.com/mae616/items/6968f78a85acc36ca361)

# 今日のお題

https://adventofcode.com/

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

# 4日目の物語
> ■ 4日目: セレスの捜索
> 「主任はここにはいないみたいだな。次！」と、歴史学者の一人がデバイスを取り出して、そこにある唯一のボタンを押した。しばらくの閃光の後、あなたは『セレスの監視ステーション』の内部を認識する！

テレポート式みたいに移動してるんですかね。さすがファンタジー٩( ᐛ )و
『セレスの監視ステーション』も Advent of Code 2019 と繋がってるみたいですね。

> 主任歴史学者をの捜索が続く中、ステーションに住む小さなエルフの子があなたのシャツを引っ張ってきた。彼女は、あなたにワードサーチ（パズルの入力）を手伝ってほしいようだ。

可愛いですね。
思わず画像生成AIで作っちゃいました。こんな感じですかね。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/5cfa132a-51ff-7b07-3ea3-7e748fb41942.png" width="500" alt="小さなエルフの女の子">

可愛いですね。

変なことしてないで、お題にいきましょう ꉂꉂ( ᐛ )

# 1問目
ワードサーチ...横、縦、斜め (逆さまもOK、他の単語と重なって現れることもあります)の中で「XMAS」の現れるところを見つけ、全部で何個「XMAS」が出現したか数を出力しましょう。

例:
```
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
```
これを「XMAS」に関係ない文字を「.」に置き換えると
```
....XXMAS.
.SAMXMS...
...S..A...
..A.A.MS.X
XMASAMX.MM
X.....XA.A
S.S.S.S.SS
.A.A.A.A.A
..M.M.M.MM
.X.X.XMASX
```
になり全部で `18` 回「XMAS」文字が現れています。

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

  const target = "XMAS";
  const graph = [];
  for (let i = 0; i < args.length; i++) {
    if (args[i] === "") continue;
    graph.push(args[i].split(""));
  }

  const H = graph.length;
  const W = graph[0].length;

  const move = [
    { check: (cx, cy) => cx > 0, x: -1, y: 0 }, // left
    { check: (cx, cy) => cy > 0, x: 0, y: -1 }, // up
    { check: (cx, cy) => cx < W - 1, x: 1, y: 0 }, // right
    { check: (cx, cy) => cy < H - 1, x: 0, y: 1 }, // down

    // 斜め
    { check: (cx, cy) => cx > 0 && cy > 0, x: -1, y: -1 }, // up left
    { check: (cx, cy) => cx < W - 1 && cy > 0, x: 1, y: -1 }, // up right
    { check: (cx, cy) => cx > 0 && cy < H - 1, x: -1, y: 1 }, // down left
    { check: (cx, cy) => cx < W - 1 && cy < H - 1, x: 1, y: 1 }, // down right
  ];

  let count = 0;

  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      (function search(cx, cy, index, pattern) {
        if (graph[cy][cx] !== target[index]) return;

        if (index === target.length - 1) {
          count++;
          return;
        }

        if (pattern === null) {
          for (const m of move) {
            if (!m.check(cx, cy)) continue;
            const nx = cx + m.x;
            const ny = cy + m.y;

            search(nx, ny, index + 1, m);
          }
        } else {
          if (!pattern.check(cx, cy)) return;
          const nx = cx + pattern.x;
          const ny = cy + pattern.y;

          search(nx, ny, index + 1, pattern);
        }
      })(x, y, 0, null);
    }
  }
  console.log(count);
}

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

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

```zsh
cd day4_1
node main.js
```
で実行できます。

# 2問目
> (解いたのに)エルフは不思議そうにあなたを見つめています。課題を誤解したのでしょうか？

可愛い٩( ᐛ )و

> 指示を探しながら、ワードサーチを裏返すと、実はこれはXMASのパズルではなく、X-MASのパズルで、Xの形をした2つのMASを見つけることが求められていることに気づきます。

## 実際のお題

Xの形をした「MAS」を探してね、てことみたいです٩( ᐛ )و
```
M.S
.A.
M.S
```
こんな感じの。

例:
```
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
```
これをXの形になってる「MAS」に関係ない文字を「.」に置き換えると
```
.M.S......
..A..MSMS.
.M.S.MAA..
..A.ASMSM.
.M.S.M....
..........
S.S.S.S.S.
.A.A.A.A..
M.M.M.M.M.
```
になり全部で `9` 回　Xの形の「MAS」文字が現れています。

面白そう。それではレッツゴー٩( ᐛ )و

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

  const graph = [];
  for (let i = 0; i < args.length; i++) {
    if (args[i] === "") continue;
    graph.push(args[i].split(""));
  }

  const H = graph.length;
  const W = graph[0].length;

  // ありえるパターン
  const patterns = [
    [
      ["M", ".", "M"],
      [".", "A", "."],
      ["S", ".", "S"],
    ],
    [
      ["S", ".", "M"],
      [".", "A", "."],
      ["S", ".", "M"],
    ],
    [
      ["S", ".", "S"],
      [".", "A", "."],
      ["M", ".", "M"],
    ],
    [
      ["M", ".", "S"],
      [".", "A", "."],
      ["M", ".", "S"],
    ],
  ];
  const offset = { x: 1, y: 1 };

  const move = [
    // 斜め
    { x: -1, y: -1 }, // up left
    { x: 1, y: -1 }, // up right
    { x: -1, y: 1 }, // down left
    { x: 1, y: 1 }, // down right
  ];

  let count = 0;

  for (let y = 1; y < H - 1; y++) {
    for (let x = 1; x < W - 1; x++) {
      if (graph[y][x] !== "A") continue;

      for (const pattern of patterns) {
        let hit = true;
        for (const m of move) {
          const nx = x + m.x;
          const ny = y + m.y;

          const px = offset.x + m.x;
          const py = offset.y + m.y;

          if (graph[ny][nx] !== pattern[py][px]) {
            hit = false;
            break;
          }
        }
        if (hit) {
          count++;
          break;
        }
      }
    }
  }
  console.log(count);
}

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

ケアレスミスしてちょっと戸惑っちゃいました٩( ᐛ )و

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

今日はこれで終わりです٩( ᐛ )و
AtCoderやLeetCodeのような問題もいいですが、Advent of Codeの問題も楽しいですね。
速さは問わないので気楽にできます ꉂꉂ( ᐛ )
お疲れさまです٩( ᐛ )و

---

今日の海外の人
https://www.reddit.com/r/adventofcode/
(謎の画像がたくさん投稿されてますね ꉂꉂ( ᐛ ))

では、また明日。