Ich muss gestehen, dass ich mir etwas Zeit gelassen habe für diesen Blogpost. Ein Wochenende mit zu langen Abenden und zu vielen Getränken warfen mich ein paar gute Tage zurück. Hinzu kam der Schwierigkeitsgrad der Aufgaben aber lasst uns beginnen.
Tag 6 Memory Reallocation
An diesem Tag geht es um die Wiedererkennung von Mustern. Ein Liste an Bankkonten soll ausgeglichen werden. Jeder bekommt einen Teil des anderen Kontos, sodass am Ende ein Gleichgewicht entsteht. Das Ziel ist es herauszufinden wie oft die Bankkonten ausgeglichen werden bis ein Muster an Zahlen wieder erscheint. Das klingt etwas kryptisch sieht aber so aus:
- 0, 2, 7, 0 (Das dritte Bankkonto hat das meiste Geld, also gibt sie den Armen einen Anteil)
- 2, 4, 1, 2 (Nun hat das zweite Bankkonto das meiste Geld und gibt es weiter)
- 3, 1, 2, 3 (usw)
- 0, 2, 3, 4
- 1, 3, 4, 1
-
2, 4, 1, 2 (und hier haben wir wieder das gleiche Muster.
Näheres zum Rätsel findet ihr wieder auf deren Webseite: http://adventofcode.com/2017/day/6
Wie habe ich es also umgesetzt. Hierbei hilft mir eine Map, eine Liste und ein simpler Integer Zähler.
Map<List<Integer>, Integer> muster = new HashMap<>();
...
while (true) {
int index = firstMax(nums);
int redistribute = numList.get(index);
numList.set(index++, 0);
while (redistribute-- > 0) {
index %= numList.size();
numList.set(index, numList.get(index++) + 1);
}
steps++;
if (muster.containsKey(numList)) {
System.out.println("Teil 2: " + (steps - muster.get(numList)));
break;
}
muster.put(numList, steps);
}
System.out.println("Teil 1: " + steps);
....In der Liste von Integern wird der Endzustand der Bankkonten nach der Verteilung gespeichert. Dieser Endzustand wird dann wiederum mit der Schrittanzahl in der Map gespeichert. Über die Methode "containsKey(Object)" kann ich so die Listen miteinander vergleichen. Wenn das Ergebnis der Abfrage true ist wird die while Schleife verlassen. Im zweiten Teil des Rätsels möchte man wissen wie viele Zyklen den eine komplette Schleife hat. Dies errechnen wir über Subtraktion der Schrittanzahl zum Endzeitpunkt der Blockumverteilung mit der Schrittanzahl der wiedererkannten Liste aus der Map. Die gute alte Map rettet uns hier vor sehr viel Programmierung.
Tag 7 Recursive Circus
Die Beschreibung an dem Tag fängt schon einmal gut an: "Wandering further through the circuits of the computer, you come upon a tower of programs that have gotten themselves into a bit of trouble. A recursive algorithm has gotten out of hand, and now they're balanced precariously in a large tower."
Aus der Beschreibung wird man nicht sehr schlau aber die Beispiele erklären es ganz gut. Die Input-Liste sieht so aus:
pbga (66) xhth (57) ebii (61) havc (66) ktlj (57) fwft (72) -> ktlj, cntj, xhth qoyq (66) padx (45) -> pbga, havc, qoyq tknk (41) -> ugml, padx, fwft jptl (61) ugml (68) -> gyxo, ebii, jptl gyxo (61) cntj (57)
Der daraus enstsehende Baum sieht so aus:
gyxo
/
ugml - ebii
/ \
| jptl
|
| pbga
/ /
tknk --- padx - havc
\ \
| qoyq
|
| ktlj
\ /
fwft - cntj
\
xhth
Die erste Aufgabe ist einfach: Finde die erste Node im Baum. Im Beispiel ist das "tknk". Dies kann man auf zwei verschiedene Arten machen. In Java lässt sich diese Frage über zwei Listen klären.
private void findNodeWithoutParent() {
ArrayList<Node> AllChildren = getAllChildren();
for (int i = 0; i < Nodes.size(); i++) {
if (!AllChildren.contains(Nodes.get(i))) {
System.out.println("The Node without Parents: " + Nodes.get(i).getName());
}
}
}
private ArrayList<Node> getAllChildren() {
ArrayList<Node> AllChildren = new ArrayList<>();
for (Node node : Nodes) {
if (node.hasChildren()) {
for (Node child : node.getChildren()) {
AllChildren.add(child);
}
}
}
return AllChildren;
}oder man macht es mit einer Bash-Anweisung :)
grep -o -E '[a-z]+' input | sort | uniq -uTeil 2 ist hier schon etwas schwieriger. Einer der Knoten hat ein unkorrekte Gewichtung und es soll herausgefunden werden welche die Korrekte Gewichtung ist. Wie macht man das also? Man durchläuft jeden Zweig und errechnet dessen Gewichtung. Danach gibt man die Gewichtung jedes Baumes aus und dann errechnet man die Differenz zwischen den Ergebnissen. Es wird nur ein Zweig eine andere Zahl haben als die anderen Zweige. Tada und auch das ist geschafft.
Tag 8 I Heard You Like Registers
Ein Tagesaufgabe die regulärer Ausdrücke bedarf. Genau das was ich mag :)
"You receive a signal directly from the CPU. Because of your recent assistance with jump instructions, it would like you to compute the result of a series of unusual register instructions."
Jede Anweisung besteht aus mehreren Teilen: dem Register zum Ändern, ob der Wert des Registers erhöht oder verringert werden soll, dem Betrag, um den es erhöht oder verringert werden soll, und einer Bedingung. Wenn die Bedingung fehlschlägt, überspringen wir den Befehl, ohne das Register zu verändern. Die Register beginnen alle bei 0.
Der Input sieht so aus: b inc 5 if a > 1 a inc 1 if b < 5 c dec -10 if a >= 1 c inc -20 if c == 10
Da a in der ersten Zeile noch unbekannt ist, wird sein Wert als 0 angenommen. Die Bedingung ist also FALSE. In der Tagesaufgabe sind jeweils der höchste Wert sowie der größte Wert gesucht. Um beides zu bekommen habe ich die Input-Datei Zeilenweise in eine Liste eingelesen. In einer Foreach Schleife laufe ich über die Liste und führe die Anweisungen aus und speichere das Ergebnis in einer Map.
private Map<String, Integer> resolveInstructions(List<String> rows) {
Map<String, Integer> registers = new HashMap<>();
Pattern pattern = Pattern.compile("(?<name>[a-z]+) (?<instruction>[a-z]+) (?<instvalue>-?[\\d]+) if (?<nameofvar>[a-z]+) (?<boolean>(<|>|<=|>=|==|!=|)[-?\\s\\d]+)");
for (String row : rows) {
Matcher matcher = pattern.matcher(row);
if (matcher.matches()) {
String name = matcher.group("name");
String instruction = matcher.group("instruction");
int amount = Integer.parseInt(matcher.group("instvalue"));
String reference = matcher.group("nameofvar");
String boolexpression = matcher.group("boolean");
registers.putIfAbsent(name, 0);
try {
ScriptEngineManager sem = new ScriptEngineManager();
ScriptEngine se = sem.getEngineByName("JavaScript");
int current = registers.get(name);
int value = registers.getOrDefault(reference, 0);
String myExpression = value + boolexpression;
boolean result = Boolean.parseBoolean(se.eval(myExpression).toString());
if (result) {
registers.put(name, instruction.equals("inc") ? current + amount : current - amount);
}
if (registers.get(name) > numbProcess) {
numbProcess = registers.get(name);
}
} catch (ScriptException e) {
System.out.println("Invalid Expression");
e.printStackTrace();
}
}
}
return registers;
}Dieses Monster von Methode erledigt im Grunde die gesamte Arbeit. Über den Matcher wird der reguläre Ausdruck auf die Zeile angewandt. Durch die Gruppen kann ich nun die einzelnen Variablen leicht anwenden. Um die Bedingung zu prüfen mache ich von der JavaScript Engine gebrauch. Diese teilt mir das Ergebnis der zusammengesteckten Boolischen Bedingung mit und je nachdem wird die Anweisung ausgeführt. Die zweite IF-Abfrage ist für den zweiten Teil des Rätsels zuständig. Darin geht es darum den höchsten Wert, der während dieses Vorgangs in einem beliebigen Register gehalten wird zu speichern.
Hier noch die anderen Methoden:
private int getMaxValueofRegister(Map<String, Integer> registers) {
return Collections.max(registers.values());
}
private int getHighestValueofRegister(Map<String, Integer> registers) {
return Collections.max(registers.values(), Comparator.comparingInt(Math::abs));
}Tag 9 Stream Processing
Ich habe richtig lang versucht diese Aufgabe rekursiv zu lösen bis ich es aufgegeben und eine iterative Lösung genommen habe. Die Aufgabe ist einen Stream von Charaktern zu parsen. Unterschieden werden die Charakter in Gruppen und Garbage.
Es funktionierte rekursiv nicht da man den State immer mitnehmen musste indem sich der Pointer befand. Ich konnte es mir jeden Falls nicht vorstellen.
Hier ein Ausschnit aus dem Input: {{{{{<>},{{<u!>},<!!!!!!!><!!u!!"!>!!!!!>!>},<,!!o>}....
Jede offene geschweifte Klammer öffnet eine neue Gruppe, jedes < bzw. > markiert Garbage. Wenn ein ! davor steht wird das danach kommende ignoriert. Das Ziel ist es die Summe der Tiefe aller Gruppen zu berechnen.
Das heißt: {{{}}} = 1+2+3 = 6
Hierbei hilft ein Enum aus indem die Zustände als Objekte eingetragen sind.
enum Zustand {
OPEN, CLOSE, GARBAGE, IGNORE, OTHER;
// Rules for Finite State Machine
static {
Zustand.OTHER.addTransition('{', Zustand.OPEN);
Zustand.OTHER.addTransition('}', Zustand.CLOSE);
Zustand.OTHER.addTransition('<', Zustand.GARBAGE);
Zustand.OPEN.addTransition('}', Zustand.CLOSE);
Zustand.OPEN.addTransition('<', Zustand.GARBAGE);
Zustand.OPEN.addTransition(',', Zustand.OTHER);
Zustand.CLOSE.addTransition('{', Zustand.OPEN);
Zustand.CLOSE.addTransition('<', Zustand.GARBAGE);
Zustand.CLOSE.addTransition(',', Zustand.OTHER);
Zustand.GARBAGE.addTransition('!', Zustand.IGNORE);
Zustand.GARBAGE.addTransition('>', Zustand.OTHER);
Zustand.IGNORE.addTransition('!', Zustand.GARBAGE);
}
final Map<Character, Zustand> transitions = new HashMap<>();
private void addTransition(char c, Zustand accept) {
transitions.put(c, accept);
}
public State getTransition(char c) {
return transitions.getOrDefault(c, this);
}
}Das Enum ermöglicht es mir nun iterativ durch den Stream durchzulaufen und dabei die gesuchten Werte zu errechnen.
for (int i = 0; i < input.length; i++) {
char c = input[i];
if (current == Zustand.IGNORE) c = '!';
Zustand next = current.getTransition(c);
switch (next) {
case OPEN:
level++;
break;
case CLOSE:
score += level--;
break;
case GARBAGE:
if (current == Zustand.GARBAGE) garbageCount++;
}
current = next;
}Aber das schlimmste kommt noch.
Tag 10 Knot Hash
Dieser Tag habe ich überhaupt nicht verstanden. Ich habe die zwei goldene Sterne zwar aber nicht durch eigene Leistung. :( Ich muss selber nochmal schauen wie Knot Hashes funktionieren.