[Advent of Code 2024] Day 11: Plutonian Pebbles

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

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

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

------

前の日: [[Advent of Code 2024] Day 10: Hoof It](https://qiita.com/mae616/items/b7819c82a31f545f95a8)
次の日: [[Advent of Code 2024] Day 12: Garden Groups](https://qiita.com/mae616/items/8cafbb6aec54c96f38d0)

# 今日のお題

https://adventofcode.com/

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

# 11日目の物語
> ■ 11日目: プルトンの小石
> 『プルトン』の古代文明は時空を操る能力で知られており、歴史学者たちがその無限の回廊を探索する中、あなたは奇妙な物理法則を無視した石たちに気づきました。

『プルトン』も Advent of Code 2019 と繋がっているみたいですね。
やっぱり過去問もそのうちやりたいですね。面白そう。

次は、変な石が相手ですね ٩( ᐛ )و

> 最初に見たとき、それらは普通の石のように見えます。きれいに直線に並んでいて、それぞれの石には数字が刻まれています。
>
> 奇妙なのは、<INS>まばたきするたび</INS>にその石たちが変化することです。
> 時々、石に刻まれた数字が変わります。別の時には、石が二つに割れ、その結果、他の石たちが少しずつずれて、完璧な直線の中でスペースを作ることになります。

なんでしょうね。不思議ですね٩( ᐛ )و

# 1問目
> しばらく観察していると、石には一定の動きがあることに気づきます。まばたきするたびに、石は同時に次のルールのうち最初に適用されるものに従って変化します。

*ルール1:* もし石に `0` の数字が刻まれていれば
→ `1` の数字が刻まれた石に変化します。

*ルール2:* もし石に 偶数<INS>桁</INS> の数字が刻まれていれば
→ 二つの石に分かれます
* (元の石に刻まれている桁の) <INS>左側の半分</INS>は新しい左の石になります
* (元の石に刻まれている桁の) <INS>右側の半分</INS>は新しい右の石になります

※ 新しい数字には余分な先頭のゼロは付きません(例えば `1000` の石は、新しい石 `10`と`0` に分かれます）

*その他のルールが適用されない場合*
→ その石は新しい石に置き換えられ、その新しい石には `古い石の数字` に `2024` を<INS>掛けた数</INS>が刻まれます

> どんなに石が変化しても、その順番は保たれ、石たちは完璧に直線のままです。
> もしあなたがずっとまばたきをし続けたら、石たちはどんな進化を遂げるのでしょうか？あなたは直線上の各石に刻まれた数字をメモします（これはパズルの入力です）。

面白そうですね٩( ᐛ )و

例1:
もし、`0 1 10 99 999` という数字が刻まれた5つの石が並んでいたら

1回まばたきをすると、石は以下のように変化します：
* 最初の石、`0` は`1` に変わります
* 2番目の石、`1` は 2024倍されて `2024` になります
* 3番目の石、`10` は (偶数桁のため) `1` の石と `0` の石に分かれます
* 4番目の石、`99`は (偶数桁のため)　2つの `9` の石に分かれます
* 5番目の石、`999` は 2024倍されて `2021976` の数字が刻まれた石に置き換えられます

![CleanShot 2024-12-12 at 07.30.21@2x.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/a1292c4e-d05e-3f99-7a22-dc6d68b84062.png)

つまり、1回まばたきをした後、5つの石は `1 2024 1 0 9 9 2021976` という7つの石に変わります。

例2:例2:
もし、`125 17` という数字が刻まれた2つの石が並んでいたら
```
Initial arrangement(最初の並び):
125 17

After 1 blink(1回目まばたき後):
253000 1 7

After 2 blinks(2回目まばたき後):
253 0 2024 14168

After 3 blinks(3回目まばたき後):
512072 1 20 24 28676032

After 4 blinks(4回目まばたき後):
512 72 2024 2 0 2 4 2867 6032

After 5 blinks(5回目まばたき後):
1036288 7 2 20 24 4048 1 4048 8096 28 67 60 32

After 6 blinks(6回目まばたき後):
2097446912 14168 4048 2 0 2 4 40 48 2024 40 48 80 96 2 8 6 7 6 0 3 2
```
 > この例では、6回まばたきをした後、石は `22` 個になります。25回まばたきをしたら、石は `55312` 個になるのです！
 > 目の前の石の配置を考えてみてください。25回まばたきした後、あなたは何個の石を持っていますか？

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

 ## 解いたコード
 ```js: ./day11_1/main.js
 function main(input) {
  const args = input.split("\n");
  let stones = args[0].split(" ").map(Number);

  const blink = 25;
  for (let i = 0; i < blink; i++) {
    stones = stones.flatMap((current) => {
      if (current === 0) {
        return 1;
      } else if (`${current}`.length % 2 === 0) {
        const half = `${current}`.length / 2;
        return [
          Number(`${current}`.slice(0, half)),
          Number(`${current}`.slice(half)),
        ];
      } else {
        return current * 2024;
      }
    });
  }
  console.log(stones.length);
}

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

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

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

# 2問目
今度は75回まばたきをしたら、何個の石になるかみたいですね。

まばたきの回数の変数を変えるだけでいけるかな٩( ᐛ )و

## 解いたコード

```js: ./day11_2
const MAX_ARRAY_LENGTH = 2 ^ (32 - 1);
function main(input) {
  const args = input.split("\n");
  let stones = args[0].split(" ").map(Number);

  let sum = 0;
  const blink = 75;
  const memo = new Map();
  for (const stone of stones) {
    sum += countStone(stone, 0, blink, memo);
  }
  console.log(sum);
}

function countStone(stone, start, blink, memo) {
  const key = `${stone}-${start}`;
  if (memo.has(key)) return memo.get(key);

  let sum = 1;
  let currentStones = [stone];

  for (let i = start; i < blink; i++) {
    const nextStones = [];
    const temp = [];
    for (const current of currentStones) {
      const currentStr = `${current}`;
      if (current === 0) {
        nextStones.push(1);
      } else if (currentStr.length % 2 === 0) {
        const half = currentStr.length / 2;
        if (nextStones.length >= MAX_ARRAY_LENGTH - 1) {
          nextStones.push(Number(currentStr.slice(0, half)));
          temp.push(Number(currentStr.slice(half)));
        } else {
          nextStones.push(Number(currentStr.slice(0, half)));
          nextStones.push(Number(currentStr.slice(half)));
          sum++;
        }
      } else {
        nextStones.push(current * 2024);
      }
    }
    for (const t of temp) {
      sum += countStone(t, i + 1, blink, memo);
    }
    currentStones = nextStones;
  }
  memo.set(key, sum);
  return sum;
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));
```
全然ちょと変えればでなかったです ꉂꉂ( ᐛ )
まじ、メモリ不足がえぐかったです ꉂꉂ( ᐛ )
海外の人とChatGPTにヒントもらっちゃいました。メモ化がポイントだったらしい٩( ᐛ )و
一つ利口になりました ꉂꉂ( ᐛ )

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

---

今日の海外の人
https://www.reddit.com/r/adventofcode/
みんなメモリ不足言ってますね٩( ᐛ )و

では、また明日（というかこの記事は予定があって遅れてしまったので、今日ですね）
お疲れさまです٩( ᐛ )و