Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
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: 12984
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: 1631
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/).
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Für den ersten Aufgabenteil habe ich mir eine supersimple `tokenize()`-Funktion ohne reguläre Ausdrücke geschrieben, denn die Token sind ja alle nur ein Zeichen lang.

Für den zweiten Aufgabenteil habe ich einfach Pyparsing verwendet um einen Parser zu basteln. 😎
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

__blackjack__ hat geschrieben: Samstag 19. Dezember 2020, 00:33 denn die Token sind ja alle nur ein Zeichen lang.
Bei den Zahlen geht das aber glaube ich nicht aus dem Aufgabentext hervor (und beim Input könnte es ja "Zufall" sein). Daher bin ich davon ausgegangen, dass es alle natürliche Zahlen sein können. Aber es könnte nach der Logik dann natürlich auch jeder andere Zahlenraum sein.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@nezzcarth: Meine Lösung für Teil 1 würde in dem Fall eine Ausnahme auslösen das ein Operator erwartet wurde, aber eine Zahl gefunden wurde:

Code: Alles auswählen

Traceback (most recent call last):
  File "./day18.py", line 129, in <module>
    main()
  File "./day18.py", line 106, in main
    print(evaluate_text("42 + 23"))
  File "./day18.py", line 89, in evaluate_text
    return evaluate_expression(peekable(tokenize(text)))
  File "./day18.py", line 78, in evaluate_expression
    operator_symbol = evaluate_operator(tokens)
  File "./day18.py", line 71, in evaluate_operator
    raise ValueError(f"expected operator, got {token!r}")
ValueError: expected operator, got Token(type=<TokenType.NUMBER: 1>, value=2)
Für den Fall könnte man den Token-Stream von der `tokenize()`-Funktion einfach nachbearbeiten in dem man Läufe von `Token` mit `TokenType.NUMBER` entsprechend zu einem solchen Token zusammenfasst.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Tag 1-3 habe ich lösen können, auch wenn sich gestandene Coder bei dem entstandenen Code wohl die Hände über dem Kopf zusammenschlagen würden. Bei Tag 4 bräuchte ich als absoluter Anfänger Hilfe. Kann mir jemand Stichworte nennen die ich googlen kann um auf die Lösung zu kommen?
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

@steveO_O: Wo ist denn genau dein Problem?

Allgemein: Teile das Problem in kleinere Teilprobleme auf, die du einfacher überblicken kannst. Also zum Beispiel den Input in einzelne Pässe aufteilen, einen Pass einlesen, etc. Dafür könnten eventuell die Methoden von `str` hilfreich sein. Und die Grunddatentypen für Collections.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@steveO_O: Da ist nichts mit Googlen, da braucht man eigentlich nur die Grunddatentypen und deren Operationen, also Zeichenketten, Listen, Wörterbücher, Mengen, und spätestens im zweiten Teil auch (ganze) Zahlen.

Ansonsten was narpfel schrob: Wenn Dir ein Problem zu gross erscheint, zerlege es in kleinere Probleme und löse die. Beispielsweise eine Funktion die eine Zeichenkette mit den Zeilen eines einzelnen Passes in eine Datenstruktur überführt mit der man gut weiterarbeiten kann. Wenn man die hat, dann lässt sich das überführen des gesamten Inhalts der Eingabe in eine Liste mit Passdatenstrukturen beispielsweise in einer einzigen Zeile lösen. Oder zwei Zeilen wenn man da eine Schleife für schreibt statt einer „list comprehension“ oder `list()` und `map()` verwendet.

Dann sollst Du gültige Pässe zählen. Ein nötiger Schritt dafür wäre ein Test ob ein gegebener Pass gültig ist oder nicht. Das drängt sich als Teilproblem für eine Testfunktion `is_valid_passport()` geradezu auf, die einen Pass als Datenstruktur bekommt und True oder False liefert, je nach dem ob die Daten einen gültigen Pass beschreiben oder nicht.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Habs mittlerweile zu Tag 7 geschafft. Der folgende Code ist noch nicht die fertige Lösung! Die möchte ich auch nicht erfragen. Bitte auch keine Profitipps, die ich eh nicht verstehen kann.
Worum ich bitten würde ist die Antwort auf die Frage, wie die Liste "bags" (Zeile 28) am Ende leer sein kann. Verzweifle da gerade.

