Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

BlackJack hat geschrieben:Wenn man das zwei mal anwendet, hat man wieder den Ausgangszustand. Das schwierigste ist IMHO das Rotieren mit gegebenen Buchstaben, weil da die Anzahl der Stellen vom Index des Buchstabens vor dem Rotieren abhängt.
Das war auch, was ich meinte; copy&paste Fehler. :oops: Wie soll man rückwirkend analytisch bestimmen, welche Position der Buchstabe vorher hatte? Das geht vermutlich doch wieder besser per (semi-)brute-force.
Naja, mal sehen, was mir dazu einfällt :)
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

nezzcarth hat geschrieben:Wie soll man rückwirkend analytisch bestimmen, welche Position der Buchstabe vorher hatte? Das geht vermutlich doch wieder besser per (semi-)brute-force.
Nein, das ist sogar ganz einfach, da die Verschiebung des Buchstabens aus der ersten Teilaufgabe eindeutig ist. Ich hatte mir eine Tabelle angelegt um dies zu testen, da ich auf brute-force keine Lust hatte. Und siehe da: auch dieser Schritt ist eindeutig umkehrbar :)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Auch dieses Jahr gibt es wieder eine Neuauflage:
http://adventofcode.com/2017
Vielleicht kennen es machen noch nicht und haben ja einige Lust, mit zu rätseln.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Wie habt ihr Tag 3 gelöst? Ich muss zugeben, dass ich mir für Teil 1 per oeis passende Formeln zusammengesucht habe, um die X und Y Koordinaten zu bestimmen. Zählt das schon als Schummeln? Jedenfalls ging es mit einem Iterator, der die Koordinaten ausspuckt dann ganz einfach... ;)
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Und auch dieses Jahr gibt's den Adventskalender für Programmierer wieder. *<:-)
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

Den werde ich mir definitv mal anschauen, danke für den Hinweis.

Achja, du hast hier einen SyntaxError:
__blackjack__ hat geschrieben: Donnerstag 29. November 2018, 09:52 *<:-)
Es muss so lauten:

*<{:-)
When we say computer, we mean the electronic computer.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@sls: Das passiert wenn man zu viel in einer Programmiersprache arbeitet die zu wenige geschweifte Klammern in der Syntax hat. :-D
“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

Direkt im ersten "Törchen" kann man heute schon was über die unterschiedliche Effizienz von Pythons eingebauten Datenstrukturen lernen ;)
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

Gibt es irgendwo Musterlösungen in Python?

Für die zweite Aufgabe habe ich eine while-Schleife verwendet, in welcher eine for-Loop immer über die für mich generierte Liste iteriert, das ganze ist allerdings dermaßen ineffizient (~ 79 Sekunden) :|

EDIT: anders gefragt, welchen Ansatz könnte / sollte ich stattdessen wählen?

Code: Alles auswählen

while True:
    for frequency in frequencies:
        ...
When we say computer, we mean the electronic computer.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

sls hat geschrieben: Samstag 1. Dezember 2018, 13:26 ... das ganze ist allerdings dermaßen ineffizient (~ 79 Sekunden) :|
Läuft bei mir unter einer Sekunde. Schau Dir mal "itertools.cycle" an.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Eine Musterlösung in dem Sinne ist mir nicht bekannt. Es gibt zu jedem Tag einen Thread im offiziellen Subreddit, in dem jeder seine Lösung vorstellen kann: https://www.reddit.com/r/adventofcode/c ... solutions/
Für viele scheint das allerdings eher ein Wettbewerb um den cleversten One-Liner zu sein (sicher auch wegen des Leaderboards), daher zeigen die Python-Lösungen meiner Meinung nach nicht immer unbedingt das sauberste Python.

Hier mal meine Lösung, die sicher auch nicht mustergültig ist:

Code: Alles auswählen

#!/usr/bin/env python3
import fileinput
from itertools import cycle

def main():
    adjustments = [int(line) for line in fileinput.input()]
    print('Sum:', sum(adjustments))
    frequencies = set()
    frequency = 0
    for adjustment in cycle(adjustments):
        frequency += adjustment
        if frequency in frequencies:
            print("Repeat:", frequency)
            break
        frequencies.add(frequency)

if __name__ == '__main__':
    main()
(Wenn man für 'seen' eine Liste nimmt statt eines Sets, wird es übrigens sehr langsam; darauf bezog sich mein erster Post).

Und hier noch meine Lösung in AWK:

Code: Alles auswählen

