ASCII-Labyrinthkomprimierung

9

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!
Beefster
quelle
Gibt es eine Größenbeschränkung für ein Labyrinth?
Verkörperung der Unwissenheit
@EmbodimentofIgnorance 100x100
Beefster
@Arnauld Eigentlich war das ein Problem beim Einfügen von Kopien, aber ich denke, dass die SE-Formatierung Leerzeichen am Ende der Zeile entfernt. Ja, es soll raumgepolstert sein.
Beefster
@ChasBrown, das zählt als Standardlücke, was bedeutet, dass es standardmäßig gesperrt ist.
Beefster
1
@schnaader, das erscheint angesichts der Beispieltestfälle vernünftig.
Beefster

Antworten:

5

JavaScript (Node.js) , Punktzahl =  586 541 503 492  479 Byte

Die Wände werden als Huffman-codierter Bitstrom gespeichert, der beschreibt, ob eine Vorhersagefunktion die richtige Vermutung zurückgibt oder nicht.

(d,c)dc

Probieren Sie es online aus!

Verbreitet

const HUFFMAN = [
  '00',       // 0000
  '010',      // 0001
  '1001',     // 0010
  '11100',    // 0011
  '011',      // 0100
  '101',      // 0101
  '11110',    // 0110
  '100010',   // 0111
  '110',      // 1000
  '11101',    // 1001
  '1111100',  // 1010
  '1111101',  // 1011
  '10000',    // 1100
  '1111110',  // 1101
  '100011',   // 1110
  '1111111'   // 1111
];

let bin = (n, w) => n.toString(2).padStart(w, '0');

let wallShape = (row, x, y) => {
  let vWall = (row[y - 1] || [])[x] | (row[y + 1] || [])[x],
      hWall = row[y][x - 1] | row[y][x + 1];

  return ' -|+'[row[y][x] ? vWall * 2 | hWall : 0];
}

let predictWall = (row, x, y, w, h) => {
  let prvRow = row[y - 1] || [];
  return !x | !y | x == w - 1 | y == h - 1 | (prvRow[x] | row[y][x - 1]) & !prvRow[x - 1];
}

Kompression

let pack = str => {
  let row = str.split('\n').map(r => [...r]),
      w = row[0].length,
      h = row.length;

  let wall = row.map((r, y) => r.map((c, x) => +/[-+|]/.test(c)));

  if(row.some((r, y) => r.some((c, x) => wall[y][x] && wallShape(wall, x, y) != c))) {
    throw "invalid maze";
  }

  row = wall.map((r, y) => r.map((v, x) => predictWall(wall, x, y, w, h) ^ v));
  row = row.map(r => r.join('')).join('');
  row = row.replace(/.{1,4}/g, s => HUFFMAN[parseInt(s.padEnd(4, '0'), 2)]);

  str =
    str.replace(/[\n|+-]/g, '').replace(/ *(\S)/g, (s, c) => {
      let n = c.charCodeAt(),
          i = '^$#'.indexOf(c);

      return (
        bin(s.length > 63 ? 0xFC000 | s.length - 1 : s.length - 1, 6) +
        bin(~i ? i : n < 91 ? (n > 80 ? 0x1F0 : 0x1E0) | ~-n & 15 : n - 94, 5)
      );
    }).trim();

  return (
    Buffer.from(
      (bin(w, 7) + bin(h, 7) + row + str)
      .match(/.{1,8}/g).map(s => parseInt(s.padEnd(8, '0'), 2))
    ).toString('binary')
  );
}

Dekompression

