Advent of Code

[__blackjack__]

@kbr: Ich finde `attr` genial. Nach dem Anfang des Umstiegs auf Python 3 hat der Wegfall von `__cmp__()` das Fass zum überlaufen gebracht. Da muss ich jetzt zwei Methoden implementieren (`__eq__()` und zum Beispiel `__lt__()`) und `functools.total_ordering` als Dekorator für die Klasse verwenden – oder `__ne__()`, `__gt__()`, `__le__()`, und `__ge__()` auch noch von Hand implementieren, wenn ich vergleichbare Werte haben will. Und wenn man `__eq__()`/`__ne__()` implementiert,sollte man auch `__hash__()` implementieren. Eine `__repr__()` habe ich auch fast immer früher oder später implementiert. Und das Muster für diese Methoden ist jedes mal gleich. Mit `attr` wird man diesen ganzen Boilerplate Code los.

Mein Code speichert das Ergebnis ja auch als Bild. Das habe ich eben noch schnell durch das markieren des nicht-überlappenden Teils ergänzt. Sieht bei jetzt so aus:

[kbr]

Schaut ein wenig aus wie Hubble Deep-Space

[ThomasL]

Bei Tag 3 habe ich irgendwie sofort an Mengen gedacht und das so umgesetzt

Code: Alles auswählen

# ----- Part 1 -----

claims = list()
with open('day_03_input.txt', 'r') as inputfile:
    for line in inputfile:
        origin, size = line.split()[2:]
        
        start_x, start_y = origin[:-1].split(',')
        origin = tuple([int(start_x), int(start_y)])
        
        width, height = size.split('x')
        size = tuple([int(width), int(height)])
        
        claims.append(tuple([origin, size]))

squares = list()
for origin, size in claims:
    start_x, start_y = origin
    width, height = size
    square_inches = set([(start_x + x, start_y + y) for x in range(width) for y in range(height)])
    squares.append(square_inches)

union = set()
for i, mat1 in enumerate(squares):
    for j, mat2 in enumerate(squares):
        if j > i:
            intersection = mat1 & mat2
            if len(intersection) > 0:
                union = union | intersection

print(len(union))

# ----- Part 2 -----

for idnum, square in enumerate(squares, 1):
    intersection = square & union
    if len(intersection) == 0:
        print(idnum)

[__blackjack__]

@ThomasL: Da sind so verdammt viele unnötige Listen drin. Warum bei den ganzen Tupeln erst eine Liste erstellen, statt gleich ein Tupel hinzuschreiben?

Die beiden verschachtelten Schleifen könnte man ohne `i` und `j` mit `collections.combinations()` schreiben. Bei den letzten drei Zeilen könnte man sich das ``if`` sparen und einfach auch die leere Menge zu verarbeiten.

[nezzcarth]

Bei Tag 3 habe ich irgendwie sofort an Mengen gedacht

Ging mir so ähnlich, deine Variante ist aber noch etwas konsequenter :

Code: Alles auswählen

#!/usr/bin/env python3
import re
import fileinput
from collections import namedtuple

Claim = namedtuple('Claim', ['id', 'left', 'top', 'width', 'height'])
PATTERN = re.compile(r'\d+')

def iter_claims():
    for line in fileinput.input():
        yield Claim(*[int(item) for item in re.findall(PATTERN, line)])


def main():
    claims = list(iter_claims())
    claim_map = dict()
    isolated = set(claim.id for claim in claims)
    for claim in claims:
        for row in range(claim.top, claim.top + claim.height):
            for cell in range(claim.left, claim.left + claim.width):
                claim_map.setdefault((row, cell), set())
                claim_map[(row, cell)].add(claim.id)
                if len(claim_map[(row, cell)]) > 1:
                    isolated -= set(claim_map[(row, cell)])
    print('Squares:', sum(len(cell) > 1 for cell in claim_map.values()))
    assert len(isolated) == 1
    print('Isolated:', isolated.pop())


if __name__ == '__main__':
    main()
    

Und was attrs angeht, bin ich persönlich eher etwas zurückhaltend, da es sich um eine externe Bibliothek handelt, die ein Kernkonzept, nämlich die Art und Weise, wie man Klassen schreibt, abändert. Man hört aber viel Gutes drüber.

[__blackjack__]

@ThomasL: Ich habe Deinen Code mal überarbeitet, aber der Ansatz ist IMHO nicht gut, denn Dein Original braucht bei mir 11 Sekunden! Das habe ich auf knapp unter 4 drücken können, ohne das ich speziell irgendwas gemacht habe ausser Vereinfachungen die IMHO alle nicht auf Kosten der Lesbarkeit gehen, aber gegen den Sekundenbruchteil den der Ansatz von kbr und mir braucht, ist das IMHO immer noch zu langsam.

