Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

mae616 Advent of CodeAdvent Calendar 2024

Day 9
@mae616

[Advent of Code 2024] Day 9: Disk Fragmenter

Last updated at Posted at 2024-12-09

この記事は、mae616 Advent of Code Advent Calendar 2024 の9日目の記事です。

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

Advent of Code は後半になるにつれて難しくなると聞くので、どこで難しさに打ちのめされるかな、と思っています ꉂꉂ( ᐛ )
ちなみに、何も意識せず始めたこのアドベントカレンダーの記事ですが、個人的に自分でこの記事の書き方が気に入っています。今後こういう感じで書こうかな、と思っています٩( ᐛ )و

前の日: [Advent of Code 2024] Day 8: Resonant Collinearity
次の日: [Advent of Code 2024] Day 10: Hoof It

今日のお題

9日目の物語

■ 9日目: ディスク断片化ツール
デバイスのボタンをもう一度押すと、あなたはまた見覚えのある『アンフィポッドたちの廊下』に移動する！みんなそれぞれ小型の潜水艦を手に入れてるから良かったね。歴史学者たちは、壁にぶつかりながらも、主任歴史学者を探してさっさと進んでいく。

『アンフィポッド』は Advent of Code 2021 と繋がっていて、んーエビみたいな形をした生き物のことなのかな？よくわからないけどそういう生き物の分類のことらしい。
小型の潜水艦はどこで手に入れたのだろう、前の年かな。

あなたは隅っこでコンピュータに困っているアンフィポッドを見かける。彼は、ファイルを圧縮して空き領域を増やそうとしているが、プログラムがうまく動かないようだ。あなたは手伝うことを申し出る。
彼はすでに生成したディスクマップ（あなたのパズルの入力）を見せてくれる。

さて、今回のパズルみたいですね。レッツゴー٩( ᐛ )و

1問目

例:

2333133121414131402

ディスクマップは、ディスク上のファイルと空き領域の配置を示すために、密なフォーマットを使っています。数字はファイルの長さと空き領域の長さを交互に示しています。

例えば、ディスクマップ 12345 は、

  • 1 ブロックのファイル
  • 2 ブロックの空き領域
  • 3 ブロックのファイル
  • 4 ブロックの空き領域
  • 5 ブロックのファイル

を表します。

ディスクマップ 90909 は、9 ブロックのファイルが3つ並んでいる（間に空き領域なし）ことを表しています。

  • 9 ブロックのファイル
  • 0 ブロックの空き領域
  • 9 ブロックのファイル
  • 0 ブロックの空き領域
  • 9 ブロックのファイル

ここから『ブロックの形式』の話になります。

ディスク上の各ファイルには、並べ替え前の順番に基づいてID番号が付けられ、IDは 0 から始まります。

つまり、ディスクマップ 12345 には3つのファイルがあります。

  • 1 ブロックのファイル ... ID: 0
  • 2 ブロックの空き領域
  • 3 ブロックのファイル ... ID: 1
  • 4 ブロックの空き領域
  • 5 ブロックのファイル ... ID: 2

各ブロックには1文字を使い、数字 がファイルIDを、ドット( . )が空き領域を示します。
ディスクマップ 12345 は次のようにブロックを表現します。
0..111....22222
※ 数字 や . の繰り返し数は、何ブロックあるかの数

ここから、『空きブロックを増やす最適化』の話に入ります。

アンフィポッドは、ファイルブロックを1つずつディスクの端から左端の空きスペースブロックに移動したいと考えています（ファイルブロック間に隙間がなくなるまで）。
ディスクマップ 12345の場合、このプロセスは次のようになります：

  • 1.まず、『ブロックの形式』にします
    0..111....22222
  • 2.『空きブロックを増やす最適化』で 一番右端のファイル を 一番左端の空き容量 に移動していくを繰り返します
    (1) 0..111....22222 → 02.111....2222.
    (2) 02.111....2222. → 022111....222..
    (3) 022111....222.. → 0221112...22...
    (4) 0221112...22... → 02211122..2....
    (5) 02211122..2.... → 022111222......
    (6) 022111222...... 最適化完了

初めの例に戻りましょう。
『ブロックの形式』にすると下記になります。

00...111...2...333.44.5555.6666.777.888899

『空きブロックを増やす最適化』は下記のステップを辿ります。

00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............

パズルの答えは、最適化した結果の『ファイルシステムのチェックサム』を求めてください、てことみたいです。
最適化後のブロックは、

0099811188827773336446555566..............

です。

チェックサムを計算するには、各ブロックの位置と、そのブロックに含まれるファイルID番号を掛け算した結果を合計します。最も左のブロックは位置0です。ブロックに空き領域が含まれている場合は、それをスキップします。

