この記事は、mae616 Advent of Code Advent Calendar 2024 の11日目の記事です。
このアドベントカレンダーは皆勤賞のQiitaくんのぬいぐるみに惹かれて挑戦している大変ゆるい挑戦のものです。そんな感じで読んでいただければ幸いです。
前の日: [Advent of Code 2024] Day 10: Hoof It
次の日: [Advent of Code 2024] Day 12: Garden Groups
今日のお題
11日目の物語
■ 11日目: プルトンの小石
『プルトン』の古代文明は時空を操る能力で知られており、歴史学者たちがその無限の回廊を探索する中、あなたは奇妙な物理法則を無視した石たちに気づきました。
『プルトン』も Advent of Code 2019 と繋がっているみたいですね。
やっぱり過去問もそのうちやりたいですね。面白そう。
次は、変な石が相手ですね ٩( ᐛ )و
最初に見たとき、それらは普通の石のように見えます。きれいに直線に並んでいて、それぞれの石には数字が刻まれています。
奇妙なのは、まばたきするたびにその石たちが変化することです。
時々、石に刻まれた数字が変わります。別の時には、石が二つに割れ、その結果、他の石たちが少しずつずれて、完璧な直線の中でスペースを作ることになります。
なんでしょうね。不思議ですね٩( ᐛ )و
1問目
しばらく観察していると、石には一定の動きがあることに気づきます。まばたきするたびに、石は同時に次のルールのうち最初に適用されるものに従って変化します。
ルール1: もし石に 0 の数字が刻まれていれば
→ 1 の数字が刻まれた石に変化します。
ルール2: もし石に 偶数桁 の数字が刻まれていれば
→ 二つの石に分かれます
- (元の石に刻まれている桁の) 左側の半分は新しい左の石になります
- (元の石に刻まれている桁の) 右側の半分は新しい右の石になります
※ 新しい数字には余分な先頭のゼロは付きません(例えば 1000 の石は、新しい石 10と0 に分かれます）
その他のルールが適用されない場合
→ その石は新しい石に置き換えられ、その新しい石には 古い石の数字 に 2024 を掛けた数が刻まれます
どんなに石が変化しても、その順番は保たれ、石たちは完璧に直線のままです。
もしあなたがずっとまばたきをし続けたら、石たちはどんな進化を遂げるのでしょうか？あなたは直線上の各石に刻まれた数字をメモします（これはパズルの入力です）。
面白そうですね٩( ᐛ )و
例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の数字が刻まれた石に置き換えられます
つまり、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回まばたきした後、あなたは何個の石を持っていますか？
やってみましょう٩( ᐛ )و
解いたコード
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"));
下記で実行できます。
$ cd day11_1
$ node main.js
2問目
今度は75回まばたきをしたら、何個の石になるかみたいですね。
まばたきの回数の変数を変えるだけでいけるかな٩( ᐛ )و
解いたコード
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://www.reddit.com/r/adventofcode/
みんなメモリ不足言ってますね٩( ᐛ )و
では、また明日（というかこの記事は予定があって遅れてしまったので、今日ですね）
お疲れさまです٩( ᐛ )و