Stranger Than Usual

Ich war seit 2015 jedes Jahr auf dem Chaos Communication Congress. Sofern der statgefunden hat, es gab da drei magere Jahre wegen der COVID-19-Pandemie. Letztes Jahr war ich auf auf dem alle vier Jahre stattfindenden Chaos Communication Camp (ich habe dazu auch gelegentlich etwas geschrieben, über die Tags am Ende des Artikels sollte das auffindbar sein).

Ich habe mir bisher jedes Jahr Notizen gemacht, zu vielem was ich dort interessant fand. Die meisten Notizen habe ich hinterher nicht mehr gelesen, das war so ein bisschen wie mit Spickzetteln: Alleine dass man es aufgeschrieben hat sorgt dafür, dass man sich besser erinnern kann. Ein paar dieser Notizdateien habe ich heute noch irgendwo herumfliegen.

Dieses Jahr ist der 38C3, und ich habe es mit Müh und Not geschafft, ein Ticket zu bekommen. Es geht also wieder los. Und da mir gestern noch einmal eine der Notizdateien von vergangenen Congressen aufgefallen ist, dachte ich mir, ich schreibe hier einfach mal, was da so drin stand. Leider habe ich nocht alle Dateien gefunden, und ich erinnere mich auch, manche dieser Dateien bearbeitet zu haben (i.d.R. weil es eine Art ToDo war und ich das abgehakt hatte). Personenbezogene Daten schreibe ich hier natürlich auch nicht hin. Als Bonus gibt es aber zu den Congressnotizen auch Notizen vom Chaos Communication Camp letztes Jahr.

In allen Fällen kann es sein, dass ich über die Sachen in diesem Blog schon einmal geschrieben habe. Dann wiederhole ich mich halt. Der Inhalt hier ist auch wild durcheinandergewürfelt, wer einen gut geschriebenen Artikel möchte, sollte diesen hier nicht lesen.

33C3

Von meinem ersten Congress, dem 32C3, habe ich leider keine Notizen mehr gefunden. Vielleicht sind die noch irgendwo, aber nicht da, wo ich gesucht habe. Also direkt zum 33C3. Die Notizen sind meist Stichpunkte, weil ich sie schnell auf einem Smartphone geschrieben habe. Ihr kriegt die Version mit etwas Interpretation meines heutigen Ichs:

