Advent of Code

[gerryontour]

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()

[__blackjack__]

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?

[gerryontour]

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.

[ThomasL]

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'))

[narpfel]

@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.

[__blackjack__]

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.

[ThomasL]

@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.

[Bolitho]

Guten Morgen und viel Spaß an Tag 11!




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...

[Whitie]

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]

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.

[snafu]

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

[Whitie]

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.

[__blackjack__]

Ich habe das noch nicht auf dem C64 umgesetzt — da wird das wahrscheinlich auch eher sehr lange brauchen…

[Bolitho]

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



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]

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]

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



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]

@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]

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]

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.

[ThomasL]

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.