Tag 15: Lagerprobleme
Am Tag 15 des Adventskalenders für Programmierer bestand die Aufgabe darin, das Verhalten eines Amok-laufenden Lagerroboters zu simulieren. Interessant waren vor Allem die Positionen der Kisten im Lager, die der Roboter ständig verschiebt, sofern sie nicht durch eine Wand oder eine Säule abgeblockt werden. Dazu war eine Abfolge von 20000 Roboterbewegungen vorgegeben.
Während im Teil 1 des Rätsels die Kisten genau ein Feld des Lagers belegen, besitzen sie im Teil 2 die doppelte Breite, so dass sie beim Verschieben auch versetzt mehrere andere Kisten mitnehmen können. Leider war meine Lösung des 1. Teils für den 2. Teil völlig unbrauchbar, so dass ein neuer Ansatz nötig wurde:
Verschiebungen laufen jetzt in zwei Phasen ab. In der ersten Phase wird rekursiv überprüft, ob die Verschiebung und die sich anschließenden Verschiebungen überhaupt möglich sind, ohne an einer Säule oder einer Wand hängenzubleiben.
def is_movable(self, pos, dx, dy):
if pos not in self.map:
return True
if self.map[pos] == "#": # Wand
return False
char = self.map[pos]
pos = (pos[0]+dx, pos[1]+dy)
if dy == 0 or char == "O": # Horizontale Verschiebung oder Teil 1
return self.is_movable(pos, dx, dy)
else:
if char == "[":
peer = (pos[0]+1, pos[1])
else:
peer = (pos[0]-1, pos[1])
return self.is_movable(pos, dx, dy) and self.is_movable(peer, dx, dy)
Nur bei positivem Ausgang der Prüfung wird die eigentliche Verschiebung wiederum rekursiv angestoßen. Die Laufzeiten für einen Testfall (700 Bewegungen) und das eigentliche Rätsel sind akzeptabel.
TEST for DAY 15
Part 1: 10092 (0.0002s)
Part 2: 9021 (0.0002s)
SOLUTION for DAY 15
Part 1: 1398947 (0.0049s)
Part 2: 1397393 (0.0062s)
