Nachdem ich mir in den ersten 20 Tagen des Python Bootcamps die Grundlagen zu Python aneignen konnte, machte mich ein ehemaliger Studienfreund auf das Event Advent of Code aufmerksam. Die Veranstaltung existiert schon seit 2015 und läuft jährlich in der Vorweihnachtszeit. Im Zeitraum vom 1. Dezember bis zum 12. Dezember konnten jeden Morgen ab 6 Uhr zwei Programmieraufgaben gelöst werden. Perfektes Timing also, um meine Programmierkenntnisse auf die Probe zu stellen und dabei ein bisschen praktische Erfahrung zu sammeln, bevor ich mich dem nächsten Lernabschnitt widme.
Die Aufgaben der jeweiligen Tage sind in eine kleine Weihnachtsgeschichte eingebettet und werden an einem einfachen Beispiel samt Testinput erklärt. Mit dem Programm, das anhand des Testinputs programmiert und getestet werden kann, muss dann eine weitaus größere Eingabe ausgewertet werden. Das korrekte Ergebnis kann dann zur Belohnung gegen einen Stern eingetauscht werden. Bei einer falschen Antwort wird eine Zeitstrafe verhängt, um das Erraten der richtigen Antwort mit einem Brute-Forcing Ansatz zu verhindern. Die Aufgaben eines Tages hängen thematisch zusammen, wobei die zweite Aufgabe meistens schwieriger ist.
In diesem Blogeintrag möchte ich von den Aufgaben, meinen Lösungen und den Herausforderungen der einzelnen Tage erzählen:
Tag 1: Anreise am Nordpol#
Teil 1: Nullen zählen#
Geschichte: Am ersten Tag reisen wir am Nordpol an, um den Elfen beim Dekorieren zu helfen. Doch am geheimen Eingang können wir die Tür, die den Zugang versperrt nicht öffnen. Das richtige Passwort lässt sich nur in einem verschlossenen Safe mit Drehzahlenschloss nachschauen.
Aufgabe: Um den Safe zu öffnen muss eine Reihe von Drehanweisungen ausgeführt werden. Dabei sind die einzelnen Anweisungen wie folgt aufgebaut L68 oder R48. Der Buchstabe gibt dabei die Drehrichtung vor, die Zahl, die Anzahl an Positionen (Klicks), die der Drehknopf gedreht werden muss.
Das gesuchte Antwort ist die Anzahl der Male, die der Dial während des Programmdurchlaufes auf der Position 0 steht.
Lösungsansatz: Den Drehknopf (engl.: Dial) mit seinen 100 Position habe ich mit einer Liste dargestellt, auch wenn im Nachhinein betrachtet eine Variable zur Speicherung der jeweiligen Zwischenergebnisse gereicht hätte. Die Eigenschaft des Dials, dessen Wert nach der 99 wieder auf 0 springt und vise versa schreit nach dem Modulo Operator. Der Startpunkt ist in der Aufgabe mit 50 vorgegeben.
Der Buchstabe legt die Drehrichtung durch einen neutralen Multiplikator fest - somit wird bei L der Zahlenwert der Anweisung vom Zahlenwert des Dials abgezogen oder bei R wird er dazu gezählt. Steht der Drehknopf am Ende einer Drehung auf 0 wird die Antwortzähler um eins erhöht.
Logik des Programms:
- Lege die Drehrichtung anhand des Buchstabens fest
- Drehe den Knopf um die Anzahl der Klicks
- Überprüfe, ob der Dial auf Null steht
- Wenn auf Null -> Zähle die Variable Passwort hoch
- Wiederhole, bis alle Zahlen des Inputs genutzt wurden
Nach dem Einlesen der Daten sah das Programm zur Lösung wie folgt aus:
state_of_dial = STARTING_POINT # STARTING_POINT = 50
password = 0
for item in test_combination:
if "L" in item:
modifier = -1
else:
modifier = 1
# Check 0 position was hit
state_of_dial = (state_of_dial + (modifier * int(item[1:]))) % 100
if state_of_dial == 0:
password += 1
print(f"Password: {password}")
Teil 2: Wirklich alle Nullen#
Aufgabe: Für den zweiten Teil mussten alle Gelegenheiten gezählt werden, bei denen der Drehknopf den Zustand 0 hat, also sowohl am Ende eines Drehvorganges als auch, wenn dieser während der Bewegung über die Null “hinwegschreitet”.
Das Schwierigste am ersten Tag war zu verstehen, dass das Überschreiten der Nullposition, wenn diese von der Nullposition ausgeht, nicht doppelt gezählt werden darf. Das hatte bei mir einen Bug verursacht, der nicht ganz trivial zu finden war.
Lösungsansatz: Das Programm sah am Ende wie folgt aus und überprüft mit einer geschachtelten Schleife _nach_ jedem Klick, ob die momentane Position des Dials Null entspricht. Damit konnte das doppelte Zählen in dem Spezialfall ausgeschlossen werden.
state_of_dial = STARTING_POINT
password = 0
for item in combination:
for _ in range(int(item[1:])):
if "L" in item:
modifier = -1
else:
modifier = 1
#Check 0 position was hit
state_of_dial = (state_of_dial + (modifier * 1)) % 100
if state_of_dial == 0:
password += 1
print(f"Password: {password}")
Fazit: Ein tolle Aufgabe, um in die Veranstaltung zu starten.
Tag 2: Der Tag im Geschenkeladen#
Teil 1: Sortieren für Anfänger#
Geschichte: Nachdem die Tür des geheimen Eingangs am ersten Tag überwunden wurde, fahren wir mit einem Aufzug in die Geschenkabteilung. Dort herrscht große Unruhe, denn ein junger Elf hat unbeabsichtigt eine große Menge ungültiger Geschenke-IDs in das Warensystem der Abteilung eingegeben.
Aufgabe: Es sollen Zahlenspannen auf ungültigen IDs überprüft werden. Die IDs lassen sich dadurch erkennen, dass deren fordere und hintere Hälfte identisch sind.
Beispiele für ungültige IDs sind:
- 77 -> 7 vorne 7 hinten
- 2323 -> 23 vorne 23 hinten
Lösungsansatz: Bei der Lösungen habe ich überprüft, ob die erste Hälfte des Strings der zweiten Hälfte entspricht. Dazu habe ich das gerade erst erlernte Slicing verwendet, um die einzelnen Hälften innerhalb des Strings anzusprechen.
Logik des Programms:
- Ist die Anzahl der Ziffern einer ID eine gerade Zahl
- Wenn nicht -> Gültige ID
- Ermittlung der Länge einer Hälfte
- Überprüfung, ob die Hälften identisch sind
- Wenn ja -> Aufsummieren des Zahlenwertes der falschen ID zur Gesamtsumme
for id in id_ranges:
st_nd_number = id.split("-")
st_num = int(st_nd_number[0])
nd_num = int(st_nd_number[1])
for number in range(st_num, nd_num + 1):
if int(len(str(number))) % 2 == 0:
length_of_half = int(len(str(number)) / 2)
first_half = str(number)[:length_of_half]
second_half = str(number)[length_of_half:]
if first_half == second_half:
invalid_id_sum += number
print(f"Final sum: {invalid_id_sum}")
Hier ist mir ein Leichtsinnsfehler unterlaufen. Da am ersten Tag die Anzahl der Nullen gezählt werden sollte, hatte ich bei der Anweisung: “What do you get if you add up all of the invalid IDs?” fälschlicherweise angenommen, das wäre hier genauso. Am Ende stellte sich heraus, dass die eigentlichen Zahlenwerte der IDs aufsummiert werden müssen.
Teil 2: Und Fortgeschrittene#
Aufgabe: Die Aufgabe im zweiten Teil war die Zahlenspannen zusätzlich auf IDs mit sonstigen Wiederholschemas zu überprüfen. Zusätzlich zu den IDs aus Teil 1 sind dabei auch folgende IDs ungültig:
- 33333 -> Sequenz (3-3-3-3-3) fünffache Wiederholung
- 272727 -> Sequenz (23-23-23) dreifache Wiederholung
Lösungsansatz: Ich habe die Überprüfung der Zahlen in eine Funktion ausgelagert. Die Funktion hat zwei Parameter - die ID und die Sequenz. Sequenz bezeichnet dabei die Länge der einzelnen Sequenz, die sich dann mehrfach wiederholt.
Logik der Programms:
- Lässt sich die ID ganzzahlig durch eine Länge der Sequenz teilen?
- Ist die Sequenz länger als die Länge der ID?
- Wenn 1. oder 2. -> Gebe False zurück
- Speichere die Anzahl der Ziffern, die die Sequenz vorgibt in einer Vergleichsvariable
- Überprüfe, ob die Ziffern aus der ID nur aus einer Abfolge des Wertes aus der Vergleichsvariable besteht.
- Wenn nein -> Gebe False zurück, ansonsten True
def recurring_sequence(id, sequence):
"""Takes an ID and sequence as argument, returns
true, if the id contains only one repeated sequence"""
# Check if sequenz is a divisor for string
if len(id) % sequence != 0:
return False
elif len(id) <= sequence:
return False
else:
# Fill compare_sample
compare_sample = []
for position in range(sequence):
compare_sample.append(id[position])
# Check if the string consists only of a single sequenz of letters
for round_to_go in range(int(len(id) / sequence)):
for position in range(sequence):
if id[round_to_go * sequence + position] != compare_sample[position]:
return False
return True
Tag 3: Ohne Saft am Fahrstuhl#
Teil 1: Batteriemaximierer#
Geschichte: Nach dem wir am Vortag die falschen IDs aus dem Warenwirtschaftssystem gefischt haben, geht es weiter in die Lobby. Ein paar Stockwerke trennen uns noch von unserem Ziel, aber nach dem Betreten der Lobby stellen wir fest, dass die Fahrstühle alle außer Betrieb sind. Ein alternativer Weg wäre eine Rolltreppe, aber um diese trotz Störung in Betrieb nehmen zu können, benötigen wir die maximale Energie aus den Notfallbatteriepacks.
Aufgabe: Die Batterien sind in mehreren Bänken (Reihen) angeordnet. Dabei hat jede Batterie einen Zustand zwischen 1 und 9 je nachdem wie viel Energie sie zur Verfügung stellen kann. In jeder Reihe soll nun die größte Energiereserve genutzt werden. Dabei ist die Gesamtenergie die größte zweistellige Zahl in der Zahlenreihe.
Lösungsansatz: Um in einer Zahlenreihe den höchsten zweistelligen Wert zu finden, muss die höchste Zahl für die Zehnerstelle in der Zahlenreihe (ausgeschlossen der letzten Position) gefunden werden. Danach sucht man in der Zahlenreihe ab der Position der Zehnerstelle die höchste Zahl für die Einerstelle. Das Ergebnis ist die Summe der höchsten Werte aller Reihen.
Programmlogik:
- Finde höchste Zahl für Zehnerstelle -> Bereich: Start Zahlenreihe bis Zahlenreihe -1
- Finde höchste Zahl für Einerstelle -> Bereich: Position Zehnerstelle bis Ende Zahlenreihe
Der Programmcode für die relevante Methode dazu sieht wie folgt aus:
def find_highest_jolt(bank):
highest_tenth_position = 0
highest_jolt = ""
# Do not check the last battery in a bank
highest = 0
for position in range(len(bank) - 1):
position_value = int(bank[position])
if position_value > highest:
highest = position_value
highest_tenth_position = position
highest_jolt += str(highest)
highest = 0
for position in range(highest_tenth_position + 1, len(bank)):
position_value = int(bank[position])
if position_value > highest:
highest = position_value
highest_jolt += str(highest)
return int(highest_jolt)
Teil 2: Völlig überladen#
Aufgabe: Im zweiten Teil der Aufgabe muss die Energie aus 12 Batterien gezogen werden und daher besteht eine Zahl aus 12 Stellen anstatt aus 2.
Lösungsansatz: Der Lösungsansatz verändert sich nicht grundlegend. Die Spanne, in der jede höchste Zahl gesucht werden kann, ist nur kleiner, da aus der Restspanne der Zahlen eine größere Anzahl an Zahlen entnommen werden muss.
Programmlogik:
- Finde höchste Zahl für Zahl 1/12 -> Bereich: Start Zahlenreihe bis Zahlenreihe -12
- Finde höchste Zahl für Zahl 2/12 -> Bereich: Position höchste Zahl aus 1. bis Zahlenreihe -11
- [ … ]
- Finde höchste Zahl für Einerstelle (12/12) -> Bereich: Position Zehnerstelle bis Ende Zahlenreihe
Die Methode zur Ergänzung findet in einer Reihe (Bank) und einer Spanne mit Anfangswert (start_value) und Endwert (stop_value) die Position der höchsten Nummer, da aus der Position der Wert der Zahl ermittelt werden kann, aber aus dem Wert nicht zwangsläufig die Position (mehrfaches Vorkommen eines Zahlenwertes). Beide Informationen sind für den Folgeschritt notwendig.
Der Programmcode für die relevante Methode dazu sieht wie folgt aus:
def find_highest_value_in_range(bank, start_value, stop_value):
"""Looks through a range of items - returns the position of the
highest value within range(start_value, stop_value) of that list"""
position_highest_number = 0
highest = 0
for position in range(start_value, stop_value):
position_value = int(bank[position])
if position_value > highest:
highest = position_value
position_highest_number = position
return position_highest_number
Tag 4: Die Geschenkpapierfabrik#
Teil 1: Suche nach der Rolle im Papierhaufen#
Geschichte: Nachdem zumindest die Rolltreppe wieder läuft, fahren wir einen Stock tiefer in die Abteilung, in der, den großen Papierrollen zur Folge wohl das Geschenkpapier hergestellt wird. Allerdings ist das eine Sackgasse. Wenn wir hier mit einem Logistikproblem helfen, wäre einer der Gabelstapler frei, um durch eine Wand zu brechen und uns einen provisorischen Durchgang zu schaffen.
Aufgabe: Vorgegeben ist ein Lageplan der Papierrollen. Es sollen alle Papierrollen ermittelt werden, die weniger als vier angrenzende Rollen haben, den diese sind die Einzigen, die von den Gabelstaplern bewegt werden können. Die gesuchte Antwort ist die Anzahl der beweglichen Rollen.
Lösungsansatz: Um die entsprechenden Rollen zu finden, muss für jede Position überprüft werden, ob dort eine Rolle gelagert wird und wie viele der Nachbarpositionen ebenfalls belegt sind.
Programmlogik:
Überprüfe für jede Position in jeder Reihe:
- Steht hier eine Rolle
- Wenn ja: Fahre wie folgt fort:
- Überprüfe, ob die Position eine Randposition ist
- Überprüfe alle Nachbarpositionen, ob diese im betrachteten Feld liegt
- Wenn ja: Überprüfe, ob hier eine Rolle steht
- Wenn ja: Zähle die Anzahl der Nachbarn hoch
- Wenn ja: Überprüfe, ob hier eine Rolle steht
- Wenn ja: Fahre wie folgt fort:
- Ist die Anzahl der Nachbarn > 3:
- Ja -> Überprüfe die nächste Position
- Nein -> Zähle die Variable movable_rolls um 1 hoch
Das Programm sieht in Python wie folgt aus:
def has_no_neighbors():
movable_rolls = 0
for rows in range(0, len(stock)):
for position in range(0, len(stock[rows])):
neighbors = 0
if stock[rows][position] == "@":
# Check upper boarder
if rows != 0:
if stock[rows - 1][position] == "@":
neighbors += 1
if position != 0:
if stock[rows - 1][position - 1] == "@":
neighbors += 1
if position != len(stock[rows]) - 1:
if stock[rows - 1][position + 1] == "@":
neighbors += 1
# Check lower boarder
if rows != len(stock) - 1:
if stock[rows + 1][position] == "@":
neighbors += 1
if position != 0:
if stock[rows + 1][position - 1] == "@":
neighbors += 1
if position != len(stock[rows]) - 1:
if stock[rows + 1][position + 1] == "@":
neighbors += 1
# Check left and right
if position != 0:
if stock[rows][position - 1] == "@":
neighbors += 1
if position != len(stock[rows]) - 1:
if stock[rows][position + 1] == "@":
neighbors += 1
if neighbors < 4:
movable_rolls += 1
return movable_rolls
Teil 2: Das Gabelstaplerballett#
Aufgabe: Im zweiten Teil sollte überprüft werden, ob nach dem Entfernen der beweglichen Papierrollen, weitere Rollen bewegt werden können, da sich durch die Veränderung zwangsläufig die Dichte im Raum reduziert.
Lösungsansatz: Grundsätzlich wurde hier die Methode aus dem ersten Teil verwendet. Allerdings muss bei einer Entnahme (einer Rolle) die Änderung in den Lageplan geschrieben werden. Die Prüfung erfolgt dabei wieder für alle Positionen. Bei einer Änderung wird ein weiterer Durchgang angestoßen, bis keine Änderungen mehr möglich sind.
Programmlogik:
- Während im letzten Durchgang Veränderung (still_changing) durchgeführt wurden:
- Prüfe für alle Rollen einer Reihe und für alle Reihen:
- Prüfe, ob Rolle beweglich ist
- Wenn ja: Ergänze Lageplan (@ -> .)
- Setze die Wiederholungsvariable (still_changing) auf True
- Prüfe, ob Rolle beweglich ist
- Prüfe für alle Rollen einer Reihe und für alle Reihen:
Das Programm sieht in Python wie folgt aus:
rolls_removed = 0
rounds = 0
still_changing = True
while still_changing:
still_changing = False
rounds += 1
for row in range(len(stock)):
for pos in range(len(stock[row])):
if has_no_neighbors(pos, row):
# Replace Roll with empty space
l = list(stock[row])
l[pos] = "."
stock[row] = "".join(l)
rolls_removed += 1
still_changing = True
print(f"Removed rolls: {rolls_removed}")
print(f"Rounds needed: {rounds}")
Tag 5: Die Guten ins Töpfchen#
Teil 1: Das große Aussortieren#
Geschichte: Der Wanddurchbruch bringt eine Cafeteria zum Vorschein. Auch hier hört man Elfen schimpfen. Wir informieren uns über den Grund. Durch die Umstellung des Warenwirtschaftssystem kann nicht mehr bestimmt werden, welche Lebensmittel frisch und welche verdorben sind - Hilfe wird erbeten.
Aufgabe: Vorgegeben sind ID-Spannen, die die frischen Zutaten beinhalten. Daneben sind die zu prüfenden IDs gelistet. Die Aufgabe besteht nun darin zu überprüfen, ob die IDs der Zutaten in eine dieser Spannen fällt oder nicht.
Lösungsansatz: Beim Einlesen der Daten wurden die Spannen als Liste mit jeweils zwei Elementen einer Liste id_ranges hinzugefügt. Eine Methode überprüft dann für eine übergebene ID in allen Spannen, ob diese beinhaltet ist.
Programmlogik:
- Einlesen des Inputs in zwei Listen
- Liste von Listen mit zwei Elementen ([Spanne obere, untere Grenze])
- Liste aller IDs
- Überprüfen, ob für eine ID folgendes gilt:
- Spanne untere Grenze <= ID <= Spanne obere Grenze
- Wenn ja -> Gebe True zurück
- Spanne untere Grenze <= ID <= Spanne obere Grenze
before = True
with open(FILE_NAME) as file:
for line in range(FILE_SIZE):
new_line = file.readline().strip()
if new_line == "":
before = False
continue if before:
id_ranges.append(new_line.split("-"))
else:
ingredients.append(new_line)
def in_range(id):
for id_range in id_ranges:
if int(id) >= int(id_range[0]) and int(id) <= int(id_range[1]):
return True
return False
for id in ingredients:
if in_range(id):
fresh_count += 1
print(f"Fresh ingredients: {fresh_count}")
Teil 2: Wenn man schon dabei ist…#
Aufgabe: Für die Aufgabe im zweiten Teil sollten nun alle IDs gezählt werden die anhand der Spannen als frisch anzusehen sind. Dabei werden nur noch die Spannen, nicht mehr die IDs aus Teil 1 betrachtet.
Lösungsansatz: Der erste Ansatz war, alle Spannen zu durchlaufen und alle beinhalteten IDs in einem Set zu speichern. Theoretisch wäre die Länge der Sets die gesuchte Antwort. Allerdings lag die spätere Antwort jenseits der Billionen, was zum ersten Mal zu einem Performanceproblemen geführt hat. Die Dimensionen waren einfach zu groß. Der alternative und erfolgreiche Ansatz war, die zu überprüfenden Spannen mit den jeweils Vorangegangenen zu vergleichen und bei Überschneidungen, die aktuelle Spanne, um die Überschneidung zu kürzen. Danach muss der Betrag aller Spannen berechnet und zur Lösung aufsummiert werden.
Programmlogik:
Für eine ID Range an der übergebenen Position (Spanne A), vergleiche mit allen vorangegangene Ranges (Spanne B) im Bereich 0 -> aktuelle Position - 1:
- Gibt es eine vollständige Überschneidung zwischen Spanne A und Spanne B?
- Ist Spanne A größer? -> Kürze Spanne A und hänge eine weitere Spanne der Liste an, die den hinteren überschneidungsfreien Anteil beinhaltet.
- Ist Spanne A kleiner? -> Setze die Spanne A auf Null
- Gibt es eine partielle Überschneidung? -> Beschneide den Anfang oder das Ende von Spanne A
- Rechne die Beträge aller Spannen zusammen
Die entsprechende Methode sieht wie folgt aus:
def cut_id_ranges(position):
global id_ranges
for id_range in range(0, position):
id_range_input = id_ranges[position]
start_id_input = int(id_range_input[0])
end_id_input = int(id_range_input[1])
start_id_compare = int(id_ranges[id_range][0])
end_id_compare = int(id_ranges[id_range][1])
# If input range is greater than compare range
if start_id_input < start_id_compare and end_id_input > end_id_compare:
id_ranges.append([str(end_id_compare + 1), str(end_id_input)])
end_id_input = start_id_compare - 1
# If input range is fully part of compare range
elif start_id_input >= start_id_compare and end_id_input <= end_id_compare:
start_id_input = 0
end_id_input = -1
# If input range overlaps compare range
else:
if start_id_input >= start_id_compare and start_id_input <= end_id_compare:
start_id_input = end_id_compare + 1
if end_id_input >= start_id_compare and end_id_input <= end_id_compare:
end_id_input = start_id_compare - 1
if start_id_input > end_id_input:
start_id_input = 0
end_id_input = -1
id_ranges[position] = [start_id_input, end_id_input]