let unpack = str => {
  str = [...str].map(c => bin(c.charCodeAt(), 8)).join('');

  let x, y, n, i, s,
      ptr = 0,
      read = n => parseInt(str.slice(ptr, ptr += n), 2),
      w = read(7),
      h = read(7),
      row = [];

  for(x = s = ''; s.length < w * h;) {
    ~(i = HUFFMAN.indexOf(x += read(1))) && (s += bin(i, 4), x = '');
  }
  for(i = y = 0; y < h; y++) {
    for(row[y] = [], x = 0; x < w; x++) {
      row[y][x] = predictWall(row, x, y, w, h) ^ s[i++];
    }
  }

  row = row.map((r, y) => r.map((c, x) => wallShape(row, x, y)));

  for(i = 0; str[ptr + 10];) {
    for(
      n = (n = read(6)) == 0x3F ? read(14) + 1 : n + 1;
      n -= row[i / w | 0][i % w] == ' ';
      i++
    ) {}

    row[i / w | 0][i % w] = String.fromCharCode(
      (n = read(5)) >= 0x1E ? read(4) + (n == 0x1F ? 81 : 65) : [94, 36, 35][n] || n + 94
    );
  }
  return row.map(r => r.join('')).join('\n');
}

Wie?

Ein Labyrinth wird als Bitstrom codiert, der schließlich in eine Zeichenfolge konvertiert wird.

Header

Der Header besteht aus:

  • w
  • h

Wanddaten

01

01

  • 000000
  • 0100001
  • 10010010
  • 111000011
  • 0110100
  • etc.

W.nP.nC.n

W.n=P.nC.n

Die endgültigen Wandformen werden auf ähnliche Weise wie Nick Kennedys Antwort abgeleitet .

Spezielle Charaktere

Jedes Sonderzeichen ist codiert als:

  • 1

    • 63
    • 111111
  • Der Code des Zeichens:

    • auf 5 Bits , wenn es ^, $, #oder[a-z]
    • 11110[A-O]
    • 11111[P-Z]