• „kein Spiel“: Hier ging es darum, dass es auf dem 33C3 kein Spiel gab. Ich bin ständig Leuten begegnet, die herumgelaufen sind und es nicht gespielt haben. Ich selber habe mich aber nie näher damit beschäftigt, kann also nicht mehr dazu sagen
• anscheinend war mir das Matrix-Protokoll damals neu, ich hatte mir das aufgeschrieben, um mich damit auseinanderzusetzen. Der 38C3 hat übrigens auch einen Matrix-Chat
• „löten“: Ich wollte mich mal wieder mehr mit Elektronik beschäftigen, oder einfach auf dem Kongress etwas zusammenlöten
• „n26“: Es gab einen Vortrag zu Sicherheitslücken bei N26, einer reinen Online-Bank
• fairSIM, ein Projekt zu freien Algorithmen und anderen Resourcen zu Structured Illumination Microscopy. Davon habe ich wohl in einem Vortrag, möglicherweise auch in einem lightning talk gehört und fand es cool.
• greenlightformakers.org
• „feinstaubmessung“, ich glaube, da ging es um förderierte Feinstaubmessungen, möglicherweise luftdaten.info
• „attraktor hamburg“, ein Makerspace in Hamburg. Ich wollte mir das mal anschauen. Ich habe siebeneinhalb in Hamburg gelebt und habe das nie durchgezogen. Ich erinnere mich, dass die an der Assembly des Attraktors eine Live-Cam von einem Ameisennest in irgendeinem Blumenkübel hatten.
• spresso.me, ein dezentraler, datenschutzfreundlicher single sign-on. Hauptproblem bis heute: fast keine Seite, bei der man sich mit SSO einloggen kann, unterstützt das.
• „http referrer“ – keine Ahnung, warum ich das aufgeschrieben habe. Vermutlich, um mal Datenschutzkrams zu checken
• ein paar Links zu Seiten, die jetzt tot sind und ich habe keine Ahnung mehr, was das war
• einen Raspberry Pi mit Power over Ethernet betreiben
• „ingenico coupon security“ – vermutlich habe ich von irgendwelchen Sicherheitsproblemen mit Gutscheinen oder bei Ingenico gehört. Da unser Kunde auch Ingenico-Geschenkkarten benutzt, wollte ich da wohl was überprüfen
• Maker Faire Ruhr. Ich bin nie da hingegangen
• ich wollte mir mal die Food Hacking Base-Assembly anschauen
• nach einem Vortrag (oder lightning talk) wollte ich mir mal wieder das von der Anno-Reihe inspirierte Spiel Unknown Horizons anschauen
• dasselbe gilt für openage, nur kann ich mich hier noch an Fetzen des Talks erinnern, es ging um das Format, indem sie Daten abgelegt haben so dass das Spiel gut modifizierbar ist. Heute wird openage auf der Website nicht mehr als von Age of Empires inspiriertes Spiel präsentiert, sondern als „cross-platform RTS game engine that provides the mechanics of Age of Empires“. Scheint, als wären sie noch mehr in die Richtung von „gut modifizierbar“ gegangen.
• tomu.im „a group of tiny boards designed to fit inside your USB port“. Daran erinnere ich mich überhaupt nicht mehr, aber ich verstehe, warum ich mir das aufgeschrieben habe
• keyless klau, über unsichere elektronische Schließsysteme, speziell Keyless-Go/Keyless-Entry bei Autos
• Techniktagebuch, ein Blog, dass ich mir noch anschauen muss.
• ein Twitter-Benutzername. Bei der Shitshow, die Musk aus Twitter gemacht hat, traue ich mich nicht, nachzuschauen (ohne Login kriegt man sowieso nicht mehr viel angezeigt)
• „datassette“ – vermutlich steckte dahinter mehr als nur ein plötzliches Interesse an diesem archaischen Speichermedium
• lisamission.org LISA: „Laser Interferometer Space Antenna“. Auf dem 33C3 gab es eine Menge Astronomie- und Raumfahrttalks
• „Michael Büker (Buch)“ Der Typ ist Wissenschaftskommunikator, ich glaube, ich habe nie eins der Bücher gelesen
• Damals war gerade meine Leidenschaft für rust entflammt, und Dropbox hatte gerade berichtet, gute Erfahrungen mit rust gemacht zu haben
• neveragain.tech, eine Absichtserklärung von Angestellten von US-Technikunternehmen, ihre Unternehmen dazu zu bringen, Datensparsam zu betreiben, insbesondere im Rückblick auf die Tatsache, dass IBM mit ihren Lochkartenmaschinen geholfen haben, den Holocaust zu organisieren

34C3

Uff… so viele Erinnerungen, so viele interessante Dinge, die ich nie weiter verfolgt habe… Naja, die Notizen vom 34C3 sind, glücklicherweise oder unglücklicherweise, deutlich kürzer

• Der Lizenzhinweisgenerator, um korrekte Lizenzhinweise für CC-lizensierte Inhalte von Wikipedia zu erzeugen
• ein Hinweis zu interessanter eInk-Technik (mittlerweile veraltet)
• „ipfs“ „Interplanetary File System“, in dem Jahr hatte die katalanische Piratenpartei das genutzt, um gesperrte Websites zum katalanischen Unabhängigkeitsreferendum online zu halten
• Borg Backup, damals war ich auf der Suche nach einem brauchbaren Backup-Tool
• Telefonnummern (Congressintern) und Matrix-Adressen von Freunden und Bekannten auf dem Congress
• PrivacyScore, ein Tool, um Datenschutz auf Websites abzuschätzen. Das Projekt sieht zuemlich tot aus, seit Jahren (seit 2018) ist nichts daran passiert
• ein Hinweis auf das Buch „Dinge geregelt kriegen - ohne einen Funken Selbstdisziplin“ von Kathrin Passig und Sascha Lobo
• eine Erinnerung, dass ich endlich meinen Freifunkrouter aufstellen muss, der seit Jahren in meiner Wohnung Staub sammelt

Chaos Communication Camp 2023

Für den 35C3 und den 36C3 habe ich keine Notizen gefunden. Also springen wir fünfeinhalb nach vorne, zum Chaos Communication Camp. Hier weiß ich, dass ich ein paar erledigte Sachen gelöscht habe, aber ich habe ja auch schon mehrere Artikel über das Camp geschrieben.