Vielen Dank! :-)

Code: Alles auswählen

SEARCH_WORD = "shiny gold"
DELETE_FROM_VALUES = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "bags", "bag", "."]
all_containers = set()


def main():
    all_rules = reading_rules_from_input()
    direct_containers = is_in_values(all_rules)
    bags = direct_containers
    queue = direct_containers
    containers_not_to_check_anymore = []
    while queue:
        for item in queue:
            if item not in containers_not_to_check_anymore:
                bags.append(item)
                queue.remove(item)
                containers_not_to_check_anymore.append(item)
                bags_output = bag_check(item, all_rules)
                if bags_output:
                    for item2 in bags_output:
                        if item2 in containers_not_to_check_anymore:
                            bags_output.remove(item2)
                    queue.extend(bags_output)
                else:
                    print("\n-----------------------------leer")
            else:
                queue.remove(item)
    print("bags5", bags)  #<------------------------------- die erwähnte Liste "bags


def bag_check(item, dictionary_one): 
    bags_output = []
    for key in dictionary_one:
        if item in dictionary_one[key]:
            bags_output.append(key)
    print("bags_ouput", bags_output)
    return bags_output


def reading_rules_from_input():
    all_rules = dict()
    with open("input_day7.txt", encoding="utf-8") as data:
        for row in data:
            begin = row.find(" bags contain")
            key = row[:begin]
            values = row[begin+len(" bags contain"):]
            for char_to_delete in DELETE_FROM_VALUES:
                values = values.replace(char_to_delete, "")
            values = values.strip()
            values = values.split(" ,  ")
            if values == ["no other"]:
                values = []
            all_rules[key] = values
    return all_rules


def is_in_values(dictionary_one):
    bags = []
    for key in dictionary_one:
        if SEARCH_WORD in dictionary_one[key]:
            bags.append(key)
    return bags


main()
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Dir ist klar das `direct_containers`, `bags`, und `queue` drei Namen für die *selbe* Liste sind und nicht drei verschiedene Listen?
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Hi Blackjack, danke für die Rückmeldung!
Gedanke war, das direct_containers - einmal erstellt - nicht mehr geändert werden sollte. Kann man sicherlich auch anders lösen, aber um die Aufgabe zu lösen war mir das geistig so einfacher. Habe mich recht schwer getan, das alles geistig zu durchdringen^^.
bags und queue werden ja im Laufe des Codes verändert, sind als nicht mehr die gleichen Listen, oder wo ist da mein Denkfehler?
bags soll die Liste sein, die am Ende sämtliche Taschen enthält, die bei der Suche rauskommen. D.h. am Schluss wird bags in ein Tupel umgewandelt und dann müsste die Länge des Tupels die Lösung sein.
Queue hat einfach die Zwischenfunktion, die sich hoffentlich aus dem Code ergibt.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

steveO_O hat geschrieben: Dienstag 26. Januar 2021, 07:08 bags und queue werden ja im Laufe des Codes verändert, sind als nicht mehr die gleichen Listen, oder wo ist da mein Denkfehler?
Listen sind in Python veränderlich (mutable). Wenn du eine Liste an einen neuen Namen bindest, bleibt das zugrunde liegende Objekt identisch.
Solche Sachen kann man gut im interaktiven Python-Interpreter ausprobieren:

Code: Alles auswählen

In [1]: p = [1,2,3,4]

In [2]: q = p

In [3]: id(p)
Out[3]: 140129565942720

In [4]: id(q)
Out[4]: 140129565942720

In [5]: p.pop()
Out[5]: 4

In [6]: q
Out[6]: [1, 2, 3]

In [7]: q.pop()
Out[7]: 3

In [8]: p
Out[8]: [1, 2]

In [9]: id(p)
Out[9]: 140129565942720

