faecher:informatik:oberstufe:java:aoc:aoc2024:day10:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:java:aoc:aoc2024:day10:start [10.12.2024 08:44] – Marco Kuemmelfaecher:informatik:oberstufe:java:aoc:aoc2024:day10:start [04.01.2025 15:16] (aktuell) – [Teil 1] Marco Kuemmel
Zeile 9: Zeile 9:
 ++++ Tipps zur Vorgehensweise: | ++++ Tipps zur Vorgehensweise: |
   * Speichere den Input in einem zweidimensionalen int-Array. Jeden ''char'' c kannst du mit ''(int)(c-'0')'' in einen ''int'' casten.   * Speichere den Input in einem zweidimensionalen int-Array. Jeden ''char'' c kannst du mit ''(int)(c-'0')'' in einen ''int'' casten.
-  * Iteriere anschließend über jede Koordinate des Arrays. Wenn eine Koordinate 0 ist (= Startpunkt eines Trails), dann starte dort einen rekursiven Aufruf. Der rekursive Aufruf benötigt folgende Parameter: +  * Iteriere anschließend über jede Koordinate des Arrays. Wenn eine Koordinate 0 ist (= Startpunkt eines Trails), dann passieren zwei Dinge: 
-    - Bei diesem **ersten** Aufruf eine **Kopie** der Karte (des int-Arrays). Hintergrund dazu: Wenn der rekursive Aufruf ein Ende eines Trails (die Zahl 9) gefunden hat, so muss er diese 9 "markieren", damit dieses Trail-Ende bei einem benachbarten rekursiven Aufruf nicht erneut gefunden/gezählt wird. Diese Markierung darf aber nur pro Startpunkt (pro ausgehender 0) gelten - ein Trail der von einer neuen Koordinate (einer neuen 0) beginnt, der darf wieder zum selben Ziel (9) führen.+    - Speichere in einer ''ArrayList<int[]>'' alle Koordinaten, die ein Ende des Pfads **von der aktuellen Startposition** darstellen (Index 0 = x-Koordinate und Index 1 = y-Koordinate). Initialisiere die ArrayList also neu! Wichtig: diese ArrayList muss eine Instanzvariable sein! 
 +    - Anschließend startest du den rekursiven Aufruf. 
 +  * Der rekursive Aufruf benötigt folgende Parameter: 
 +    - Die Karte (das zweidimensionale int-Array). 
     - Die zu erwartende Höhe an der nächsten Koodinate (siehe nächste Parameter).     - Die zu erwartende Höhe an der nächsten Koodinate (siehe nächste Parameter).
     - Nächste x-Koordinate     - Nächste x-Koordinate
Zeile 16: Zeile 19:
   * Pro rekursivem Aufruf gilt nun folgendes:   * Pro rekursivem Aufruf gilt nun folgendes:
     * Prüfe auf den Basis-Fall, ob die übergebenen Koordinaten außerhalb der Map liegen. Falls ja, dann gib eine 0 zurück, da mit diesem rekursiven Aufruf ganz offensichtlich kein weiterer Weg zum Ziel gefunden werden kann.     * Prüfe auf den Basis-Fall, ob die übergebenen Koordinaten außerhalb der Map liegen. Falls ja, dann gib eine 0 zurück, da mit diesem rekursiven Aufruf ganz offensichtlich kein weiterer Weg zum Ziel gefunden werden kann.
