Tag 12 – Gartengruppen
Auch dieses Jahr macht der Adventskalender für Programmierer Spaß. Ganz ohne Verknüpfung mit einer Lehrveranstaltung oder einem Fakultäts-Leaderboard ist es diesmal ganz entspannt.
Am Tag 12 geht es darum, den Elfen beim Einzäunen von Beeten zu helfen. Ein Beet enthält immer genau eine Pflanzensorte. Die Lage der Pflanzen ist in Form eines großen Buchstabensalats gegeben – 140 Zeilen mit jeweils 140 Zeichen. Jeder Buchstabe steht für eine Pflanzensorte. Die erste Herausforderung besteht darin, effizient die Beete zu identifizieren.
Eine schicke Möglichkeit ist es, jede einzelne Pflanze zunächst als eigenes Beet zu sehen und anschließend benachbarte Pflanzen gleicher Sorte zu vereinen. Mit einem UNION-FIND-Algorithmus lässt sich beides jeweils in linearer Zeit erledigen.