Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day12:start [12.12.2023 18:45] – angelegt Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aco2023:day12:start [15.12.2023 18:42] (aktuell) – Marco Kuemmel
@@ Zeile 59: / Zeile 59: @@
 ===== Teil 2 =====
-Teil 2 ist definitiv nicht trivial. Beide einfachen Ansätze aus Teil 1 genügen hier nicht mehr, da mehrere Milliarden Kombinationen durchprobiert werden müssten! Man wird sich wohl z. B. die "dynamische Programmierung" zunutze machen müssen. Damit speichert man für jeden rekursiven Methodenaufruf dessen Ergebnis, bevor es als ''return'' zurückgegeben wird. Dann kann man zu Beginn jedes Aufrufs dieser Methode bei gegebenen Parametern überprüfen, ob diese Parameter schon einmal aufgerufen wurden und man dazu direkt das Ergebnis liefern kann. //(Mangels Zeit konnte ich leider keine Lösung finden, die mit der dynamischen Programmierung funktioniert.)//
+//Mit 3 Tagen Verspätung nun auch endlich eine ausformulierte Lösung für Teil 2... (danke an Frank Schiebel für den Impuls 😊)//\\
+Teil 2 ist definitiv nicht trivial. Beide einfachen Ansätze aus Teil 1 genügen hier nicht mehr, da (je nach Eingabedatei) etwa 1,6 Billionen (!) Kombinationen durchprobiert werden müssten! Man muss sich daher dringend die "dynamische Programmierung" zunutze machen. Damit speichert man für jeden rekursiven Methodenaufruf dessen Ergebnis, bevor es als ''return'' zurückgegeben wird. Dann kann man zu Beginn jedes Aufrufs dieser Methode bei gegebenen Parametern überprüfen, ob diese Parameter schon einmal aufgerufen wurden und man dazu direkt das Ergebnis liefern kann.
+  * Rufe pro Eingabezeile eine rekursive Methode ''getMatches()'' auf, die zwei Parameter entgegennimmt. Erstens die 5-fach hintereinander gehängten linken Strings. Zweitens die 5-fach hintereinander gehängten Zahlen als int-Array.
+  * Die Methode ''getMatches()'' soll nun für den jeweils übergebenen (noch vorhandenen) Eingabestring und die verbleibenden Zahlen zurückgeben, wie viele Kombinationen möglich sind. Die Grundidee ist, den Eingabestring vorne immer weiter zu kürzen (ebenso die Zahlen) und rekursiv dieselbe Methode wieder mit verkürztem String aufzurufen. Dabei wird immer nur das vorderste Zeichen überprüft und beim Vorkommnis eines ''?'' kann es passieren, dass die Methode sich rekursiv aufsplittet in zwei Methoden - dadurch kommen die gigantisch großen Kombinationsmöglichkeiten zustande. Wie funktioniert die Methode nun im Detail?
+    * Der ganz entscheidende Punkt ist es, direkt zu Beginn innerhalb der Methode zu prüfen, ob die rekursive Methode bereits mit denselben Parametern aufgerufen wurde. Man speichert sich für jeden Parameter unmittelbar vor dem ''return'' den Rückgabewert und kann damit später direkt zum Einstieg in die Methode prüfen, ob nun wieder rekursiv zig Unter-Varianten geprüft werden müssen, oder ob direkt das bereits zuvor berechnete Ergebnis zurückgegeben werden kann. Dies nennt sich __dynamische Programmierung__, ein unheimlich mächtiges Programmierverfahren.
+    * Eine gute Datenstruktur dazu ist die ''HashMap'' in Java, welche über ''import java.util.HashMap;'' eingebunden werden muss. Dies ist eine **key-value-Datenstruktur**: Das bedeutet, dass man über einen (Such-)Key einen (Daten-)Wert finden kann. Prinzipiell ist es ein wenig mit einem Array bzw. einer ArrayList vergleichbar: dort findet man "für" einen Index einen Wert. Allerdings kann der Key (≈ Index) bei HashMaps gänzlich flexibel sein und muss __nicht__ den aufsteigenden Indizes genügen. Vielmehr bastelt man sich direkt zu Beginn des Methodenaufrufs den Key direkt als String aus den beiden Methodenparametern zusammen.
+    * Wurde der Key bisher noch __nicht__ in die HashMap eingetragen, dann muss man sich zuerst um die Abbruchbedingungen kümmern. Davon gibt es mehrere, u. a.:
+      * Genügt die Anzahl an String-Buchstaben um alle Zahlen-Vorkommnisse im besten Falle unterzubringen?
+      * Ist der String empty?
+      * Gibt es keine Zahlen mehr, sodass keine "Matches" mehr möglich sind ?
+    * Anschließend muss in Abhängigkeit des __ersten__ Characters vom String vielfach unterschieden werden. Je nachdem, ob der erste Buchstabe ein ''.'', ein ''?'' oder ein ''#'' ist, muss anders verfahren werden:
+      * Bei einem ''.'' kann einfach mit dem restlichen Substring exklusive des ersten Zeichens die Methode wieder aufgerufen werden.
+      * Bei einem ''#'' müssen zahlreiche Fälle unterschieden werden (teste es mit Stift und Papier, welche Fälle alle auftreten können, auch bei verschiedenen Zahlen-Matches).
+      * Bei einem ''?'' musst du die Rekursion aufsplitten in die Fälle, dass das ''?'' durch ein ''.'' oder durch ein ''#'' ersetzt wird.
+    * Immer bei einer Abbruchbedingung gibt es entweder den Fall, dass dies zu einem oder zu keinem Match führt. In der Summe führt das insgesamt zu Billionen (!) Fällen, die dank der dynamischen Programmierung in einigen Millisekunden (!) berechnet werden können.
+++++ Lösungsvorschlag Teil 2 |
+<code java>
+public long partTwo() {
+    long summe = 0;
+    int zeile = 0;
+    for (String line: inputLines) {
+        String s = line.split(" ")[1];
+        int[] numbers = strToIntArray(s + "," + s + "," + s + "," + s + "," + s);
+        cache = new HashMap<String, Long>();
+        long arrangements = 0;
+        String input = line.split(" ")[0];
+        arrangements = getMatches(input + "?" + input + "?" + input + "?" + input + "?" + input, numbers);
+        summe += arrangements;
+    }
+    return summe;
+}
+private long getMatches(String input, int[] numbers) {
+    // berechne key:
+    String key = input;
+    for (int n: numbers) {
+        key += n + "-";
+    }
+    // prüfe, ob key bereits vorhanden...
+    if (cache.containsKey(key)) {
+        return cache.get(key);
+    }
+    // wenn input nicht mehr ausreicht für noch zu treffende matches
+    int summeZahlen = 0;
+    for (int n: numbers) {
+        summeZahlen += n;
+    }
+    if (input.length() < summeZahlen + numbers.length - 1) {
+        cache.put(key, (long)0);
+        return 0;
+    }
+    // leerer input
+    if (input.length() == 0) {
+        if (numbers.length > 0) {
+            cache.put(key, (long)0);
+            return 0;
+        } else {
+            cache.put(key, (long)1);
+            return 1;
+        }
+    }
+    // keine zahlen mehr
+    if (numbers.length == 0) {
+        if (input.contains("#")) {
+            cache.put(key, (long)0);
+            return 0;
+        } else {
+            cache.put(key, (long)1);
+            return 1;
+        }
+    }
+    // wenn input mit . beginnt
+    if (input.charAt(0) == '.') {
+        long res = getMatches(input.substring(1), numbers.clone());
+        cache.put(key, res);
+        return res;
+    }
+    // wenn input mit # beginnt
+    else if (input.charAt(0) == '#') {
+        // prüfe, dass anzahl an vorderen # für erste Zahl ausreicht.
+        for (int i = 0; i < numbers[0]; i++) {
+            // -> reicht nicht
+            if (input.charAt(i) == '.') {
+                cache.put(key, (long)0);
+                return 0;
+            }
+        }
+        // -> reicht
+        String next = input.substring(1);
+        int[] nextNumbers;
+        // wenn erste Zahl nur noch 1 ist
+        if (numbers[0] == 1 && next.length() > 0) {
+            if (next.charAt(0) == '#') {
+                cache.put(key, (long)0);
+                return 0;
+            } else if (next.charAt(0) == '?') {
+                next = '.' + next.substring(1);
+            }
+            // entferne die vorderste Zahl
+            nextNumbers = new int[numbers.length - 1];
+            for (int i = 0; i < numbers.length - 1; i++) {
+                nextNumbers[i] = numbers[i+1];
+            }
+            long res = getMatches(next, nextNumbers.clone());
+            cache.put(key, res);
+            return res;
+        } else if (numbers[0] == 1 && next.length() == 0) {
+            cache.put(key, (long)1);
+            return 1;
+        }
+        // wenn nächstes Zeichen ? ist, muss es # werden
+        if (next.charAt(0) == '?') {
+            next = '#' + next.substring(1);
+        }
+        numbers[0] = numbers[0] - 1;
+        long res = getMatches(next, numbers.clone());
+        cache.put(key, res);
+        return res;
+    }
+    // wenn input mit '?' beginnt
+    else if (input.charAt(0) == '?') {
+        long res = getMatches('.' + input.substring(1), numbers.clone())
+            + getMatches('#' + input.substring(1), numbers.clone());
+        cache.put(key, res);
+        return res;
+    }
+    return 0;
+}
+</code>
+++++
 </pane>
 </tabs>