Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Benutzeravatar
kbr
User
Beiträge: 957
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: 586
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: 5633
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...
shcol (Repo | Doc | PyPi)
Sirius3
User
Beiträge: 8805
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: 957
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: 419
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."
Benutzeravatar
kbr
User
Beiträge: 957
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: 586
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: 419
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."
Antworten