Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
gerryontour
User
Beiträge: 23
Registriert: Dienstag 30. Juni 2020, 15:50

Für das Testset funktioniert der Code.

Code: Alles auswählen

def main():
    print("------------\n\n")
    with open("pe.txt", "r") as file:
        numbers = [int(line) for line in file]

    for i, number in enumerate(numbers[5:]):
        previous_numbers = numbers[i : i + 5]
        sums = []
        for number_a in previous_numbers:
            for number_b in previous_numbers:
              if number_a != number_b:
                sums.append(number_a + number_b)
        if number not in sums:
            print(number)
            break


if __name__ == "__main__":
    main()
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Was ist denn *das* Testset? Da werden ja insgesamt 9 Testfälle beschrieben. Laufen die alle? Und wie sieht es jetzt mit den tatsächlichen Daten aus?
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
gerryontour
User
Beiträge: 23
Registriert: Dienstag 30. Juni 2020, 15:50

__blackjack__ hat geschrieben: Donnerstag 10. Dezember 2020, 15:09 Was ist denn *das* Testset? Da werden ja insgesamt 9 Testfälle beschrieben. Laufen die alle? Und wie sieht es jetzt mit den tatsächlichen Daten aus?
Sorry, dass ich das Forum hier zu zuspamme haha!

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

Code: Alles auswählen

def main():
    print("------------\n\n")
    with open("pe.txt", "r") as file:
        numbers = [int(line) for line in file]

    for i, number in enumerate(numbers[5:]):
        previous_numbers = numbers[i : i + 5]
        sums = []
        for number_a in previous_numbers:
            for number_b in previous_numbers:
              if number_a != number_b:
                sums.append(number_a + number_b)
        if number not in sums:
            print(number)
            break


if __name__ == "__main__":
    main()
hier wird die 127 erkannt und geprintet.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Hier meine Lösung für Tag 10. Hat mich auch etwas Zeit gekostet, den Zusammenhang zwischen der Anzahl der Einserfolgen und der Anzahl der Kombinationen zu erkennen.

Code: Alles auswählen

with open('input.txt') as file:
    data = [0] + sorted([int(line) for line in file])
data.append(data[-1] + 3)

difs = ''.join(str(x - data[i]) for i, x in enumerate(data[1:]))

# part 1
print(difs.count('1') * difs.count('3'))

# part 2
difs = difs.split('3')
print(2**difs.count('11') * 4**difs.count('111') * 7**difs.count('1111'))
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
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

@ThomasL: Dein Teil 2 funktioniert nicht mehr, wenn mehr als 4 Einsen hintereinander kommen.

Meine Lösung funktioniert dann auch nicht mehr:

Code: Alles auswählen

» cat input
1
2
3
4
5
6
» ./solution.js
6
16
Ich habe es mit dem Binomialkoffizienten probiert (2 == comb(2, 2) + 1; 4 == comb(3, 2) + 1; 7 == comb(4, 2) + 1), aber das passt für Längen größer 4 auch nicht mehr.

Code: Alles auswählen

λ» diff = zipWith subtract <*> tail
diff :: Num c => [c] -> [c]

λ» possibleCombinations n = length . filter ((<= 3) . maximum . diff) . map (\xs -> 0 : xs <> [n + 3]) . subsequences $ [1..n]
possibleCombinations :: (Ord a, Num a, Enum a) => a -> Int

λ» map possibleCombinations [0..20]
[1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,35890,66012,121415]
Wenn man die Sequenz bei der OEIS eingibt, kommt man zu A000073, den Tribonacci-Zahlen. Da ist jetzt die Frage, wo da der Zusammenhang herkommt.
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
Antworten