なので、左から順に

  • 1文字目: インデックス 0 * ID 0 (0 * 0) = 0
  • 2文字目: インデックス 1 * ID 0 (1 * 0) = 0
  • 3文字目: インデックス 2 * ID 9 (2 * 9) = 18
  • 4文字目: インデックス 3 * ID 9 (3 * 9) = 27
  • 5文字目: インデックス 4 * ID 8 (4 * 8) = 32
  • ... (続く)

となって求めた値の合計 (0 + 0 + 18 + 27 + 32 + ... ) = の 1928 が答えになります。

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

解いたコード

./day9_1/main.js
function main(input) {
  const args = input.split("\n");
  const s = args[0];

  // ブロック化
  let id = 0;
  let isFile = true;
  const aryFileBlock = [];
  for (let c of s) {
    if (isFile) {
      aryFileBlock.push(...new Array(Number(c)).fill(id));
      id++;
    } else {
      aryFileBlock.push(...new Array(Number(c)).fill("."));
    }
    isFile = !isFile;
  }

  // 最適化
  let blank = 0;
  let file = aryFileBlock.length - 1;
  while (blank < file) {
    if (aryFileBlock[blank] !== ".") {
      blank++;
    }
    if (aryFileBlock[file] === ".") {
      file--;
    }
    if (aryFileBlock[blank] === "." && aryFileBlock[file] !== ".") {
      [aryFileBlock[blank], aryFileBlock[file]] = [
        aryFileBlock[file],
        aryFileBlock[blank],
      ];
      blank++;
      file--;
    }
  }

  // チェックサムの計算
  let sum = 0;
  for (let i = 0; i < aryFileBlock.length; i++) {
    if (aryFileBlock[i] !== ".") {
      sum += i * Number(aryFileBlock[i]);
    }
  }
  console.log(sum);
}

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

IDが二桁以上ある場合を考慮できなくてミスっちゃいました ꉂꉂ( ᐛ )

下記で実行できます。

zsh
$ cd day9_1
$ node main.js

2問目

個々のブロックを移動するのではなく、ファイル全体を移動してディスクを最適化しましょう。

あ、やっぱりそうきますよね ꉂꉂ( ᐛ )

今回は、ファイルが収まる左端の空き領域にファイル全体を移動することを試みます。ファイルID番号が大きいものから順に、各ファイルを1回だけ移動してみてください。もしファイルを収めるのに十分な空き領域が左側に見つからなければ、そのファイルは移動しません。

初めの例での今回の最適化のステップは下記になります。

00...111...2...333.44.5555.6666.777.888899
0099.111...2...333.44.5555.6666.777.8888..
0099.1117772...333.44.5555.6666.....8888..
0099.111777244.333....5555.6666.....8888..
00992111777.44.333....5555.6666.....8888..

チェックサムは 2858 になります。

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

解いたコード

./day9_2/main.js
function main(input) {
  const args = input.split("\n");
  const s = args[0];

  // ブロック化
  let id = 0;
  let isFile = true;
  const aryFileBlock = [];
  for (let c of s) {
    if (isFile) {
      aryFileBlock.push(...new Array(Number(c)).fill(id));
      id++;
    } else {
      aryFileBlock.push(...new Array(Number(c)).fill("."));
    }
    isFile = !isFile;
  }

  // 最適化
  let prevIndex = aryFileBlock.length - 1;
  let fileCount = 1;
  // 右端からfileを探す
  for (let i = aryFileBlock.length - 2; i >= 0; i--) {
    if (aryFileBlock[prevIndex] === ".") {
      prevIndex = i;
      fileCount = 1;
      continue;
    }
    if (aryFileBlock[prevIndex] === aryFileBlock[i]) {
      fileCount++;
      continue;
    }
    // 左端から空き容量を探す
    let start = 0;
    let blankCount = 0;
    for (let j = 0; j < prevIndex; j++) {
      if (aryFileBlock[j] !== ".") {
        start = j + 1;
        blankCount = 0;
        continue;
      }
      blankCount++;

      if (blankCount === fileCount) {
        const fileId = aryFileBlock[prevIndex];
        for (let k = 0; k < fileCount; k++) {
          aryFileBlock[start + k] = fileId;
          aryFileBlock[prevIndex - k] = ".";
        }
        break;
      }
    }
    prevIndex = i;
    fileCount = 1;
  }

  // チェックサムの計算
  let sum = 0;
  for (let i = 0; i < aryFileBlock.length; i++) {
    if (aryFileBlock[i] !== ".") {
      sum += i * Number(aryFileBlock[i]);
    }
  }
  console.log(sum);
}

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

ちょっとケアレスミスしてハマっちゃいました ꉂꉂ( ᐛ )
prevIndex のあたりが頭の中でごちゃついちゃいました ꉂꉂ( ᐛ )

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

今日の海外の人は
https://www.reddit.com/r/adventofcode/
昔のパソコンを思い出して懐かしんでますね ٩( ᐛ )و

では、また明日。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?