Hier der überarbeitete Code:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import combinations

# ----- Part 1 -----

claims = list()
with open('day_03_input.txt', 'r') as inputfile:
    for line in inputfile:
        origin, size = line.split()[2:]
        origin = tuple(map(int, origin[:-1].split(',')))
        size = tuple(map(int, size.split('x')))
        claims.append((origin, size))


squares = [
    set((start_x + x, start_y + y) for x in range(width) for y in range(height))
    for (start_x, start_y), (width, height) in claims
]

union = set()
for mat1, mat2 in combinations(squares, 2):
    union |= mat1 & mat2

print(len(union))

# ----- Part 2 -----

for idnum, square in enumerate(squares, 1):
    if union.isdisjoint(square):
        print(idnum)

[ThomasL]

@ThomasL: Ich habe Deinen Code mal überarbeitet, aber der Ansatz ist IMHO nicht gut, denn Dein Original braucht bei mir 11 Sekunden! Das habe ich auf knapp unter 4 drücken können, ohne das ich speziell irgendwas gemacht habe ausser Vereinfachungen die IMHO alle nicht auf Kosten der Lesbarkeit gehen, aber gegen den Sekundenbruchteil den der Ansatz von kbr und mir braucht, ist das IMHO immer noch zu langsam.

Hi __blackjack__, es ist mir immer eine Freude, deine Code-Beispiele durch zu arbeiten, sie zu verstehen und daraus zu lernen.
Persönlich habe ich die täglichen AoC Aufgaben nicht so verstanden, dass es dabei darum geht, Code mit der kürzesten runtime zu schreiben.
Bei den Teilnehmern die auf eine Platzierung im Leaderboard "scharf" waren, ging es eher darum, so schnell wie möglich eine Lösung zu coden
um unter die Top100 zu kommen. Klar, wenn der gewählte Algorithmus dann eine Runtime von Stunden hat ist das kontraproduktiv.
Aber 1h die runtime zu optimieren um dann 11sek zu "sparen" macht keinen Sinn.
Aber ich kann mir vorstellen, dass du einen beruflichen Background hast, bei dem es wichtig ist, das jede ms in der Produktion eingespart wird und das ist auch gut so.

Ich habe mal meine Kenntnisse in regular expressions aufgefrischt (Danke an @kbr für seinen Einlese-Code)
und das Einlesen der Daten und das Erstellen der "squares"-Liste zusammen gefasst.
Auf meiner todo-Liste steht definitiv noch die Einarbeitung in das Modul itertools, das ist bisher zu kurz gekommen.

Code: Alles auswählen

from itertools import combinations
import re

# ----- Part 1 -----
pattern = re.compile(r'#\d+ @ (\d+),(\d+): (\d+)x(\d+)')
squares = list()
with open('day_03_input.txt', 'r') as inputfile:
    for line in inputfile:
        start_x, start_y, width, height = list(map(int, pattern.match(line).groups()))
        squares.append(set((start_x + x, start_y + y) for x in range(width) for y in range(height)))

union = set()
for mat1, mat2 in combinations(squares, 2):
    union |= mat1 & mat2
print(len(union))

# ----- Part 2 -----
for idnum, square in enumerate(squares, 1):
    if union.isdisjoint(square):
        print(idnum)

[__blackjack__]

@ThomasL: Viel Webanwendungen. Da zählt nicht jede Millisekunde, aber wenn eine Seite/Benutzeraktion ~10 Sekunden braucht, dann werden die Benutzer schon ungeduldig. Hier geht es IMHO nicht wirklich ums Optimieren, denn das ist einfach der falsche Algorithmus wenn man statt quadratischer Laufzeit mit einem viel einfacheren Ansatz in linearer Laufzeit (und weniger Speicherverbrauch und ”-geschaufel”) in einem Sekundenbruchteil das Ergebnis haben kann.

Und weder der linear laufende Ansatz noch das ”optimieren” Deines Codes hat eine Stunde gedauert. Optimieren in Anführungsstriche weil es mir dabei gar nicht in erster Linie auf die Geschwindigkeit ankam, sondern einfach nur auf vereinfachen des Codes ohne das die Lesbarkeit stark leidet. Der Geschwindigkeitszuwachs war ein netter Nebeneffekt.

