Dynamic Programming ist keine schwarze Magie

• Auch Probleme mit vielen Sonderfällen, wie Advent of Code 2023 Day 12, lassen sich mit Dynamic Programming angehen, wenn man eine Struktur erkennt, bei der dieselben Teilprobleme wiederholt gelöst werden
• Der Kern besteht darin, ein Problem rekursiv zu zerlegen, doppelte Berechnungen durch Memoization zu reduzieren und dies anschließend in eine iterative Berechnung zu überführen, bei der die benötigten Werte in der Reihenfolge ihrer Abhängigkeiten gefüllt werden
• Das Fibonacci-Beispiel zeigt, dass naive Rekursion f(1) wiederholt auswertet; mit Cache müssen jedoch nur n + 1 Werte von f(0) bis f(n) berechnet werden
• Levenshtein-Distanz und Advent of Code Day 12 zeigen, wie Zustandsindizes wie Stringlänge und Regelindex als Cache-Schlüssel dienen und rekursive Aufrufe in das Füllen eines Arrays überführt werden können
• Wer Dynamic Programming beherrscht, verbessert nicht nur die Performance, sondern erkennt auch die Zwischenzustände und Abhängigkeiten eines Algorithmus und findet leichter Möglichkeiten zur Speicheroptimierung

---

Der Name ist verwirrend, die Idee aber einfach

• Der Begriff „dynamic programming“ hat keinen direkten Bezug zu modernen Bedeutungen wie „Programmierstil“ oder „dynamische Typisierung“
• Im Kern geht es um eine Methode des Algorithmenentwurfs, bei der ein Problem in kleinere, ähnliche Probleme zerlegt und deren Ergebnisse wiederverwendet werden
• Es gibt eine redaktionelle Anmerkung, dass der Ausdruck Sinn ergibt, wenn man „programming“ in seiner historischen Bedeutung versteht
• Ausgangspunkt ist meist eine Form, die das Problem wie eine rekursive Funktion in kleinere Probleme zerlegt
• Wenn dieselben Teilprobleme mehrfach auftreten, entsteht ganz natürlich der Bedarf an Caching, um Berechnungsergebnisse zu speichern und erneut zu verwenden

Caching und Iteration am Beispiel Fibonacci

• Die Fibonacci-Funktion ist definiert als f(n) = f(n - 1) + f(n - 2), und eine naive rekursive Implementierung berechnet dieselben Werte immer wieder
• f(1) ist ein Wert, der tatsächlich zum Gesamtergebnis addiert wird; je größer f(n) wird, desto schneller steigt daher auch die Zahl der Auswertungen bei naiver Rekursion
• Wenn man Ergebnisse cached oder Memoization einsetzt, müssen bereits berechnete Werte wie f(4), f(3) und f(2) nicht erneut berechnet werden
• In diesem Ansatz werden von f(0) bis f(6) insgesamt nur 7 Werte ausgewertet; allgemein reduziert sich dies auf n + 1 Auswertungen
• Geht man noch einen Schritt weiter und füllt die benötigten Werte der Reihe nach ab f(0) und f(1), verschwinden die rekursiven Aufrufe
  • F[2] = F[1] + F[0]
  • F[3] = F[2] + F[1]
  • Auf dieselbe Weise wird bis F[6] = 8 gerechnet
• Bei Fibonacci braucht man nicht einmal das ganze Array; es genügt, den vorherigen und den davorliegenden Wert zu behalten
• Dieser Ablauf zeigt einen systematischen Weg von der mathematischen Definition hin zu einer iterativen Implementierung

Erweiterung am Beispiel der Editierdistanz

• Die Editierdistanz zweier Strings ist die minimale Anzahl von Bearbeitungsschritten, die nötig ist, um einen String in den anderen umzuwandeln
• Je nach erlaubten Bearbeitungen ändert sich das Problem
  • Sind nur Zeichenersetzungen erlaubt, handelt es sich um die Hamming distance
  • Sind auch Einfügen und Löschen erlaubt, handelt es sich um die Levenshtein distance