• Dect-Nummern von Freunden und Bekannten
• basebanana.org, benutzt „banana words“ (Wörter, in denen alle Silben aus einem Konsonanten und einem Vokal bestehen, so wie „Banane“) um Nummern, Zahlen oder ähnlich schwierig zu merkende Daten in ein einfach auszusprechendes Wort zu übersetzen (und zurück). Ich wollte das mal in Rust implementieren, bin aber bisher noch nicht dazu gekommen.
• Notizen zu lightng talks, die ich nicht mehr einordnen kann
• Open Steno Project, ein Projekt, Stenografie freier und zugänglicher zu machen
• StopDataPorn, eine Initiative, Daten über sexuelle Vorlieben von Internetnutzern besser zu schützen
• ich hatte zwei Mal das Wort „hanggliding“ ohne Kontext und habe keine Ahnung, was ich damit gemeint habe
• ein lightning talk über bug bounty triage, eine Hackerin, die gemeldete Bugs überprüfen muss, ob sie einer Bug Bounty würdig sind
• Datenschutzmythen
• „chatkontrolle“
• Notizen von einem Workshop zu Pen & Paper-Rollenspiel-Sicherheit bei den Haecksen, wenn ich das richtig verstanden habe ist die Haeckse, die den Workshop gemacht hat, auch am Podcast „Plus 1 auf Podcast“ beteiligt. In den Podcast muss ich einmal reinhören
• Notizen zu den Hackern, die bei Chaos West die Anstecker gemacht haben, vermutlich, damit ich ihnen eine Karte per Chaospost schicken konnte
• Verweis auf einen WLAN-Ausfall (oder Netzwerkausfall allgemein?) gegen 21:00 Uhr an Tag 4. Am nächsten Tag stellte sich heraus, dass die Italian Hacker Embassy dafür verantwortlich war
• Tipps vom LaTeX-Helpdesk zu meinem persistenten Problem, dass ich keine vollständige Unicode-Unterstützung in LaTeX kriege. Hinweis: Mit spezieller Schriftart müsste das gehen, bei luatex eigentlich sogar out of the box

37C3

