印刷キュー

コード 2024 の出現 5 日目

パート 1

秩序が生まれるでしょう！

これはとんでもないことになるでしょう。

更新に含まれないページのルールは考慮すべきではないという追加の警告が気に入っています。

このパズルにどのように取り組むかについて、漠然としたアイデアがあります。

しかし、明確にして実際のコードを書く準備ができていることを確認するために、ここで戦略を練る必要があります。

戦略につまずいてほしい

面白いですね。過剰チェックっぽい方法でこれを解決する方法がわかったような気がします。

これが私が考えていることです。

2 つのリストの最初のリストを、その前に置く必要がある任意の/すべてのページのページ番号のカタログに変換します。

これから:

47|53
97|13
97|61
...

こちらへ:

{
  47: [53],
  97: [13, 61],
  ...
}

でも、どうやって使えばいいのでしょう?

待ってください。ピボット!!

最初のサンプルページの更新を確認してください:

75,47,61,53,29

そして、その正しい順序について詳細な証明をレビューします...

...あまりにも退屈なアプローチについて考えさせられます:

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

パフォーマンス面での欠点:

• これには、各リストのページ順序ルールのセット全体を調べる必要があります
• 考えられるすべての数値のペアをチェックするタスクの階乗のように見えます

そのアプローチについてはよくわかりません。

キーのオブジェクトと「以前」のリストに戻ります。

オブジェクトをより包括的にしたらどうなるでしょうか:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

• 最初のネストされたリストは、その前に来る必要がある数値をカタログ化します
• 2 番目のネストされたリストは、その後に来る必要がある数値をカタログ化します

理論上 (および疑似コード):

For each number in the list
  Create an ordered list of the previous numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  Create an ordered list of the subsequent numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  If both flags are true
    Number is in the correct order

チュートリアルの例:

75

Before: []
After: [47,61,53,29]

Catalog:
{
  75: [ [29, 47, 53, 61, 13], [97] ]
}

Before: Empty - success

After: [True, True, True, True]

All True? Yes - success

Correct Order

少なくともカタログ オブジェクトを構築するアルゴリズムを作成する時期が来たと確信しています。

カタログ化アルゴリズムの構築

更新リストからルールを分離する:

let [rules, updates] = input.split('\n\n')

入力を解析して、各項目が数値である 2 項目のリストのリストを作成します。

rules = rules.split('\n').map(el => el.split('|').map(Number))

そのリストをキーとリスト値でいっぱいのオブジェクトに縮小します:

rules = rules.reduce((obj, item) => {
  if (!(item[0] in obj)) {
    obj[item[0]] = []
  }
  obj[item[0]].push(item[1])
  return obj
}, {})

これは期待どおりに機能しますか?

はい、次のオブジェクトが出力されます:

{
  '29': [ 13 ],
  '47': [ 53, 13, 61, 29 ],
  '53': [ 29, 13 ],
  '61': [ 13, 53, 29 ],
  '75': [ 29, 53, 47, 61, 13 ],
  '97': [ 13, 61, 47, 29, 53, 75 ]
}

指定された番号の後に来る必要がある番号のみを記録するように戻っていることに注意してください。

両方を確認する必要はないと思うからです。

私は間違っているかもしれません。

しかし、私はこの仮定の下で話を進めます。

各数字の後のすべての数字を確認する

最初の例の更新に取り組みます。これは正しいものとして表示されるはずです。

まず、入力を数値のリストに解析する必要があります。

updates = updates.split("\n").map((el) => el.split(",").map(Number));

次に、テスト用に最初のリストを抽出します。

let test = updates[0];

ここからは実際の作業です。

最初の試み:

47|53
97|13
97|61
...

5 番目の例のリスト項目で試してみるまでは機能しているように見えました:

{
  47: [53],
  97: [13, 61],
  ...
}

