Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aoc2024:day09:start [09.12.2024 17:52] – Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aoc2024:day09:start [04.01.2025 14:53] (aktuell) – [Teil 1] Marco Kuemmel
@@ Zeile 17: / Zeile 17: @@
 ++++ Vorgehensweise: |
   * Speichere der Reihe nach alle Dateien in einer ArrayList<Integer>. Das Ergebnis muss exakt so aussehen, wie es im Wiki in den längeren Zeilen zu sehen ist. Weil du nur Integer speicherst, empfiehlt es sich, an Leerstellen eine -1 zu speichern.
-    * Speichere dir in einer boolean, ob die nächste Ziffer vom Input für eine Datei oder eine Leerstelle stehe und switche den boolean zum Abschluss immer hin und her.
+    * Speichere dir in einer boolean, ob die nächste Ziffer vom Input für eine Datei oder eine Leerstelle steht und switche den boolean zum Abschluss immer hin und her (''leerstelle = !leerstelle'').
     * Füge für jede Ziffer so viele Male die nächst größere Dateien-Ziffer oder eine -1 (Leerstelle) zur Disk hinzu, wie es die aktuelle Ziffer angibt.
   * Nutze zwei Zeiger-Variablen:
@@ Zeile 90: / Zeile 90: @@
     }
+    System.out.println(checksum);
+}
+</code>
+++++
+===== Teil 2 =====
+Teil 2 ist insgesamt knifflig zu programmieren, da man (zumindest bei der hier gewählten Vorgehensweise) sowohl Buch halten muss über die aktuell vorhandenen Leerstellen, als auch ganze Zahlenblöcke betrachten muss. Die Vorgehensweise lässt sich nicht sinnvoll beschreiben und auch im Code nur schwer nachvollziehen. Der Vollständigkeit halber ist der Code hier trotzdem präsentiert.
+++++ Lösungsvorschlag |
+<code java>
+public void partTwo() {
+    ArrayList<Integer> disk = new ArrayList(); // Speichere hierin alle Zahlen der Disk
+    boolean isFile = true; // Zum Hin- und Herschalten zwischen Datei und Leerstelle
+    int fileCounter = 0; // Zählt hoch, für späteres 0..111..2222.33. etc. der Dateiblöcke
+    // Iteriere über jeden Character
+    for (char c: inputLines.get(0).toCharArray()) {
+        int number = (int)(c-'0'); // Wandle damit die char-Ziffer in dieselbe int-Ziffer um
+        // Jeweils abwechselnd kommt eine Datei/Leerstelle
+        if (isFile) {
+            // speichere so viele Mal den fileCounter wie lang die Datei sein soll
+            for (int i = 0; i < number; i++) {
+                disk.add(fileCounter);
+            }
+            fileCounter++;
+        } else {
+            for (int i = 0; i < number; i++) {
+                disk.add(-1); // speichere -1 für eine Leerstelle
+            }
+        }
+        isFile = !isFile;
+    }
+    // Erstelle ArrayList, das alle freie Lücken (jeweils Beginn und Ende) speichert
+    ArrayList<int[]> spaces = new ArrayList();
+    int start = -1;
+    int end = -1;
+    for (int i = 0; i < disk.size(); i++) {
+        if (disk.get(i) == -1 && start == -1) {
+            start = i;
+        }
+        else if (disk.get(i) != -1 && start != -1) {
+            end = i-1;
+            spaces.add(new int[]{start, end});
+            start = -1;
+            end = -1;
+        }
+    }
+    // Suche von hinten komplette (!) Zahlenblöcke
+    int number = -1;
+    int length = 0;
+    for (int i = disk.size()-2; i >= 0; i--) {
+        // Falls Beginn eines Blocks bei i+1
+        if (!disk.get(i).equals(disk.get(i+1)) && disk.get(i+1) != -1 ) {
+            int blockIndex = i+1;
+            while (blockIndex < disk.size()-1 && disk.get(blockIndex).equals(disk.get(blockIndex+1))) {
+                blockIndex++;
+            }
+            int blockLength = blockIndex-i;
+            // Finde einen Space, der lang genug ist
+            for (int[] space: spaces) {
+                if (space[0] < i+1 && space[1]-space[0]+1 >= blockLength) {
+                    for (int x = 0; x < blockLength; x++) {
+                        disk.set(space[0]+x, disk.get(i+1+x));
+                        disk.set(i+1+x, -1);
+                    }
+                    // reduziere die Größe des benutzten Spaces = verschiebe den Anfang nach hinten
+                    space[0] += blockLength;
+                    break;
+                }
+            }
+        }
+    }
+    // checksum
+    long checksum = 0;
+    System.out.println(disk.size());
+    for (int i = 0; i < disk.size(); i++) {
+        if (disk.get(i) != -1) {
+            checksum += (long)i * (long)disk.get(i);
+        }
+    }
+    System.out.println();
     System.out.println(checksum);
 }
 </code>
 ++++