Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
BlackJack

Dienstag 15. Dezember 2015, 00:09

Unter http://adventofcode.com/ gibt's einen Adventskalender mit einem Rätsel/Puzzle für Programmierer für jeden Tag bis Weihnachten. :-)
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Samstag 19. Dezember 2015, 14:16

Interessant, danke für den Tipp :)
Mich würden ja insb. verschiedene Lösungsansätze in Python interessieren. Können die hier diskutiert werden, oder lieber erst später?
BlackJack

Samstag 19. Dezember 2015, 14:25

@nezzcarth: Ich habe bis jetzt alles bis Tag 17 ausser Tag 15 gelöst. Eigentlich immer ziemlich plump, wenn ich ehrlich bin. Also eher „brute force“ als nachdenken, wenn's die Wahl gab. :-)

Wenn Du über irgendeinen Tag diskutieren möchtest, dann mach am besten im „Allgemeine Fragen“-Unterforum einen Beitrag auf mit einem entsprechenden Betreff „AoC - Tag X“ mit X = dem Tag/der Nummer des Puzzles. Es gibt ja offiziell eine Diskussion auf Reddit. Da sind auch mindestens zwei Github-Repositories verlinkt die Lösungen sammeln. Gegen eine öffentliche Diskussion hier sollte also eigentlich nichts sprechen.

Es bekommt übrigens nicht jeder bei jedem Puzzle die gleichen Daten! :-)
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Samstag 19. Dezember 2015, 16:10

BlackJack hat geschrieben:@nezzcarth: Ich habe bis jetzt alles bis Tag 17 ausser Tag 15 gelöst. Eigentlich immer ziemlich plump, wenn ich ehrlich bin. Also eher „brute force“ als nachdenken, wenn's die Wahl gab. :-)
Okay, das klingt so, als würde es mit der Zeit etwas langweilig? Bin erst bei 4b und bisher macht es Spaß :) Hatte das bisher meist etwas umfangreicher programmiert, als es sein müsste, zu Übungszwecken. Aufgabe 4 (Zahl finden, die gemeinsam mit einem festen String einen md5 Hash nach einem bestimmten Muster hat) ist die erste, die ich tatsächlich mit Brute Force löse. Ginge das eigentlich auch anders?
Wenn Du über irgendeinen Tag diskutieren möchtest, dann mach am besten im „Allgemeine Fragen“-Unterforum einen Beitrag auf mit einem entsprechenden Betreff „AoC - Tag X“ mit X = dem Tag/der Nummer des Puzzles. Es gibt ja offiziell eine Diskussion auf Reddit. Da sind auch mindestens zwei Github-Repositories verlinkt die Lösungen sammeln. Gegen eine öffentliche Diskussion hier sollte also eigentlich nichts sprechen.
Konkreter Diskussionsbedarf besteht nicht; mich würde einfach nur interessieren, wie man es noch lösen kann. Aber dann schaue ich einfach mal, was sich bei Reddit/Github so findet.
Es bekommt übrigens nicht jeder bei jedem Puzzle die gleichen Daten! :-)
Danke für den Hinweis.
BlackJack

Samstag 19. Dezember 2015, 16:59

@nezzcarth: Die Tage 1 bis 3 haben ja auch noch nichts was man mit roher Gewalt durchprobieren müsste. Da kann man ja einfach nach den vorgegebenen Regeln das Ergebnis ausrechnen.

Tag 4 muss man durchprobieren. Es sei denn wir haben auf magische Weise passende „rainbow tables“ vorliegen. Aber die müsste ja auch vorher jemand mal berechnet haben. :-)

Auch wenn Du Alternativen zu Deinen Lösungen oder Anmerkungen zu bekommen, kannst Du ja ein Thema dafür starten.
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Montag 21. Dezember 2015, 23:02

Ist bei Tag 7 Rekursion auch für Python die eleganteste Lösung, oder gibt es da eine äquivalente Alternative?
BlackJack

Dienstag 22. Dezember 2015, 00:38

@nezzcarth: Man könnte wiederholt alle Ausdrücke auswerten bei denen die beteiligten Operanden aus Zahlen/bereits ausgewerten Variablen bestehen, solange bis alles ausgewertet ist. Was jetzt nicht wirklich elegant ist, aber simpel ist und mit wenig Stapelspeicher auskommt. Oder man sortiert die Ausdrücke topologisch nach Variablenabhängigkeiten und wertet dann einfach der Reihe nach aus. Eleganter, aber durch den Sortieralgorithmus etwas aufwändiger als einfach rekursiv auszuwerten.

Kleiner Tipp zum rekursiv auswerten (habe ich gemacht, war das naheliegendste): Die Ergebnisse der Variablen cachen sobald sie berechnet sind, sonst dauert das eeeewig. :-)