• Die Levenshtein-Distanz lässt sich anhand der letzten Zeichen der beiden Strings A und B in kleinere Probleme zerlegen
  • Wenn die letzten Zeichen gleich sind, ignoriert man beide Zeichen und verwendet die Distanz der übrigen Strings
  • Wenn die letzten Zeichen unterschiedlich sind, wählt man die minimalen Kosten aus Ersetzen, Löschen und Einfügen
  • Wenn A leer ist, müssen alle Zeichen von B eingefügt werden, die Kosten betragen also b
  • Wenn B leer ist, müssen alle Zeichen von A gelöscht werden, die Kosten betragen also a
• Überträgt man diese Definition direkt in eine rekursive Python-Implementierung, wird sie bei langen Strings und Strings mit vielen Unterschieden sehr langsam
• Während Fibonacci sich in jedem Schritt des Aufrufbaums ungefähr in zwei Zweige aufteilt, kann sich diese Rekursion je nach Fall in drei Zweige aufteilen
• Mit Pythons functools.cache lassen sich die Berechnungsergebnisse gleicher Teilstring-Kombinationen wiederverwenden
• Eine bessere Implementierung erzeugt nicht ständig neue Strings, sondern übergibt nur die ursprünglichen Strings A, B sowie die Teilstringlängen a und b
• Im letzten Schritt erstellt man direkt ein zweidimensionales cache-Array und füllt es der Reihe nach so, dass cache[a][b] = levenstein(A[:a], B[:b]) gilt
• Die iterative Version läuft a und b von 0 bis zur jeweiligen Stringlänge durch und referenziert dabei Werte aus der bereits gefüllten vorherigen Zeile und vorherigen Spalte

Anwendung auf Advent of Code 2023 Day 12

• Die Aufgabe vom 12. Dezember 2023 bei Advent of Code besteht darin, ein eindimensionales Nonogram zu lösen
• Eine Beispieleingabe hat die Form .??..??...?##. 1,1,3; ? kann dabei zu . oder # werden
• Ein Brute-Force-Ansatz verwendet Backtracking, doch bei n Fragezeichen müssen 2^n Kandidaten ausgewertet werden, was exponentiell wächst
• Es zeigt sich eine Struktur, in der dieselben Teilprobleme wiederkehren
  • ..#..??...?##. (1),1,3
  • .#...??...?##. (1),1,3
  • Verwirft man den bereits verarbeiteten vorderen Teil, entstehen fast identische Probleme wie .??...?##. 1,3 bzw. ..??...?##. 1,3
• Die grundlegende Backtracking-Funktion erhält conditions und rules und berechnet die Anzahl möglicher Anordnungen
  • Wenn keine Regeln mehr übrig sind, prüft sie, ob in den verbleibenden Bedingungen noch ein # vorkommt
  • Wenn keine Bedingungen mehr übrig sind, prüft sie, ob noch Regeln übrig sind
  • Wenn das aktuelle Zeichen . oder ? ist, rechnet sie eine Position weiter
  • Wenn das aktuelle Zeichen # oder ? ist, prüft sie die Größe der nächsten Regel und die Separator-Bedingung und wechselt dann in den nächsten Zustand
• In Python reicht es, @cache hinzuzufügen, um Memoization anzuwenden
• Um dies in Dynamic Programming zu überführen, schneidet man Strings und Regeln nicht mehr zurecht, sondern verwendet den String-Offset i und den Regel-Offset j als Zustand
• Anschließend erstellt man cache[i][j] direkt und ersetzt die Rekursion durch iterative Berechnung, indem man die Indizes in umgekehrter Reihenfolge füllt
• Ein Beispiel für eine Rust-Implementierung ist im Artikel über den Link Rust implementation verfügbar

