Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aoc2024:day07:start [07.12.2024 18:35] – angelegt Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aoc2024:day07:start [07.12.2024 18:47] (aktuell) – [Teil 1] Marco Kuemmel
@@ Zeile 19: / Zeile 19: @@
 ++++
-++++ Genau Vorgehensweise in der Rekursion: |
+++++ Genaue Vorgehensweise in der Rekursion: |
   * Zunächst die Abbruchbedingung: Wenn der Index gleich groß ist, wie die Anzahl der Zahlen in der ArrayList, dann bedeutet das, dass bereits alle Zahlen in die aktuelle Berechnung eingeflossen sind. Damit kann nun das Ergebnis überprüft werden. Das Ergebnis dieser Überprüfung (Vergleich der Berechnung mit dem erwarteten Ergebnis) ist auch direkt der Rückgabewert: Entweder es stimmt überein (true) oder nicht (false).
   * Wenn der Index noch 0 ist, die Rekursion also gerade das erste Mal aufgerufen wird, dann müssen direkt zwei Zahlen miteinander verrechnet werden. Man prüft zunächst rekursiv, ob eine Addition der ersten beiden Zahlen korrekt ist. Der Index im nächsten rekursiven Aufruf muss also direkt auf 2 gesetzt werden, da gleich zwei Zahlen zu Beginn verrechnet werden müssen. Außerdem wird diese Rechnung ''Zahl1 + Zahl2'' als letzter Parameter gesetzt. Wenn dieser erste Rekursive Aufruf mit der Addition nicht zum Erfolg geführt hat, dann muss das Ganze noch mit der Multiplikation durchgeführt werden.
-  * Wenn der Index >= 2 ist ("else"), da müssen ebenso nacheinander wieder die Fälle für die Addition und dann noch (falls nötig) für die Multiplikation überprüft werden. Nun muss aber jeweils der Index nur noch um 1 erhöht werden und das aktuelle Ergebnis der Berechnung ist "das aktuelle Ergebnis +/* der Zahl am gegebenen Index".
+  * Wenn der Index >= 2 ist ("else"), dann müssen ebenso nacheinander wieder die Fälle für die Addition und dann noch (falls nötig) für die Multiplikation überprüft werden. Nun muss aber jeweils der Index nur noch um 1 erhöht werden und das aktuelle Ergebnis der Berechnung ist "das aktuelle Ergebnis +/* der Zahl am gegebenen Index".
 ++++
@@ Zeile 34: / Zeile 34: @@
         ArrayList<Integer> numbers = new ArrayList();
-        // Interiere über jede Zahl (noch als String-Array)
+        // Iteriere über jede Zahl (noch als String-Array)
         for (String number: line.split(":")[1].trim().split(" ")) {
             numbers.add(Integer.parseInt(number));
@@ Zeile 68: / Zeile 68: @@
     return false;
 }
+</code>
+++++
+===== Teil 2 =====
+Der Beginn von Teil 2 ist identisch! Einzig die rekursive Methode muss um einen dritten Fall (Zusammenfügen der Zahlen anstatt +/*) erweitert werden!
+Das Zusammenfügen geht vermutlich am einfachsten, indem man die "vordere Zahl" mit der Zehnerpotenz $10^x$ multipliziert, wobei  $x$ die Anzahl der Ziffern der "hinteren Zahl" ist. Schließlich müssen alle Ziffern der "vorderen Zahl" entsprechend nach //links geschoben// werden. Anschließend muss man noch die hintere Zahl addieren. Die Potenz geht mit folgendem Code: ''Math.pow(10, String.valueOf(numbers.get(index)).length())''. Die hintere Zahl wird also in einen String umgewandelt, von dem man dann die String-Länge ermitteln kann. Dies ist der Exponent. Achtung: Diese Zahl wird meist ungeheuerlich groß -> In Long umwandeln!
+++++ Lösungsvorschlag |
+<code java>
+public void partTwo() {
+    long sum = 0;
+    for (String line: inputLines) {
+        long result = Long.parseLong(line.split(":")[0]);
+        ArrayList<Integer> numbers = new ArrayList();
+        for (String number: line.split(":")[1].trim().split(" ")) {
+            numbers.add(Integer.parseInt(number));
+        }
+        if (equationPossible2(result, numbers, 0, 0)) {
+            sum += result;
+        }
+    }
+    System.out.println(sum);
+}
+private boolean equationPossible2(long result, ArrayList<Integer> numbers, int index, long calculation) {
+    if (index == numbers.size()) {
+        return result == calculation;
+    }
+    if (index == 0) {
+        if (equationPossible2(result, numbers, 2, numbers.get(0) + numbers.get(1))) {
+            return true;
+        } else if (equationPossible2(result, numbers, 2, numbers.get(0) * numbers.get(1))) {
+            return true;
+        } else if (equationPossible2(result, numbers, 2, (long)(numbers.get(0) * Math.pow(10, String.valueOf(numbers.get(1)).length())) + numbers.get(1))) {
+            return true;
+        }
+    } else {
+        if (equationPossible2(result, numbers, index+1, calculation + numbers.get(index))) {
+            return true;
+        } else if (equationPossible2(result, numbers, index+1, calculation * numbers.get(index))) {
+            return true;
+        } else if (equationPossible2(result, numbers, index+1, (long)(calculation * Math.pow(10, String.valueOf(numbers.get(index)).length())) + numbers.get(index))) {
+            return true;
+        }
+    }
+    return false;
+}
 </code>
 ++++