Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day5:start [05.12.2023 14:59] – [Lösung Teil 1] Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aco2023:day5:start [06.12.2023 12:18] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
+~~NOTOC~~
+====== Tag 5: If You Give A Seed A Fertilizer ======
 <tabs>
   * [[#variante1|Variante 1]]
@@ Zeile 5: / Zeile 10: @@
 ==== Lösung Teil 1 ====
-Die heutige Aufgabe war ziemlich schwer zu verstehen und dadurch auch noch schwerer zu erklären. Auch mangels Zeit gibt es daher für diese Variante 1 leider nur einen Lösungsvorschlag. Diese Lösung ist noch dazu etwas verzwickt nachzuvollziehen, da sie als Haupt-Datenstruktur eine ArrayList von ArrayLists von long-Arrays nutzt (''ArrayList<ArrayList<long[]>>''). Dafür ist sie aber sehr effizient und verzichtet quasi auf jegliche Schleifen (von der direkten Länge der Eingabedaten abgesehen).
+Die heutige Aufgabe war ziemlich schwer zu verstehen und dadurch auch noch schwerer zu erklären. Auch mangels Zeit gibt es daher für diese Variante 1 leider nur einen Lösungsvorschlag. Diese Lösung ist noch dazu etwas verzwickt nachzuvollziehen, da sie als Haupt-Datenstruktur eine ArrayList von ArrayLists von long-Arrays nutzt (''ArrayList<ArrayList<long[]> >''). Dafür ist sie aber sehr effizient und verzichtet quasi auf jegliche Schleifen (von der direkten Länge der Eingabedaten abgesehen).
-++++ Lösungsvorschlag |
+++++ Lösungsvorschlag Teil 1 |
 <code java>
 private long[] numbersToIntArray(String numbersStr) {
@@ Zeile 70: / Zeile 75: @@
     return smallest;
+}
+</code>
+++++
+==== Lösung Teil 2 ====
+Der Lösungsvorschlag für Teil 2 baut auf Teil 1 auf. Es wird also nur minimal am Code geändert und für jeden möglichen Eingabe-Seed wird das Ergebnis berechnet. Dies ist ziemlich ineffizient und benötigt viel Rechenzeit, da größenordnungsmäßig 2 Milliarden Eingaben berechnet werden müssen (dauert etwa mindestens 10 Minuten zum Berechnen).
+Vermutlich wäre eine effizientere Lösung möglich, indem man die ganzen Mappings rückwärts in der Eingabedatei von unten nach oben durchgeht. Man könnte also z. B. bei der kleinsten möglichen location (0) beginnen, die ganzen Rechnungen der Mappings rückwärts gehen und dann so lange die location erhöhen bis man einen erlaubten Seed findet. Das sollte hoffentlich schneller gehen.
+Hier aber der "langsame" Lösungsvorschlag:
+++++ Lösungsvorschlag Teil 2 |
+<code java>
+public long partTwo() {
+    long[] seeds = numbersToIntArray(inputLines.get(0).split(":")[1]);
+    ArrayList<ArrayList<long[]>> allMaps = new ArrayList<ArrayList<long[]>>();
+    ArrayList<long[]> map = new ArrayList<long[]>();
+    for (int l = 2; l < inputLines.size(); l++) {
+        String line = inputLines.get(l);
+        if (line.length() <= 1) {
+            allMaps.add(map);
+            continue;
+        }
+        if (line.contains(":")) {
+            map = new ArrayList<long[]>();
+            continue;
+        }
+        map.add(numbersToIntArray(line));
+    }
+    // add last map to allMaps
+    allMaps.add(map);
+    long smallest = Long.MAX_VALUE;
+    for (int i = 0; i < seeds.length; i+=2) {
+        for (int x = 0; x < seeds[i+1]; x++) {
+            long seed = seeds[i] + x;
+            for (int mapCount = 0; mapCount < allMaps.size(); mapCount++) {
+                seed = getMapping(allMaps.get(mapCount), seed);
+            }
+            if (seed < smallest) {
+                smallest = seed;
+            }
+        }
+    }
+    return smallest;
 }
 </code>