ディスクの断片

コード 2024 の到来 9 日目

パート 1

三相ガントレット。エキサイティング！？？

私が見た段階の説明:

1. 記憶をリストとして表現します
2. 値を末尾から先頭に移動します
3. ラインに沿ってチェックサムを計算します

どれも特に難しいとは感じません。

そして、その一部は実際には、さらに別の楽しいアルゴリズムの課題のように思えます!

リストの作成

これを回転させたい:

12345

これに:

0..111....22222

次のことを考慮する必要があります:

• ループの使用
• 偶数インデックスと奇数インデックスを確認する
• 値を 0 から 1 ずつ増加させます

これが私のディスク生成アルゴリズムです:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

魔法のように効きます!

値を末尾から先頭へ移動する

ディスク上のすべての空の場所のリストを作成すると、これを簡単に行うことができます。

次の 2 か所でアルゴリズムを更新する必要があります:

1. 新しい変数: let empty = []
2. .: empty.push(disk.length - 1) を挿入した後の新しいアクション

この例でテストすると、各 .!

の予想されるインデックス番号が表示されます。

これは、値をリストの末尾から先頭、そしてそれ以降に移動するときに繰り返し処理するリストです。

でも待ってください。

これは私が思っていたよりも難しいかもしれません。

値の移動をやめるべきタイミングはどうすればわかりますか?

• 空のインデックスのリストを反復処理しますか?いつやめるべきですか?
• ディスクを逆方向に反復処理するのでしょうか?いつやめるべきですか?

ひらめき: 魔法の数字 10

これは短い例の最後の状態です:

022111222......

最初の例:

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

これは、すべての ID が左側にあり、すべての空のスペースが右側にある点が来ることを意味します。

その状態を確認するにはどうすればよいですか?

数字の 10 を入力してください。

連続する空きスペースの数が 9 を超えることはありません。

したがって、空のスペースを見つけたら、9 スペース (またはディスク リストの最後まで) 先を見て、すべての空のスペースを見れば、断片化が完了していることがわかります。

このアルゴリズムの残りの部分の書き方はわかったと思います!

断片化アルゴリズムを作成する

動作するアルゴリズムは次のとおりです:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

仕組み:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

ありがたいことに、両方の例と同じ出力が表示されます!

チェックサムの計算

これはかなり簡単で簡単だと思われます:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

擬似コード内:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

成功!入力例に対する正しい答えが生成されます!

パズルの入力でも同じことが行われますか?

...

はい!!!

うおおお!!!

第 2 部ではどんな展開になるでしょうか?わずかなルールの調整、それともスケールへの挑戦?

パート 2

興味深い展開

部品でした。これで完全になりました。

これには間違いなくアルゴリズムの調整が必要になります。

おそらく、ギャップとブロックのサイズをより確実に追跡します。

最初の戦略を実行する

私はそれぞれの空がどこにあるのか追跡していました。

それぞれの空がどこにあるのか、どのくらいの大きさなのかを追跡する必要があると思います。

それはどのようになりますか?

それをスクラッチしてください。たぶん新しい戦略。

最初の例の使用:

12345

ファイルのブロック サイズは奇数です:

0..111....22222

空のセルのサイズは偶数です:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

奇数の終わりと偶数の始まりから始めて、奇数以上の偶数を探します。

022111222......

すぐに一致する相手を見つけます。

結果:

• 奇数が動きます
• 偶数が減ります
• しかし、今では 2 つの奇数には隙間がありません
• そして、2 番目の 2 秒 ID を紛失してしまいました

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

この戦略は間違いなくうまくいきません。

2 番目の戦略を実行する

これがパフォーマンスに与える影響は好きではありません。

しかし、実行が完了する限り、うまくいくと信じています。

ディスク入力の各数値をリスト項目として記録します:

1. ファイルブロックまたは空のセル
2. 長さ
3. ID

例:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

次のようになります:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

えー、それをきれいにしましょう:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

データ型によってギャップとファイル ブロックを区別します。

変更された入力例では、ファイル ブロックの移動は次のようになります:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

これは 100,000 回の反復ごとに行われます:

• 大きな配列内の項目の検索
• 配列をインプレースで変更する

どちらも非常にコストのかかるタスクです。

しかし、このパズルを解くために私が思いつく唯一の方法です。

それでは、これが私のアプローチとなります。

戦略を体系化する

上記のデータ アーキテクチャを取得する JavaScript は次のとおりです。

2333133121414131402

メインループを開始および終了するにはどうすればよいですか?

ファイル ID 番号が最も大きいファイルから順に、各ファイルを 1 回だけ移動しようとします

後ろから前に移動すると、必要なことを実行できるようです。

これは for ループ スケルトンが機能するはずです:

[2,4,1,4,2,5,5,3,5,2]

検索、移動、置換

[3,3,3,1,1,1,1,1,0]

if の 2 番目の句が最後のデバッグでした。最低の ID を設定するのが早すぎました。

ディスクプリンターのコーディング

ディスクが断片化されていくのをほぼリアルタイムで確認する必要があることに気づきました。チュートリアルの例のように、少なくともそのログ。

ありがたいことに、コーディングは難しくありませんでした。 2 つのインデックスを混同し、本当に奇妙な出力が表示された部分だけです:

12345

• 文字列を構築します
• ディスク内のアイテムのタイプに基づく
• いずれの方法でも、配列を作成し、.s またはブロックの ID を入力します。

それはうまくいきます!ファイルがどこに移動されているかを確認でき、コードのトラブルシューティングがはるかに簡単になりました!

私が見たものを好きになる

0..111....22222

ファイル移動アルゴリズムが機能しているようです!

最後のステップは、新しいチェックサムを計算することです。

最後に、さらに数学的なことを

Double-Reduce の方法:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• 最初のreduceは、IDと.sの分散配列を取得します
• 2 番目の Reduce は、項目が ID の場合は適切な計算を実行し、項目が の場合は計算を実行しません。

効果ありますか？

パズル入力例について?はい！

私のパズル入力について?

...

やったー！

うわー。びっくりしました。パート 2 に提出した数値はパート 1 とほぼ同じでした。もっと高いと思っていました。

これ以上調査することに興味はありません。

苦労して獲得した 2 つの金の星を持って、10 日目まで歩きたいと思います。

さようなら 9 日目!

以上がディスクの断片の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。