Was sichtbar wird, wenn man den Cache selbst füllt

• Die Dynamic-Programming-Version von Advent of Code Day 12 kann langsamer wirken als die Memoization-Version
• Dieser Unterschied liegt möglicherweise an einer nicht optimierten Python-Implementierung
• Wenn man den Cache selbst aufbaut, sieht man besser, welche Werte tatsächlich benötigt werden
• Bei Day 12 lässt sich über die Dynamic-Programming-Version erkennen, dass nur die vorherige Spalte benötigt wird
• Daher kann man das zweidimensionale Array durch zwei eindimensionale Arrays ersetzen, die die vorherige und die aktuelle Spalte darstellen

Übungsaufgaben und Fazit

• Dynamic Programming ist nicht trivial, aber für die meisten Programmierer keine unzugängliche Technik
• Wenn man versteht, wie sich ein Problem in kleinere Probleme zerlegen lässt, kann bereits Memoization in vielen Situationen eine naive Implementierung deutlich verbessern
• Mit mehr Übung versteht man eine ganze Familie von Algorithmen, kann Trade-offs besser einschätzen und zusätzliche Optimierungen finden
• Als Übungsaufgaben werden folgende Probleme genannt
  • longest common subsequence
  • line wrap
  • subset sum
  • partition
  • knapsack
• Nach der Implementierung sollte man Benchmarks und Profiling nicht vergessen

[GN⁺]

Meinungen auf Hacker News

• Mir gefällt, dass der Artikel herausstellt, dass Algorithmen der dynamischen Programmierung letztlich nur eine clevere Methode sind, Rekursion zu cachen. Meiner Erfahrung nach ist es der beste Ausgangspunkt für eine DP-Lösung, zuerst eine rekursive Lösung zu finden; wenn man sie einmal hat, ist Memoization einfach und kann einen großen Geschwindigkeitsschub bringen.
  Manchmal ist das sogar schneller als Bottom-up-DP, weil nur die tatsächlich benötigten Lösungen berechnet werden. Entscheidend ist: Es ist in Ordnung, wenn der Aufrufbaum viele Teilprobleme enthält, aber die Zahl der verschiedenen Teilprobleme muss vergleichsweise klein sein. Es gibt keinen Grund, Ergebnisse zu cachen, die nur einmal gebraucht werden, und die Schwierigkeit besteht darin, das ursprüngliche Problem in hinreichend wenige verschiedene Teilprobleme zu zerlegen.

  • Der Punkt, dass es vergleichsweise wenige verschiedene Teilprobleme geben muss, ist der Kern. Ob der Gesamtalgorithmus rekursiv oder iterativ ist, ist zweitrangig; dynamische Programmierung zeigt sich meist häufiger bei rekursiven Algorithmen.
  • Die Erklärung „dynamische Programmierung ist eine Methode, Rekursion zu cachen“ war für mich genau der Moment, in dem es Klick gemacht hat. An der Uni wirkten die Beispiele aus dem Lehrbuch zum Bottom-up-Ausfüllen von Tabellen wie Magie, vermutlich weil damals prozedurale Programmierung vorherrschend war.
    Praktisch gesehen ist das sinnvoll, weil Tail-Call-Eliminierung nicht immer greift; ich hätte es aber lieber zuerst aus der intuitiveren Perspektive einer Top-down-Rekursion mit Cache gelernt.
  • Als ich es zum ersten Mal gelernt habe, dachte ich, wenn das so eine schicke Technik ist, sollte man sie doch eher Array-Memoization oder Call-Stack-Memoization nennen. Den Namen „dynamische Programmierung“ hätte man sich für etwas Besseres aufheben sollen.
  • Dynamische Programmierung nur als memoized recursion zu sehen, halte ich für ein weit verbreitetes Missverständnis. Wenn man es so lernt, wird es sehr schwer, DP-Probleme vom Typ zweidimensionales Array ausfüllen zu verstehen.
    Schaut man sich zum Beispiel die LeetCode-Reihe „Best Time to Buy and Sell Stock“ an, wirkt bei einem Problem wie https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... das Ausfüllen eines Arrays deutlich natürlicher. Ich habe es nie rekursiv gelöst und weiß auch nicht recht, ob es dafür eine natürliche rekursive Lösung gibt.
    Der obige Link ist zwar zu III, aber wer neu damit anfängt, sollte mit dem ersten Problem https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... beginnen; das eignet sich gut als Einstieg in dynamische Programmierung.
  • Zu sagen „dynamische Programmierung ist einfach Caching/Memoization“ ist ungefähr so, als würde man sagen: „Investieren heißt einfach, etwas zu kaufen und später wieder zu verkaufen.“ Technisch mag das bis zu einem gewissen Grad stimmen, aber es lässt so viel von der Komplexität und Schwierigkeit des Themas aus, dass es eher lächerlich als aufschlussreich wirken kann.