-    * Prüfe auf den Basisfall, dass die Höhe der übergebenen Koordinate nicht der ebenfalls übergebenen erwarteten Höhe entspricht → ebenfalls 0 zurückgeben. //Für alle nun nachfolgenden Bedingungen weiß man dann entsprechend, dass die erwartete Höhe mit der vorgefundenen Höhe übereinstimmt.// +    * Prüfe auf den Basisfall, dass die Höhe der übergebenen Koordinate nicht der ebenfalls übergebenen erwarteten Höhe entspricht c ebenfalls 0 zurückgeben. //Für alle nun nachfolgenden Bedingungen weiß man dann entsprechend, dass die erwartete Höhe mit der vorgefundenen Höhe übereinstimmt.// 
-    * Prüfe auf den Basisfall, dass die Höhe der Zahl 9 entspricht. Gib 1 zurück, da **ein** weiter Trail gefunden wurde.+    * Prüfe auf den Basisfall, dass die Koordinate bereits (auf einem anderen Weg) von derselben Startkoordinate beginnend gefunden wurde. Iteriere dazu über die zuvor initialisierte ArrayList und prüfe, ob die aktuelle Koordinate [x,y] dort bereits enthalten ist. Falls ja, dann darf das Ziel nicht nochmals gezählt werden → ''return 0''. 
 +    * Prüfe auf den Basisfall, dass die Höhe der Zahl 9 entspricht. Gib 1 zurück, da **ein** weiter Trail gefunden wurde. Füge zuvor noch die Koordinate zur ArrayList der Ziele hinzu.
     * Ansonsten sind wir auf dem richtigen Weg, aber noch nicht am Ziel und müssen entsprechend in alle 4 möglichen Richtungen weiterlaufen. Ruf also der Reihe nach die Rekursion 4x auf, wobei du jedes Mal eine der Koordinaten um +/- 1 veränderst und die nächste erwartete Zahl/Höhe um eins erhöhst. Ermittle die Summe der Rückgabewerte aller 4 rekursiven Aufrufe. So viele neue Trails konnten ermittelt werden und diese Zahl muss entsprechend zurückgegeben werden.     * Ansonsten sind wir auf dem richtigen Weg, aber noch nicht am Ziel und müssen entsprechend in alle 4 möglichen Richtungen weiterlaufen. Ruf also der Reihe nach die Rekursion 4x auf, wobei du jedes Mal eine der Koordinaten um +/- 1 veränderst und die nächste erwartete Zahl/Höhe um eins erhöhst. Ermittle die Summe der Rückgabewerte aller 4 rekursiven Aufrufe. So viele neue Trails konnten ermittelt werden und diese Zahl muss entsprechend zurückgegeben werden.
 ++++ ++++
Zeile 23: Zeile 27:
 ++++ Lösungsvorschlag: | ++++ Lösungsvorschlag: |
 <code java> <code java>
 +private int width;
 +private int height;
 +    
 +// Speichert pro Startkoordinate alle gefundenen Enden
 +// Jeweils als eindimensionales Array mit index 0 = x-Koordinate und index 1 = y-Koordinate
 +private ArrayList<int[]> trailEnds; 
 +
 public void partOne() {         public void partOne() {        
     // Instanzvariablen (!) für Höhe und Breite der Karte     // Instanzvariablen (!) für Höhe und Breite der Karte
     width = inputLines.get(0).length();     width = inputLines.get(0).length();
     height = inputLines.size();     height = inputLines.size();
-    +
     // Karte als int-Array     // Karte als int-Array
     int[][] map = new int[width][height];     int[][] map = new int[width][height];
Zeile 40: Zeile 51:
  
     int sumOfTrails = 0; // speichert die Summe aller Trails     int sumOfTrails = 0; // speichert die Summe aller Trails
-    +
     // Iteriere über jede Koordinate     // Iteriere über jede Koordinate
     for (int x = 0; x < width; x++) {     for (int x = 0; x < width; x++) {
Zeile 46: Zeile 57:
             // Wenn die Koordinate mit 0 beginnt, dann starte den rekursiven Aufruf             // Wenn die Koordinate mit 0 beginnt, dann starte den rekursiven Aufruf
             if (map[x][y] == 0) {             if (map[x][y] == 0) {
-                /* Wichtig: Starte den Aufruf mit einer KOPIE der Map, da die gefundenen  +                trailEnds = new ArrayList(); // setzte diese Instanzvariable für die aktuelle Startposition zurück 
-                * Trail-Enden pro Aufruf markiert werden müssen. Diese Markierungen dürfen +                sumOfTrails += trail(map, 0, x, y);
-                * im nächsten Aufruf aber nicht mehr vorhanden sein. +
-                */ +
-                sumOfTrails += trail(copyMap(map), 0, x, y);+
             }             }
         }         }
Zeile 76: Zeile 84:
     if (map[x][y] != h) {     if (map[x][y] != h) {
         return 0;         return 0;
 +    }
 +    
 +    // Basisfall: Aktuelle Koordinate (x,y) ist bereits in den gefundenen Enden 
 +    // des aktuellen Startpunktes enthalten.
 +    for (int[] end: trailEnds) {
 +        if (end[0] == x && end[1] == y) {
 +            return 0;
 +        }
     }     }
  
     // (Erfolgreicher) Basisfall: Ein Ende des Trails wurde erreicht!      // (Erfolgreicher) Basisfall: Ein Ende des Trails wurde erreicht! 
     if (map[x][y] == 9) {     if (map[x][y] == 9) {
-        map[x][y] = -1; // Markiere das Ende, damit dieses Trail-Ende nicht nochmals gefunden wird!+        trailEnds.add(new int[]{x,y}); // Speichere das aktuelle Trail-Ende.
         return 1; // return 1, damit dieses gefundene Trail-Ende gezählt wird.         return 1; // return 1, damit dieses gefundene Trail-Ende gezählt wird.
     }     }
Zeile 91: Zeile 107:
     sumOfTrails += trail(map, h+1, x, y-1);     sumOfTrails += trail(map, h+1, x, y-1);
     return sumOfTrails;     return sumOfTrails;
-} 
- 
-/** 
- * Erstellt eine Kopie der Karte 
- */ 
-private int[][] copyMap(int[][] map) { 
-    // Erstelle int-Array mit denselben Maßen 
-    int[][] copy = new int[width][height]; 
-     
-    // Kopiere jede Koordinate 
-    for (int x = 0; x < width; x++) { 
-        for (int y = 0; y < height; y++) { 
-            copy[x][y] = map[x][y]; 
-        } 
-    } 
-    return copy; 
 } }
 </code> </code>