私のアルゴリズムは、各番号がカタログ内にキーとして存在するかどうかをチェックし、関連するリスト内のすべての番号が一致するかどうかをチェックします。

しかし、13 はカタログに載っていません。私のアルゴリズムは正しい判定を誤って仮定しています。

そして 29 になると、それ以上の数字はないので、これも正しいと想定されます。

それでは、戦略を調整する必要があります。

2 回目の試行:

75,47,61,53,29

これにより、すべての例リストに対して正しい答えが生成されます!

各番号の後に表示される番号のサブリスト内の各番号が、チェック対象の番号 (サブリストの直前の番号) に含まれているかどうかを正確にチェックします。

したがって、次の場合:

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

13 に遭遇すると、29 を検索すると 13 が表示されます。これは、それらの順序が間違っていることを意味します。

これをreduceに接続して中間の数値を加算します

思ったほど大変ではありませんでした:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

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

私のパズル入力はどうなるでしょうか?

またしても正解が生成されました!!!

うおおお!!!

私はしばらくそれを考えすぎたような気がします。そして、何がうまくいかなかったのかを確認すると、答えが明らかになりました。

楽しいこと!

パート 2 ではどのような新たな課題がもたらされるのでしょうか...?

パート 2

並べ替えの練習

私はおそらく、これが来るのを予見していたはずです。

ありがたいことに、私のアルゴリズムがこれに適した設定になっていると思います。

各リストを並べ替える必要があります。

並べ替えは、2 つの値を比較し、3 つの結果のいずれかに基づいて 2 つのうちの 1 つを実行することで機能します。

• 並べ替え関数から -1 が返された場合、最初の値が 2 番目の値の前に来ます
• 1 が返された場合、2 番目の値は最初の値の前に来る必要があります
• 0 が返された場合、値は等しいため移動されません

私のアルゴリズムはブール値のリストを生成します。

すべてのブール値が true の場合、それらを正しく生成した数値がすべての値の前に来ます。

ただし、ブール値が false の場合は、それらの数値の 1 つが現在の数値の前に来る必要があります。

しかし、2 つの数値を比較し、両方のリストに false の値が含まれている場合、どちらを先にすべきかをどうやって知ることができるでしょうか?

私が実際に対処できる方法は、一方のリストがすべて真でもう一方がそうでない場合、または両方がすべて真である場合のみです。

うーん。

数値のリストではなく、一度に 2 つの数値に対してテストを実行する必要があると思います。

並べ替えの仕組みとまったく同じです: a 対 b

1 対多ではなく 1 対 1 の戦闘用にアルゴリズムを調整する

頭を悩ませ、三項チェックを行い、再度推測した結果、機能するアルゴリズムに到達しました。

47|53
97|13
97|61
...

間違った順序のサンプル更新ごとに実行すると、正しい順序のリストが生成されます!

両方の入力のすべてのリストで実行することに興奮しており、うまくいけば 2 つの金星を獲得して今日を終えることができれば幸いです!

非常に細かい部分まで見渡す

入力例に対してアルゴリズムを実行したところ、表示されているよりも大きな数値が得られました。

その理由は分かりませんでした。正しくソートされた各リストを出力すると、その要素が正しい順序であることが証明されました。

その後、説明書をもう一度読みました。

間違って注文されたアップデートのみ

それは当然ですね!すべてのリストの中間値を合計していました!

これを修正するには、リストを複製するために少しスライス()を実行し、文字列化されたバージョンを比較する必要があります:

{
  47: [53],
  97: [13, 61],
  ...
}

ヴィオラ！入力例に対して正しい答えが得られました。

パズルの入力に役立ちます!

確かに!!!

甘い!!

2 つの金の星。全部私のものです!

また楽しいパズルですね。

考え抜いていくつかの戦略を導き出すのに数日かかりました。

しかし、最終的には霧の中を通り抜ける道を見つけました。

6 日目へ!

以上が印刷キューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。