kactl

KACTL

Dieses Repo enthält KACTL, das Referenzdokument des ICPC-Teams von KTH. Es besteht aus 25 Seiten kopier- und einfügbarem C++-Code zur Verwendung in Programmierwettbewerben im ICPC-Stil.

Siehe kactl.pdf für die endgültige, durchsuchbare Version und content/ für den rohen Quellcode.

Bestrebungen

KACTL-Algorithmen sollten nützlich, kurz, schnell genug, gut getestet und gegebenenfalls lesbar und leicht zu ändern sein. Sie sollten nicht zu allgemein gehalten sein, da der Code manuell eingegeben wird und dadurch nur der Mehraufwand entsteht. Aus Platzgründen schließen wir auch Algorithmen aus, die sehr häufig/einfach (z. B. Dijkstra) oder sehr ungewöhnlich (allgemeines gewichtetes Matching) sind.

Wenn Sie das Gefühl haben, dass etwas fehlt, bereinigt werden könnte oder Sie einen Fehler bemerken, reichen Sie bitte ein Problem ein oder senden Sie eine Pull-Anfrage!

Anpassen von KACTL

Während KACTL unverändert verwendet werden kann, lässt es sich auch leicht ändern, wenn Sie eine personalisierte Kopie erstellen möchten. Insbesondere möchten Sie möglicherweise das Deckblatt ändern oder die einzuschließenden Algorithmen selbst auswählen – aus Platzgründen sind nicht alle Algorithmen im Repo im PDF enthalten. Möglicherweise möchten Sie auch die farbige Syntaxhervorhebung aktivieren.

content/kactl.tex ist die Hauptdatei von KACTL und kann bearbeitet werden, um Teamnamen, Logo, Syntaxhervorhebung usw. zu ändern. Es importiert chapter.tex -Dateien aus jedem der content/ -Unterverzeichnisse, die den Inhalt jedes Kapitels definieren. Dazu gehören Quellcode, Text und Mathematik in Form von LaTeX. Um Code zu einem Kapitel hinzuzufügen bzw. daraus zu entfernen, fügen Sie eine entsprechende kactlimport Zeile zur Datei chapter.tex hinzu bzw. entfernen Sie sie. Für eine bessere Ausrichtung möchten Sie möglicherweise die Befehle hardcolumnbreak , columnbreak oder newpage einfügen, obwohl dies normalerweise nur vor wichtigen Wettbewerben und nicht im Hauptzweig erfolgt. Die Algorithmen, die nicht im PDF enthalten sind, bleiben in der Datei chapter.tex auskommentiert.

Um KACTL zu erstellen, geben Sie make kactl (oder make fast ) auf einem *nix-Rechner ein – dadurch wird kactl.pdf aktualisiert. (Windows funktioniert möglicherweise auch, wurde aber nicht getestet.) doc/README enthält noch ein paar Hinweise dazu.

Tipps:

1. Überprüfen Sie, was standardmäßig ausgeschlossen ist, indem Sie make showexcluded ausführen. Die Standardkonfiguration ist so gewählt, dass sie ein angemessenes Gleichgewicht für Anfänger und Fortgeschrittene bietet.
2. Nutzen Sie das Hashing, wenn Sie diese Algorithmen eingeben. Jeder Algorithmus verfügt oben rechts über einen 6-stelligen MD5-Hash. Dieser Hash kann mithilfe von hash.sh oder dem Befehl :Hash aus der .vimrc generiert werden. Beim Hashing werden Leerzeichen und Kommentare ignoriert.

Codierungsstil

KACTL verwendet einen relativ prägnanten Codierungsstil mit einer Handvoll in der Vorlage definierter Makros/Typedefs, die zur Verkürzung des Codes beitragen. Die Zeilenbreite beträgt 63 Zeichen, mit Tabulatoren zum Einrücken (Tabulator = 2 Leerzeichen im PDF).

Jeder Algorithmus enthält einen Header mit dem Autor des Codes, dem Datum seiner Hinzufügung, einer Beschreibung des Algorithmus, seinem Teststatus und vorzugsweise auch Quelle, Lizenz und zeitlicher Komplexität.

kactl.pdf ist auf 25 Seiten + Deckblatt zu beschränken. Gelegentlich wird die generierte kactl.pdf der Einfachheit halber in das Repo übernommen, aber nicht allzu oft, da dadurch Git-Vorgänge langsamer werden.

Testen

KACTL strebt ein hohes Maß an Vertrauen in die Korrektheit des Algorithmus an. Die Tests werden sowohl mit Online-Richtern als auch (bei neueren Algorithmen) mit Stresstests durchgeführt, die die Ausgabe für eine große Anzahl zufällig generierter Fälle mit einem naiveren Algorithmus vergleichen. Diese Tests befinden sich im stress-tests Verzeichnis und werden bei jedem Commit mit CI ausgeführt. Das CI überprüft außerdem, ob alle Header kompiliert werden (mit Ausnahme einer Ausschlussliste in docs/scripts/skip_headers ) und dass der Latex kompiliert wird.

old-unit-tests enthält ein paar defekte Unit-Tests, die zuletzt vor etwa zehn Jahren berührt wurden.

Lizenz

Wie bei Wettbewerbsprogrammen üblich, ist die Lizenzsituation etwas unklar. Viele Quelldateien sind mit einer Lizenz gekennzeichnet (wir versuchen, CC0 zu verwenden), viele jedoch auch nicht. Allerdings ist von einem guten Willen anderer Autoren auszugehen und in vielen Fällen dürfte keine Genehmigung erforderlich sein, da der Code nicht weitergegeben wird. Um die Rückverfolgbarkeit zu erleichtern, werden in Quelldateien Quellen und Autoren vermerkt.

Alles in stress-tests ist implizit CC0, mit Ausnahme von Referenzimplementierungen aus dem Internet.