• Der Ursprung des Namens „dynamische Programmierung“ geht auf den Erfinder Richard Bellman zurück. 1950 suchte er bei RAND nach einem Namen für mehrstufige Entscheidungsprozesse; der damalige Verteidigungsminister Wilson soll das Wort „Forschung“ krankhaft gehasst haben, und „Mathematik“ sollte man erst recht vermeiden.
  Bellman brauchte innerhalb von RAND einen Namen, der gegenüber Wilson und der Air Force verschleierte, dass er in Wirklichkeit Mathematik betrieb. Da es um Planung, Entscheidungen und Denken ging, „planning“ aber aus verschiedenen Gründen ungünstig war, wählte er „programming“; um das Konzept mehrerer Stufen und zeitlicher Veränderung einzufangen, setzte er „dynamic“ davor, das in der klassischen Physik eine genaue Bedeutung hat.
  Ihm gefiel auch, dass „dynamic“ als Adjektiv schwer negativ zu verwenden ist, und weil selbst ein Abgeordneter kaum etwas gegen diesen Namen haben konnte, verwendete er dynamic programming als Sammelbezeichnung für seine Tätigkeit.
  Quelle: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

• Mir gefällt, dass der Artikel das Problem zuerst rekursiv herausarbeitet, dann schrittweise Caching hinzufügt und am Ende die Cache-Größe auf das Nötige reduziert.
  Ich bin oft direkt auf eine DP-Lösung losgegangen und stecken geblieben oder habe mich verrenkt, um sie zum Laufen zu bringen. Künftig will ich mich selbst dazu zwingen, die Schritte der Reihe nach zu gehen.

  • Meiner Erfahrung nach fühlt sich dynamische Programmierung wie ein Puzzle an, wenn man sie direkt unterrichtet. Wenn man die Schritte durchgeht, erklärt, warum man eine Tabelle verwendet, und das Konzept mit Caching verknüpft, wird es viel verständlicher.

• Eine schöne Anwendung dynamischer Programmierung ist das paarweise Alignment von Nukleotid-/Proteinsequenzen.
  https://en.wikipedia.org/wiki/Sequence_alignment
  https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
  https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

  • Ich halte diese Algorithmen für einige der wichtigsten in der Bioinformatik/Biologie. Ihr Anwendungsbereich ist sehr breit.

