Advent of Code 13.2 von Raphael
Raphael hat einen kleinen Beitrag zur zweiten Teilaufgabe vom 13. Advent of Code geschrieben. Nathan hat da nämlich quasi aufgegeben.
Raphael, der uns vor Ewigkeiten mal im Podcast beehrt hat, hat sich bei der 13. Aufgabe vom Advent of Code klüger angestellt als Nathan. Er löst den AoC in Swift und hat uns angeboten, da mal einen kleinen Gastbeitrag zu schreiben. Vielen Dank für den Gastbeitrag, lieber Raphael und viel Spaß beim Lesen!
Das Rätsel
Den zweiten Teil des 13. Türchens des Advent of Code 2020 fand ich besonders schwierig zu lösen. Es gibt verschiedene Busse. Jeder Bus fährt alle x Minuten. Zum Beispiel gibt es die Buslinien 7, 13, 59, 31 und 19. Buslinie 7 fährt auf Minute 7, 14, 21, 28, …; Analog für Buslinie 13 ist es Minute 13, 26, …
Gefragt ist, zu welchem Zeitpunkt folgende Konfiguration auftritt:
- Bus 7 fährt zum Zeitpunkt t
- Bus 13 fährt bei t+1
- Bus 59 fährt bei t+4
- Bus 31 fährt bei t+6
- Bus 19 fährt bei t+7
Was ist t? (Aus t ergibt sich natürlich trivial t+1 usw.)
Eine naive Lösung
Prüfe jeden Zeitpunkt t auf t % 7 == 0 && (t+1) % 13 == 0 && ... (Der Operator % bedeutet hier den Rest einer Division, besser bekannt als Modulo). Diese Lösung funktioniert, wenn t nicht zu groß ist. Die Beschreibung im AoC verrät allerdings, dass die finale Lösung über 100.000.000.000.000 liegt. Selbst bei 1.000.000 Berechnungen pro Sekunde wäre eine Lösung frühestens nach 3 Jahren gefunden.
Ein schrittweiser Ansatz
Es gibt zu viele Kombinationen, die überprüft werden müssten, wenn ich alle Busse auf einmal betrachte. Deshalb muss ich die Lösung schrittweise finden.
Sagen wir, es gibt nur zwei Busse
Eine Lösung für ein Buspaar zu finden geht schnell. Ich kann in diesem Fall alle Paarungen mit Bus 7 untersuchen, da sich die Lösung der anderen Busse aus dem 7er ergibt (wie gesagt, t+1,… ist trivial).
Die Paarungen sind also (7, 13), (7, 59), (7, 31), (7, 19).
Durchprobieren für das erste Paar, und natürlich analog für alle anderen Paare, geht mit folgendem Code:
let a = 7
let b = 13
let diff = 1
var cnt1 = 1
var cnt2 = 1
while true {
if a * cnt1 == b * cnt2 - diff {
print(cnt1, cnt2)
break
}
if a * cnt1 < b * cnt2 - diff {
cnt1 += 1
}
else {
cnt2 += 1
}
}
Kurz gesagt, liest sich der Algorithmus wie folgt: "Kommt der 7er Bus vor dem 13er, dann lasse den nächsten 7er Bus kommen. Kommt der 13er Bus vor dem 7er, dann lasse den nächsten 13er Bus kommen. So lange, bis der 13er genau eine Minute nach dem 7er fährt."
Die Lösung ist t=(7*11), t+1=(13*6).
Dies ist der früheste Zeitpunkt für eine Lösung. Alle weiteren Lösungen ergeben sich mit t = 7 * (11 + n * 13) für die Paarung mit dem 13er Bus. Das ist wichtig zu verstehen! Ich habe einen frühesten Zeitpunkt und ich weiß, wie sich alle folgenden Zeitpunkte zusammensetzen.
Der dritte Bus
Das nächste Buspaar ist (7, 59) mit der Lösung t = 7 * 50. Das weiß ich aus dem vorigen Abschnitt.
Nun muss ich eine Kombination finden, bei der sowohl der 13er Bus, als auch der 59er Bus gleichzeitig abfahren. Wie schon erwähnt, ist die Lösung für den 13er Bus t = 7 * (11 + n * 13), analog für den 59er t = 7 * (50 + m * 59). Um beide Regeln zu erfüllen, muss als 7 * (11 + n * 13) == 7 * (50 + m * 59) sein. Die 7 kann ich rauskürzen (11 + n * 13) == (50 + m * 59). Eine Lösung finde ich erneut durch ausprobieren.
let a = 11
let afac = 13
let b = 50
let bfac = 59
var cnt1 = 1
var cnt2 = 1
while true {
if a + afac * cnt1 == b + bfac * cnt2 {
print(cnt1 * afac + a)
break
}
if a + afac * cnt1 < b + bfac * cnt2 {
cnt1 += 1
}
else {
cnt2 += 1
}
}
Der nächste Zeitpunkt, bei dem sowohl der 13er, als auch der 59er zum richtigen Zeitpunkt fahren, ist bei t = 7 * 817. Damit kenne ich den frühesten Zeitpunkt. Jeder folgende Zeitpunkt, wie bereits erklärt, folgt bei t = 7 * (817 + n * 13 * 59). Somit kann ich für jedes weitere Buspaar eine Lösung finden, bis zur endgültigen Lösung. Wären da nicht diese verdammt großen Zahlen.
Die verdammt großen Zahlen
Es ist leicht zu sehen, dass die Zahlen für a und afac im obigen Algorithmus schnell sehr groß werden, während sie für b und bfac recht klein bleiben. cnt2 hat also allerhand zu tun, wieder aufzuholen.
Es ist möglich, cnt2 etwas auf die Sprünge zu helfen
let diff = (a + afac * cnt1) - (b + bfac * cnt2)
if diff % bfac == 0 {
cnt2 += diff / bfac
continue
}
cnt2 += (diff - (diff % bfac)) / bfac
Der Algorithmus liest sich wie folgt: "Was ist die Differenz der beiden Teilergebnisse? Sofern sich die Differenz glatt durch bfac teilen lässt, mache cnt2 direkt so groß, dass die Differenz 0 wird. Falls nicht, mache cnt2 so groß, dass die Differenz immerhin fast 0 ergibt."
Dies ist ein Beitrag von Raphael Sprenger. Er (also der Beitrag, nicht Raphael) ist als CC BY-NC 4.0 lizenziert.