Einführung des Code-Day-Leinenlayouts

Tag 19: Leinenlayout

GitHub-Lösung

Die heutige Herausforderung war eine erfrischende Abwechslung zu den üblichen 2D-Rätseln und Dijkstras Algorithmen. So bin ich vorgegangen:

Teil 1

Das Ziel war einfach: Prüfen Sie, ob die vorgegebenen Handtuchanordnungen mit den verfügbaren Handtüchern erstellt werden können.

Was Sie NICHT tun sollten:

Zunächst habe ich versucht, alle möglichen Handtuchkombinationen mit itertools.combinations zu generieren. Es wurde schnell klar, dass dies weder praktisch noch effizient war.

Was hat funktioniert:

Verwendung von Rekursion in Kombination mit einem Wörterbuch (Memo), um bereits verarbeitete Designs zwischenzuspeichern. Dies verhindert redundante Berechnungen und macht die Lösung wesentlich effizienter.

So funktioniert es:

Versuchen Sie bei jedem Design, den Anfang mit einem der Handtuchmuster abzugleichen.
Wenn es eine Übereinstimmung gibt, entfernen Sie den übereinstimmenden Teil und rekursieren Sie für den Rest.
Verwenden Sie Memo, um Ergebnisse für Designs, die wir bereits überprüft haben, zwischenzuspeichern und so doppelte Arbeit zu vermeiden.
Der rekursive Ansatz mit Memoisierung hält die Komplexität auch bei größeren Eingaben beherrschbar und sorgt dafür, dass die Lösung effizient läuft.

Teil 2
Der zweite Teil ging noch einen Schritt weiter: Zählen Sie die Anzahl der Möglichkeiten, jedes Handtuchdesign anhand der verfügbaren Muster herzustellen.

Wichtige Erkenntnisse:
Die Funktion count_arrangements erweitert die rekursive Logik aus Teil 1, berechnet nun aber alle möglichen Wege zum Aufbau eines Designs.

Für jedes passende Handtuch wiederholen Sie den Rest des Designs.
Verwenden Sie ein anderes Wörterbuch (memo_count), um Ergebnisse für zuvor gelöste Teilprobleme zwischenzuspeichern.

Beispiel:
Wenn „brgr“ auf zwei Arten erstellt werden kann, geben wir einfach 2 aus dem Cache zurück, anstatt es neu zu berechnen.

Optimierung:
Dank Teil 1 wissen wir bereits, welche Designs möglich sind. Wir berechnen nur Arrangements für diese.

for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

Indem wir alle gültigen Möglichkeiten zusammenfassen, erhalten wir ganz einfach die endgültige Antwort für Teil 2.

Wie gesagt, die heutige Herausforderung hat mir sehr viel Spaß gemacht und war eine schöne Abwechslung. Ich hoffe, dieser Artikel hat bei zukünftigen Herausforderungen/Codierungen geholfen.

Folgen Sie mir wie immer gerne oder kontaktieren Sie mich auf Twitter

Das obige ist der detaillierte Inhalt vonEinführung des Code-Day-Leinenlayouts. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!