Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Ich habe das als Graphenproblem aufgefasst. Also Ladebuchse, jeder Adapter, und das zu ladenende Gerät sind Knoten. Alle Knoten deren Wert nicht mehr als 3 voneinander entfernt sind haben eine Kante/Verbindung vom kleineren Wert zum grösseren. Hier mal das kleine Beispiel aus der Aufgabe:

Code: Alles auswählen

     +----+
     | 0  |
     +----+
       |
       v
     +----+
     | 1  |
     +----+
       |
       v
     +----+ 
  +- | 4  | -+
  |  +----+  | 
  |    |     |
  |    v     |
  |  +----+  |
  |  | 5  | -+----+
  |  +----+  |    | 
  |    |     |    |
  |    v     |    |
  |  +----+  |    |
  |  | 6  | <+    |
  |  +----+       | 
  |    |          |
  |    v          |
  |  +----+       |
  +> | 7  | <-----+
     +----+    
       |
       v
     +----+
     | 10 | -+
     +----+  | 
       |     |
       v     |
     +----+  |
     | 11 |  |
     +----+  | 
       |     | 
       v     |
     +----+  |
     | 12 | <+
     +----+
       |
       v
     +----+
     | 15 |
     +----+
       |
       v
     +----+
     | 16 |
     +----+
       | 
       v
     +----+
     | 19 |
     +----+
Frage ist jetzt wie viele Wege es von der Ladebuchse zum Gerät bzw. letzten Adapter gibt. Das könnte man rekursiv von der Ladebuchse aus machen, aber wenn man sich mal anschaut wie das abläuft, sieht man, dass man das recht effizient vom Gerät aus lösen kann in dem man linear von hinten durch die Adapter geht und die Anzahl der Wege die vom aktuellen Adapter zum Ziel führen einfach auf die Anzahl der Wege aller direkten Vorgänger addiert.

Hier die Lösung in BASIC für den C64:

Code: Alles auswählen

   10 TI$="000000":OM=1000000:DIM A(100),H(3),J(100,2):N=0
   20 PRINT"READING ADAPTER JOLTS...":OPEN 2,8,2,"INPUT10,S,R"
   30 IF ST<>0 THEN CLOSE 2:PRINT"READING TIME: "TI$:GOTO 100
   40 INPUT#2,A(N):PRINT N:PRINT"{UP}";:N=N+1:GOTO 30
  100 PRINT"SORTING ADAPTERS..."
  110 F=0:FOR I=1 TO N:IF A(I-1)<A(I) THEN F=-1:T=A(I):A(I)=A(I-1):A(I-1)=T
  120 NEXT:IF F THEN 110
  130 REM CALCULATE DIFFERENCE HISTOGRAM
  140 FOR I=1 TO N:D=A(I-1)-A(I):H(D)=H(D)+1:NEXT
  150 PRINT"PART 1:";H(1)*(H(3)+1):PRINT"TIME SO FAR: "TI$
  200 REM CALCULATE TOTAL JOLTAGE
  210 J(0,0)=1:FOR I=0 TO N:FOR J=I+1 TO I+3:IF J>N THEN 250
  220 IF A(I)-A(J)>3 THEN 250
  230 L=J(I,0)+J(J,0):H=J(I,1)+J(J,1):IF L>OM THEN L=L-OM:H=H+1
  240 J(J,0)=L:J(J,1)=H
  250 NEXT:NEXT:PRINT"PART 2:"J(N,1)"MIO. +"J(N,0):PRINT"TOTAL TIME: "TI$
Es hat mal wieder die Genauigkeit der Gleitkommazahlen vom C64 nicht gereicht, weshalb ich die Summe auf zwei Werte aufgeteilt habe: einer zählt die ganzen Millionen und der andere den Rest. Darum wird das Ergebnis 14.173.478.093.824 als ``14173478 MIO. + 93824`` ausgegeben. 🤓
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

narpfel hat geschrieben: Donnerstag 10. Dezember 2020, 19:22 @ThomasL: Dein Teil 2 funktioniert nicht mehr, wenn mehr als 4 Einsen hintereinander kommen.
Hi, das ist mir durchaus bewusst, mein Code ist auf die Tagesaufgabe zugeschnitten, eine Generalität ist aber auch nicht erforderlich.
Aber Danke für den Hinweis auf die Tribonacci Zahlen, da werde ich mich mal einlesen.
Wieder etwas gelernt durch Advent of Code. :-)
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Guten Morgen und viel Spaß an Tag 11!

