Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Benutzeravatar
kbr
User
Beiträge: 1005
Registriert: Mittwoch 15. Oktober 2008, 09:27

Sonntag 2. Dezember 2018, 15:09

Ok, da funktionierende Lösungen hier schon kursieren, zeige ich auch mal meine, um dazu beizutragen, möglichst pythonische Lösungen zu finden. Die Idee zu Aufgabe Tag 2a war die Nutzung von Counter und Sets:

Code: Alles auswählen

from collections import Counter

two_seen = 0
three_seen = 0
with open('day02a.inp') as fobj:
    for line in fobj:
        n = {v for v in Counter(line).values()}
        two_seen = two_seen + 1 if 2 in n else two_seen
        three_seen = three_seen + 1 if 3 in n else three_seen
print(two_seen, three_seen)
print(two_seen * three_seen)

und zu Aufgabe b habe ich nicht gegoogelt und in die difflib hatte ich gleichfalls keinen Blick geworfen. Die builtins haben aber auch gereicht:

Code: Alles auswählen

def diff_by_one(p, q):
    return sum(1 for i, j in zip(p, q) if i != j) == 1

def check_against_known(known, new):
    for k in known:
        if diff_by_one(k, new):
            return k, new
    known.append(new)
    return None, None

def remove_uncommon(p, q):
    return ''.join(p for p, q in zip(p, q) if p==q)

with open('day02a.inp') as fobj:
    known = []
    for line in fobj:
        new = list(line.strip())
        p, q = check_against_known(known, new)
        if p:
            result = remove_uncommon(p, q)
            break
print(result)
nezzcarth
User
Beiträge: 678
Registriert: Samstag 16. April 2011, 12:47

Sonntag 2. Dezember 2018, 15:35

kbr hat geschrieben:
Sonntag 2. Dezember 2018, 15:09
Ok, da funktionierende Lösungen hier schon kursieren, …
Ich denke, das ist okay. Der Lösungs-Thread auf reddit wird freigegeben, sobald die ersten 100 Plätze des Leaderboards gefüllt sind. Das ist im Moment noch sehr schnell der Fall ;) Insofern finde ich es sehr gut, wenn wir hier pythonische Lösungen sammeln können.

Hier meine kombinierte Lösung für beide Teilaufgaben. Für die Differenzberechnung habe ich so eine Art Hamming-Distanz implementiert, die allerdings Indices ausgibt:

Code: Alles auswählen

#!/usr/bin/env python3
import fileinput
from collections import Counter
from itertools import combinations

def get_difference(s1, s2):
    assert len(s1) == len(s2)
    return [i for i, chars in enumerate(zip(s1, s2)) if chars[0] != chars[1]]


def main():
    box_ids = [box_id.strip() for box_id in fileinput.input()]
    twos = 0
    threes = 0
    for box_id in box_ids:
        amounts = Counter(box_id)
        if 2 in amounts.values():
            twos += 1
        if 3 in amounts.values():
            threes += 1
    print('Result:', twos * threes)
    for pair in combinations(box_ids, 2):
        difference = get_difference(*pair)
        if len(difference) == 1:
            index = difference[0]
            print(pair[0][:index] + pair[0][index+1:])


if __name__ == '__main__':
    main()
Benutzeravatar
snafu
User
Beiträge: 5785
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Sonntag 2. Dezember 2018, 20:07

Also ich habe den ersten Tag einfach so gelöst:

Code: Alles auswählen

def make_frequency(changes):
    return sum(map(int, changes))
EDIT: Nun verstanden, dass sich eure Diskussion auf die zweite Aufgabe bezog...
Sirius3
User
Beiträge: 9702
Registriert: Sonntag 21. Oktober 2012, 17:20

Montag 3. Dezember 2018, 06:29

@kbr: `set` kann mit jedem Iterable initialisiert werden und boolsche Ausdrücke werdenals 0 oder 1 interpertiert, womit sich Deine Teillösung vereinfacht:

Code: Alles auswählen

