Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day18:start [21.12.2023 09:30] – angelegt Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aco2023:day18:start [21.12.2023 16:56] (aktuell) – Marco Kuemmel
@@ Zeile 17: / Zeile 17: @@
 ++++ Lösungsvorschlag |
 <code java>
+private int breite;
+private int hoehe;
+private ArrayList<int[]> trenchList;
+Deque<int[]> fillQueue = new ArrayDeque();
+private char[][] map;
 public int partOne() {
     trenchList = new ArrayList();
@@ Zeile 130: / Zeile 137: @@
 ===== Lösungshinweise Teil 2 =====
   * Für Teil 2 werden die Zahlen zu groß, sodass die Lösung aus Teil 1 nicht mehr ausreicht. Die Hauptvorgehensweise ist folgende:
-{{ :faecher:informatik:oberstufe:java:aoc:aco2023:day18:2023-12-21_10-24-13-0.png?400|}}
+{{ :faecher:informatik:oberstufe:java:aoc:aco2023:day18:2023-12-21_17-17-10-0.png?400|}}
-  * Gehe der Reihe nach die Befehle entlang. Trage aber keine Kreuze in eine 2-dimensionale Matrix, sondern betrachte nur die einzelnen Spalten. Wenn
+  * Gehe der Reihe nach die Befehle entlang. Trage aber keine Kreuze in eine 2-dimensionale Matrix, sondern betrachte nur die einzelnen Spalten (x-Werte). Führe eine ArrayList, um pro Spalte mehrere y-Werte eintragen zu können, an denen "etwas passiert".:
+    * Wenn du gerade nach **rechts** läufst, dann markierst du, dass du mit dem aktuellen y-Wert das **obere Ende** des Lava-Pools.
+    * Beim nach **links** laufen markierst du mit dem y-Wert das **untere Ende** des Lava-Pools.
+    * Wenn du nach **unten** läufst, dann ist dein oberer Startpunkt, das obere Ende des Lava-Pools. Als weiteren y-Wert trägst du ein, wie viele y-Werte du weiter nach unten zu gehen hast (das ist dann ein mögliches unteres Ende des Pools).
+    * Beim nach **oben** laufen ist der untere Startpunkt ein unteres Ende des Pools, und beim "Ziel" des nach-oben-laufens ist das obere Ende des Pools.
+  * Beispiel für das rechte Bild (Annahme, dass die Erstellung des Pfades im Uhrzeigersinn geschah): in der Spalte für x=5 stehen folgende y-Werte drin:
+<code>
+(wegen "rechts")
+(wegen oberes Ende von "oben")
+(wegen "rechts")
+(wegen unteres Ende von "oben")
+(wegen "links")
+(wegen "rechts")
+(wegen oberes Ende von "unten")
+(wegen unteres Ende von "unten")
+(wegen "links")
+</code>
+Nun muss man zusätzlich noch unterscheiden, ob die Eintragung jeweils das obere oder untere Ende vom Pool markiert. Platzsparend kann man dies z. B. tun, indem man die Zahlen als String abspeichert und hinten eine 0 für oberes Ende und 1 für unteres Ende anhängt. Damit steht eigentlich in der Spalte:
+<code>
+
+
+
+
+
+
+
+
+
+</code>
+Hat man diese Werte, kann man schnell die Differenzen ausrechnen und damit die Fläche über alle Spalten aufsummieren. Wichtig ist nun, die Werte noch zu bereinigen:
+y=1 hat die Endung 0 und 1 (kommt doppelt vor). Wir können daher y=1 gänzlich aus der Liste streichen. Ebenso können wir alle anderen Dopplungen streichen und müssen die Einträge sortieren (der Pfad kann "chaotisch" verlaufen und die Werte müssen nicht bereits automatisch aufsteigend sortiert sein. Am Ende bleibt übrig:
+<code>
+</code>
+Die Fläche in der einen Spalte ist also: ''( (3-1) + 1) + ( (7-5) + 1) ''
+++++ Lösungsvorschlag Teil 2 |
+<code java>
+private ArrayList<ArrayList<Integer>> spalten;
+public long partTwo() {
+    ArrayList<String> anweisungen = new ArrayList();
+    spalten = new ArrayList();
+    int breite = 0;
+    for (String line: inputLines) {
+        String hex = line.split("#")[1].split("[)]")[0];
+        int steps = Integer.parseInt(hex.substring(0, 5), 16);
+        // zähle alle schritte nach rechts
+        if (hex.substring(5).equals("0")) {
+            breite += steps;
+        }
+        anweisungen.add(steps + hex.substring(5));
+    }
+    ArrayList<ArrayList<String>> spalten = new ArrayList();
+    for (int i = 0; i < breite; i++) {
+        spalten.add(new ArrayList<String>());
+    }
+    int x = 0;
+    int y = 0;
+    for (String anweisung: anweisungen) {
+        // rechts
+        if (anweisung.charAt(anweisung.length()-1) == '0') {
+            // 0 am Ende bedeutet: ein oberes Ende vom Pool innerhalb der Spalte
+            spalten.get(x).add(y + "" + 0);
+            int steps = Integer.parseInt(anweisung.substring(0, anweisung.length()-1));
+            for (int i = 0; i < steps; i++) {
+                x = (x+1) % breite;
+                spalten.get(x).add(y + "" + 0);
+            }
+        }
+        // unten
+        else if (anweisung.charAt(anweisung.length()-1) == '1') {
+            spalten.get(x).add(y + "" + 0);
+            int steps = Integer.parseInt(anweisung.substring(0, anweisung.length()-1));
+            y += steps;
+            spalten.get(x).add(y + "" + 1);
+        }
+        // links
+        else if (anweisung.charAt(anweisung.length()-1) == '2') {
+            // 1 am Ende bedeutet: ein unteres Ende vom Pool innerhalb der Spalte
+            spalten.get(x).add(y + "" + 1);
+            int steps = Integer.parseInt(anweisung.substring(0, anweisung.length()-1));
+            for (int i = 0; i < steps; i++) {
+                x--;
+                if (x < 0) {
+                    x = breite - 1;
+                }
+                spalten.get(x).add(y + "" + 1);
+            }
+        }
+        // oben
+        else if (anweisung.charAt(anweisung.length()-1) == '3') {
+            spalten.get(x).add(y + "" + 1);
+            int steps = Integer.parseInt(anweisung.substring(0, anweisung.length()-1));
+            y -= steps;
+            spalten.get(x).add(y + "" + 0);
+        }
+    }
+    long summe = 0;
+    // Gehe über jede Spalte
+    for (ArrayList<String> spalte: spalten) {
+        // entferne alle vollständigen dopplungen (wandelt es in ein "sortiertes" Set um (alles kann dort nur einmalig vorkommen))
+        Set<String> set = new LinkedHashSet<>(spalte);
+        spalte.clear();
+        spalte.addAll(set);
+        // sortiere
+        spalte = sortArrayList(spalte);
+        // prüfe nun, ob direkte Nachfolger in allen Zeichen exklusive dem letzten übereinstimmen -> y-koordinate gleichzeitig oberes und unteres Ende -> kann entfernt werden.
+        for (int i = 0; i < spalte.size() - 1; i++) {
+            if (spalte.get(i).substring(0, spalte.get(i).length()-1).equals(spalte.get(i+1).substring(0,spalte.get(i+1).length()-1))) {
+                spalte.remove(i);
+                spalte.remove(i); //zweimal i, da durch das erste Löschen die hinteren Elemente 1 nach vorne rücken
+                i--;
+            }
+        }
+        for (int i = 0; i < spalte.size(); i = i+2) {
+            summe += Integer.parseInt(spalte.get(i+1).substring(0, spalte.get(i+1).length()-1)) - Integer.parseInt(spalte.get(i).substring(0, spalte.get(i).length()-1)) + 1;
+        }
+    }
+    return summe;
+}
+/**
+ * Selection-Sort, um die Werte pro Spalte nach Zahlenwert zu sortieren.
+ */
+private ArrayList<String> sortArrayList(ArrayList<String> input) {
+    for (int i = 0; i < input.size(); i++) {
+        int min = i;
+        for (int j = i; j < input.size(); j++) {
+            if (Integer.parseInt(input.get(j).substring(0, input.get(j).length()-1)) < Integer.parseInt(input.get(min).substring(0, input.get(min).length()-1))) {
+                min = j;
+            }
+        }
+        String temp = input.get(min);
+        input.set(min, input.get(i));
+        input.set(i, temp);
+    }
+    return input;
+}
+</code>
+++++
 </pane>
 </tabs>