Tag 12 - Hot Springs

Lösungshinweise Teil 1

Teil 1 ist (noch) über verschiedene Wege lösbar. Prinzipiell die einfachste (aber nicht die schnellste) Methode ist, sich rekursiv alle möglichen Eingabestrings zu erstellen.
Sobald der String erstellt ist, ist der Basisfall der Rekursion erreicht und man kann mithilfe eines regulären Ausdrucks prüfen, ob der String den angeforderten Gruppengrößen entspricht. Z. B. ^\\.*\\#{3}\\.+\\#{2}\\.*$ würde prüfen, ob zuerst eine Dreiergruppe an Rauten und dann eine Zweiergruppe an Rauten im String vorkommt.

Alternativ lässt man die Überprüfung mit regulären Ausdrücken weg (diese sind nämlich langsam) und überprüft Buchstaben für Buchstaben, ob dies den angeforderten Gruppen-Größen entspricht.

Lösungshinweis für reguläre Ausdrücke

public int partOne() {
    int summe = 0;
 
    for (String line: inputLines) {
        int[] numbers = strToIntArray(line.split(" ")[1]);
 
        // Baue einen korrekten regulären Ausdruck (regex) 
        String regex = "^\\.*";
        for (int n: numbers) {
            regex += "\\#{" + n + "}\\.+";
        }
        regex = regex.substring(0, regex.length()-1);
        regex += "*$";
 
        correctArrangementsPerLine = 0;
        // Baue nacheinander alle denkbaren arrangements auf.
        buildArrangements(line.split(" ")[0], "", regex);
        summe += correctArrangementsPerLine;
    }
 
    return summe;
}
 
private void buildArrangements(String input, String current, String regex) {
    if (current.length() == input.length()) {
        // Prüfe, ob dieser String erlaubt ist.
 
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(current);
        if (matcher.find()) {
            correctArrangementsPerLine++;
        }
 
    } else if (input.charAt(current.length()) != '?') {
        buildArrangements(input, current + input.charAt(current.length()), regex);
    } else {
        buildArrangements(input, current + '.', regex);
        buildArrangements(input, current + '#', regex);
    }
}

Teil 2

Mit 3 Tagen Verspätung nun auch endlich eine ausformulierte Lösung für Teil 2…
Teil 2 ist definitiv nicht trivial. Beide einfachen Ansätze aus Teil 1 genügen hier nicht mehr, da (je nach Eingabedatei) etwa 1,6 Billionen (!) Kombinationen durchprobiert werden müssten! Man muss sich daher dringend die "dynamische Programmierung" zunutze machen. Damit speichert man für jeden rekursiven Methodenaufruf dessen Ergebnis, bevor es als return zurückgegeben wird. Dann kann man zu Beginn jedes Aufrufs dieser Methode bei gegebenen Parametern überprüfen, ob diese Parameter schon einmal aufgerufen wurden und man dazu direkt das Ergebnis liefern kann.

• Rufe pro Eingabezeile eine rekursive Methode getMatches() auf, die zwei Parameter entgegennimmt. Erstens die 5-fach hintereinander gehängten linken Strings. Zweitens die 5-fach hintereinander gehängten Zahlen als int-Array.