Advent of Code

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

BlackJack hat geschrieben:@kbr: Naja, das liegt ja eher nicht an der Sprache BASIC an sich, sondern an den Implementierungen für die 8-Bit-Rechner damals. Die Beschränkung auf maximal zwei signifikante Zeichen bei Variablennamen, kein ELSE, kein BREAK, kein WHILE oder UNTIL, alles ein globales Programm ohne Funktionen oder benannte Unterprogramme, der langsame Interpreter und nur 40×25 Zeichen auf dem Bildschirm, …
... und zudem jede Menge GOTOs. Im Kontext bezog ich mich auch auf das C64 Basic, jedenfalls was meine Programme anging. Nach dem C64 habe ich Basic dann nicht mehr verwendet. Im Sinne von Jack Reacher: "Never go back" ... 8)
BlackJack

@kbr: Die vielen GOTOs (und GOSUBs) sind ja eine direkte Folge der Einschränkungen von: kein ELSE, BREAK, WHILE, UNTIL, und keine benannten Funktionen. Es gab ja auch BASIC-Erweiterungen die so etwas zur Verfügung gestellt haben. Simons BASIC zum Beispiel hatte so einiges davon. Leider sind die Programme dadurch eher langsamer geworden.

So sieht das dann in QBasic aus wenn man noch eigene Datentypen und benannte Unterprogramme und Funktionen dazu nimmt:
[codebox=qbasic file=Unbenannt.txt]CONST AscA=ASC("a")

TYPE RoomType
name AS STRING
sectorID AS INTEGER
checksum AS STRING*5
END TYPE

TYPE HistogramType
count(25) AS INTEGER
letter(25) AS INTEGER
END TYPE


SUB ParseRoom(room AS RoomType, s AS STRING)
i=INSTR(s, ANY "0123456789")
room.name=MID$(s,1,i-2)
room.sectorID=VAL(MID$(s,i))
room.checksum=MID$(s,LEN(s)-5,5)
END SUB


SUB InitHistogram(histogram AS HistogramType)
FOR i=0 TO 25
histogram.count(i)=0
histogram.letter(i)=i
NEXT
END SUB


SUB CountLetters(histogram AS HistogramType, s AS STRING)
FOR i=1 TO LEN(s)
c$=MID$(s,i,1)
IF c$<>"-" THEN
c=ASC(c$)-AscA
histogram.count(c)=histogram.count(c)+1
END IF
NEXT
END SUB


SUB SortHistogram(histogram AS HistogramType)
DO
swapHappend=0
FOR i=0 TO 24
x=histogram.count(histogram.letter(i))
y=histogram.count(histogram.letter(i+1))
IF x<y OR (x=y AND histogram.letter(i)>histogram.letter(i+1)) THEN
t=histogram.letter(i)
histogram.letter(i)=histogram.letter(i+1)
histogram.letter(i+1)=t
swapHappend=1
END IF
NEXT
LOOP WHILE swapHappend
END SUB


FUNCTION IsValid(room AS RoomType)
DIM histogram AS HistogramType

InitHistogram histogram
CountLetters histogram,room.name
SortHistogram histogram

checksum$=""
FOR i=0 TO 4
checksum$=checksum$+CHR$(histogram.letter(i)+AscA)
NEXT

IsValid=checksum$=room.checksum
END FUNCTION


FUNCTION DecodeName$(room AS RoomType)
name$=""
FOR i=1 TO LEN(room.name)
c$=MID$(room.name,i,1)
IF c$="-" THEN
c$=" "
ELSE
c$=CHR$((ASC(c$)-AscA+room.sectorID) MOD 26+AscA)
END IF
name$=name$+c$
NEXT
DecodeName$=name$
END FUNCTION


DIM room AS RoomType, northPoleRoom AS RoomType
sum=0
northPoleRoom.sectorID=-1

inFile=FreeFile
OPEN "input.txt" FOR INPUT AS #inFile
WHILE NOT EOF(inFile)
LINE INPUT #inFile,line$
ParseRoom room,line$
IF IsValid(room) THEN
sum=sum+room.sectorID
IF INSTR(DecodeName(room),"north") THEN northPoleRoom=room
END IF
WEND
CLOSE #inFile

PRINT sum,"North Pole stuff is in sector:";northPoleRoom.sectorID[/code]
Das könnte man dann schon fast als lesbar bezeichnen. :-) Da hat sich ein Microsoft so ein bisschen in Richtung Pascal bewegt. Was dann auch meine nächste Programmiersprache auf dem PC war.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

BlackJack hat geschrieben:@kbr: Die vielen GOTOs (und GOSUBs) sind ja eine direkte Folge der Einschränkungen von: kein ELSE, BREAK, WHILE, UNTIL, und keine benannten Funktionen.
Ja klar, ich wollte auch nichts anderes behaupten.
BlackJack hat geschrieben:Da hat sich ein Microsoft so ein bisschen in Richtung Pascal bewegt. Was dann auch meine nächste Programmiersprache auf dem PC war.
Bei mir ebenso, Turbo Pascal 2 oder 3; das weiß ich gar nicht mehr so genau :)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Für die heutige Aufgabe will mir noch kein passender Lösungsansatz einfallen. Meine Ausgangsidee war, dass die Aufgabenstellung Ähnlichkeiten mit den Türmen von Hanoi hat und man Algorithmen dafür adaptieren könnte. Allerdings hat diese Variante ja deutlich mehr Zusatzbedingungen, die das Ganze komplexer machen. Bin ich grundsätzlich auf dem richtigen Weg? Gibt es vielleicht etwas anderes, was man sich zur Inspiration ansehen könnte?
BlackJack

