Advent of Code 2024 Day 9: Disk Fragmenter
このページは
2024 年の Advent of Code の Day9 の記事です。 Day8 はこちら。
Day 9: Disk Fragmenter
今回はディスク上のファイルと空き容量の配置が与えられます。指示に従って、ファイルを空き容量のスペースに移動させるといったような問題です。
23325 といったような配置情報が与えられたとき、それぞれの数字はファイルの容量と空きスペースの容量が交互に表されています。例えばこちらの表現の場合、数字をファイルを ID、. を空きスペースとすると、
00...111..22222
のようなファイル配列を表しています。
このような配列になっている状態から、指示に従ってファイルの移動を行っていくという問題です。
Part1
Part1 では、右端のファイルから順に、左端の空き容量に対してファイルを移動させるというものです。例えば先の例の
00...111..22222
の場合
00...111..22222
002..111..2222.
0022.111..222..
00222111..22...
002221112.2....
0022211122.....
といったような移動をさせるとします。
23325 というようなフォーマットで与えられるため、これらを ファイルなのか、空きスペースなのかを分類しましょう。"左端からとる"、"右端からとる" のように両端からアクセスすることを考えると、 deque などの両端キューを使うのが良さそうです。
キューに保存する際には、 "ファイルなのか空きスペースなのか"、”元々の数字の値"、"ファイルが配置されていた場所" などの情報が必要なため、それらも保存しておくようにします。
あとは、前から見たときに処理を行っていき
- ファイルの場合はそのまま
- 空きスペースの場合は、末尾にあるファイルを取り出して移動
といった処理を行えば良さそうです。こんな感じになりました。
Part2
Part2 では、Part1 とは少しルールが変わります。Part1 では、ファイルの一部だけでも空きスペースに移動させることが出来ましたが、Part2 ではファイル全体が移動できるスペースがある場合のみ移動できるものとします。
例えば
00...11..222.3333
となっていた場合、3333 を移動させるスペースがないため、移動できません。一方で、222 は移動できるため、
0022211......3333
のようになります。
考え方としては、ファイルと空きスペースを別々に管理していき、ファイルは右から処理、していき空きスペースは左から条件に合うものを探していきます。条件に合うものがあれば移動、なければ今のまま確定という処理をしていけば良さそうです。
Part1 よりはよりシンプルに考えられるかもしれません。
Day 10 に続きます。
Discussion