Brückenreparatur

Advent of Code 2024 Tag 7

Teil 1

Erste Rekursion des Jahres

Zumindest habe ich heute vor, mir so einen goldenen Stern zu verdienen:

• Beginnen Sie mit der vollständigen Liste
• Überprüfen Sie sowohl Addition als auch Multiplikation
• Fahren Sie für jedes Ergebnis mit dem Rest der Liste fort
• Bis ich die Gesamtsumme entweder überschritten oder erreicht habe

Die Schwierigkeit liegt im Detail.

Lass uns das tun!

Ich erstelle meinen Algorithmus

Zuerst muss ich jede Zeile in eine Liste von Zahlen zerlegen:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Das erste Element ist die gewünschte Summe.

Der Rest sind die geordneten Operanden der Gleichung.

Ich muss dies in meiner rekursiven Funktion berücksichtigen.

Hier ist meine rekursive Funktion:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Und hier ist die Reduzierung, die es verwendet:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Wie ich gehofft, aber nie erwartet habe, wird die richtige Antwort für die Beispieleingabe generiert!

Wird die Verarbeitung meiner Rätseleingabe abgeschlossen?

Und wenn ja, wird die richtige Antwort generiert?

Ich bin mir ehrlich gesagt nicht sicher...

HAT ES!!!

Woah!!!

So aufgeregt ich auch bin, ich befürchte, dass im nächsten Teil entweder weitere Operatoren hinzugefügt werden oder fortgeschrittene CS erforderlich sind, damit die Rekursion keine praktikable Lösung mehr ist.

Teil 2

Völlig unerwartet! Und viel schwieriger

Wie soll ich das überhaupt machen?

...

Ein paar Tage später...

Eine Zusammenfassung meines Denkprozesses:

• Ist es so einfach, meiner Rückgabebedingung eine dritte Klausel hinzuzufügen? Nein
• Ist meine rekursive Funktion von Teil 1 überhaupt richtig konfiguriert, um erfolgreich zu sein? Nein
• Oh nein, ist es überhaupt möglich, einen Betrag anzusammeln, der aus früheren Operationen resultiert? Nein
• Muss ich das wirklich mit einer neuen Strategie angehen? Ja

Unter Berücksichtigung aller neuen Variationen

Für diese Gleichung:

292: 11 6 16 20

Dies sind alle möglichen Gleichungen mit den drei Operatoren:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Vielleicht kann ich für jede Gleichung eine Zeichenfolge erstellen und diese manuell in meiner rekursiven Funktion auswerten.

Zum Beispiel:
Ich beginne mit einer leeren Zeichenfolge im äußersten Funktionsaufruf:

""

Von dort aus erstelle ich drei Variationen mit der nächsten Nummer:

"" + "+N"
"" + "*N"
"" + "N"

Hmm, aber das funktioniert nicht für die erste Nummer.

Ich muss meinen ersten Funktionsaufruf mit der ersten Zahl beginnen, nicht mit einer leeren Zeichenfolge:

"N"

Das Gleiche von dort:

"N" + "+N"
"N" + "*N"
"N" + "N"

Ja, das sollte funktionieren.

Am Ende werde ich diese Beispielvariationen haben, alle auswertbar:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Weiter zu: Ich habe es programmiert ... und ein größeres Problem entdeckt

Ich habe Code geschrieben, der alle Gleichungsvarianten erfolgreich generiert.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

• Ich bin es gewohnt, die Liste der Zahlen durchzugehen
• Die letzte Klausel wird nur fortgesetzt, wenn i vor oder am vorletzten Index steht

Die Funktion erhält vier Werte:

1. Eine Kopie der Zahlenliste abzüglich der erwarteten Gesamtsumme
2. Der nächste Index
3. Die Gleichungszeichenfolge mit einer von drei daran verketteten Zeichenfolgen
4. Die gleiche Testnummer

Ich rufe die Funktion mit fast derselben Signatur wie in Teil 1 auf:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Der Unterschied besteht darin, was ich als Argumente übergebe:

1. Die Liste ohne den erwarteten Gesamtbetrag
2. Beginnen Sie bei Index 0
3. Eine Zeichenfolge, die die erste Zahl enthält
4. Der erwartete Gesamtbetrag

Tolle Neuigkeiten:

• Es generiert alle Gleichungsvarianten

Schlechte Nachrichten:

• Es wertet alle Gleichungen mit PEMDAS aus, nicht von links nach rechts

Ich hätte besser wissen müssen, dass der integrierte JavaScript-Evaluator standardmäßig die richtige Reihenfolge der Operationen verwendet, nicht von links nach rechts.

Das macht meinem Algorithmus wirklich noch mehr Probleme:

• Ich muss jede Gleichung zerlegen und Teil für Teil auswerten

Uggghhh.

Zum Glück glaube ich, dass ich genau weiß, wie das geht.

Manuell Mathe machen

Ich benötige JavaScript, um eine Gleichung wie diese auszuwerten:

292: 11 6 16 20

In dieser Reihenfolge:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Ich würde diese Gleichung gerne in ihre Teile aufteilen:

""

