faecher:informatik:oberstufe:java:aoc:aoc2024:day11:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Day 11: Plutonian Pebbles  ======

Dieser Tag ist etwas kniffliger. Teil 1 kann man noch zur **mittleren Schwierigkeit** zählen, Teil 2 hingegen zählt definitiv zur **höchsten Schwierigkeitsstufe**, da man **Memoisation bzw. dynamische Programmierung** benötigt. Das bedeutet, dass man Zwischenergebnisse speichern muss, um bei erneuten rekursiven Aufrufen mit denselben Parametern direkt das vorherige Ergebnis zurückliefern zu können. Andernfalls würde die Rechenzeit für Teil 2 explodieren. Hierzu wird eine **HashMap** benötigt.

===== Teil 1 =====

Teil 1 lässt sich noch relativ //straight-forward// lösen. Man speichert die Input-Zahlen also in einer ArrayList und iteriert 25x über die Schleife. Pro Iteration erstellt man am besten eine **neue** ArrayList, die man mit den neuen Werten füllt, die sich nach den Regeln aus der **alten** ArrayList (des letzten Durchgangs) ergeben.

++++ Lösungsvorschlag |
<code java>
public void partOne() {
    // Übertrage die Input-String-Zahlen in ein Array
    ArrayList<Long> input = new ArrayList();
    for (String n: inputLines.get(0).split(" ")) {
        input.add(Long.parseLong(n));
    }

    // 25x "blinzeln"
    for (int blink = 0; blink < 25; blink++) {
        // erstelle pro Durchgang eine neue ArrayList für die neuen Werte
        ArrayList<Long> next = new ArrayList();

        // pro altem Wert des letzten Durchgangs
        for (long i: input) {
            if (i == 0) {
                next.add((long)1);
            } else if (String.valueOf(i).length() % 2 == 0) {
                // Aufteilung in vordere/hintere Hälfte der Zahl
                next.add((long) (i / Math.pow(10,(String.valueOf(i).length()/2))));
                next.add((long) (i % Math.pow(10,(String.valueOf(i).length()/2))));
            } else {
                next.add(i * 2024);
            }
        }
        // mache die aktuelle/neue ArrayList "next" zur alten für den nächsten Durchlauf
        input = next;
    }
    System.out.println(input.size());
}
</code>
++++

===== Teil 2 =====

Eine ausführliche Erklärung würde hier vermutlich den Rahmen sprengen. Der Quellcode des Lösungsvorschlags ist ein wenig kommentiert...

++++ Lösungsvorschlag |
<code java>
public void partTwo() { 
    // Speichert pro "Steinzahl" ein Array, das wiederum pro Zeitschritt 0-74 die bereits 
    // errechneten Ergebnisse (Anzahl der Steine bei Zeitschritt 75) speichert.
    memo = new HashMap(); 

    // Übertrage die Input-String-Zahlen in ein Array
    ArrayList<Long> input = new ArrayList();
    for (String n: inputLines.get(0).split(" ")) {
        input.add(Long.parseLong(n));
    }

    // Starte pro Input-Zahl den rekursiven Aufruf
    long stones = 0;
    for (long i: input) {
        stones += calculate(i, 0);
    }
    System.out.println(stones);
}

private long calculate(long i, int times) {        
    // Letzter Zeitschritt? Dann gibts genau einen (weiteren) Stein
    if (times == 75) {
        return 1;
    }
    
    // Schaue im Speicher der Zwischenergebnisse nach, ob schon einmal die Anzahl der Steine 
    // beim Input i zum Zeitpunkt times berechnet wurde.
    long[] stones = memo.get(i);
    if (stones != null && stones[times] != 0)  {
        return stones[times];
    } else if (stones == null) {
        // Wenn zu dieser Zahl noch nie nachgeschaut wurde, dann erstelle schon mal das leere Array für die verschiedenen Zeitpunkte
        stones = new long[75]; 
    }

    long result = 0;
    if (i == 0) {
        result += calculate((long)1,times+1);
    } else if (String.valueOf(i).length() % 2 == 0) {
        result += calculate((long) (i / Math.pow(10,(String.valueOf(i).length()/2))), times+1);
        result += calculate((long) (i % Math.pow(10,(String.valueOf(i).length()/2))), times+1);
    } else {
        result += calculate(i * 2024,times+1);
    }

    // Speichere das neue Ergebnis für den Zeitpunkt times
    stones[times] = result;
    // speichere das ganze Array der verschiedenen Zeitpunkte in der HashMap passend zum Wert i
    memo.put(i, stones);
    
    return result;
}
</code>
++++