Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day18:start [21.12.2023 16:18] – [Lösungshinweise Teil 2] 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 (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.
@@ Zeile 139: / Zeile 146: @@
 <code>
 (wegen "rechts")
-(wegen oberes ende von "oben")
+(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>