• Ich hatte einen sehr guten Algorithmik-Professor, der an der UCLA studiert hatte. Seine Vorlesung zu dynamischer Programmierung war hervorragend: Er begann mit einem Problem, bei dem die einfache Lösung exponentielle Zeitkomplexität hatte, zerlegte das Problem dann in kleinere Probleme, um die Komplexität auf polynomielles Niveau zu senken, und wandte anschließend Memoisierung an, wodurch sie auf linear fiel.
  Ich wünschte, ich könnte mich erinnern, welche Probleme er damals verwendet hat.

  • Kandidaten wären die Fibonacci-Folge, das Münzwechselproblem, das 0/1-Rucksackproblem, Matrixkettenmultiplikation, längste gemeinsame Teilsequenz, längste steigende Teilsequenz, kürzeste-Wege-Probleme wie Floyd-Warshall sowie Editierdistanz (Levenshtein-Distanz).
    Alles typische Beispiele, bei denen eine naive Lösung ineffizient ist und dynamische Programmierung große Verbesserungen bringt.
  • Im Artikel sind ebenfalls einige aufgeführt; es sind Probleme, die man häufig in Vorlesungen oder Übungen sieht. Zum Beispiel längste gemeinsame Teilsequenz, längster gemeinsamer Teilstring, Line Warp, Teilmengensumme, Partitionierung und Rucksackproblem.
    Weitere Beispiele gibt es unter https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms....
  • Neben den von anderen genannten Problemen könnte es auch ein Scheduling-Problem gewesen sein. Also etwa N zeitlich überlappende Events, Stundenpläne oder CPU-Prozesse, die nach Kriterien wie Durchsatz optimiert werden sollen.
    Soweit ich weiß, wird es deutlich komplexer und schwieriger zu handhaben als gewöhnliche dynamische Programmierung, wenn man spezielle Nebenbedingungen hinzufügt, etwa „diese beiden Kurse müssen gemeinsam belegt werden“.
  • War das jemand, der an der UCLA bei Kang studiert hat?

• Die Originalseite scheint dem Traffic nicht standzuhalten, daher hier ein Archiv-Link:
  https://web.archive.org/web/20240114111200/https://qsantos.f....

• Dank dynamischer Programmierung konnte die Zahl legaler Go-Stellungen berechnet werden; sie war eine Zahl mit 171 Stellen.
  Der naive Ansatz betrachtet alle möglichen Stellungen auf einem n×n-Go-Brett und braucht dafür 3^(n^2) Zeit, aber dynamische Programmierung entfernt im Grunde eine Dimension und reduziert die Zeitkomplexität auf O(n^5 * 5.4^n) und die Speicherkomplexität auf O(n * 5.4^n).
  https://tromp.github.io/go/legal.html
  https://tromp.github.io/go/gostate.pdf

• Der Name „Dynamic Programming“ kann seltsam wirken, weil „programming“ hier nicht das Fachgebiet Programmieren meint. In diesem Fall hat es, ähnlich wie bei linearer Programmierung, eher die Bedeutung von Optimierung.
  Dynamische Programmierung kann man als Methode sehen, um Entscheidungsprobleme in diskreter Zeit zu lösen: also unter Nebenbedingungen die optimale Folge {a_t} zu wählen, die \sum_t u_t(a_t) maximiert. Man definiert die Wertfunktion V* als V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } und reduziert so die Dimensionalität des Optimierungsproblems erheblich.

  • Tatsächlich ist die offizielle Herkunft des Namens https://en.wikipedia.org/wiki/Dynamic_programming#History ziemlich amüsant. Bellman soll „dynamic“ gut gefunden haben, weil es ein Adjektiv sei, das unmöglich negativ verwendet werden könne, und er hielt es für einen Namen, gegen den nicht einmal ein Abgeordneter etwas einwenden könne.
  • Wenn andere Leute „dynamische Programmierung“ sagen, wirkt es manchmal wie Angeberei, um besonders klug zu erscheinen. In Wirklichkeit nutzt man nur einen natürlichen und intuitiven Ansatz, sobald man erkennt, dass sich ein Problem in immer kleinere Teilprobleme zerlegen lässt, redet aber so, als hätte man eine besondere Technik „eingesetzt“.
  • Interessant ist, dass früher das Berechnen von Dingen, etwa bei Optimierungsproblemen, in den Vorstellungen davon, was man mit Computern macht, viel dominanter war. Heute geht es meistens um Datenspeicherung, Abfragen und Networking; selbst wenn darin Berechnungen vorkommen, wirken sie meist gut gekapselt.
  • Auch der Begriff „Optimierung“ führt ähnlich leicht zu Missverständnissen. Ich habe einmal einen Informatikkurs namens „optimization“ belegt und dabei etwas völlig anderes erwartet.
  • Geht man noch weiter zurück, beschreibt „programming“ dieses Konzept ziemlich genau. Was wir heute „Programmieren“ nennen, ist eigentlich Code schreiben und lässt sich in verschiedene Arten von Programmierung wie funktionale, deklarative oder prozedurale Programmierung einordnen. Unter diesem Dach steckt noch deutlich mehr.