In [10]: id(q)
Out[10]: 140129565942720
Wenn du eine echte Kopie erzeugen möchtest, geht das zum Beispiel mit der der Notation 'p = q[:]'. Oft gibt es ab bessere Lösungen (ich habe mir deinen Code nicht im Detail angesehen).
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Ah, da liegt der Hund begraben! Jetzt verstehe ich es. Grober Verständnis-Schnitzer auf meiner Seite :-). Das Kapitel "tiefes vs. flaches Kopieren" sollte ich wohl noch einmal lesen. Krass, dass es dennoch solange bei mir zu den gewünschten Ergebnissen geführt hat.

Vielen Dank!
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Ok, jetzt hab ich die korrekt Lösung. Besten Dank, Lektion gelernt. Melde mich beim nächsten Problem :-)
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@steveO_O: Allgemeine Anmerkungen zum gezeigten Quelltext:

Wenn man Schlüssel *und* Wert aus einem Wörterbuch in einer Schleife braucht, dann sollte man gleich über diese Paare iterieren und nicht nur über den Schlüssel:

Code: Alles auswählen

def is_in_values(dictionary_one):
    bags = []
    for key, value in dictionary_one.items():
        if SEARCH_WORD in value:
            bags.append(key)
    return bags
Und bei diesem Code drängt sich eine „list comprehension“ geradezu auf:

Code: Alles auswählen

def is_in_values(dictionary_one):
    return [
        key for key, value in dictionary_one.items() if SEARCH_WORD in value
    ]
Gilt auch für `bag_check()`:

Code: Alles auswählen

def bag_check(item, dictionary_one):
    bags_output = [
        key for key, value in dictionary_one.items() if item in value
    ]
    print("bags_ouput", bags_output)
    return bags_output
Wobei die Funktionen nahezu das gleiche machen, nur mit anderen Werten. Das könnte man also zu einer Funktion zusammenfassen.

In der `main()`-Funktion begehst Du neben dem schon genannten Fehler noch einen weiteren: Man darf Datenstrukturen über die man gerade iteriert im allgemeinen nicht verändern. Und im besonderen ist das entfernen von Elementen aus Listen vor oder genau an dem Punkt, an dem sich der Iterator gerade befindet ein Problem, weil dann Elemente übersprungen werden in der Schleife. Beispiel:

Code: Alles auswählen

In [334]: items = list(range(10))                                               

In [335]: for item in items: 
     ...:     print(item) 
     ...:     if item == 5 or item == 6: 
     ...:         items.remove(item) 
     ...:                                                                       
0
1
2
3
4
5
7
8
9

In [336]: items                                                                 
Out[336]: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Die 6 ist immer noch da, weil die nie geprüft wurde.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

__blackjack__ hat geschrieben: Mittwoch 27. Januar 2021, 09:16 ....

In der `main()`-Funktion begehst Du neben dem schon genannten Fehler noch einen weiteren: Man darf Datenstrukturen über die man gerade iteriert im allgemeinen nicht verändern. Und im besonderen ist das entfernen von Elementen aus Listen vor oder genau an dem Punkt, an dem sich der Iterator gerade befindet ein Problem, weil dann Elemente übersprungen werden in der Schleife. Beispiel:

Code: Alles auswählen

In [334]: items = list(range(10))                                               

In [335]: for item in items: 
     ...:     print(item) 
     ...:     if item == 5 or item == 6: 
     ...:         items.remove(item) 
     ...:                                                                       
0
1
2
3
4
5
7
8
9

In [336]: items                                                                 
Out[336]: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Die 6 ist immer noch da, weil die nie geprüft wurde.
Danke für die Tipps!

Wie machts man das dann in dem Beispiel wenn man die Liste beim Iterieren nicht ändern darf?
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

steveO_O hat geschrieben: Mittwoch 27. Januar 2021, 17:27 Wie machts man das dann in dem Beispiel wenn man die Liste beim Iterieren nicht ändern darf?
Man erzeugt dann eine neue Liste. Das geht besonders elegant mit List-Comprehensions:

Code: Alles auswählen

In [1]: items = list(range(10))

In [2]: items = [item for item in items if item not in {5, 6}]

In [3]: items
Out[3]: [0, 1, 2, 3, 4, 7, 8, 9]
Mit einer Schleife wie im Originalbespiel ist das natürlich auch möglich, nur eben deutlich unhandlicher.
Antworten