Okay, zunächst einmal ist Serge an allem schuld. Im Zug auf dem Rückweg von Schiphol stellte er mir https://www.adventofcode.com vor und gemeinsam lösten wir das erste Rätsel, das auch meine ersten Schritte in Python markierte.
Ich war sofort Feuer und Flamme.
Jedes Jahr versuche ich, mindestens eine neue Sprache oder Fähigkeit zu erlernen, aber in den letzten Jahren fühlte es sich wie Betrug an. Zuerst lernte ich AppleScript, dann Blender und letzten Sommer entschied ich mich für kOS Scripting, interessant, aber nicht sehr tiefgründig und vor allem nicht sehr praktisch. Python erwies sich als etwas anderes. Es erinnerte mich an C, Pascal, Bash und alles andere. Es schien mir sehr natürlich zu sein und gleichzeitig überraschte es mich immer wieder mit einfachen Konstrukten, mit denen man Dinge elegant und effizient erledigen kann.
Aber das war nicht das Einzige, wonach ich süchtig war.
Der Advent des Codes ist eine Reihe von Rätseln, die 25 Tage lang vor Weihnachten täglich veröffentlicht werden. Jedes Rätsel besteht aus zwei Teilen und ähnelt einem mathematischen Problem, das in einer Erzählung beschrieben wird. Dieses Jahr hat sich der Weihnachtsmann am Rande des Sonnensystems verirrt und wir müssen ihn retten. Da ich ein kleiner Weltraumfan bin, klang diese Geschichte für mich erstaunlich, vor allem weil sie auf einer realen Alternative wie der Ziolkowsky-Raketengleichung beruhte.
"Der Weihnachtsmann ist am Rande des Sonnensystems gestrandet, während er Geschenke an andere Planeten ausliefert! Um seine Position im All genau zu berechnen, seinen Warp-Antrieb sicher auszurichten und rechtzeitig zur Erde zurückzukehren, um Weihnachten zu retten, braucht er Sie, um ihm Messungen von fünfzig Sternen zu bringen."
Was ist mit den grünen Männern?
Nun ja, ich gebe zu, es ist eine obskure Referenz und vor allem Clickbait, aber ich bin ein großer Fan von https://kerbalspaceprogram.com, seit es in der Alpha-Version war. Ich habe sogar einige Mods dafür erstellt. Ein Teil des Spiels besteht darin, die kleinen grünen Männchen zu anderen Planeten in ihrem Sonnensystem zu bringen, was nur effizient möglich ist, wenn die Ausrichtung der Planeten korrekt ist. Womit wir beim Rätsel von Tag 12 wären.
Moment mal, Planetenausrichtung?
Ja, anstatt direkt zu einem Planeten zu fliegen, nimmt ein Raumschiff etwas Geschwindigkeit auf (wenn es nach außen fliegt) und holt sozusagen einen sich langsamer bewegenden Planeten ein. Am höchsten Punkt seiner Umlaufbahn trifft es dann auf das Ziel und voilà. Geschwindigkeit und Zeitpunkt des Abflugs sind also wichtig, aber auch der Zeitpunkt des Abflugs. Hier ist ein Bild des Insight-Raumschiffs, das den Mars einholt, das ich aus Wikipedia geklaut habe.
Kerbal Space Program verwendet ein vereinfachtes Modell, bei dem sich die Planeten nicht gegenseitig beeinflussen. Im Grunde können Sie also berechnen, wie oft eine bestimmte Ausrichtung auftritt, indem Sie den gemeinsamen Nenner zwischen dem Produkt ihrer Zykluszeit betrachten. Dies geschieht natürlich in der 3-Achse, aber da die meisten Planeten (mit Ausnahme von Moho) fast in der gleichen Ebene liegen, neigen die Spieler dazu, dies zu ignorieren. Teil 2 von Tag 12 war also eine angenehme Überraschung.
Das N-Body Problem, das keines war
An Tag 12 wird das N-Körper-Problem der Monde des Jupiters vorgestellt, und zwar nicht aller Monde, sondern nur der galileischen Monde. Jeder Mond beeinflusst den anderen. Anstatt sich kontinuierlich zu bewegen, führen die Monde einen himmlischen Tanz (oder einen Judokampf) auf, bei dem sie sich gegenseitig anschieben und ziehen und so ihre Geschwindigkeit und Position beeinflussen. Dies wird als N-Körper-Problem bezeichnet. In den Notizen war jedoch ein kleiner Hinweis versteckt, der das Leben sehr viel einfacher machte: Die Anfangsgeschwindigkeit war 0. Das bedeutete, dass die Monde im Laufe der Zeit mit ihrer Anfangsgeschwindigkeit (die 0 war) wieder in ihre Ausgangsposition zurückkehren würden.
Unsere Aufgabe war es, zu berechnen, wie lange es dauern würde, bis das Universum in seinen ursprünglichen Zustand zurückkehrt. Mein erster Versuch war, einen Simulator zu schreiben, aber das Universum ist ein großes Ding und es Schritt für Schritt zu simulieren würde sehr lange dauern. Da erinnerte ich mich an die kleinen grünen Männchen in Kerbal Space Program und die Antwort kam.
Wir können zunächst prüfen, ob alle Planeten in der x-Ebene, dann in der y-Ebene und dann in der z-Ebene ausgerichtet sind. Dies ist ein 3-faches O(n)-Problem und nicht ein O(n^3)-Problem, also haben wir:
align_x = steps to align whole system in x plane
align_y = steps to align whole system in y plane
align_z = steps to align whole system in z plane
Damit erhalten wir die Kombinationen align_x * align_y * align_z, aber es könnte auch frühere Ausrichtungen geben. Betrachten wir zwei Ebenen wie in Kerbal Space Program:
align_xy = align_x * align_y / gcd(align_x, align_y)
Das sah schon besser aus, aber wie schnell lässt sich das mit der Z-Ebene in Einklang bringen:
align_xyz = align_xy * align_z / gcd(align_xy, align_z)
Wegen der Anfangsgeschwindigkeit von Null setzt sich das System im Grunde alle n Zyklen zurück, was ziemlich cool ist! Ich habe es geliebt, dieses Rätsel zu lösen, das einen eleganten Code hervorgebracht hat, ganz im Gegensatz zum int-Computer (basierend auf dem agc), der zu einem dampfenden Haufen Schrott geworden ist.
Was nun?
Ich werde weiter rätseln. Bisher habe ich es geschafft, alle Rätsel zu lösen, aber Tag 16 Teil 2 entzieht sich mir vorerst. Es gibt da ein Muster, das ich nicht erkennen kann, aber das wird schon noch kommen. Es ist mir auch gelungen, die Hilfe anderer kleiner Männer in Anspruch zu nehmen.
Mein Sohn hat es geschafft, das Labyrinth-Rätsel mehr als eine Stunde zu lösen, bevor ich es geschafft habe, einen Algorithmus für den Labyrinth-Löser in Python zu implementieren ;-)
Advent of Code 2019 Series
- Advent of Code 2019 Has Started - Join In!
- Advent of Code 2019 - Day 2
- Advent of Code: How Excel Made My Day and Saved My Son's Day Too
- Advent of Code - Day 4: Visualize
- Advent of Code - Day 5: Saintaerkla2s
- Advent of Code - Day 6: How I Got Hooked on AoC
- Advent of Code - Day 7: Share Your Workflow
- Advent of Code - Day 8: How Simple Things Can Be Very Hard for Some People
- Advent of Code - Day 9: How I Started Enjoying Solving Programming Puzzles
- Advent of Code - Day 10: Space Cowboys Shooting Pixels in the Sky
- Advent of Code - Day 11: To Be or Not to Be
- Advent of Code - Day 12: Shooting for the Moon
- Advent of Code - Day 14: Chain Reaction
- Advent of Code - Day 16: Curses
- Advent of Code - Day 17: Vacuuming a Scaffold with the Intcode Program
- How Little Green Men Helped Me Solve a Puzzle
- Advent of Code - Day 20: A Little Bit of Revision
- Advent of Code - Day 21: It's a Marathon, Not a Sprint
- Advent of Code - Day 22: Shuffling Cards Until Eternity
- Advent of Code - Day 23: The Network is Reliable
- Advent of Code - Day 24 & 25: Think Out of the Box
Verfasst von
Chris Lukassen
Contact