Bild


Gäbe es einen Preis für die längste Lösung, heute hätte ich ihn gewonnen. Ich kann mich auch in Brute-Force-König umbenennen...
Benutzeravatar
Whitie
User
Beiträge: 216
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Ich konnte durch umstellen einer Schleife die Laufzeit von >10min auf <10s drücken. Ist aber immer noch eine Brute-Force-Lösung :-(

Gruß
Whitie
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Das Ergebnis ist bei mir in unter 2 Sekunden da. Dann gehört die Krone vielleicht doch dir :)

Vor dem Refactoring hatte ich 110 Zeilen Code. Damit würden manche hier im Forum eine komplette Klimasimulation hinbekommen. :)
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Bolitho hat geschrieben: Freitag 11. Dezember 2020, 13:24 Vor dem Refactoring hatte ich 110 Zeilen Code. Damit würden manche hier im Forum eine komplette Klimasimulation hinbekommen. :)
Bestimmt. :)

-> https://medium.com/informatics-lab/simp ... d0d0b4af03
Benutzeravatar
Whitie
User
Beiträge: 216
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Bolitho hat geschrieben: Freitag 11. Dezember 2020, 13:24 Das Ergebnis ist bei mir in unter 2 Sekunden da. Dann gehört die Krone vielleicht doch dir :)
Kommt wohl auch etwas auf den Rechner an. Hier zu hause dauert es 1,4s und es sind etwa 60 Zeilen Code.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Ich habe das noch nicht auf dem C64 umgesetzt — da wird das wahrscheinlich auch eher sehr lange brauchen…
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Heute mit Verspätung: Mahlzeit! Viel Spaß bei Türchen 12!

Bild

Mein Schiff hält Kurs und ich bin ganz zufrieden mit der Lösung. Auch wenn das bestimmt effizienter geht. Leider habe ich im Moment keine Zeit den Code hier zu posten oder andere Lösungen zu studieren. Das wird wohl auch im Dezember nicht mehr besser. Im aktuellen Projekt gehen wir noch vor Heiligabend live und müssen ab Start Support leisten zur Sicherstellung des Jahresabschlusses. Aber so ist es nun mal und besser als machen, die im Moment gerne arbeiten würden aber nicht können und oder dürfen.
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Die heutige Aufgabe gefällt mir besonders gut, weil man mal ein Feature von Python zum Einsatz bringen kann, das glaube ich nicht so viele Sprachen haben: komplexe Zahlen als eingebauter Datentyp. :) (In anderen Sprachen braucht man dafür oft Bibliotheken)
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Wünsche einen schönen dritten Advent und viel Spaß mit Rätsel 13!

Bild

Heute gebührt mir eigentlich nur ein Stern. An der Lösung zu Rätsel 2 rechnet mein Laptop immer noch. Schon seit gut einer halben Stunde. Ich verstehe die Mathematik hinter anderen Lösungen auch nicht wirklich. Schade, dass ich auch heute keine Zeit für eine tiefere Auseinandersetzung habe. Familie ruft.
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

@Bolitho: Wie lange hat dein Rechner insgesamt an der Lösung für Teil 2 gerechnet? Ich gehe eigentlich davon aus, dass diese Aufgabe ohne die mathematischen Hintergründe nicht in vertretbarer Zeit lösbar sein sollte.
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Ich habe nach 60 Minuten abgebrochen. Hätte gerne gewusst, wie weit er gerechnet hat bis dahin. :)

Hab das nicht ausgerechnet, aber die Testaufgabe mit der Lösung bei 1Mrd. war sofort da. Aber mehrere hundert Billionen sind eben doch was anderes.
Caskuda
User
Beiträge: 26
Registriert: Sonntag 15. März 2020, 22:09

Den Advent of Code kannte ich noch gar nicht. Lieben Dank fürs teilen.


