Druckwarteschlange

Advent of Code 2024 Tag 5

Teil 1

Es wird Ordnung herrschen!

Das wird ein Kinderspiel.

Mir gefällt der zusätzliche Vorbehalt, dass Regeln für Seiten, die nicht in einem Update enthalten sind, nicht berücksichtigt werden sollten.

Ich habe eine vage Vorstellung davon, wie ich dieses Rätsel angehen soll.

Aber ich muss hier meine Strategie ausarbeiten, um Klarheit zu bekommen und sicherzustellen, dass ich bereit bin, tatsächlichen Code zu schreiben.

Ich hoffe, ich stolpere über eine Strategie

Es ist lustig. Ich habe das Gefühl, dass ich weiß, wie ich das auf eine überprüfbare Art und Weise lösen kann.

Das denke ich.

Konvertieren Sie die erste von zwei Listen in einen Katalog mit Seitenzahlen für alle Seiten, die davor stehen müssen:

Davon:

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

Dazu:

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

Aber wie könnte ich es verwenden?

Warte. Drehpunkt!!

Sehen Sie sich das erste Beispielseiten-Update an:

75,47,61,53,29

Und den ausführlichen Beweis auf seine korrekte Reihenfolge überprüfen...

...lässt mich über den allzu langwierigen Ansatz nachdenken:

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

Nachteile in Bezug auf die Leistung:

• Dazu müssen die gesamten Seitenreihenfolgeregeln für jede Liste befolgt werden
• Scheint wie eine Fakultät bei der Prüfung aller möglichen Zahlenpaare

Ich bin mir bei diesem Ansatz nicht ganz sicher.

Zurück zu meinem Schlüsselobjekt und den Vorher-Listen.

Was wäre, wenn ich das Objekt umfassender machen würde:

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

becomes:

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

• Die erste verschachtelte Liste katalogisiert die Zahlen, die davor stehen müssen
• Die zweite verschachtelte Liste katalogisiert die Zahlen, die darauf folgen müssen

In der Theorie (und im Pseudocode):

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

Eine beispielhafte Komplettlösung:

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

Ich denke definitiv, dass es an der Zeit ist, einen Algorithmus zu schreiben, der zumindest mein Katalogobjekt erstellt.

Erstellen des Katalogisierungsalgorithmus

Trennen der Regeln von der Update-Liste:

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

Parsen der Eingabe in eine Liste mit Listen mit zwei Elementen, wobei jedes Element eine Zahl ist:

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

Reduzieren dieser Liste in ein Objekt voller Schlüssel und Listenwerte:

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

Funktioniert das wie erwartet?

Ja, dieses Objekt wird ausgegeben:

{
  '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 ]
}

Beachten Sie, dass ich wieder nur Zahlen aufzeichne, die nach einer bestimmten Zahl stehen müssen.

Das liegt daran, dass ich nicht glaube, dass ich beide Seiten überprüfen muss.

Vielleicht irre ich mich.

Aber ich gehe von dieser Annahme aus.

Überprüfen Sie alle Zahlen nach jeder Zahl

Ich werde am ersten Beispielupdate arbeiten, das als korrekt angezeigt werden sollte.

Zuerst muss ich die Eingabe in Zahlenlisten analysieren:

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

Dann extrahieren Sie die erste Liste zum Testen:

let test = updates[0];

Jetzt zur eigentlichen Arbeit.

Erster Versuch:

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

Es schien zu funktionieren, bis ich es am fünften Beispiellistenelement ausprobierte:

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

Mein Algorithmus prüft, ob jede Nummer als Schlüssel im Katalog vorhanden ist, und prüft alle Nummern in der zugehörigen Liste auf Übereinstimmung.

Aber 13 ist nicht im Katalog. Mein Algorithmus geht fälschlicherweise von einem korrekten Urteil aus.

Und wenn es bei 29 ankommt, geht es auch davon aus, dass es richtig ist, da es keine Zahlen mehr gibt.

Also muss ich meine Strategie anpassen.

Zweiter Versuch:

75,47,61,53,29

Dadurch wird für jede Beispielliste die richtige Antwort generiert!

Es prüft korrekt jede Nummer in der Unterliste der Nummern, die nach jeder Nummer erscheint, auf die Einbeziehung der überprüften Nummer (die Nummer, die unmittelbar vor der Unterliste steht).