• Ist es falsch, bei „dynamischer Programmierung“ einfach an Memoisierung zu denken? Der fehlende Teil könnte darin bestehen, das Problem geschickt zu zerlegen, damit man Memoisierung einsetzen kann

  • Memoisierung ist eine allgemeinere Technik. Oft bedeutet sie nur, bereits berechnete Ergebnisse für den Fall zu cachen, dass man sie später wieder braucht
    Dynamische Programmierung ist eher systematische Memoisierung. Man löst immer größere Teilprobleme, bis man zur Lösung des Gesamtproblems gelangt. Der Begriff „Induktionsalgorithmus“ würde bis zu einem gewissen Grad ebenfalls passen, denn ein typischer Algorithmus der dynamischen Programmierung ähnelt im Grunde einem Beweis per mathematischer Induktion. Leider hat dieser Begriff bereits andere Bedeutungen
  • Genau so unterrichte ich dynamische Programmierung. Zuerst löst man das Problem rekursiv und fügt dann Memoisierung hinzu. Das nennt man Top-down
    Danach sieht man, dass Rekursion und Memoisierung Overhead haben; wenn man die Tabelle von unten nach oben aufbaut und die rekursiven Aufrufe entfernt, wird daraus dynamische Programmierung
  • In meinem Ansatz ist Memoisierung Schritt 2 von 3 der dynamischen Programmierung. Schritt 1 ist, einen rekursiven Algorithmus zu finden, Schritt 2 ist Memoisierung, Schritt 3 ist, ihn iterativ/Bottom-up zu machen, und wenn möglich folgt als 3b eine Speicheroptimierung
    Schritt 3 ist der charakteristischste Teil der dynamischen Programmierung, aber ich denke, auch wenn man bei Schritt 2 stehen bleibt, kann man es dynamische Programmierung nennen. Es ist dann nur nicht so effizient, wie es sein könnte. Anders gesagt: Memoisierung ist Caching, und Schritt 3 fragt, ob es eine Möglichkeit gibt, diesen Cache im Voraus zu füllen
  • Es gibt auch Lösungen mit dynamischer Programmierung, die nicht auf Memoisierung basieren. Beim Finden des längsten gemeinsamen Teilstrings zweier Strings braucht man zum Beispiel die linke und obere Zelle der Tabelle jeweils nur einmal, daher hilft Memoisierung nicht besonders
    Allgemein gilt: Wenn sich Teilprobleme stark überlappen und optimale Teilprobleme Bestandteil der global optimalen Lösung sein müssen, gibt es eine Chance für dynamische Programmierung. Zu sagen, Memoisierung allein sei dynamische Programmierung, ist ungefähr so, als würde man sagen, nur Hash-Tabellen seien abstrakte Datentypen
  • Nach meinem Verständnis ist diese Sichtweise falsch. Zunächst gibt es das offensichtliche Gegenbeispiel, dass Memoisierung auch außerhalb der dynamischen Programmierung eingesetzt werden kann. Umgekehrt lassen sich die meisten Algorithmen der dynamischen Programmierung so implementieren, dass Ergebnisse in einer Tabelle gespeichert und später die beste Antwort aus dieser Tabelle gefunden wird
    Memoisierung ist im Kern eine Strategie, um Algorithmen schneller zu machen