Arnauld
quelle
Haben Sie andere Komprimierungsalgorithmen als ausprobiert deflate? Es gibt sehr viel im Regal!
dfeuer
Es gibt keine Regel, die besagt, dass es in TIO funktionieren muss!
dfeuer
O_o schön, frage mich, ob die Dezimalkomprimierung überhaupt helfen würde (im Grunde das Gegenteil von Huffman, der Raum ist 0 zu 1, unterteilt in Abschnitte mit beliebiger Größe (<1 natürlich), und die Codierung ist die kürzeste Binärzahl, die in diesen Bereich fällt das richtige Stück des Leerzeichens
ASCII
@ Nur-ASCII-Dezimalcodierung (auch bekannt als arithmetische Codierung) sollte das Komprimierungsverhältnis definitiv verbessern, aber wahrscheinlich bei einem so kurzen Datenstrom um einen kleinen Rand. Ich bin mir jedoch sicher, dass es möglich ist, die Huffman-Codierung und / oder die Vorhersagefunktion zu verbessern, bevor zur arithmetischen Codierung gewechselt wird (beide sind derzeit wirklich grundlegend).
Arnauld
@ Nur ASCII Zum Beispiel sollte ich wahrscheinlich längere Codes ausprobieren (die Verwendung von Nibbles ist willkürlich). Ich könnte auch ein 1-Bit-Flag in den Header einfügen, das angibt, ob die Daten mit den statischen Standard-Huffman-Codes oder mit dynamischen Codes entpackt werden sollen (wenn sich herausstellt, dass die Komprimierung einiger Labyrinthe verbessert wird). Eine Sache, die ich versucht habe, war, das Labyrinth um 90 ° zu drehen und zu sehen, ob es besser komprimiert wurde. Aber das sparte insgesamt nur 1 Byte.
Arnauld
4

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

r <- as.raw

int_as_raw <- function(int, bytes = 2) {
  if (bytes == 1) {
    r(int)
  } else {
    do.call(c, lapply(int, function(.x) r(c(.x %/% 256, .x %% 256))))
  }
}

raw_as_int <- function(raw, bytes = 2) {
  if (bytes == 1) {
    as.integer(raw)
  } else {
    sapply(
      seq(1, length(raw) - 1, 2),
      function(.x) as.integer(as.integer(raw[.x + 0:1]) %*% c(256, 1))
    )
  }
}

Komprimierungsalgorithmus

compress_maze <- function(maze) {
  maze_array <- do.call(rbind, strsplit(maze, ""))
  simple_maze <- r(maze_array %in% c("+", "#", "-", "|"))
  simple_maze <- packBits(c(simple_maze, rep(r(0), (8 - length(simple_maze)) %% 8)))
  maze_dim <- int_as_raw(dim(maze_array), 1)
  bytes_needed <- 1 + (length(maze_array) > 256)
  start_finish <- int_as_raw(sapply(c("^", "$"), function(.x) which(maze_array == .x)) - 1, bytes = bytes_needed)
  other_ascii_locs_rle <- rle(!(maze_array %in% c(" ", "+", "#", "-", "|", "$", "^")))
  other_ascii_locs <- cumsum(
    c(1, other_ascii_locs_rle$lengths[-length(other_ascii_locs_rle$lengths)])
  )[other_ascii_locs_rle$values]
  other_ascii_locs_length <- other_ascii_locs_rle$lengths[other_ascii_locs_rle$values]

  encode_ascii <- function(loc, len) {
    text <- charToRaw(paste(maze_array[loc:(loc + len - 1)], collapse = ""))
    if (len > 1) {
      text[1:(len - 1)] <- text[1:(len - 1)] | r(128)
    }
    c(int_as_raw(loc - 1, bytes = bytes_needed), text)
  }

  other_ascii_encoded <- Map(encode_ascii,
    other_ascii_locs,
    other_ascii_locs_length
    )
  other_ascii_encoded <- do.call(c, other_ascii_encoded)
  c(maze_dim, simple_maze, start_finish, other_ascii_encoded)
}

Dekomprimierungsalgorithmus

decompress_maze <- function(c_maze) {
  dim_maze <- as.integer(c_maze[1:2])
  len_maze <- prod(dim_maze)
  len_maze_b <- ceiling(len_maze / 8)
  bit_maze <- rawToBits(c_maze[-(1:2)])[1:len_maze]
  dim(bit_maze) <- dim_maze
  bit_maze[-1, ] <- bit_maze[-1, ] | rawShift(bit_maze[-nrow(bit_maze), ] & r(1), 1)
  bit_maze[-nrow(bit_maze), ] <- bit_maze[-nrow(bit_maze), ] | rawShift(bit_maze[-1, ] & r(1), 1)
  bit_maze[, -1] <- bit_maze[, -1] | rawShift(bit_maze[, -ncol(bit_maze)] & r(1), 2)
  bit_maze[, -ncol(bit_maze)] <- bit_maze[, -ncol(bit_maze)] | rawShift(bit_maze[, -1] & r(1), 2)
  bit_maze[(bit_maze & r(1)) == r(0)] <- r(0)
  array_maze <- c(" ", "#", "|", "-", "+")[(as.integer(bit_maze) + 1) %/% 2 + 1]
  dim(array_maze) <- dim_maze
  bytes_needed <- 1 + (len_maze > 256)
  start_finish <- raw_as_int(c_maze[2 + len_maze_b + 1:(bytes_needed * 2)], bytes_needed) + 1
  array_maze[start_finish] <- c("^", "$")
  i <- 3 + len_maze_b + 2 * bytes_needed
  while (i < length(c_maze)) {
    loc <- raw_as_int(c_maze[i + 1:bytes_needed - 1], bytes_needed) + 1
    i <- i + bytes_needed
    text <- character(0)
    while (c_maze[i] & r(128)) {
      text <- c(text, rawToChar(c_maze[i] & r(127)))
      i <- i + 1
    }
    text <- c(text, rawToChar(c_maze[i]))
    array_maze[loc:(loc + length(text) - 1)] <- text
    i <- i + 1
  }
  apply(array_maze, 1, paste, collapse = "")
}

Probieren Sie es online aus!

Nick Kennedy
quelle
Ich wusste, dass Sie die Wände als Bits speichern können, aber ich mag Ihren Ansatz zum Komprimieren der Positionsdaten von Nicht-Wandcharakteren. +1
Neil