Tag 8: Haunted Wasteland

public int partOne() {
    String instructions = inputLines.get(0).trim();
    int instructionPointer = 0;
 
    ArrayList<String[]> nodes = new ArrayList<String[]>();
    for (int i = 2; i < inputLines.size(); i++) {
        String line = inputLines.get(i);
        String[] node = new String[3];
        node[0] = line.split("=")[0].trim();
        node[1] = line.split("[=]")[1].split("[,]")[0].split("[(]")[1].trim();
        node[2] = line.split("=")[1].split(",")[1].split("[)]")[0].trim();
        nodes.add(node);
    }
 
    int steps = 0;
    String nextWord = "AAA";
    while (!nextWord.equals("ZZZ")) {
        for (String[] node: nodes) {
            if (node[0].equals(nextWord)) {
                if (instructions.charAt(instructionPointer) == 'L') {
                    nextWord = node[1];
                } else {
                    nextWord = node[2];
                }
                break;
            }
        }
        steps++;
        instructionPointer = (instructionPointer + 1) % instructions.length();
    }
 
    return steps;
}

• Es genügt tatsächlich, für jedes Start-Wort nur das erste End-Wort zu finden und sich zu merken, wie viele Schritte das waren.
• Am Ende muss man von allen Schritten für alle Start-Wörter nur das kleinste gemeinsame Vielfache (kgV) finden. Da gibt es bei google genügend mögliche Implementationen zu finden.
• Die kgV-Methode kann immer nur zwei Zahlen verarbeiten. Du kannst ja aber in einer Schleife immer eine Zahl aus allen Schritten entfernen, und mit dem bisherigen kgV verrechnen.

public long partTwo() {
    String instructions = inputLines.get(0).trim();
 
    ArrayList<String[]> nodes = new ArrayList<String[]>();
    for (int i = 2; i < inputLines.size(); i++) {
        String line = inputLines.get(i);
        String[] node = new String[3];
        node[0] = line.split("=")[0].trim();
        node[1] = line.split("[=]")[1].split("[,]")[0].split("[(]")[1].trim();
        node[2] = line.split("=")[1].split(",")[1].split("[)]")[0].trim();
        nodes.add(node);
    }
 
    ArrayList<String> nextWords = new ArrayList<String>();
    for (String[] node: nodes) {
        if (node[0].endsWith("A")) {
            nextWords.add(node[0]);
        }
    }
 
    ArrayList<Integer> wordSteps = new ArrayList<Integer>();
 
    for (String nextWord: nextWords) {
        int steps = 0;
        int instructionPointer = 0;
        while (!nextWord.endsWith("Z")) {
            for (String[] node: nodes) {
                if (node[0].equals(nextWord)) {
                    if (instructions.charAt(instructionPointer) == 'L') {
                        nextWord = node[1];
                    } else {
                        nextWord = node[2];
                    }
                    break;
                }
            }
            steps++;
            instructionPointer = (instructionPointer + 1) % instructions.length();
        }
        wordSteps.add(steps);
    }
 
    long result = wordSteps.remove(0);
    while (wordSteps.size() > 0) {
        result = kgv(result, wordSteps.remove(0));
    }
    return result;
 
}
 
private long ggt(long a, long b) {
    if (b == 0) {
        return a;
    } else {
        return ggt(b, a % b);
    }
}
 
private long kgv(long a, long b) {
    return (a * b) / ggt(a, b);
}