Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:java:aoc:aco2023:day20:start [24.12.2023 10:46] – angelegt Marco Kuemmel
+++ faecher:informatik:oberstufe:java:aoc:aco2023:day20:start [24.12.2023 21:57] (aktuell) – [Lösungshinweise Teil 2] Marco Kuemmel
@@ Zeile 200: / Zeile 200: @@
 ++++
-  * Erstelle aus jeder Eingabezeile die nötigen Puls-Module, die alle auch vom Typ der Oberklasse ''PulseModule'' sind. Daher kannst du alle in einer ''HashMap<String,PulseModule>'' speichern. Mit dieser ArrayList, kannst du für jeden Modulnamen (key) sofort das dazugehörige Modul bekommen, egal ob es ein FlipFlop oder eine Conjunction ist.
+  * Erstelle aus jeder Eingabezeile die nötigen Puls-Module, die alle auch vom Typ der Oberklasse ''PulseModule'' sind. Daher kannst du alle in einer ''HashMap<String,PulseModule>'' speichern. Mit dieser HashMap kannst du für jeden Modulnamen (key) sofort das dazugehörige Modul bekommen, egal, ob es ein FlipFlop oder eine Conjunction ist.
   * Du musst nach dem Erstellen der Module noch ein zweites Mal über jedes erstellte Modul iterieren, um die Vorgänger in die Conjunctions eintragen zu können (damit jede Conjunction Buch führen kann, ob ihre Vorgänger jeweils high oder low waren).
   * Um einen einzelnen Durchlauf (Knopfdruck bis Ende) zu erreichen, und die Pulse in der richtigen Reihenfolge abzuarbeiten, musst du eine Queue nutzen. Stecke zu Beginn die Broadcast-Pulse in die Queue. Dann iteriere in einer while-Schleife solange die Schleife nicht leer ist:
@@ Zeile 294: / Zeile 294: @@
     return lowPulses*highPulses;
+}
+</code>
+++++
+===== Lösungshinweise Teil 2 =====
+  * Für Teil 2 ist es wichtig, den folgenden Kniff zu sehen: Der Output ist low, wenn **alle** Eingänge der letzten Conjunction high sind. Dies passiert aber erst nach vielen Billionen (!) Iterationen. Daher muss man noch einen Schritt weiter denken: Schaue dir jeden Vorgänger der letzten Conjunction an und speichere dir, wann diese Module jeweils **einzeln** einen high-Pulse an die letzte Conjunction aussenden! Multipliziere am Ende alle diese minimalen Iterationen für die jeweiligen high-Pulses.
+++++ Lösungsvorschlag Teil 2 |
+<code java>
+public long partTwo() {
+    String[] broadcasters = new String[0];
+    for (String line: inputLines) {
+        if (line.startsWith("broadcaster")) {
+            String[] inits = line.split(">")[1].replaceAll("\\s+", "").split(",");
+            for (String s: inits) {
+                s = s.trim();
+            }
+            broadcasters = inits;
+            ArrayList<String> nachfolger = new ArrayList<String>();
+            nachfolger.addAll(Arrays.asList(inits));
+            modules.put("broadcaster", new Broadcaster("broadcaster", nachfolger));
+        } else if (line.startsWith("%")) {
+            String moduleName = line.split("-")[0].split("%")[1].trim();
+            ArrayList<String> nachfolger = new ArrayList();
+            String[] nf = line.split(">")[1].replaceAll("\\s+", "").split(",");
+            for (String s: nf) {
+                nachfolger.add(s.trim());
+            }
+            modules.put(moduleName, new FlipFlop(moduleName, nachfolger));
+        } else if (line.startsWith("&")) {
+            String moduleName = line.split("-")[0].split("&")[1].trim();
+            ArrayList<String> nachfolger = new ArrayList();
+            String[] nf = line.split(">")[1].replaceAll("\\s+", "").split(",");
+            for (String s: nf) {
+                nachfolger.add(s.trim());
+            }
+            modules.put(moduleName, new Conjunction(moduleName, nachfolger));
+        }
+    }
+    // gehe alle module durch, um die vorgänger der conjuctions einzutragen
+    for (PulseModule m: modules.values()) {
+        ArrayList<String> nachfolger = m.getNachfolger();
+        for (String n: nachfolger) {
+            PulseModule nachfolgeModule = modules.get(n);
+            if (nachfolgeModule instanceof Conjunction) {
+                ((Conjunction)nachfolgeModule).addInput(m.getModuleName());
+            }
+        }
+    }
+    // finde letzte conjunction
+    String letzteConjunction = "";
+    for (PulseModule m: modules.values()) {
+        ArrayList<String> nachfolger = m.getNachfolger();
+        for (String n: nachfolger) {
+            if (modules.get(n) == null) {
+                letzteConjunction = m.getModuleName();
+            }
+        }
+    }
+    // finde alle Vorgänger dieser letzten Conjunction
+    HashMap<String,Integer> vorletzteConjunctions = new HashMap();
+    for (String s: ((Conjunction)modules.get(letzteConjunction)).getInputs()) {
+        vorletzteConjunctions.put(s, 0);
+    }
+    long i = 0;
+    //HashMap<String,Integer> statesFound = new HashMap<String,Integer>();
+    while (true) {
+        i++;
+        long result = 1;
+        for (Integer iteration: vorletzteConjunctions.values()) {
+            result *= iteration;
+        }
+        if (result != 0) {
+            System.out.println(result);
+            return result;
+        }
+        // Fülle die Queue mit den ersten Pulses vom Broadcaster
+        Queue<Pulse> queue = new LinkedList<>();
+        for (String s: broadcasters) {
+            queue.offer(new Pulse("broadcaster", s, 0));
+        }
+        while(queue.size() > 0) {
+            Pulse p = queue.poll();
+            PulseModule pm = modules.get(p.getTo());
+            if (pm == null) {
+                if (p.getPulse() == 0) {
+                    return i;
+                } else {
+                    continue;
+                }
+            }
+            Pulse[] nachfolger = pm.pulse(p);
+            for (Pulse nfp: nachfolger) {
+                // wenn eine vorletzteConjunction HIGH sendet, dann merken!
+                if (vorletzteConjunctions.get(nfp.getFrom()) != null && nfp.getPulse() == 1) {
+                    vorletzteConjunctions.put(nfp.getFrom(), (int)i);
+                }
+                queue.offer(nfp);
+            }
+        }
+    }
 }
 </code>