Wie man eine Brücke repariert, Advent of Code, 7

Nach einer gefühlten Ewigkeit (fünf Stunden, um genau zu sein) entschied sich Tag 20 Teil 2 schließlich zur Zusammenarbeit. Ich bin immer noch etwas benommen vom Warten, aber die Pflicht ruft! Heute befassen wir uns mit Tag 7 von Advent of Code und machen dort weiter, wo wir letzte Woche mit Tag 6 aufgehört haben. Unsere heutige Aufgabe besteht darin, eine Brücke zu reparieren, damit wir sie überqueren und unsere Suche nach dem Chefhistoriker fortsetzen können.

Eine niedliche Illustration, erstellt von Microsoft Copilot

Die heutige Herausforderung stellt uns vor ein ganz anderes Problem: Wir erhalten Listen mit Zahlen, die in einem bestimmten Format angeordnet sind (zum Glück heute kein 2D-Puzzle …). Jede Zeile soll eine Gleichung bilden, die Operatoren fehlen jedoch. Unsere Aufgabe besteht darin, verschiedene Operatoren zu testen, um festzustellen, ob die resultierende Gleichung wahr ist.

Wir verwenden zwei Parsing-Funktionen, um die Eingabe zu verarbeiten. Die Analysefunktion teilt zunächst jede Zeile durch das Doppelpunktzeichen (:) auf:

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

parse_line konvertiert die erwartete Zeichenfolge und die Operandenfolge in Ganzzahlen und gibt ein Tupel zurück, das die erwartete Ganzzahl und ein Tupel ganzzahliger Operanden enthält

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Ich bevorzuge einen funktionalen Programmierstil und trotz des zwingenden Charakters von Python sind Bibliotheken wie toolz/cytoolz unglaublich nützlich. Heute verwenden wir thread_first von toolz.functoolz. So funktioniert thread_first: Es nimmt einen Anfangswert und wendet dann eine Folge von Funktions-Argument-Paaren an, wobei das Ergebnis durch jeden Schritt geleitet wird.

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

In diesem Beispiel beginnt thread_first mit 1, wendet dann add mit 2 an (was zu 3 führt) und wendet schließlich mul mit 2 an (was zu 6 führt). Dies entspricht mul(add(1, 2), 2).

Wir definieren nun die Berechnungsfunktion, um die Operationen anzuwenden. Es benötigt ein Tupel von Funktionen (funcs) und ein Tupel von Operanden (operands) als Eingabe:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

Die Behauptung stellt einen Operanden mehr als Funktionen sicher. operands[1:] stellt die Operanden für die Funktionen bereit. zip und * erstellen die Funktions-Operanden-Paare für thread_first, das die verketteten Berechnungen durchführt.

Beispiel:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Jetzt können wir jede Zeile der Eingabe mit der Funktion check_can_kalibrieren überprüfen. Diese Funktion verwendet das erwartete Ergebnis, die Operanden und ein Tupel möglicher Funktionen als Eingabe und gibt „True“ zurück, wenn eine Kombination von Funktionen das erwartete Ergebnis liefert, andernfalls „False“:

def check_can_calibrate(
    expected: int,
    operands: tuple[int, ...],
    funcs: tuple[Callable[[int, int], int], ...],
) -> bool:
    return next(
        filter(
            None,
            (
                calculate(funcs, operands) == expected
                for funcs in product(funcs, repeat=len(operands) - 1)
            ),
        ),
        False,
    )

itertools.product generiert alle Funktionskombinationen. Ein Generatorausdruck prüft, ob eine Kombination mit dem erwarteten Ergebnis übereinstimmt. filter(None, ...) und next(..., False) finden effizient das erste True-Ergebnis oder geben False zurück, wenn keines gefunden wird.

Für Teil 1 erhalten wir nur Multiplikations- und Additionsoperatoren. Das Rätsel fragt nach der Summe der erwarteten Werte, wobei mit diesen Operatoren eine gültige Gleichung gebildet werden kann. Wir implementieren die Evaluierungsfunktion, um diese Summe zu berechnen:

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

Es durchläuft die analysierte Eingabe und summiert die erwarteten Werte, für die check_can_kalibrate „True“ zurückgibt.

Zuletzt bauen wir Teil 1 aus dem zusammen, was wir bisher bereits gebaut haben

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Diese Funktion analysiert die Eingabe mithilfe von „parse“ und ruft dann „evalue“ mit den analysierten Daten und dem Tupel von Funktionen (operator.mul, Operator.add) auf, die jeweils Multiplikation und Addition darstellen.

In Teil 2 begegnen wir einem Verkettungsoperator, der zwei Zahlen miteinander verbindet. In Python entspricht dies der Verwendung eines F-Strings:

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

Dadurch wird effektiv eine neue Nummer erstellt, indem die Ziffern der zweiten Nummer an das Ende der ersten Nummer angehängt werden.

Alternativ können wir die Verkettung mithilfe einer mathematischen Formel durchführen. Die Anzahl der Ziffern in einer positiven ganzen Zahl x kann mit der Formel berechnet werden:

Das funktioniert, weil log₁₀(x) die Potenz angibt, um die 10 erhöht werden muss, um x zu erhalten. Die Floor-Funktion rundet dies auf die nächste ganze Zahl ab und die Addition von 1 ergibt die Anzahl der Ziffern. Nehmen wir als Beispiel 123:

Implementierung als int_concat-Funktion:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

Durch die mathematische Durchführung der Ganzzahlverkettung wird der Mehraufwand für String-Konvertierungen vermieden. Die Verkettung von Zeichenfolgen umfasst die Speicherzuweisung und -manipulation, was weniger effizient ist als die direkte Ganzzahlarithmetik, insbesondere bei großen Zahlen oder vielen Verkettungen. Dieser mathematische Ansatz ist daher im Allgemeinen schneller und speichereffizienter.

Zuletzt implementieren wir Teil 2. Der einzige Unterschied zu Teil 1 ist die Hinzufügung des int_concat-Operators:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Ta-da! Wir haben Tag 7 gemeistert. Dies war eine relativ einfache Herausforderung, insbesondere im Vergleich zu den späteren Tagen (die Optimierung an Tag 20 bereitet mir immer noch Kopfschmerzen?). Obwohl es vielleicht nicht die leistungsstärkste ist, habe ich der Lesbarkeit Priorität eingeräumt.

Das ist alles für heute. Frohe Feiertage und ein frohes neues Jahr?! Wir drücken die Daumen für eine bessere Arbeitssituation im nächsten Jahr (immer noch #OpenToWork, pingen Sie mich für Kooperationen an!), und ich werde nächste Woche wieder schreiben.

Das obige ist der detaillierte Inhalt vonWie man eine Brücke repariert, Advent of Code, 7. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!