Die Implementierung und Fehlersuche auf dem C64 hat ewig gedauert. Das aber hauptsächlich weil ich so gar nicht mit einer bestimmten Hardwareeigenschaft der Speichererweiterung gerechnet hatte und da laaaange nach dem Fehler im Code gesucht hatte. Dessen Lösung dann am Ende super einfach war.

Da könnte ich locker noch mehr Zeit reinstecken um das schneller und/oder kleiner zu bekommen. Eine einfache Idee die Hälfte des Speichers einzusparen wäre nur bis 2 zu zählen, also 0 = kein „claim“, 1 = genau ein „claim“, oder 2 = mehr als ein „claim“. Dann käme man mit 1 MB Speicher aus. Da dann pro in² zwei Bits ausreichen würden, könnte man vier Werte pro Byte kodieren, und käme sogar mit nur 256 KB aus, also die mittlere von Commodores Original-Speichererweiterungen. Die Bitoperationen würden dafür dann aber auf die Rechenzeit gehen. Noch mehr auf die Rechenzeit würde es gehen wenn man nicht das gesamte grosse Gewebe auf einmal berechnen würde, sondern das ganze in Streifen aufteilt, die noch in den normalen Speicher passen. Für den zweitem Aufgabenteil könnte man die Daten für die Streifen noch mal auf 1-Bit pro 2er-Wert eindampfen und auf Diskette speichern. Die 125 KiB passen auf eine normale 1541-Diskettenseite.

Bei den beiden Ansätzen in Python ist auf dem Rechner an dem ich gerade sitze der Geschwindigkeitsunterschied Faktor 36. Hätte sich der Aufgabensteller entschieden die doppelte Anzahl von Eingabezeilen zu liefern wäre die Lösung mit den Mengen hier schon um den Faktor 344 langsamer. Absolut gesehen ≈1½ Minuten gegen ≈⅓ Sekunde.

[__blackjack__]

Nur so als Erinnerung: Auch dieses Jahr gibt's den Kalender wieder, immer noch unter der bekannten URL: https://adventofcode.com/

[ThomasL]

Ich bin schon gespannt wie nen Flitzebogen
Habe in den letzten Wochen fast alle Aufgaben der Jahre 2015 bis 2017 bearbeitet und viel Spaß dabei gehabt.
Bei manchen Aufgaben habe ich nur mehr Zeit gebraucht diese zu lesen wie die Topcoder benötigten das Ergebnis einzugeben. Hmmm, ich schiebe das mal aufs Alter.

[nezzcarth]

Die Idee mit dem 'intcode'-Computer, der im Laufe der "Türchen" fortentwickelt wird, finde ich an sich gut. Nur habe ich das Gefühl, dass bei mir schon jetzt der Schwellwert erreicht ist, an dem ich die Aufgaben nicht mehr tagesaktuell Abends noch mal eben schnell löse. So früh musste ich bei Advent of Code noch nie aussteigen Vermutlich ist es, wenn ich die Aufgabenstellung noch mal in Ruhe lese doch nicht so aufwendig zu implementieren, aber eine etwas weniger stark ansteigende Komplexität hätte etwas für sich.

[__blackjack__]

@nezzcarth: Jau, der Intcode hat mich auch ausgebremst. Da ist immer die Frage wie flexibel man Code gestaltet was Erweiterungen angeht. Ich hatte den am 2. so simpel wie möglich gehalten, ohne Klassen, und dann lieber Zeit in eine BASIC-Version für den C64 gesteckt und Pascal auf dem DOS-Rechner war auch noch drin. Am Donnerstag hatte ich vor der Arbeit dann nur geschafft die Lösung von Donnerstag flexibler/erweiterbarer zu gestalten die Ein- und Ausgabe-Instruktionen + Tests zu implementieren und zu testen das das Programm vom 2. immer noch mit dem neuen Intcode-Prozessor — jetzt eine Klasse — immer noch läuft. Von da bis heute abend hatte ich dann keine Zeit. Jetzt habe ich immerhin den 5. abgeschlossen.

Ich bin froh über das Wochenende zum aufholen. Mal sehen ob ich morgen die drei fehlenden Tage schaffe.

[ThomasL]

Nun, ob sich die Arbeit an der intcode Prozessor Klasse gelohnt hat, wirst du dann bei Tag 7 Part 2 feststellen. (oder haste schon)
Da wurste ich noch dran, alles andere, insbesondere heute war doch bisher easy peasy, oder?

[__blackjack__]

