Rotnasige Berichte

Advent of Code 2024 Tag 2

Teil 1

Einfach lösen oder optimal lösen? Das ist die Frage

Um es einfach zu lösen:

• Vergleichen Sie die Liste in Originalreihenfolge mit zwei Kopien, jeweils sortiert, jedoch in umgekehrter Reihenfolge. Wenn eines übereinstimmt, dann Erfolg für Kriterium eins
• Durchlaufen Sie jedes Element in der Liste, außer dem ersten. Verfolgen Sie den Unterschied zwischen jedem Artikel und dem vorherigen Artikel. Wenn irgendwelche Unterschiede 0 oder größer als 3 sind, schlägt dieser Test fehl.

Leistungsmäßig bedeutet das:
Für Kriterium 1:

• Zwei Listenkopien
• Jedes Exemplar sortieren
• Originalliste zweimal vergleichen Für Kriterium 2:
• Überprüfen Sie jede Zahl in jeder Liste

Um es optimal zu lösen:

• Für Kriterium 2 verwende ich eine While-Schleife, um nachfolgende Zahlen auf gültige Unterschiede zu überprüfen. Auf diese Weise werden die restlichen Zahlen nicht verarbeitet, sobald eine disqualifizierende Differenz auftritt
• Für Kriterium 1 verfolge ich die Unterschiede und prüfe dann einmal, ob alle kleiner oder größer als Null sind

Ich glaube, dass das funktionieren wird. Es gibt nur einen Weg, das herauszufinden.

Einen optimierten Algorithmus schreiben

Hier ist mein Code zur Identifizierung von Kriterium 2 (Unterschied von 1, 2 oder 3):

let differFlag = true;
let i = 1;
while (differFlag && i < list.length) {
  let amount = Math.abs(list[i] - list[i - 1]);
  if (![1, 2, 3].includes(amount)) {
    differFlag = false;
  }
  i++;
}

• Ich gehe die Liste nur so lange durch, bis ein ungültiger Unterschied festgestellt wird, falls vorhanden
• Sobald einer gefangen wird, wird die while-Schleife beendet
• Nach der while-Schleife kann ich differentFlag auf die Ergebnisse überprüfen

Hier ist mein Code zur Identifizierung von Kriterium 1 (alle Unterschiede nehmen zu oder ab):

let differFlag = true;
let i = 1;
let differences = [];
while (differFlag && i < list.length) {
  let amount = list[i] - list[i - 1];
  differences.push(amount);
  if (![1, 2, 3].includes(Math.abs(amount))) {
    differFlag = false;
  }
  i++;
}

• Ich erstelle eine Liste aller Unterschiede
• Ich habe die Absolutwertberechnung auf die Bedingung verschoben, weil ich eigentlich das Vorzeichen der Differenz erfassen möchte
• Nach der while-Schleife kann ich Unterschiede überprüfen, um zu sehen, ob jeder Wert positiv oder negativ ist

Hier ist die letzte Bedingung, die einen sicheren Bericht erfasst:

if (
     differFlag &&
    (differences.every((el) => el > 0) || 
     differences.every((el) => el < 0))
    ) {
      safeCount++;
    }

Insgesamt generiert mein Algorithmus die richtige Antwort für die Beispieleingabe.

Wird es dasselbe für meine Puzzle-Eingabe tun??

Yessssirrrreee!!

Süß!

Teil 2

Naja...schieß.

Das macht die Sache sicherlich etwas komplizierter.

Ich möchte einen Algorithmus vermeiden, der jede mögliche Permutation eines Berichts prüft. Dafür müssten Millionen von Berichten erstellt werden.

Die erste gute Nachricht ist:

• Alle sicheren Meldungen können weiterhin als sicher gewertet werden

Für meine Rätseleingabe sind das ungefähr 200, bei denen ich keine Permutationen überprüfen muss.

Dennoch ist 800/1000 immer noch eine Menge an Listen, um Permutationen vollständig zu erkunden.

Ich sehe ehrlich gesagt keinen Weg, um zu vermeiden, dass mein Algorithmus bei jeder Permutation unsicherer Berichte ausgeführt wird.

Mist.

Es ist Zeit, eine Schleife hinzuzufügen, um jede Zahl in unsicheren Berichten zu durchlaufen – die Zahl, die entfernt werden soll, und dann die mutierte Liste auf eine bestandene Note zu überprüfen.

Hinzufügen einer Permutationsprüfschleife

Am Ende habe ich meine while-Schleife mit den hinzugefügten Zeilen dupliziert, um eine Zahl aus jedem nachfolgenden Testbericht zu duplizieren und zu entfernen.

Es ist viel mehr Code.

Aber es funktioniert! Ich generiere die richtige Antwort für die Rätseleingabe!

Frage ist:

• Wird es ausgeführt ... und die richtige Antwort für meine Rätseleingabe generieren?

Lassen Sie es uns ausführen und sehen...

Hmmm, es läuft, aber ich bekomme eine Antwort, die nur geringfügig größer ist als meine Antwort in Teil 1. Das scheint falsch.

Es schadet nicht, es einzureichen, oder????

Es istrichtig!

Heiliger Rauch!

Das ist unglaublich!

Und es macht wirklich Spaß, es zu lösen!

Vier goldene Sterne für Tag 3.

Bring noch mehr wundervolle Rätsel!

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