Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day12:start [15.12.2023 18:41] – Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aco2023:day12:start [15.12.2023 18:42] (aktuell) – Marco Kuemmel
@@ Zeile 75: / Zeile 75: @@
     * 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>