Herausforderung
Entwerfen Sie einen Komprimierungsalgorithmus, der auf das Komprimieren von ASCII-Labyrinthen spezialisiert ist. Sie müssen sowohl einen Komprimierungsalgorithmus als auch einen Dekomprimierungsalgorithmus erstellen. Ihre Punktzahl basiert auf der Größe Ihrer komprimierten Labyrinthe.
Labyrinthe
Diese Labyrinthe sind in erster Linie der Figuren gemacht (Böden),
+
, -
, |
, und #
(Wände) und genau ein jeweils ^
(Start) und $
(Ende). Sie können auch ASCII-Buchstaben enthalten, die als Bodenfliesen gelten. Für die Zwecke dieser Herausforderung müssen Labyrinthe nicht lösbar sein und die tatsächliche Bedeutung des Labyrinthinhalts ist irrelevant.
+
wird für Wandzellen verwendet, bei denen mindestens eine horizontal benachbarte Wandzelle und mindestens eine vertikal benachbarte Wandzelle vorhanden sind.|
wird für Wandzellen verwendet, bei denen mindestens eine vertikal benachbarte Wandzelle vorhanden ist, jedoch keine horizontal benachbarten Wandzellen.-
wird für Wandzellen verwendet, bei denen mindestens eine horizontal benachbarte Wandzelle vorhanden ist, jedoch keine vertikal benachbarten Wandzellen#
wird nur für Wandzellen verwendet, die nicht orthogonal an andere Wandzellen angrenzen.
Alle Labyrinthe sind rechteckig, haben jedoch nicht unbedingt eine regelmäßige Gitter- / Wandausrichtung.
Labyrinthe zu komprimieren
Labyrinth 1
+----+----
| o | |
| -- | o--+
| | | $
--^-+-+---
Labyrinth 2
+-----+---+
| a | |
^ +-+-+ # |
| | | B |
| | | --+ |
| c | $
+-------+--
Labyrinth 3
----------+-+-+-----+-+
^ | | | | |
+-- --+R # | |p| | | |
| | | | | |
+---+ +-+-+-- +-+ | | |
| m| | | | | | | |
| +-+ | | | | | --+ | |
| | | h | | | | |
| | | | | | # --+-+ |
| | | | | | S| $
+-----+-+-+-+-+---+----
Labyrinth 4
+-----+---+-+---+-------^-----+
| |x | | | tsrq |
+-+-- +-- | +-- # --+---- --+
| | | | | |
| | | | | +-+-+---+ | +-- | +-+
| | | u | | | | | | | | |
| +-+ | | | | +---- +-+---+ | |
| | | | | y | w |
| | --+ | --+ +-- | +---- | | |
| | | | | | | | | |
+-- --+ +-+ | | | | +-- | +-+-+
| | | | | | | | | |
$ | --+-+ | --+-+ | +-+-+-- --+
| | | z| | | v |
+-+---+-------+---+---+-------+
Labyrinth 5
++ -----------+
++- Beep|
$ ----+---+--+
+-+boop| | |
| +--- | | | ++
| | | +++
+------+-+--+ ^
Labyrinth 6
+-$---------------+-+--
| | |j
| |l ---- # ---+ | |
| | | m | +--+ |
| | | +-+---- # |
| | | | | +----+ |
|o| | | | +----+ | |
| | | | -- | |
| | | | | | -+ | | |
| | | | | | | +--- | |
| | | | +- | | | | ++
+-+ |n| | | ++ +--+ |
| | -+- | | | +-
+---+ +--- | | | ^
| | --+ --+ | |
| -- | | k | | ++
| | | +--- | ++
| | | | | |
+-- -+---- | +----+--+
Labyrinth 7
+---+-+-------------+-+^+-----+-------+---+-+---+-+---+-+---+
| |c| | | | c | | | | | | |c| |
+-- | | +-- +-- # | | | +-- --+ +---- +-- | +-+ | | +-+ | --+
| | | | | | | | |c| | |
| | +-- | +-+-- +-+ +-- # +- # -+-- +-- | | --+ | | | | --+C|
|c| | | | c | | |c | | | |
+-+-+---+-+-----+---------+---------+---+-------------+---+$|
Labyrinth 8
------+-+-+---+-+---+-----------+---+-----+---------------+-+
^ | | | | | | | | | r | |
+-- | | | t | | +-- +----- # ---+-- +-- --+-- ----+-+ --+ | |
| | | | | | | r | | | | | |
| | | | | +-+ --+ --+-- --------+-- | ----+ --+ | | | --+ | |
| |r| | rotation | | | | | | $
+-+-+-+-----------------------------------+---+-+---+---+-+--
Labyrinth 9
|$|^--+-+---+-----+-+---+-+-+---+---+-+---+-----+
| | | | | | | | | | f | | | | |
| +-+ | | # +-+ --+ +-+ | | | # | +-+ +-- | ----+
| | | | f| | | | | | f |
| |F+-+ | | | | +---+ | | | ----+-+ | | --+ --+-+
| | | | | | | | | f | | | |
| | | | +-+-+---+-- | | | +-+-+-+ +-+ +--- # -+ |
| | | | | | | | | | | | | | |
+-+-+ | +---+ --+ | +---+-+ | | --+ f | | | | --+
| | | | | | | | | |
| --+f| | | +-- --+--f--+ --+ | ----+ | +-+ +---+
| | | | | | | | | |
+---+-----+-+-----+-----+---+-+-----------+-----+
Labyrinth 10
+-----+-+-----------+
| q | | q |
|Q+-+ | +-+-+-+---- |
$ | | | | | q |
+-+ | | | | | +-- +-+
| | | | | | |
| +-- +-+ |q| +-+ | |
| q| | | | |
| | | +-- | +-+ | --+
| | | | | | | |
+-+-+-+ +-+-+ +-- | |
| | | |
+--- # -+ | | +-- | |
| q | | | | ^
+-+ +-- | | +-+ | +-+
| | | | |q| | |
| +-+-+ | +-+-- | | |
| | | | | | |
| | | +-+-+-- +-+ +-+
| | | | q |
+-+-+---------+-----+
Regeln, Annahmen, Wertung
- Standardlücken sind verboten
- Schreiben Sie ein allgemeines Programm, das nicht nur für die zehn Testfälle funktioniert. Es muss in der Lage sein, mit jedem beliebigen Labyrinth umzugehen.
- Sie können davon ausgehen, dass es genau einen Eingang und einen Ausgang gibt. Ein- und Ausgänge befinden sich immer am Rand des Labyrinths.
- Sie können davon ausgehen, dass alle Eingaben Wände verwenden, die den oben aufgeführten Regeln entsprechen. Ihr Komprimierungsalgorithmus muss nicht für Labyrinthe funktionieren, die Wände enthalten, die gegen diese Regeln verstoßen.
- Eingabelabyrinthe können lösbar sein oder nicht.
- Sie können davon ausgehen, dass das Labyrinth in beiden Richtungen nicht größer als 100 Zeichen ist.
- Sie können davon ausgehen, dass am Rand des Labyrinths keine Buchstaben erscheinen. (da dies bei den bereitgestellten Beispielen der Fall ist)
- Ihre Punktzahl ist die Gesamtgröße aller komprimierten Labyrinthe in Bytes (Oktetten).
- Sie können Hex-, Base64-, Binärzeichenfolgen oder ein ähnliches Format als Darstellung für Ihr komprimiertes Labyrinth verwenden, wenn Sie dies für bequemer halten. Sie sollten das Ergebnis immer noch in ganzen Oktetten zählen, die für jedes Labyrinth aufgerundet sind (z. B. 4 base64-Ziffern sind 3 Bytes, 2 hexadezimale Ziffern sind 1 Byte, 8 binäre Ziffern sind 1 Byte usw.)
- Die niedrigste Punktzahl gewinnt!
quelle
Antworten:
JavaScript (Node.js) , Punktzahl =
586 541 503 492479 ByteDie Wände werden als Huffman-codierter Bitstrom gespeichert, der beschreibt, ob eine Vorhersagefunktion die richtige Vermutung zurückgibt oder nicht.
Probieren Sie es online aus!
Verbreitet
Kompression
Dekompression
Wie?
Ein Labyrinth wird als Bitstrom codiert, der schließlich in eine Zeichenfolge konvertiert wird.
Header
Der Header besteht aus:
Wanddaten
00
→0000
010
→0001
1001
→0010
11100
→0011
011
→0100
Die endgültigen Wandformen werden auf ähnliche Weise wie Nick Kennedys Antwort abgeleitet .
Spezielle Charaktere
Jedes Sonderzeichen ist codiert als:
Der Code des Zeichens:
^
,$
,#
oder[a-z]
[A-O]
[P-Z]
quelle
deflate
? Es gibt sehr viel im Regal!R, Punktzahl 668 Bytes
Dies nutzt die Tatsache aus, dass der Wandcharakter durch seine Umgebung bestimmt wird. Als solche können Wandzeichen als Bits codiert werden. Die verbleibenden Informationen, die gespeichert werden müssen, sind die Abmessungen des Labyrinths, die Positionen von Start und Ziel sowie die Positionen aller anderen Nicht-Wand-Charaktere. Da die Nicht-Wand-Zeichen ASCII sind, habe ich das höchstwertige Bit jedes Bytes verwendet, um anzugeben, ob ein anderes Zeichen folgt, damit bei einigen Wörtern in den Labyrinthen nicht die Position jedes Zeichens gespeichert werden muss separat. Beachten Sie auch, dass für Labyrinthe mit weniger als oder gleich 256 Zeichen (z. B. bis zu 16 x 16 oder äquivalente rechteckige Labyrinthe) die Positionen in einem Byte gespeichert werden können, während für größere Labyrinthe die Positionen zwei Bytes benötigen.
Dienstprogrammfunktionen
Komprimierungsalgorithmus
Dekomprimierungsalgorithmus
Probieren Sie es online aus!
quelle