faecher:informatik:oberstufe:java:aoc:aoc2024:day07:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:java:aoc:aoc2024:day07:start [07.12.2024 18:37] – [Teil 1] Marco Kuemmelfaecher: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).   * 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 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.
Zeile 34: Zeile 34:
                  
         ArrayList<Integer> numbers = new ArrayList();         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(" ")) {         for (String number: line.split(":")[1].trim().split(" ")) {
             numbers.add(Integer.parseInt(number));             numbers.add(Integer.parseInt(number));
Zeile 68: Zeile 68:
     return false;     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> </code>
 ++++ ++++
  • faecher/informatik/oberstufe/java/aoc/aoc2024/day07/start.1733596670.txt.gz
  • Zuletzt geändert: 07.12.2024 18:37
  • von Marco Kuemmel