from collections import Counter

two_seen = 0
three_seen = 0
with open('day02a.inp') as lines:
    for line in lines:
        n = set(Counter(line).values())
        two_seen += 2 in n
        three_seen += 3 in n
print(two_seen, three_seen)
print(two_seen * three_seen)
Benutzeravatar
kbr
User
Beiträge: 1005
Registriert: Mittwoch 15. Oktober 2008, 09:27

Montag 3. Dezember 2018, 09:25

@Sirius3: Stimmt. Viel öfter als man vermutet wird man für seinen eigenen Code blind und umständliche Dinge bleiben drin. In diesem Fall wird auch der Bytecode etwas kürzer und die Ausführung leicht schneller.
Benutzeravatar
ThomasL
User
Beiträge: 662
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Montag 3. Dezember 2018, 12:52

Wie geil ist das denn :shock: , das muss ich mir merken :!:
Sirius3 hat geschrieben:
Montag 3. Dezember 2018, 06:29

Code: Alles auswählen

        two_seen += 2 in n
        three_seen += 3 in n
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
Benutzeravatar
kbr
User
Beiträge: 1005
Registriert: Mittwoch 15. Oktober 2008, 09:27

Montag 3. Dezember 2018, 22:04

Ich weiß nicht, ob ihr unter der Woche Zeit für AoC habt. Heute im ICE hatte ich aber etwas Muße und poste hier mal, was mir für den dritten Tag so eingefallen ist. Dabei geht es mir um pythonische Lösungen. Falls also Kommentare und Verbesserungen angesagt sind: nur zu!

Code: Alles auswählen

import re
import numpy as np


PATTERN = re.compile(r'#(\d+) @ (\d+),(\d+): (\d+)x(\d+)')


def fabric_file(fobj):
    fobj.seek(0)
    for line in fobj:
        yield map(int, PATTERN.match(line).groups())

def get_dimensions(fobj):
    width = height = 0
    for _, x, y, w, h in fabric_file(fobj):
        width = max(width, x+w)
        height = max(height, y+h)
    return width, height

def get_fabric(fobj, width, height):
    fabric = np.zeros(width*height).reshape(width, height)
    for _, x, y, w, h in fabric_file(fobj):
        fabric[x:x+w, y:y+h] += 1
    return fabric

def get_nonoverlap_id(fobj, fabric):
    for i, x, y, w, h in fabric_file(fobj):
        if fabric[x:x+w, y:y+h].sum() == w * h:
            return i

with open('day03a.inp') as fobj:
    width, height = get_dimensions(fobj)
    fabric = get_fabric(fobj, width, height)
    print(len(fabric[fabric>1]))
    print(get_nonoverlap_id(fobj, fabric))
nezzcarth
User
Beiträge: 678
Registriert: Samstag 16. April 2011, 12:47

Dienstag 4. Dezember 2018, 06:51

Als Regex habe ich '\d+' verwendet, das macht es m.M.n. etwas übersichtlicher. Ansonsten fällt mir gerade nichts auf. :)
Benutzeravatar
ThomasL
User
Beiträge: 662
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Sonntag 9. Dezember 2018, 18:53

Hallöchen zusammen,
ich hoffe doch ihr seid alle noch eifrig am #AdventOfCoden....

Bei der heutigen Aufgabe habe ich zuerst überhaupt nicht verstanden wie "gespielt" wird.
Bekam dann durch einen Tweet den Hinweis "double linked list".
Ok, habe ich hinbekommen, nicht elegant aber funktionierte, Aufgabe gelöst. 2 Sternchen

Da bei Teil die Schleife um Faktor 100 vergrößert wird, benötigte meine alte Möhre ca. 18sek.
Dachte mir, "there is always a better way" und bin auf collections.deque gestossen.
Ein wenig herum experimentiert und neue Lösung geschrieben.

Ergebnis siehe unten, nur noch 22 Zeilen von zuvor 57 und ca. 7-fach schneller.

Code: Alles auswählen

