[Advent of Code 2024] Day 10: Hoof It

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

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

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

10日目だから何気に3分の1は過ぎていましたね٩( ᐛ )و

------

前の日: [[Advent of Code 2024] Day 9: Disk Fragmenter](https://qiita.com/mae616/items/740ec17c7b8e7d60271b)
次の日: [[Advent of Code 2024] Day 11: Plutonian Pebbles](https://qiita.com/mae616/items/b6f4c5331188937ea314)

# 今日のお題

https://adventofcode.com/

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

# 10日目の物語
> ■ 10日目: 足を使って進む
あなたや歴史学者たちは空に浮かぶ島の『溶岩生産施設』に到着します。歴史学者たちが広大な工業複合施設を探索し始める中、あなたは小さな鼻が足に軽くぶつかるのを感じ、下を見ると、安全帽をかぶったトナカイがいます。

『溶岩生産施設』も Advent of Code 2023 と繋がっているみたいですね。
エルフ、ゾウ、エビっぽいのときて今度はトナカイですね ٩( ᐛ )و

> そのトナカイは「溶岩島ハイキングガイド」という本を持っています。しかし、その本を開くと、ほとんどが溶岩で焼けてしまっていることに気づきます！助けが必要だと思い始めたその時、トナカイはあなたに周囲の地形図（パズルの入力）を渡し、わくわくした様子で見上げてきます。
> 
> もしかしたら、欠けているハイキングコースを埋める手伝いができるかもしれません。
> 
> 地形図には、各位置の高さが `0`（最も低い）から `9`（最も高い）のスケールで示されています。

今度は地形図ですね٩( ᐛ )و

ところで、トナカイかわいいですね。また画像生成AIで生成してみましょうか٩( ᐛ )و
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/29699b12-6c52-c286-c206-276a73d5e258.png" width=600>

安全帽じゃなく、サンタ帽子をかぶったトナカイができちゃいました。
でも、かわいいのでヨシ٩( ᐛ )و

さあ、戻って問題にいきましょう ꉂꉂ( ᐛ )

# 1問目
例:
```
0123
1234
8765
9876
```
> 「溶岩島ハイキングガイド」の本の焼けていないページの切れ端を元に、良いハイキングコースはできるだけ長く、均等で緩やかな登りの傾斜があると判断します。
> 実際的には、ハイキングコースとは、標高 `0` から始まり、標高 `9` で終わり、各ステップで標高が正確に 1 ずつ増加する道のことです。
> ※ ハイキングコースでは斜めの移動は含まれません(地図の視点からの上下左右のみ移動できます）。

また、graphの問題っぽいですね。

> あなたは地図から目を離し、トナカイが親切にもハイキングコースの更新に必要な鉛筆、マーカー、定規、コンパス、シール、その他の道具を小さな山に積んでいるのに気付きます。 

トナカイ、かわいい٩( ᐛ )و

　
次から『トレイルヘッド』の説明になります。
> 『トレイルヘッド』は、1つ以上のハイキングコースが始まる位置のことです。ここでは、これらの位置は常に標高 `0` です。
> (「溶岩島ハイキングガイド」の本の) ページのさらに多くの断片を組み立てると、『トレイルヘッドのスコア』は、そのトレイルヘッドからハイキングコースを通じて到達できる標高 `9` の<INS>位置の数</INS>であることがわかります。例では、左上隅(標高 `0`)の唯一のトレイルヘッドは、1つの標高 `9` （左下にあるもの）に到達できるため、スコアは `1` です。
>
![名称未設定2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/15c2acf5-90c2-4b5e-5515-9c301bb74ba7.png)

> ※ 左上の `0` から `1` ステップずつ標高の増加していくハイキングコースは、いずれも標高`9` は左下のものにたどり着くため、(たどり着く)標高 `9` の数(トレイルヘッドのスコア)は `1` 

他の例ものっています。

> 下記での『トレイルヘッドのスコア』は `2` です。
> ```
> ...0...
> ...1...
> ...2...
> 6543456
> 7.....7
> 8.....8
> 9.....9
> ```
中央上の `0` から `1` ステップずつ標高の増加していくハイキングコースで辿り着ける、標高`9`の地点は `2` つあります。
ちなみに `.` は通行不可のタイルで、実際にはハイキングコースのルールでは辿り着けない標高の `数字` が入っています。

> 下記の『トレイルヘッドのスコア』は `4` です
> ```
> ..90..9
> ...1.98
> ...2..7
> 6543456
> 765.987
> 876....
> 987....
> ```

![CleanShot 2024-12-10 at 21.09.48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/4a971d03-8dec-6ddb-2445-38f7f0b4cbf6.png)

> 下記の例は、2つの『トレイルヘッド』があります。上の『トレイルヘッドのスコア』は　`1` で、下の『トレイルヘッドのスコア』は `2` です
> ```
> 10..9..
> 2...8..
> 3...7..
> 4567654
> ...8..3
> ...9..2
> .....01
> ```

![CleanShot 2024-12-10 at 21.21.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/53f21764-d9d5-15f8-4396-39de415cf669.png)

> これはちょっと大きな例になります。
> ```
> 89010123
> 78121874
> 87430965
> 96549874
> 45678903
> 32019012
> 01329801
> 10456732
> ```
> この例には `9` つの『トレイルヘッド』があります。
> 『トレイルヘッドのスコア』は `5`、`6`、`5`、`3`、`1`、`3`、`5`、`3`、`5` です。
> 『トレイルヘッドのスコア』を合計した `5 + 6 + 5 + 3 + 1 + 3 + 5 + 3 + 5 =` の `36` が答えになります。

> トナカイは嬉しそうに分度器を持ち上げ、それを積み上げた山に加えます。あなたの地形図上のすべてのトレイルヘッドのスコアの合計は何ですか？

それではやってみましょう٩( ᐛ )و

## 解いたコード
```js: ./day10_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("").map(Number));
  }

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

  const hiking = {
    top: { x: 0, y: -1 },
    right: { x: 1, y: 0 },
    bottom: { x: 0, y: 1 },
    left: { x: -1, y: 0 },
  };

  const score = new Set();
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (graph[y][x] !== 0) continue;

      (function bfs(cy, cx, nextScore) {
        for (const key of Object.keys(hiking)) {
          const ny = cy + hiking[key].y;
          const nx = cx + hiking[key].x;

          if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
          if (graph[ny][nx] !== nextScore) continue;

          if (nextScore === 9) {
            score.add(`${y}:${x}|${ny}:${nx}`);
            continue;
          }
          bfs(ny, nx, nextScore + 1);
        }
      })(y, x, 1);
    }
  }
  console.log(score.size);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
作っていて `continue` なのか、 `break` なのか、 `return` なのか、どれがロジックに適切なのか頭がこんがらがっちゃいました ꉂꉂ( ᐛ )

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

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

# 2問目
トナカイが『トレイルヘッドの評価』という方法でも測定してほしいらしいですね。
今までの『トレイルヘッドのスコア』では、下記のような、開始の標高 `0` と ゴール地点の標高 `9` が同じコースは `1` と測定していたけど、コースが違うものは、`2` (もしくはもっと、の<INS>コースの数分</INS>) かぞえてほしいみたいですね。

![名称未設定2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/15c2acf5-90c2-4b5e-5515-9c301bb74ba7.png)

1問目の例のものの『トレイルヘッドの評価』は `81` になるようです。

ちょっと変えればいけるかな٩( ᐛ )و

## 解いたコード
```js: day10_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("").map(Number));
  }

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

  const hiking = {
    top: { x: 0, y: -1 },
    right: { x: 1, y: 0 },
    bottom: { x: 0, y: 1 },
    left: { x: -1, y: 0 },
  };

  const score = new Set();
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (graph[y][x] !== 0) continue;

      (function bfs(cy, cx, nextScore, strRoute) {
        for (const key of Object.keys(hiking)) {
          const ny = cy + hiking[key].y;
          const nx = cx + hiking[key].x;

          if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
          if (graph[ny][nx] !== nextScore) continue;

          if (nextScore === 9) {
            score.add(`${strRoute}|${ny}:${nx}`);
            continue;
          }
          bfs(ny, nx, nextScore + 1, `${strRoute}|${ny}:${nx}`);
        }
      })(y, x, 1, `${y}:${x}`);
    }
  }
  console.log(score.size);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
`strRoute` 変数を渡すようにするだけでいけましたね٩( ᐛ )و

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

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

---

今日の海外の人は
https://www.reddit.com/r/adventofcode/
1問目に2問目のコードを書いてしまった人が多い感じなのかな٩( ᐛ )و
わかる気がします٩( ᐛ )و

では、また明日。