• Links zur Euclid-Mission
• vermutlich nach einem Talk zum Extremely Large Telescope (hieß früher „European Extremely Large Telescope“, bis jemandem aufgefallen ist, dass es nicht in Europa steht sondern in Südamerika): Der Hinweis, dass die Leute von dem Talk bei der SFT Assembly zu finden seien. Ich kann mich nicht erinnern, mit ihnen gesprochen zu haben, vermutlich habe ich sie nicht gefunden
• „kill your phone workshop“, wo man sich eine Abschirmung für sein Smartphone zusammennähen kann. Nicht gegen irgendwelchen geschwurbelten Elektrosmog, sondern als Privacy-Tool
• Stichworte, mit denen ich nichts mehr anfangen kann (wie immer)
• meine Dect-Telefonnummer
• Stichpunkte aus den lightning talks, darunter
  • InvenTree, eine OpenSource Inventar-Management-Software für Firmen und Privatanwender
  • saildart.org
  • Pocket Science Lab, ein Sammelsurium von Messgeräten auf einem Board, kann mit Smartphones verbunden werden, mit normalen Computern und die neueste Version kann auch ohne Verbindung Daten sammeln, um sie dann später abzufragen. Entwickelt von FOSSASIA. Klingt cool, ich will mir noch eins besorgen, das neue Modell konnte man damals aber noch nicht bestellen
  • Nationale Forschungsdateninfrastruktur](https://www.nfdi.de/)
  • „task tracker systems“, vermutlich jemand, der über task tracker geredet hat?
  • FIM, ein image viewer, der mit sehr verschiedenen Outputs arbeiten kann
  • analog computer
  • Das @all-Kollectiv
  • lernOS
  • der Schlüsseltechnologie-Podcast
• ein Haufen ToDos, teils für den Congress, teils für die Zeit danach, die ich mittlerweile größtenteils abgearbeitet habe, darunter auch ein Verweis auf den Ultimate Gameboy Talk vom 33C3, den ich zufälligerweise unabhängig davon vor Kurzem endlich angeschaut habe.
• Digitaldruide, eine Parodie auf Esoterik-Shoppingseiten, die bieten z.B. Code-Segnungszertifikate an. Dazu gab es eine Menge Aushänge auf dem Congress
• und eine ToDo-Liste, was ich für den nächsten Congress vorbereiten muss. Ganz oben steht natürlich Pixelflut

Es ist wieder Advent of Code. Das heißt 25 Tage jeden Tag ein Programmierpuzzle während man Santas Elfen dabei zusieht, die Dinge auf eine etwas… eigene Art zu erledigen.

Nachdem man in den letzten Jahren Schnee machen, den Schlüssel von Santas Schlitten vom Meeresgrund fischen, Rentierfutter besorgen oder Santa vom Rand des Sonnensystems retten musste (und in einem Fall einfach mal Urlaub machen wollte), muss man dieses Jahr Santas Chefhistoriker finden, der sich irgendwo in der Weltgeschichte herumtreibt.

Das erste Puzzle war wie üblich einfach, und üblicherweise steigt die Schwierigkeit im Laufe des Monats im Schnitt an, die Puzzle sind also sowohl etwas für Programmieranfänger als auch für erfahrene Programmierer. Alle Puzzle können mit zehn Jahre alter Hardware in 15 Sekunden lösbar sein. Es gibt also immer eine halbwegs effiziente Lösung.

Man kann die Puzzle in jeder Programmiersprache (und theoritisch auch auf vöölig andere Weise als Programmieren) lösen. Ich schreibe meine Lösungen wir üblich in Rust, meine Lösungen sind wie üblich auf GitHub (falls mich jemand fragt: „Warum GitHub?“, die Antwort ist: Konsistenz. Meine anderen Advent of Code-Lösungen sind halt da. Neuere Projekte packe ich üblicherweise woanders hin).

Es gibt übrigens wie in den letzten Jahren auch Advent of Code-Comics von Gary Grady. Früher hat er die auf Twitter getweeted, mittlerweile ist Grady glücklicherweise auf Mastodon umgestiegen.

Ein Highlight des Advent of Code-Community sind ja Visualisierungen der Puzzle. Bei manchen Puzzlen ist das naheliegender, bei anderen weniger. Manche Visualisierungen sind sehr konkret auf das Problem bezogen (z.B. der Pfad durch einen Irrgarten), andere eher abstrakt (z.B. das Verhalten von Knoten einer Graphendarstellung des Problems). Manchmal kann man den Lösungsweg an der Animation gut sehen, manchmal sieht man einfach nur eine Darstellung der Lösung. Auch der Stil unterscheidet sich erheblich, von bunten Puxeldarstellungen über Sprite-basierte Grafiken bis hin zu 3D-Grafiken.

Heute habe ich jemanden gefunden, der animierte Darstellungen aller bisherigen AoC-Puzzle als GIF-Dateien erstellt hat. Es lohnt, sich das anzuschauen. Viel Spaß!

Die gesamte Politik ist in den letzten Jahren ja nach rechts gerückt. Im verzweifelten Versuch, der AfD Herr zu werden rücken die anderen Parteien, allen voran CDU und CSU immer weiter nach rechts. Die Idee: Die Themen der AfD aufgreifen, damit die Wähler wieder die CDU wählen anstatt der AfD.

Wie Politikwissenschaftler aber immer wieder gezeigt haben: Das funktioniert nicht. Die Wähler denken sich dann: „Oh, vorher wollte ich die AfD nicht wählen, weil sie zu extrem war. Aber die CDU hat die gleichen Themen, also ist das ja nicht extrem. Da kann ich dann ja auch die AfD wählen.“ Oder anders: Rechtsradikalität wird gesellschaftsfähig, da wählen die Leute lieber das Original.

Das hat auch die AfD selber erkannt. Die halten sich für „koalitionsfähig“. Kann jemand das den anderen bitte sagen? Ach warte, denen wurde das schon gesagt.

Ich frage mich, welche von den noch demokratischen Parteien als erste auf Landes- oder Bundesebene umkippt und mit der AfD koaliert. Ich würde ja auf CDU/CSU tippen. Und dann werden einige Leute hier in Deutschland ein böses Erwachen haben, die sich dachten, es wird schon nicht so schlimm mit der AfD. So wie die Trumpwähler, die nach der Wahl gegoogled haben was eigentlich Zölle sind und wie sie die Lebensmittelpreise beeinflussen.

Daniel Stenberg (der Maintainer von curl) hat einen lesenswerten Artikel über International Domain Names (IDN) geschrieben. IDN sind Domainnamen mit Unicode code points außerhalb des ASCII-Bereiches.

Er konzentriert sich in dem Artikel auf Homoglyph-Attacken (er nennt die Homograph-Attacken, ich habe im Netz beide Schreibweisen gefunden) auf URLs. Die Idee dahinter ist, dass man in einer URL unterschiedliche Code Points benutzen kann, die gerendert ähnlich oder gleich aussehen. Eine bekannte Attacke, die von Browsern dadurch abgemildert wird, dass sie Domains mit Zeichen aus unterschiedlichen Sprachen escaped anzeigen, es also offensichtlich ist, dass man nicht auf der Seite ist, auf der man zu sein glaubt.

So weit nichts Neues. Curl hat natürlich keine solche Schutzmechanismen, und Stenberg möchte die Aufmerksamkeit darauf lenken, dass man URLs, die man mit curl aufruft, vorher noch einmal überprüft.

Für mich neu hingegen waren einige der konkreteren Szenarien. So habe ich z.B. gelernt, dass für IDN Zeichen normalisiert werden, also unterschiedliche code points auf ASCII-Zeichen übersetzt werden um die URL zu vereinheitlichen.

Dazu habe ich einige neue code points kennengelernt, deren Nutzen sich mir entzieht. So gibt es zum Beispiel zusätzlich zum regulären Schrägstrich / auch einen Schrägstrich für Brüche ⁄ (U+2044). Oder lateinische Buchstaben, die nur für römische Zahlen gedacht sind.

Letztere haben mich doch sehr verwundert. Das komische an den römischen Zahlen ist schließlich, dass sie die Buchstaben sind. Und dennoch wäre laut Unicode „MMXXIV“ nicht die korrekte Codierung von „2024“. Stattdessen wäre es „ⅯⅯⅩⅩⅣ“. Ich würde spontan behaupten, dass diese speziellen Codepoints für römische Zahlen so gut wie nie verwendet werden. Ich wusste nicht, dass es sie gibt, vermutlich weiß kaum jemand, dass es sie gibt und noch weniger Leute verwenden sie. Selbst der Wikipedia-Artikel zu römischen Zahlen benutzt einfach die ASCII-Zeichen.

Interessant ist es auch, sich den Unicode-Block anzuschauen, in dem die römischen Zahlen stehen. Dort gibt es natürlich die einzelnen Ziffern wie Ⅰ, Ⅴ, Ⅹ, usw, aber die Zahlen von 1 bis 12 haben sogar jeweils einen eigenen Code Point, auch wenn man sie als Kombination der anderen Zahlen schreiben könnte.

Ich frage mich ja, was die Geschichte dahinter ist. Ob die eingeführt wurden, um Kompatibilität zu einem anderen Zeichensatz herzustellen? Oder der Vollständigkeit halber, weil das Zahlen sind und keine Buchstaben und deswegen eigene Code Points verdient haben (ein Schlag ins Gesicht aller, die ihre Probleme mit der Han-Vereinheitlichung haben)? Jedenfalls kann doch niemand erwarten, dass diese Code Points ernsthaft verwendet werden, oder?

Update: Empfehlung des Unicode consortiums

Die Frage, wer zur Hölle denn die spezifischen code points für rmische Zahlen verwendet, hat mir keine Ruhe gelassen. Ich habe noch einmal kurz nachgeschaut. Dabei habe ich diese Stackexchange-Antwort gefunden. Die verweist auf ein Spezifikationsdokument (Abschnitt 22.3, Seite 20 im verlinkten Dokument bzw. Seite 755 in der absoluten Seitenzählung). Kurz: In den meisten Fällen sollte man einfach die ASCII-Zeichen für die rmischen Zahlen verwenden, nur in speziellen Fällen mit ostasiatischem Textlayout sollte man die spezifischen code points verwenden.

Der Programmierpuzzleadventskalender Advent of Code ist für dieses Jahr durch. Dieses Jahr war das zehnte Mal, dass dieser Adventskalender seine Türchen öffnete, und anlässlich dieses Jubiläums ging es in einer rasanten Tour durch Raum und Zeit, um die Orte zu besuchen, die man in den vorherigen Advents of Code schon einmal besucht hat.

SPOILER ALERT: Das hier ist ein Rückblick auf den Advent of Code 2024 und vielleicht auch auf vorherige Advents of Code. Wer sich die Geschichte und die Puzzle nicht spoilern möchte, sollte hier aufhören zu lesen.

Erst einmal ein paar allgemeine Anmerkungen. Wie schon am Anfang des Monats geschrieben musste man dieses Mal Santas Chefhistoriker suchen, der unbedingt bei Santas Schlittenstart zusehen möchte, aber leider gerade nirgendwo zu finden ist. Die Vermutung ist: Er wird sich irgendwo an historisch relevanten Orten herumtreiben (d.h. Orte aus vorherigen Jahren). Deswegen nehmen dich die anderen Historiker mit, um ihn zu suchen.

Was die Puzzle angeht: Ich habe mich an den ersten Tagen erstaunlich schwer mit den Puzzlen getan (sie waren nicht schwer, aber dafür habe ich doch ein paar Probleme gehabt). Auf der anderen Seite habe ich es seit 2020 zum ersten Mal geschafft, alle Puzzle am Tag ihrer Veröffentlichung zu lösen.

Die Community (hauptsächlich auf reddit) war wieder sehr aktiv. Egal, wie sehr ich weiter unten über komische Kommentare auf reddit lästere: Die Community ist hilfsbereit und kreativ, sowohl in den Lösungen als auch in Visualisierungen und Memes. Aufgefallen ist mir, dass es gefühlt weniger Posts mit „Meine Lösung funktioniert für das Beispiel aber nicht für den wirklichen Input“ gab. Es gab sie, aber es waren weniger als letztes Jahr. Auch wieder dabei: eine inoffizielle Erhebung zu den Teilnehmern des AoC.

Während die Historiker den Chefhistoriker suchen hilft man nur in seltenen Fällen dabei, sondern löst meist irgendwelche anderen Probleme, die die Leute vor Ort haben. Am Ende stellt sich heraus: Der Chefhistoriker war die ganze Zeit in seinem Büro und hat gerarbeitet und war ganz am Anfang nur kurz weg, um sich Kaffee zu holen.

Die Puzzle

Meine Lösungen zu den Puzzles

Tag 2: Auf oder Ab

Am zweiten Tag musste man in Teil 1 kurze Zahlenfolge auf bestimmte Eigenschaften überprüfen. In Teil 2 musste man herausfinden, welche ungültigen Zahlenfolgen gültig werden, wenn man genau ein Element entfernt.

Auf reddit eine Menge Leute, die das einfach brute-forced haben. Ich selber habe einen Ansatz gewählt, bei dem ich nur vier Optionen ausprobieren musste. Auf reddit gab es auch ein paar, die es mit drei oder sogar nur zwei Optionen geschafft haben.

Tag 3: Corrupted Memory

An Tag 3 musste man arithmetische Operationen wie mul(9,6) in einem kauderwelsch von korrumpierten Speicher finden. Da ich in rust ohne externe Abhängigkeiten arbeite, konnte ich das nicht mit regulären Audrücken machen, auch wenn es hilfreich gewesen wäre. Schwierig war es aber trotzdem nicht. Auf reddit natürlich Programmieranfänger, die sich in Regexes einlesen.

Tag 5: Absolute Ordnung

Am fünften Tag musste man den Elfen helfen, das Schlittensicherheitshandbuch auszudrucken. Weil die Elfen immer alles etwas komisch machen, sind die Seiten seltsam sortiert. Ich habe erst einmal einen primitiven Ansatz gewählt (Sortierfunktion der Standardbibliothek, mit selbstgeschriebener Vergleichsfunktion, die die komischen Regeln beinhaltet). Hat auf Anhieb funktioniert. Ich hatte auch eine sauberere Lösung im Kopf, aber wie sich herausstellte wäre das keine gute Idee gwesen: Die Seitenreihenfolge ist nämlich nicht absolut. Sie funktioniert nur, weil jede zu sortierende Liste keine widersprüchlichen Kombinationen enthält.

Auf reddit gibt es ein paar Leute, die keine Lust hatten und einfach Bogosort verwendet haben.

Tag 6: Vagabundierende Wachen

Eine kleine Zeitreise. Um ein Paradox zu vermeiden, muss man einer Wache, die sich nach bestimmten Regeln verhält und and Hindernissen immer nach rechts abbiegt, ein zusätzliches Hindernis in den Weg legen, damit sie im Kreis läuft. Meine Brute-Force-Ansatz, einfach alle möglichen Positionen für ein Hindernis (also alle Positionen auf dem normalen Pfad der Wache) auszuprobieren lief in 1.5s durch, also habe ich mir keine Mühe gemacht, das weiter zu optimieren.

Tag 7: Gestohlene Operatoren

Dieses Mal musste man Gleichungen lösen, indem man die richtigen Operatoren einfügt. Die wurden nämlich von Elefanten gestohlen (makes just as much sense in context). Ich habe es wieder brute-forced, und es lief sogar schneller durch als meine brute-force-Lösung vom Vortag. Einzig ein dummer Tippfehler in Teil 2 hat mich Zeit gekostet.

Tag 9: Defragmentieren

Am neunten Tag musste man Flohkrebsen dabei helfen, ihre Festplatte zu defragmentieren. Meine Lösung ist eher unsauber (mir ging es nicht gut an dem Tag), funktioniert aber ohne Probleme. Auf reddit hingegen sind viele Leute darüber gestolpert, dass es Datei IDs größer als 9 gibt, wobei ich nicht einmal verstanden habe, warum das ein Problem ist. Stellt sich heraus: die haben auf Strings gearbeitet da kann jede Speicherzelle und einen code point als ID haben. ASCII-Codepoints reichen aber nicht aus für die Anzahl der Dateien. Anstatt eine ordentliche Lösung zu machen, sind einige Leute auf Unicode-IDs umgestiegen. Ich konnte nicht umhin anzumerken, wie viele Probleme dieser Ansatz bringt. Das war ungefähr auf dem Niveau der „twoneight“-Probleme aus dem letzten Jahr.

Tag 10: Lesen hilft, falsch lesen hilft mehr

Ein Pfadesucheproblem, bei dem man im ersten Teil alle Ziele, die man von einem Startpunkt erreichen kann, ausfindig machen muss. Ich habe es zuerst falsch gelesen und alle Pfade gezählt. Der Bug war leicht behoben. In Teil 2 musste man dann aber alle Pfade Zählen. Der Bug war ebensoleicht unbehoben wie ich ihn vorher behoben habe und ich war in fünf Minuten mit Teil 2 fertig.

Tag 11: You blink, you miss it

An Tag 11 musste man Steine zählen, die sich mit jedem Blinzeln nach bestimmten Regeln verfielfältigen. Exponentiell. Teil 2 war dann wie Teil 1, aber man blinzelte häufiger. Ein klassisches „und jetzt mach das gleiche noch einmal mit dieser riesigen Zahl“-Problem. Mit dynamic programming aber kein Problem.

Tag 12: Zäune ziehen

Dieses Mal musste man den Umfang von Gärten berechnen, damit Zäune gezogen werden können. In Teil zwei dann nicht den Umfang, sondern die Anzahl der Seiten. Meine Lösung ist hässlich und sie zu schreiben war frickelig. Wenn ich, wie einige Leute auf reddit, auf die Idee gekommen wäre dass die Anzahl der Ecken gleich die Anzahl der Kanten ist, wäre es vermutlich schöner geworden.

Tag 13: Lineare Gleichungen

Wieder eins von den Puzzeln, bei denen beim zweiten Teil eine unmöglich große Zahl gefordert wird. Ich habe einfach auf dem Papier eine generelle Lösung für das geforderte Gleichungssystem aufgestellt und die dann in das Programm übertragen. Hat auf Anhieb funktioniert, was mich selber erstaunt hat. Ich war mir sicher, ich hätte mich irgendwo verrechnet.

Tag 14: Weihnachts-Easteregg

Die Historiker müssen auf Toilette und der beste Ort dafür ist aus irgendeinem Grund das Osterhasenhauptquartier. Dort darf man sich als Weihnachtself natürlich nicht erwischen lassen, also musste man die Positionen der Wachroboter voraussagen.

In Teil 2 hat man dann vermutet, dass die Roboter vom Nordpol gestohlen oder kopiert wurden. Dazu musste man ein Easteregg finden (ironischerweise), bei dem sich die Roboter irgendwann in Form eines Tannenbaums gruppieren. Leider kriegt man keine Beschreibung, wie der Tannenbaum aussieht. Ich dachte zunächst, der Tannenbaum würde so aussehen wie der von 2015 und habe überschlagen, dass ich 30 Roboter in einer Reihe erwarten kann, wenn der Tannenbaum zu sehen ist.

Nun, diese Annahme war falsch, weil der Tannenbaum komplett anders aussah. Allerdings hatte er einen Rahmen, der diese Bedingung erfüllte, also war ich gerettet. Auf reddit haben sich viele über die ungenaue Spezifikation beschwert, auf der anderen Seite gab es aber auch eine Menge kreativer Methoden, den Tannenbaum zu finden. Von statistischen Analysen der Varianz der Roboterpositionen über groß angelegte Plots bis hin zu so einfachen Heuristiken wie meiner.

Tag 16: Rentierrennen

Den kürzesten Pfad für ein Rentier in einem Irrgarten finden. Das Besondere: Abbiegen ist viel, viel teurer als geradeaus laufen. Erster Einsatz von Dijkstra dieses Jahr.

Tag 17: Codeanalyse

Wieder eins von diesen Problemen wo man einen eigens erdachten Maschinencode ausführen muss. In Teil zwei musste man dann einen Input finden, der das Programm zu einem Quine macht. Dieser Input war natürlich wieder riesig, zu groß, um ihn per Brute Force herauszufinden. Also musste man das Programm analysieren (ich habe dafür einen Disassembler geschrieben um das Programm einfacher verstehen zu können). Dann konnte man Schritt für Schritt einen Input konstruieren, der die Lösung findet.

Mein Ansatz lag zuerst daneben, aber nicht weit daneben. Deswegen konnte ich den Rest doch mit Brute Force machen. Als ich das geschafft habe, habe ich in Ruhe noch die Bugs in meinem ersten Ansatz behoben, dann ging es.

Tag 18: Ein einfacher Einschub

Im Verhältnis zu den vorherigen Tagen war Tag 18 sehr einfach. Erst einen kürzesten Pfad mit Einheitskosten finden (BFS), dann herausfinden, ab welchem hinzugefügten Hindernis kein Pfad mehr zum Ziel führt. Mit binärer Suche einfach und effizient.

Tag 19: Handtücher in Heißen Bädern

Man muss herausfinden, wie bestimmte Streifenmuster mit vorgegebenen gestreiften Handtüchern zu bilden sind. Teil 2 war wieder effizient mit dynamic programming lösbar.

Tag 20: Schummelrennen

Eigentlich ein schönes Puzzle: Man musste einen kürzesten Pfad finden, wenn man ein mal für eine bestimmte Zeit Hindernisse ignorieren kann. Ein einfaches kürzeste-Pfade-Problem, aber leider ist für Teil 2 (man darf deutlich länger schummeln als bei Teil 1) der Suchraum wieder explodiert. Ich habe einen unbrauchbaren Ansatz gewählt und komplett implementiert. Dann habe ich noch einen unbrauchbaren Ansatz gewählt und komplett implementiert. Dann habe ich einen guten Ansatz gefunden, hatte aber einen Bug. Und noch einen Bug, und noch einen Bug. Der erste Tag, an dem ich richtig gelitten habe.

Tag 21: Robots all the way down

Einer der Historiker hat sich auf Santas Reindeer-Class-Raumschiff verirrt. Man muss ihn retten, indem man Mit Pfeiltasten einen Roboter steuert, mit Pfeiltasten einen Roboter zu steuern, der mit Pfeiltasten einen anderen Roboter steuert, der Code in ein Nummernpad eingibt.

Man soll die Länge der kürzesten Folge von Befehlen finden, die den letzten Roboter den richtigen Code eingeben lässt. Klingt einfach, oder? Ist es aber nicht. Es gibt viele subtile Probleme, hauptsächlich ist es wichtig, in welcher Reihenfolgen man die Befehle für eine Taste eingibt. Ich habe für Teil 1 ewig gebraucht.

Teil zwei war das gleiche, nur mit 25 Robotern an den Pfeiltasten anstatt nur zwei. Die Liste von Befehlen würde so lang, dass sie nicht mehr in den Speicher passt. Im Verhältnis zu Teil 1 habe ich das aber recht schnell mit – mal wieder – dynamic Programming gelöst, weil mir aufgefallen ist, dass man bestimmte Befehle unabhängig voneinander betrachten kann. Vermutlich das schwerste Puzzle dieses Jahr.

Tag 22: Bananen und Affen

Ein Affe hat den Raum-Zeit-Teleporter der Historiker geklaut. Um ihn zurückzukriegen muss man ihm Bananen geben, die man sich von anderen Affen erhandelt. Einfaches durch-die-Gegend-schieben von Zahlen, eine Erleichterung nach dem vorherigen Tag.

Tag 23: Die LAN-Party

Man muss direkt vernetzte Computer in einem Netzwerk finden. Ein Cliquenproblem, wie ich gelernt habe, das NP-Vollständig ist. Ich habe mal geschaut, wie man so etwas löst und bin auf den Bron-Kerbosch-Agorithmus gestoßen. Für den gegebenen Input hat das auch ziemlich schnell funktioniert.

Tag 24: Plus

An Heiligabend musste man zunächst Inputs durch einen logischen Schaltkreis (ohne Schleifen) schicken. Einfach. In Teil 2 stellte dich dann heraus, dass der Schaltkreis eigentlich addieren soll. Nach einigem Überlegen bin habe ich mir den Schaltkreis einfach geplotted (mit Graphviz und die Fehler manuell gesucht, das ging schneller. Ich habe bis jetzt keine Allgemeine Lösung, aber warum auch? Es war Heiligabend, ich hatte nicht viel Zeit für den AoC. Mit meiner manuellen Lösung hatte ich ironischerweise meinen bis dahin besten Rang erreicht.

Tag 25: Schlüssel-Schloss

Heute musste man dann schauen, welche Schlüssel auf welche Schlösser passten. Sie mussten nicht einmal genau passen. Ich konnte jeden Schlüssel und jedes Schloss als 64-bit Integer darstellen und konnte so das Problem effizient mit bitweisem AND lösen.

Jetzt bin ich durch und habe meinen persönlich besten Rang für die Lösung aller Puzzle in einem Jahr erreicht.