@ThomasL: Tag 7, Teil 2 bin ich gerade. Gelohnt denke ich schon, aber in der Tat muss ich da jetzt nachdenken wie ich das umsetze. Eingabe ist schon über ein ”iterable” gelöst und für die Ausgabe kann man bereits eine Rückruffunktion angeben. Ich müsste also eigentlich einfach ein `Wire` oder eine `Connection` schreiben können die zwei Prozessoren verbindet und die Prozessoren einfach in Threads nebenläufig laufen lassen. Dann müsste ich die Prozessor-Implementierung nicht anfassen. Alternativ könnte ich einen einzelnen Schritt/Takt aus der `Processor.run()` als Methode heraus ziehen und Prozessorstati wie RUNNING, BLOCKING_ON_IO, und HALTED einführen und dann eine externe `run()`-Funktion einführen der man auch mehrere Prozessoren geben kann, die dann nacheinander immer für einen Schritt/Takt angestossen werden, bis alle nicht mehr RUNNING sind.

[ThomasL]

Hätte ich nicht gedacht, dass ich das hinkriege.

[nezzcarth]

Da wurste ich noch dran, alles andere, insbesondere heute war doch bisher easy peasy, oder?

Langsam wird das ja eher zum Advent of Intcode Inzwischen versuche ich jedenfalls zu antizipieren, was die nächste Erweiterung sein könnte (hat heute nicht geklappt); wenn wie bisher alle zwei bis drei "Türchen" wieder so eine Aufgabe kommt, steht da ja noch einiges aus. An sich finde ich den Intcode-Interpreter auch nicht schwierig zu implementieren, was mir aber Schwierigkeiten bereitet, ist ein Design zu finden, das die Features transparent, gut erweiterbar und ohne Wiederholungen abbildet. Insb. mit meiner Implementierung des Parameterhandlings bin ich noch nicht so glücklich. Vielleicht können wir später mal vergleichen, wie der Interpreter zum Schluss jeweils aussieht. Das würde mich wirklich interessieren.

[ThomasL]

Ja, gerne. Ich hatte mir schon vorgenommen, hier Code zu posten, um auch konstruktive Kritik von unseren Meistern zu bekommen
Aber um jetzt niemanden zu spoilern, würde ich das dann nach Weihnachten machen.

[__blackjack__]

@nezzcarth: Mein Umgang mit den Parametern ist ziemlich hässlich. Zum einen weil das ja alles dezimal ist wo in echten Rechnern binär zum tragen kommt und man die einzelnen Komponenten per Bitoperationen wie Shiften und Maskieren isolieren kann. Da habe ich mit Umwandlung in Zeichenketten und dann die einzelnen Ziffern wieder in `int` umwandeln gearbeitet, und dann die Reihenfolge umgedreht und per „slicing“ nur die nötige Anzahl davon dann weitergereicht. Superhässlich. Zum anderen ist das halt alles mit jeder Anforderung gewachsen, statt einmal mit allen Anforderungen im Kopf entworfen worden zu sein.

Würde das aber natürlich trotzdem zeigen. Sind so etwa 280 Zeilen ohne die `main()` von heute und die ganze Unittests.

Heute stand da ja am Anfang des zweiten Aufgabenteils der Satz: „You now have a complete Intcode computer.“. Hervorgehoben. Vielleicht war's das ja mit Erweiterungen. Was nicht heissen muss, dass der Computer nicht in weiteren Aufgaben benutzt werden kann. Wir können ja mal versuchen zu raten was noch kommen kann. Vielleicht kommt demnächst als Puzzle-Eingabe Assemblerquelltext für diese Rechner und die Aufgabe wird sein den in Intcode zu übersetzen und auf dem Rechner laufen zu lassen.

Schade fand ich heute die beiden Erweiterungen mit grossen Zahlen und quasi nicht näher begrenztem Hauptspeicher. Damit bekommen Pläne das auf dem C64 zu versuchen einen Dämpfer.

[ThomasL]

....Da habe ich mit Umwandlung in Zeichenketten und dann die einzelnen Ziffern wieder in `int` umwandeln gearbeitet, und dann die Reihenfolge umgedreht und per „slicing“ nur die nötige Anzahl davon dann weitergereicht......

Kommt mir bekannt vor....

[Whitie]

Hallo zusammen,
ich hab auch erst mit Zeichenketten rumgespielt. Als der dritte Mode dazu kam, habe ich dann sowas gemacht:

Code: Alles auswählen

def _parse_instruction(instruction):
    opcode = instruction % 100
    modes = [
        (instruction // 100) % 10,
        (instruction // 1000) % 10,
        (instruction // 10000) % 10,
    ]
    return opcode, modes

Gruß
Whitie