Tag 8: Haunted Wasteland

Tag 8 ist wieder verhältnismäßig einfach.

Die Aufgabe schreit eigentlich nach Rekursion. Leider wird dies bei der Verwendung von Java zu einem Stack-Overflow führen, da viele rekursive Aufrufe nötig sind. Java unterstützt wohl leider auch noch immer nicht die Optimierung bei Verwendung einer "Endrekursion" (wenn dies falsch ist, dann bitte diese Aussage korrigieren). Daher muss auf eine iterative Vorgehensweise zurückgegriffen werden.

Hilfestellung Teil 1

  • Lies die erste Zeile als normalen String ein und speichere sie z. B. als instructions.
  • Lies alle restlichen Zeilen jeweils als String-Array ein (entferne die dazwischenliegenden Zeichen, indem du mehrfach split() verwendest). Du weißt dann, dass pro Zeile bei Index 0 immer der 'Input' der Zeile ist, bei Index 1 der linke Nachfolger und bei Index 2 der rechte Nachfolger. Speichere dann alle Zeilen (String-Arrays) in einer ArrayList<String[]>.
  • Halte in einer Variablen fest, welche das nächste zu suchende Wort ist (z. B. nextWord). Anfangs ist nextWord natürlich "AAA".
  • Setzte einen instructionPointer anfangs auf 0, um dir zu merken, welche nächste Instruktion (R oder L) ausgeführt werden muss. Du kannst dir dann mithilfe dieses Pointers jeweils den Character aus dem String instructions geben lassen mit instructions.charAt(instructionPointer).
  • Wiederhole nun solange bis nextWord dem gesuchten String "ZZZ" entspricht:
    • Suche diejenige Zeile, bei der der Input dem nextWord entspricht.
    • Je nachdem, ob die nächste Instruktion nun L oder R ist, wird nextWord auf den Index 1 oder 2 der aktuellen Zeile gesetzt.
    • Erhöhe den instructionPointer um eins und stelle sicher, dass er, wenn er das Ende aller Instruktionen erreicht hat, wieder bei 0 beginnt (→ Modulo-Operator %).
    • Zähle in der Schleife außerdem einen counter hoch für die Anzahl der Schritte.

Lösungsvorschlag

Hilfestellung Teil 2

  • Tipp vorneweg: die Ergebniszahl wird riesig. Es ist also keine Lösung, einfach für alle Start-Wörter (die auf "A" enden) jeweils gleichzeitig einen Schritt zu berechnen und immer zu prüfen, ob nun alle Wörter mit "Z" enden. Dann würde der PC womöglich noch in einigen Monaten am Rechnen sein.
  • Schaue dir besser in der Aufgabenerklärung noch mal genau den Verlauf für die beiden Start-Wörter an. Wann / mit welcher Häufigkeit findet jedes Wort sein End-Wort (mit "Z" am Ende)? Erkennst du da ein Muster?

Ja, ich habe das Muster erkannt

Lösungsvorschlag