@ Bolitho:
Falls du einen Spoiler für den Lösungsansatz zu Tag 13 Teil 2 magst, kann ich dir gerne ein Schlagwort nennen.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Ich habe zwar 2 Stunden gebraucht aber ich bin ohne Wissen über einen Chinese Remainder Theorem auf eine Lösung gekommen und wenn ich sehe, wie viele Teilnehmer keine Lösung für Teil 2 haben, auch etwas Stolz auf mich.
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Guten Morgen und viel Spaß bei Türchen 14!

Bild

Mir fiel es heute wieder leichter. Ging ganz flott und der Code sieht, in meinen Maßstäben, gut aus.

@ThomasL: Das kannst du auch! Glückwunsch!

@Caskuda: Danke für das Angebot. Wenn du das CRT Stichwort meinst, suche ich da noch nach einer Erklärung für Nicht-Mathematiker (Auf Youtube gibt es ja den einen oder anderen Kanal, auf dem die Aufgaben gelöst werden. Vielleicht ist da was für mich bei...). Den Wikipedia Artikel verstehe ich nicht. Leider ist Zeit der limitierende Faktor im Moment. Vielleicht habe ich ab nächste Woche Donnerstag etwas mehr Zeit und kann versuchen die eine oder andere Lücke zu schließen.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Bolitho: Ich habe es ”ohne” CRT gelöst. Die Anführungsstriche weil es letztlich doch auf dem CRT basiert, aber ohne dass ich das nachgelesen/nachvollzogen oder vorher da drüber nachgedacht hätte.

Meine Lösung basiert darauf erst einmal zwei Busse zu ”synchronisieren”. Dazu gehe ich in Schritten des ersten Busses von 0 an durch die Zeit und prüfe bei jedem Schritt ob der zweite Bus im richtigen Abstand abfährt. Wenn ich den Zeitpunkt habe, kann ich überlegen nach wie vielen Schritten diese Situation wieder vorkommen kann. Das passiert ja periodisch und zwar immer beim kleinsten gemeinsamen Vielfachen (kgV) der beiden Busnummern. Das kgV von zwei Primzahlen ist das Produkt von beiden, und alle Busnummern sind prim. Also kann man nach jedem Bus die Schrittweite in der man sucht mit der letzten Busnummer multiplizieren. Damit werden die Schrittweiten ziemlich schnell recht gross und man kommt schnell auf das Ergebnis.

Es ist letztlich diese simple Schleife die meine Eingabedaten in unter 1.000 Schritten verarbeitet:

Code: Alles auswählen

def solve_part_2(busses):
    time = 0
    step_size = 1
    for bus_id, offset in busses:
        while (time + offset) % bus_id != 0:
            time += step_size
        step_size *= bus_id

    return time
Supersimpel und schnell, sogar auf dem C64 problemlos machbar wenn die Zahlen nicht so verdammt gross werden würden. Aber ich habe eine ganze Weile daran gesessen das bisschen Code zu schreiben. 😎
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Guten Morgen, Türchen 15 wartet!

Bild

Hat heute wieder Spaß gemacht und ich habe mir beide Sterne selbst verdient. :)

@__blackjack__: Danke, für Deine Erklärung und Lösung. Damit habe ich den Ansatz zur effizienten Lösung verstanden. Ich hatte zwar in meinem Versuch das kgV schnell bei der Hand, konnte es aber nicht zur Lösung einsetzen. Ich bin "immerhin" so weit gekommen, dass ich den Takt des größten Busses als Schrittlänge genommen habe. Aber das hat natürlich bei weitem nicht gereicht.
Caskuda
User
Beiträge: 26
Registriert: Sonntag 15. März 2020, 22:09

Guten Abend allerseits.

Das heutige Türchen ist eine schöne Erinnerung an John Conway.
Leider, wenn auch in hohem Alter, in diesem Jahr an SARS-COV2 verstorben.

https://www.youtube.com/watch?v=1eAmxgINXrE
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Bei der heutigen Aufgabe kann man (je nach Ansatz), eine vielleicht nicht ganz so bekannte, undokumentierte Klasse aus Pythons RegEx-Modul anwenden: re.Scanner (s. a. https://lucumr.pocoo.org/2015/11/18/pyt ... n-re-gems/).
Antworten