@nezzcarth: Alte Informatikerweisheit: Man kann fast jedes Problem als Graphenproblem ausdrücken. :-) Ich musste spontan an das Ziege, Kohlkopf, Wolf-Rätsel denken. Ich denke das hat dazu mehr Ähnlichkeit als zu den Türmen von Hanoi.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

BlackJack hat geschrieben:@nezzcarth: Alte Informatikerweisheit: Man kann fast jedes Problem als Graphenproblem ausdrücken. :-) Ich musste spontan an das Ziege, Kohlkopf, Wolf-Rätsel denken. Ich denke das hat dazu mehr Ähnlichkeit als zu den Türmen von Hanoi.
Stimmt, diese Rätsel hatte ich ganz vergessen; die sind natürlich noch näher dran, als die Türme von Hanoi. Tatsächlich nennt der Autor der Rätsel ein vergleichbares als Referenz und der deutschsprachige Wikipedia-Artikel zu diesem Rätseltyp schlägt eine graphen-basierte Lösung vor. Mal sehen… :)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Wie ist eure Zwischenbilanz bislang so? Ich war anfangs ganz gut dabei, nach Tag Zehn fehlen mir inzwischen 5½ Tage; mal sehen, was ich noch aufholen kann. Sagen euch die Aufgaben zu? Es sind gefühlt immer dieselben paar Aufgaben-Typen (Maximum/Minmum von etwas bestimmen, Eingaben nach Mustern durchsuchen, einen Interpreter für eine Mini-DSL schreiben) aber sind für mich ausreichend interessant. Was mich tatsächlich ein bisschen stört, ist dass die Lösungen, die man im Netz findet sehr auf schnellen und trickreichen Einsatz der verwendeten Programmiersprache ausgelegt sind, was unmittelbar mit der Leaderboard-Mechanik zusammenhängt; insb. die Pythonlösungen sind für meinen Geschmack oftmals eher unschön.
BlackJack

@nezzcarth: Die Ranglisten sind für'n A****. Ich denke was da hauptsächlich zählt ist in welcher Zeitzone man lebt, oder zumindest an welche man seinen Tages-/Nachtrhythmus angepasst hat. Wobei wir es hier in Mitteleuropa ja gar nicht so schlecht getroffen haben. Ich glaube das neue Rätsel kommt so gegen 6 Uhr morgens raus. Und die ersten 1000 richtigen Lösungen bekommen Punkte beziehungsweise in der Reihenfolge der Lösungsabgabe in die Rangliste.

Am 11. und heute fehlt mir noch der zweite Stern und 14, 15, und 19 habe ich noch nicht gelöst. Ich schaue mich eigentlich nicht woanders um, also die Diskussionen und Lösungen bei Reddit gehen an mir vorbei. Aus Zeitgründen kommt hier mittlerweile Python zum Einsatz, also nicht mehr der C64 mit BASIC und Compiler dafür. :-) Ob die Python-Lösungen schön sind, die ich dafür ”verbreche” weiss ich nicht. Es geht ja primär um die Lösung der Probleme und nicht saubere Programme zu schreiben die lange im Einsatz sind. Wobei es sich doch manchmal lohnt gleich für die erste Aufgabe eine abstraktere Lösung zu schreiben, weil man ab und zu vom zweiten Aufgabenteil dazu gezwungen wird, die Lösung für den ersten Teil etwas generischer zu gestalten. Für den 21. hatte ich beispielsweise je eine Funktion pro Operation, die ich dann für den zweiten Teil für die Umkehrfunktionen dann doch zu Klassen gemacht habe. Und da bin ich dann heute morgen vor der Arbeit bei Umkehrung irgendwo falsch abgebogen und musste abbrechen. Und abends war dann Firmenweihnachtsfeier, deshalb habe ich da nicht mehr weiter gemacht.

Ich habe übrigens gerade festgestellt das ich mal besser auf die ASCII-Grafik auf der Indexseite geachtet hätte. Da unten wo jetzt die Tanne steht war am Anfang noch ein leerer Parkplatz. Wer weiss was ich da zwischenzeitlich verpasst habe. :-)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

@BlackJack:
Ja, die Ranglisten sind auch nicht mein Fall -- für viele andere aber scheinbar ein großer Teil des Spaßes. Und ich finde, sie führen teilweise zu "unschönem" Code. Zwar müssen es keine solide durchgeplanten Programme mit Tests usw. sein, aber ich finde, auch bei solchen Aufgaben kann es sinnvoll sein, sich an gängige Konventionen der verwendeten Programmiersprache zu handeln (bei Python also z. B. PEP 8 inkl. Vermeidung von *-Importen, Verzicht auf globale Variablen usw.). Ich schaue mir nachdem ich eine Lösung gefunden habe gerne an, wie andere das gelöst haben. Und zumindest auf Reddit sehen die Lösungen nicht selten eher nach Quick and Dirty und/oder Code-Golf aus.

Mir fehlen noch Tag 11, 13, 17, 19, 21.2, 22-25. Mal sehen, was ich bis Ende des Jahres noch schaffe ;) Bei 21.2 -- was du ja gerade angesprochen hast -- überlege ich noch, wie ich die Umkehrung gut realisieren kann; "reverse positions X through Y" ist, glaube ich, doch nicht umkehrbar...
Die Änderungen an der ASCII-Grafik waren mir gar nicht aufgefallen, danke für den Hinweis ;)
BlackJack

Mir fehlen noch 11.2, 14, 15, 19, 21.2, 22.2, 24, und 25.

Bei „reverse X through Y“ ist das doch selbst schon die Umkehrfunktion. 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.
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.
Antworten