#!/usr/bin/awk -f
{
    sum += $1
    buffer[NR-1] = $1
}

END {
    print "Sum:", sum
    frequency = 0
    i = 0
    size = length(buffer)
    while (1) {
        frequency += buffer[i]
        if (frequency in seen) {
            print "Repeat:", frequency
            break
        }
        seen[frequency] = 1
        i = (i+1) % size
    }
}
Zuletzt geändert von nezzcarth am Samstag 1. Dezember 2018, 13:54, insgesamt 2-mal geändert.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@sls: Also ich habe `itertools.cycle()` statt der zwei Schleifen verwendet, aber das kommt von der Komplexität letztlich auf das gleiche heraus.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

Danke für den Hinweis mit cycle()!

Ich hatte für "frequencies" ursprünglich eine Liste als Container zur Sammlung aller bisherigen resultierenden Frequenzen verwendet, dadurch wurde das ganze elendig langsam. Vielen dank für den Hinweis @nezzcarth!

cycle() ist ja genial, dadurch spare ich mir auch noch die while-Schleife.

Erster Versuch, mit while-Loop ohne cycle()

Code: Alles auswählen

adjustments = [16, 9, 11, 13 ...
frequencies = set()
frequency = 0
not_seen = True

while not_seen:
    for adjustment in adjustments:
        frequency += adjustment
        if frequency in frequencies:
            print("Twice: ", frequency)
            not_seen = False
            break
        frequencies.add(frequency)
Zweiter Versuch mit cycle()

Code: Alles auswählen

frequencies = set()
frequency = 0

for adjustment in itertools.cycle(adjustments):
    frequency += adjustment
    if frequency in frequencies:
        print("Twice: ", frequency)
        break
    frequencies.add(frequency)
When we say computer, we mean the electronic computer.
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

Ich habe mir die nächste "Tür" angeschaut und es so gelöst:

Code: Alles auswählen

from collections import Counter


def main():
    with open('item_ids.txt', 'r') as fd:
        box_ids = fd.read().splitlines()

    twice = 0
    triple = 0

    for box_id in box_ids:
        letter_count = Counter(box_id).values()
        if 2 in letter_count:
            twice += 1
        if 3 in letter_count:
            triple += 1

    print("Checksum: ", twice * triple)


if __name__ == '__main__':
    main()
Da meine Lösung für meine IDs passt, gehe ich mal davon aus dass die Buchstaben immer ein, zwei oder maximal drei mal in einer Box-ID vorkommen können.
When we say computer, we mean the electronic computer.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

sls hat geschrieben: Sonntag 2. Dezember 2018, 14:03Da meine Lösung für meine IDs passt, gehe ich mal davon aus dass die Buchstaben immer ein, zwei oder maximal drei mal in einer Box-ID vorkommen können.
"Davon ausgehen" ist *meistens* eine böse Falle...
Bei mir gab es in einer Sequenz einen Buchstaben 4fach und das hat mich Zeit gekostet. :oops:
Bin dann auf diese Lösung gekommen, ich erzeuge das dictionary von Hand, mit collections.Counter ist es verdammt eleganter

Code: Alles auswählen

sequences = [...]

twos, threes = 0, 0
for sequence in sequences:
    count = {}
    for letter in sequence:
        try:
            count[letter] += 1
        except:
            count[letter] = 1
    most = set(count.values())
    if 2 in most:
        twos += 1
    if 3 in most:
        threes += 1

print(f'Checksum: {twos} * {threes} = {twos*threes}')
Hier mein Code für den zweiten Teil:

Code: Alles auswählen

from difflib import SequenceMatcher, ndiff

sequences = [...]
matcher = SequenceMatcher(None, '', '')
for row, first_sequence in enumerate(sequences):
    matcher.set_seq2(first_sequence)
    for column, second_sequence in enumerate(sequences):
        if column > row:
            matcher.set_seq1(second_sequence)
            if int(matcher.ratio() * len(first_sequence)) == len(first_sequence) - 1:
                matching = [letter[-1] for letter in ndiff(first_sequence, second_sequence) if letter[0] not in '+-']
                print(''.join(matching))
Hatte einfach mal nach "python string find differences" gegoogelt und Beispiele gesehen, die difflib verwenden und mich da mal reingefuxt.
Am meisten Zeit hat mich die Nachbearbeitung gekostet um vernünftige Variablennamen zu verwenden, die die Gnade von __blackjack__ bekommen :lol:
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: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

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: 1631
Registriert: Samstag 16. April 2011, 12:47

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: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@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: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

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