from collections import deque

max_player = 452
last_marble = 71250 * 100 + 1

score = {key: 0 for key in range(1, max_player + 1)}
circle = deque([0])

current_player = 1
for marble in range(1, last_marble):
    if marble % 23 != 0:
        circle.rotate(-1)
        circle.append(marble)
    else:
        circle.rotate(8)
        score[current_player] += marble + circle[0]
        circle.popleft()
        circle.rotate(-1)
    current_player = current_player % max_player + 1

best_player = max(score, key=lambda key: score[key])
print(f'Best player {best_player} with Score {score[best_player]}')
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
Benutzeravatar
__blackjack__
User
Beiträge: 3094
Registriert: Samstag 2. Juni 2018, 10:21

Freitag 14. Dezember 2018, 18:33

Der erste Teil von Tag 1 war supereinfach in BASIC auf dem C64:

Code: Alles auswählen

10 S=0:OPEN 2,8,2,"INPUT01,S"
20 INPUT#2,N:S=S+N:IF ST=0 THEN 20
30 CLOSE 2:PRINT S
Für den zweiten Teil reicht der Speicher leider nicht aus. :-(

Tag 2 liess sich dagegen komplett in BASIC lösen:

Code: Alles auswählen

   10 TI$="000000":CR$=CHR$(13):A=ASC("A"):DIM ID(255,25),H(25)
  100 PRINT"READ IDS..."
  110 I=0:J=0:OPEN 2,8,2,"INPUT02,S"
  120 GET#2,C$:IF ST<>0 THEN 170
  130 PRINT C$;
  140 IF C$<>CR$ THEN ID(I,J)=ASC(C$)-A:J=J+1:GOTO 120
  150 PRINT"{UP}                                       "
  160 I=I+1:J=0:PRINT"{UP}";I;:GOTO 120
  170 CLOSE 2:IC=I:PRINT:PRINT TI$
  200 TI$="000000":PRINT:PRINT"PART 1...{DOWN}":C2=0:C3=0
  210 FOR I=0 TO IC:PRINT"{UP}";I
  220 FOR J=0 TO 25:H(J)=0:NEXT:FOR J=0 TO 25:K=ID(I,J):H(K)=H(K)+1:NEXT
  230 F2=0:F3=0:FOR J=0 TO 25:IF H(J)=2 THEN F2=-1
  240 IF H(J)=3 THEN F3=-1
  250 IF F2 AND F3 THEN J=25
  260 NEXT:C2=C2+-F2:C3=C3+-F3:NEXT:PRINT C2*C3:PRINT TI$
  300 TI$="000000":PRINT"PART 2...{DOWN}":FOR I=0 TO IC:PRINT"{UP}";I
  310 FOR J=I+1 TO IC:DC=0:DI=-1
  320 FOR K=0 TO 25:IF ID(I,K)<>ID(J,K) THEN DC=DC+1:DI=K:IF DC>1 THEN K=25
  330 NEXT:IF DC=1 THEN 400
  340 NEXT:NEXT:PRINT"NO SIMILAR IDS FOUND!":PRINT TI$:END
  400 FOR J=0 TO 25:IF J<>DI THEN PRINT CHR$(ID(I,J)+A);
  410 NEXT:PRINT:PRINT TI$
Ist natürlich nicht besonders schnell. Einlesen der Daten in ein 2D-Array hat ca. 3 Minuten gedauert. Aufgabenteil 1 hat 4 Minuten 17 Sekunden gedauert. Und Aufgabenteil 2 fast 14 Minuten. Wobei das auch länger hätte dauern können wenn der Treffer nicht schon an 22. Stelle gewesen wäre.
“In computing, invariants are ephemeral.” – Alan J. Perlis
Benutzeravatar
__blackjack__
User
Beiträge: 3094
Registriert: Samstag 2. Juni 2018, 10:21

Donnerstag 20. Dezember 2018, 13:21

Boah, dieses Jahr komme ich zeitlich nicht wirklich gut hin. Habe gerade fast drei Tage verplempert den Fehler in meiner Lösung für Tag 3 zu finden, der letztlich auf Hardwareverhalten zurückzuführen war, mit dem ich nicht gerechnet hatte. Also bei der Lösung für den C64 mit einer 2MiB RAM Erweiterung (REU) um 1000×1000 16-Bit-Ganzzahlen für das grosse Stoffquadrat zu speichern. :-)