• Es hat Spaß gemacht, den diesjährigen Advent of Code abzuschließen. Es war klar, dass Tag 1, insbesondere Teil 2, deutlich schwieriger war als in früheren Jahren, und ich habe darüber auch unter https://blog.singleton.io/posts/2024-01-02-advent-of-code-20... geschrieben, aber allein der Vergleich der aktuellen Statistiken von 2022 mit den aktuellen Statistiken von 2023 macht das nicht eindeutig. Denn die Rätsel von 2022 hatten ein Jahr mehr Zeit, von Leuten gelöst zu werden
  Als ich die 2022-Statistiken vom 14. Januar 2023 https://web.archive.org/web/20230114172513/https://adventofc... herangezogen habe, war der Unterschied ziemlich groß. Zeichnet man die Abschlussstatistik für Teil 2 https://blog.singleton.io/static/imgs-aoc23/completion.png, war die Größe der Startgruppe an Tag 1 ähnlich, aber 2023 wirkt bis Tag 15 eindeutig schwieriger als 2022
  Auch der Anteil der Personen, die Teil 1 gelöst, aber Teil 2 nicht geschafft haben https://blog.singleton.io/static/imgs-aoc23/ratios.png, ist 2023 an vielen Tagen deutlich höher und deutet insbesondere darauf hin, dass Tag 5, Tag 10, Tag 12 und Tag 22 Teil 2 schwierig waren

  • Die frühen Jahre von Advent of Code haben Spaß gemacht, und bis vor den späteren Tagen konnte man auch ohne große Techniken gut durchhalten. Später wurde es schwieriger und weniger unterhaltsam, also habe ich aufgegeben und seitdem nicht mehr weitergemacht
  • Beim diesjährigen Advent of Code bin ich aus Zeitmangel nicht weit gekommen, aber vielleicht versuche ich es später noch einmal
    Allerdings war ich überrascht, wie schwierig Tag 5 Teil 2 war. Ich habe ihn zwar gelöst, ohne aufzugeben, dachte aber, ich hätte vielleicht etwas Offensichtliches übersehen und die Lösung unnötig kompliziert gemacht. Zu erfahren, dass es tatsächlich eine recht anspruchsvolle Aufgabe war, war beruhigend
  • Das ist nur meine persönliche Erfahrung, und es mag auch daran liegen, dass ich es in einer anderen Sprache als meiner üblichen versucht habe, aber Tag 1 Teil 2 fand ich weniger schwierig als vielmehr schlecht beschrieben
    Als Beispiele wurden two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen angegeben, aber ein zentrales Beispiel wie oneight fehlte. Ohne solche Beispiele ist es schwer, genau herauszufinden, wie die Werte ersetzt werden sollen
  • Ergänzend zu dieser Diskussion: Ich habe ein Skript, das den Fortschritt pro Tag betrachtet. Die letzten beiden Spalten zeigen, wie gnadenlos 2023 im Vergleich zu 2022 war, besonders am Anfang
    2022 blieben in den ersten Tagen die meisten weiter dabei, an vielen Tagen lag die Retentionsrate über 80 %, und fast alle lösten beide Teile. Dagegen schafften an Tag 1 im Jahr 2023 nur 76 % derjenigen, die Teil 1 gelöst hatten, auch Teil 2, und an Tag 3 und Tag 5 gaben viele auf
    Interessanterweise sind die letzten Tage nicht so niedrig, was sich damit erklären lässt, dass Advent of Code 2023 aktueller ist als 2022. Meine Interpretation ist, dass diese Gruppe aus Leuten besteht, die unabhängig vom Schwierigkeitsgrad bis zu einem gewissen Punkt alle Herausforderungen meistern, während viele andere aufhören, wenn sie das Gefühl haben, dass es zu viel Zeit kostet