Ich bin heute (Blick auf die Uhr) äh, gestern endlich mit allen Tagen von 1 bis 21 fertig geworden. Momentan sitze ich an Tag 6 in C mit der Einschränkung, dass das am Ende auf einem C64 laufen soll. Also mit unter 64 KiB Speicher für Programm und Daten. Da bekommt man nicht einmal die eine Million Lampen aus Aufgabenteil A gleichzeitig im Arbeitsspeicher abgebildet wenn man nur ein Bit pro Lampe verwendet. Habe dafür aber schon einen Lösungsansatz. :-)
DasIch
User
Beiträge: 2448
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 22. Dezember 2015, 09:56

nezzcarth hat geschrieben:Ist bei Tag 7 Rekursion auch für Python die eleganteste Lösung, oder gibt es da eine äquivalente Alternative?
Es gibt Alternativen die vielleicht eleganter sind. Rekursion ist aber meiner Meinung nach am einfachsten zu Verstehen und mit Memoization so schnell, dass du mit anderen Ansätzen wohl kaum spürbar schneller wird.
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Dienstag 22. Dezember 2015, 20:44

Okay, ich denke, dann werde ich einfach mal beide Ansätze versuchen :) Danke für die Tipps. Dass ich bis zum 25. fertig werde, ist ohnehin nicht mehr aufhole.

(Möglicherweise reicht aber auch ein Fortran-Compiler?

Code: Alles auswählen

$ file day7.txt 
day7.txt: FORTRAN program, ASCII text
;)
)

@BlackJack: So aus Neugier, wie verwendet man mehr Speicher, als man hat? Zwischenspeichern, irgendwie in Blöcke aufteilen?
BlackJack

Mittwoch 23. Dezember 2015, 01:52

@nezzcarth: Nette Idee mit dem FORTRAN-Compiler, aber leider:

Code: Alles auswählen

$ gfortran input.txt 
/usr/bin/ld:input.txt: file format not recognized; treating as linker script
/usr/bin/ld:input.txt:1: syntax error
:-)

Zwischenspeichern ist bei der üblichen Massenspeicherlösung, einem 1541-Laufwerk, für 1 Million Bitwerte zwar möglich — eine Diskettenseite fasst ca. 170 KiB und man braucht nur 122 KiB für eine entsprechende Bitmap — aber spätestens beim Aufgabenteil B reicht das nicht mehr. Da könnte man dann höchstens die ausgelagerten Teile komprimieren und hoffen dass der Platz dann ausreicht. Die ”Geschwindigkeit” des Laufwerks wäre aber auch für Teil A schon ein KO-Kriterium.

Teil A könnte ich noch mit der 2 MiB „RAM Extension Unit“ (REU) lösen die heute in meinem C64 steckt, aber bei Teil B würde auch das nicht reichen. Eine 16 MiB REU könnte ich gerade noch so im Emulator verwenden, aber AFAIK gab es die damals nie in echt, das ist nur die Obergrenze die man mit der Technik hätte adressieren können. Das wäre wohl auch ein ziemlich grosser Kasten geworden der extra Strom benötigt hätte. Die originalen 512 KiB REUs von Commodore hatten am C64 teilweise schon Probleme mit dessen normaler Stromversorgung (die waren eigentlich für den C128 gedacht). Das 2 MiB-Modul ist ein Nachbau einer anderen Firma, das kleiner ist (normale Steckmodulform) und anscheinend weniger Strom verbraucht.

Also meine Idee war die Instruktionen zu parsen und dann jede Zeile einzeln zu berechnen in dem ich schaue welche Instruktionen sich auf die jeweils aktuell berechnete Zeile beziehen. Im Grunde recht einfach und naheliegend.
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Donnerstag 1. Dezember 2016, 22:39

BlackJack hat geschrieben:Unter http://adventofcode.com/ gibt's einen Adventskalender mit einem Rätsel/Puzzle für Programmierer für jeden Tag bis Weihnachten. :-)
Gibt's übrigens dieses Jahr wieder -- falls wer Interesse an Rätseln hat. Fand ich letztes Jahr ganz nett.
BlackJack

Montag 5. Dezember 2016, 11:25

Verdammt, der erste Tag dieses Jahr bei dem ich die Lösung nicht für den C64 programmiert habe. :-)
nezzcarth
User
Beiträge: 488
Registriert: Samstag 16. April 2011, 12:47

Montag 5. Dezember 2016, 20:07

BlackJack hat geschrieben:Verdammt, der erste Tag dieses Jahr bei dem ich die Lösung nicht für den C64 programmiert habe. :-)
Auf Reddit wurde für die heutige Aufgabe (insb. Teil 2) ja recht schnell die B-Note "möglichst Hacker-Film-artigen Output erzeugen" eingeführt. Ich glaube, da würde der C64 eine gute Figur machen ;)
BlackJack

Montag 5. Dezember 2016, 20:31

@nezzcarth: So eine Ausgabe ist kein Problem, aber das berechnen von mehreren Millionen MD5-Hashwerten könnte auf dem C64 länger dauern als der Adventskalender läuft. ;-)
DasIch
User
Beiträge: 2448
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Montag 5. Dezember 2016, 20:46

Sollte man nicht eigentlich jede Challenge in einer anderen Sprache lösen?
Antworten