Das Programm ist in C geschrieben und findet die Lösung für Aufgabenteil 1 und 2 in 8 Minuten und 14 Sekunden. Dabei entfallen 2½ Minuten auf das laden der rechteckigen Anforderungen, 5 Minuten und 14 Sekunden auf das ermitteln der überlappten Quadratzoll, und eine halbe Minute um alle Anforderungen zu suchen die sich nicht mit anderen überschneiden.
“In computing, invariants are ephemeral.” – Alan J. Perlis
Benutzeravatar
ThomasL
User
Beiträge: 662
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Donnerstag 20. Dezember 2018, 17:45

Schau dir mal Tag 19 an, da hättest du (oder hattest bereits) deine Freude dran. Vermute ich.
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
nezzcarth
User
Beiträge: 678
Registriert: Samstag 16. April 2011, 12:47

Freitag 21. Dezember 2018, 18:49

__blackjack__ hat geschrieben:
Donnerstag 20. Dezember 2018, 13:21
Boah, dieses Jahr komme ich zeitlich nicht wirklich gut hin.
Während ich die letzten Jahre eigentlich immer ganz gut dabei war, war dieses Jahr nach Tag 7.1 irgendwie die Luft raus, obwohl ich am Anfang recht motiviert war. Vielleicht schaffe ich bis zum letzten Tag noch was, aber ich vermute, dieses mal wird mindestens die Hälfte liegen bleiben :( Die Aufgaben, die ich bisher gesehen habe, sind oft Variationen von früheren.
Benutzeravatar
__blackjack__
User
Beiträge: 3094
Registriert: Samstag 2. Juni 2018, 10:21

Sonntag 23. Dezember 2018, 22:00

@kbr: Etwas spät, ich weiss, aber ich wollte noch was zu Deiner Lösung für Tag 3 schreiben.

Was mir nicht so gefällt, ist das dieses `fobj` überall übergeben wird. Das macht alle Funktionen unnötig unabhängig von einem Dateiobjekt das „seekbar“ ist und der `fabric_file()`-Funktion. Wenn die Funktionen einfach ein iterierbares Objekt mit (id, x, y, width, height)-Tupeln übergeben bekommen würden, dann wären sie wesentlich leichter testbar, weil man einfach eine feste Liste übergeben könnte.

Statt ein flaches Array mit der Anzahl der Gesamtelemente zu erstellen und das dann zu `reshape()`\en, hätte man gleich die richtige Form erzeugen können: ``np.zeros((w, h))``.

Den Test auf nicht-überlappen finde ich zu ”berechnend”. Da hätte ich einfach getestet ob alle Werte gleich 1 sind: ``(fabric[x:x+w, y:y+h] == 1).all()``. Ist auch ein kleines bisschen robuster gegen Rechtecke die nicht zum `fabric` passen, weil die Summe auch zu Breite mal Höhe passen könnte, wenn die Werte dort *nicht* alle 1 sind. Zumindest auf solche Fälle fällt der Test auf nur 1en nicht herein. Ganz sicher ist der natürlich auch nicht.

In der Funktion würde ich zudem noch etwas zurückgeben wenn kein Treffer gefunden wurde. Und wenn es nur das implizite `None` als explizites ``return None`` ist. Funktionen bei denen es Zweige gibt in denen ein ``return`` steht, und solche in denen keines steht (und auch nichts anderes was die Funktion garantiert beendet), sehen immer so halb fertig aus, und man fragt sich ob das so sein soll, oder ob der Programmierer da noch Fälle nicht bedacht hat.

Statt die Elemente die grösser als 1 sind, tatsächlich zu selektieren und dann die Länge davon zu nehmen, hätte ich nur die Wahrheitswerte gezählt: ``(fabric > 1).sum()``.

Meine Lösung ist etwas klassischer und etwas mehr selbst ausprogrammiert:

Code: Alles auswählen

#!/usr/bin/env python3
from attr import attrib, attrs


@attrs(frozen=True)
class Patch:
    id = attrib()
    x = attrib()
    y = attrib()
    width = attrib()
    height = attrib()

    @property
    def top(self):
        return self.y
    
    @property
    def bottom(self):
        return self.y + self.height
    
    @property
    def left(self):
        return self.x
    
    @property
    def right(self):
        return self.x + self.width

    def iter_coordinates(self):
        for y in range(self.top, self.bottom):
            for x in range(self.left, self.right):
                yield x, y

    @classmethod
    def from_line(cls, line):
        id_part, rect_part = line.split('@', 1)
        if not id_part.startswith('#'):
            raise ValueError('ID does not start with `#`')
        coordinate_part, dimension_part = rect_part.split(':', 1)
        x, y = map(int, coordinate_part.split(',', 1))
        width, height = map(int, dimension_part.split('x', 1))
        return cls(int(id_part[1:]), x, y, width, height)


class Sheet:
    
    def __init__(self, size=1000):
        self.squares = [[0] * size for _ in range(size)]

    @property
    def size(self):
        return len(self.squares)

    def get_max_value(self):
        return max(map(max, self.squares))
    
    def count_overlapped(self):
        return sum(sum(c > 1 for c in row) for row in self.squares)
    
    def check(self, patch):
        for x, y in patch.iter_coordinates():
            if self.squares[y][x] != 1:
                return False
        return True

    def claim(self, patch):
        for x, y in patch.iter_coordinates():
            self.squares[y][x] += 1
    
    def save_pgm(self, filename):
        max_value = self.get_max_value()
        if max_value > 255:
            raise ValueError('too many gray levels')
        with open(filename, 'wb') as out_file:
            out_file.write(
                f'P5 {self.size} {self.size} {self.get_max_value()}\n'.encode(
                    'ascii'
                )
            )
            out_file.writelines(map(bytes, self.squares))


def main():
    with open('input03.txt') as lines:
        patches = [Patch.from_line(line) for line in lines]
    print(
        'max width/height:',
        max(max(patch.width, patch.height) for patch in patches),
    )
    sheet = Sheet()
    for patch in patches:
        sheet.claim(patch)
    sheet.save_pgm('sheet.pgm')
    print(sheet.count_overlapped())
    print([patch for patch in patches if sheet.check(patch)])


if __name__ == '__main__':
    main()
“In computing, invariants are ephemeral.” – Alan J. Perlis
Benutzeravatar
kbr
User
Beiträge: 1005
Registriert: Mittwoch 15. Oktober 2008, 09:27

Mittwoch 26. Dezember 2018, 15:44

@__blackjack__: schön, dass Du Dir die Mühe gemacht hast, die Aufgabe auch einmal durchzugehen; quasi ein Weihnachtsgeschenk ;)

Bei den AoC Aufgaben habe ich auf Robustheit nur wenig Wert gelegt, da die Eingaben wohldefiniert und meine Lösungen auch nur darauf abgestimmt waren. Ansonsten hast Du recht: das lässt sich auch stabiler und testbarer machen.

Ob mir die Nutzung von 'attr' gefällt, weiß ich noch nicht. Zwar finde ich dies besser als Dataclasses (die mir auch nicht gefallen), aber mit Klassendekoratoren ist es wie mit Metaklassen: man muss wissen, dass der sichtbare Quellcode nicht mit dem übereinzustimmen braucht, der dann auch ausgeführt wird. Das kann zu eleganten Code beitragen, aber auch zu Intransparenz führen. Ich würde solche Techniken nur sehr gezielt und sparsam einsetzen wollen.
Antworten