Also im Fall von:

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

Wenn es auf 13 trifft, sucht es nach 29 und sieht 13, was bedeutet, dass sie in der falschen Reihenfolge sind.

Setzen Sie dies in eine Reduzierung ein und addieren Sie die mittleren Zahlen

Es war nicht so schwer, wie ich dachte:

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

becomes:

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

Es generiert die richtige Antwort für die Beispieleingabe!

Wie wird es mit meinem Puzzle-Input funktionieren???

Es hat wieder die richtige Antwort generiert!!!

Woohoo!!!

Ich habe das Gefühl, dass ich eine Weile darüber nachgedacht habe. Dann wurde die Antwort klar, als ich sah, was nicht funktionierte.

Lustiges Zeug!

Welche neuen Herausforderungen wird Teil 2 mit sich bringen...?

Teil 2

Eine Sortierübung

Das hätte ich wahrscheinlich kommen sehen sollen.

Zum Glück denke ich, dass mein Algorithmus mich dafür gut vorbereitet hat.

Ich muss jede Liste sortieren.

Das Sortieren funktioniert durch den Vergleich zweier Werte und das Ausführen eines von zwei Dingen basierend auf einem von drei Ergebnissen:

• Wenn von der Sortierfunktion ein -1 zurückgegeben wird, kommt der erste Wert vor dem zweiten
• Wenn eine 1 zurückgegeben wird, sollte der zweite Wert vor dem ersten stehen
• Wenn eine 0 zurückgegeben wird, werden keine Werte verschoben, da sie gleich sind

Mein Algorithmus generiert Listen mit booleschen Werten.

Wenn alle booleschen Werte wahr sind, steht die Zahl, die sie korrekt generiert hat, vor allen.

Wenn jedoch boolesche Werte falsch sind, sollte eine dieser Zahlen vor der aktuellen Zahl stehen.

Aber wenn ich zwei Zahlen vergleichen würde und beide Listen einen falschen Wert hätten, woher würde ich dann wissen, welche zuerst kommen sollte?

Ich habe wirklich nur eine Möglichkeit, Fälle anzusprechen, in denen eine Liste alle wahr ist und die andere nicht, oder beide alle wahr sind.

Hmmmm.

Ich denke, ich muss meinen Test an zwei Zahlen gleichzeitig durchführen, anstatt an einer Liste von Zahlen.

Genau wie beim Sortieren: a vs b

Ich passe meinen Algorithmus für einen 1-gegen-1-Kampf statt für einen 1-gegen-viele-Kampf an

Nach einigem Kopfkratzen, ternären Überprüfungen und Nachdenken gelangte ich zu einem funktionierenden Algorithmus:

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

Wenn Sie es auf jedes der Beispielupdates mit falscher Reihenfolge ausführen, wird eine Liste mit korrekter Reihenfolge erstellt!

Ich freue mich darauf, es auf allen Listen in beiden Eingaben laufen zu lassen und heute hoffentlich mit zwei wohlverdienten goldenen Sternen abzuschließen!

Mit Blick auf ein riesiges...kleines Detail

Ich habe meinen Algorithmus mit der Beispieleingabe ausgeführt und eine größere Zahl als angezeigt erhalten.

Ich hatte keine Ahnung warum. Das Ausdrucken jeder korrekt sortierten Liste beweist, dass ihre Elemente in der richtigen Reihenfolge sind.

Dann habe ich die Anleitung noch einmal gelesen:

nur die falsch bestellten Updates

Das macht Sinn! Ich habe den Mittelwert jeder Liste addiert!

Um dieses Problem zu beheben, ist ein kleines Slice()ing erforderlich, um die Liste zu duplizieren, und anschließend wird der String-Versionen verglichen:

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

Viola! Ich bekomme die richtige Antwort für die Beispieleingabe.

Ich drücke die Daumen für meinen Rätsel-Input!

In der Tat!!!

SWEEEEEET!!

Zwei goldene Sterne. Alles meins!

Was für ein weiteres lustiges Rätsel.

Es hat ein paar Tage gedauert, einige Strategien zu überdenken und abzuleiten.

Aber ich habe schließlich meinen Weg durch den Nebel gefunden.

Weiter zu Tag 6!

Das obige ist der detaillierte Inhalt vonDruckwarteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!