Advent of Code

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

Dienstag 27. Dezember 2016, 11:36

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

Dienstag 27. Dezember 2016, 12:55

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

Freitag 1. Dezember 2017, 08:41

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

Dienstag 5. Dezember 2017, 10:49

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: 1585
Registriert: Samstag 2. Juni 2018, 10:21

Donnerstag 29. November 2018, 09:52

Und auch dieses Jahr gibt's den Adventskalender für Programmierer wieder. *<:-)

Code: Alles auswählen

    **** COMMODORE 64 BASIC V2 ****
 64K RAM SYSTEM  38911 BASIC BYTES FREE
   CYBERPUNX RETRO REPLAY 64KB - 3.8P
READY.
█
Benutzeravatar
sls
User
Beiträge: 286
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Tannhauser Gate

Freitag 30. November 2018, 08:21

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:

*<{:-)
With great processing power comes great responsibility.
Benutzeravatar
__blackjack__
User
Beiträge: 1585
Registriert: Samstag 2. Juni 2018, 10:21

Freitag 30. November 2018, 12:07

@sls: Das passiert wenn man zu viel in einer Programmiersprache arbeitet die zu wenige geschweifte Klammern in der Syntax hat. :-D

Code: Alles auswählen

    **** COMMODORE 64 BASIC V2 ****
 64K RAM SYSTEM  38911 BASIC BYTES FREE
   CYBERPUNX RETRO REPLAY 64KB - 3.8P
READY.
█
nezzcarth
User
Beiträge: 586
Registriert: Samstag 16. April 2011, 12:47

Samstag 1. Dezember 2018, 08:30

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

Samstag 1. Dezember 2018, 13:26

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:
        ...
With great processing power comes great responsibility.
Benutzeravatar
kbr
User
Beiträge: 957
Registriert: Mittwoch 15. Oktober 2008, 09:27

Samstag 1. Dezember 2018, 13:43

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

Samstag 1. Dezember 2018, 13:50

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: 1585
Registriert: Samstag 2. Juni 2018, 10:21

Samstag 1. Dezember 2018, 13:51

@sls: Also ich habe `itertools.cycle()` statt der zwei Schleifen verwendet, aber das kommt von der Komplexität letztlich auf das gleiche heraus.

Code: Alles auswählen

    **** COMMODORE 64 BASIC V2 ****
 64K RAM SYSTEM  38911 BASIC BYTES FREE
   CYBERPUNX RETRO REPLAY 64KB - 3.8P
READY.
█
Benutzeravatar
sls
User
Beiträge: 286
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Tannhauser Gate

Sonntag 2. Dezember 2018, 12:05

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)
With great processing power comes great responsibility.
Benutzeravatar
sls
User
Beiträge: 286
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Tannhauser Gate

Sonntag 2. Dezember 2018, 14:03

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.
With great processing power comes great responsibility.
Benutzeravatar
ThomasL
User
Beiträge: 421
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Sonntag 2. Dezember 2018, 14:40

sls hat geschrieben:
Sonntag 2. Dezember 2018, 14:03
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.
"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."
Antworten