Das sehe ich nur mit diesem dreifach verketteten Ausdruck:

"" + "+N"
"" + "*N"
"" + "N"

Ich fülle jeden Operator mit Leerzeichen auf, nur um ihn als Trennzeichen zu verwenden.

Eine Tatsache zu dieser Liste von Gleichungsteilen:

• Es wird immer eine ungerade Anzahl an Artikeln enthalten, die 3 oder mehr beträgt

Wie kann ich diese Tatsache in einer Schleife nutzen, die jedes Operanden-Operator-Operanden-Paar durchläuft?

Hier ist meine Idee:

• Entfernen Sie die ersten drei Elemente
• Fügen Sie sie als Zeichenfolge zusammen und werten Sie diese als mathematischen Ausdruck aus
• Fügen Sie das Ergebnis wieder am Anfang der Gleichungsliste ein
• Wiederholen, bis die Gleichungsliste leer ist

Wir hoffen, dass es funktioniert!

Mein funktionierender Mathe-Simulator in JavaScript:

"N"

Tolle Neuigkeiten:

• Es zeigt mir die erwarteten berechneten Werte

Schlechte Nachrichten:

• Ich bekomme immer noch nicht die richtige Antwort für eine Gleichung in der Beispieleingabe

Die Beispielantwort kann nicht falsch sein ... oder??

Die Antwort, die ich immer wieder erzeuge, liegt etwa 7.000 unter der erwarteten Antwort.

Das lässt mich vermuten, dass mein Algorithmus diese Gleichung nicht als korrekt erkennt:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

In der Erklärung der Beispieleingabe ist dies die Erfolgsgleichung:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Mein Algorithmus wertet diese Gleichung aus und generiert dieses Ergebnis:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Das liegt daran, dass mein Algorithmus so läuft:

292: 11 6 16 20

Ich verstehe nicht, wie es eine andere Nummer sein könnte.

Also...ich habe gegoogelt.

Und ich habe meine Antwort gefunden, die wie immer in der Erklärung versteckt war:

Alle Operatoren werden weiterhin von links nach rechts ausgewertet.

Ich habe Werte bei jedem rekursiven Funktionsaufruf vorab verkettet.

Stattdessen sollte mein Algorithmus Folgendes tun:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Da ich nun verstehe, was passieren soll, kann ich meinen Algorithmus an dieses Verarbeitungsverhalten anpassen?

Von links nach rechts...diesmal wirklich

Zum Glück war die Anpassung meines Algorithmus relativ einfach.

Ich habe eine replaceAll()-Klausel hinzugefügt, um ||.

zu berücksichtigen

Die neue while-Schleife, in der ich alle drei Elemente verarbeite, sieht folgendermaßen aus:

""

Und ich habe die || meiner Rückgabeerklärung angepasst Klausel, um diese Zeichen einzuschließen, anstatt die beiden Zahlen sofort zu verketten.

Testen und erneut testen

Ich habe den Algorithmus für die Beispieleingabe ausgeführt.

Es endlich hat die richtige Antwort generiert!!

Was für eine Erleichterung!!

Ich frage mich, ob es zu Ende läuft und die richtige Antwort auf meine Rätseleingabe generiert.

Drücken Sie Ausführen...

...

...

Ich habe eine Antwort bekommen!

Es ist riesig, also ist das wahrscheinlich ein gutes Zeichen.

Ist es die richtige Antwort?

...

Nein. Zu hoch.

Mist.

Vermisse ich einen Randfall?

Meine Bedingung für eine erfolgreiche Gleichung ist einfach, dass die verarbeitete Mathematik der Testmenge entspricht.

Aber was ist, wenn eine der Variantengleichungen es zulässt, dass eine Teilmenge von Zahlen eine korrekte Antwort generiert?

Um dieses Szenario abzufangen und auszuschließen, habe ich meine if-Bedingung um eine weitere Klausel erweitert:

"" + "+N"
"" + "*N"
"" + "N"

Auf diese Weise wird die Gleichung nur gezählt, wenn alle Zahlen verarbeitet wurden und der resultierende Betrag der Testzahl entspricht.

Die große Frage:

• Ändert sich dadurch die Antwort, die ich bekomme?

Drücken Sie erneut „Ausführen“...

...

Hmm, es sieht auf jeden Fall immer noch nach der gleichen Antwort aus.

Oh, Moment, da sind am Ende zwei Ziffern, die unterschiedlich sind!

Meine neue Antwort ist genau 80 weniger als zuvor.

Gibt es eine Gleichung mit 80 als erwartetem Betrag?

Ja!

"N"

Gibt es eine Möglichkeit, 80 zu erreichen, ohne alle Zahlen zu verwenden?

Ja!

"N" + "+N"
"N" + "*N"
"N" + "N"

War dies der einzige Randfall, den ich ausschließen musste?

Ich sende meine neue Antwort...

ES IST RICHTIG!!!

Woohoo!!!

Ich habe es geschafft!!!

Das. War. Anstrengend. Und berauschend. Und wirklich laufen. Und herausfordernd.

Und alle Gründe, warum ich diese Rätsel liebe.

Weiter zum nächsten!

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