Zeile 115: Zeile 115:
 Für den Teil 2 muss nur eine **winzige Kleinigkeit** angepasst werden.  Für den Teil 2 muss nur eine **winzige Kleinigkeit** angepasst werden. 
  
-In Teil 1 geht es darum, pro Startpunkt zu zählen, wie viele Trail-Enden man erreichen kann. Jedes Trail-Ende darf also nur einmal erreicht werden. Daher mussten wir da auch markieren, falls wir ein Ende erreicht hatten.+In Teil 1 geht es darum, pro Startpunkt zu zählen, wie viele Trail-Enden man erreichen kann. Jedes Trail-Ende darf also nur einmal erreicht werden. Daher mussten wir uns auch merken, ob wir ein Ende bereits erreicht hatten.
  
 In Teil 2 geht es darum, pro Startpunkt zu zählen, wie **oft** ein Trail-Ende erreicht werden kann. Jedes Trail-Ende darf also von "benachbarten" rekursiven Aufrufen beliebig oft erreicht werden.  In Teil 2 geht es darum, pro Startpunkt zu zählen, wie **oft** ein Trail-Ende erreicht werden kann. Jedes Trail-Ende darf also von "benachbarten" rekursiven Aufrufen beliebig oft erreicht werden. 
   * Es muss daher nun **kein** Trail-Ende mehr als "bereits gefunden" markiert werden.    * Es muss daher nun **kein** Trail-Ende mehr als "bereits gefunden" markiert werden. 
-  * Da nichts mehr markiert bzw. am Array "manipuliert" werden muss, musst du den ersten rekursiven Aufruf auch nicht mehr mit einer Kopie des Arrays starten.+  * Ebenso benötigt man also die ''ArrayList<int[]>'' nun nicht mehr
 Achte bei den Aufrufen der rekursiven Methoden darauf, dass du überall die korrekten, neuen Methoden für Teil 2 aufrufst. Achte bei den Aufrufen der rekursiven Methoden darauf, dass du überall die korrekten, neuen Methoden für Teil 2 aufrufst.
  
  • faecher/informatik/oberstufe/java/aoc/aoc2024/day10/start.1733820265.txt.gz
  • Zuletzt geändert: 10.12.2024 08:44
  • von Marco Kuemmel