Wyzwanie

Zaprojektuj algorytm kompresji specjalizujący się w kompresji labiryntów ASCII. Konieczne będzie utworzenie zarówno algorytmu kompresji, jak i algorytmu dekompresji. Twój wynik będzie oparty na rozmiarze twoich skompresowanych labiryntów.

Labirynty

Te labirynty są wykonane głównie z bohaterów (piętrach), +, -, |, oraz #(ściany), a dokładnie jeden każda ^(start) i $(koniec). Mogą również zawierać litery ASCII, które liczą się jako płytki podłogowe. Na potrzeby tego wyzwania labirynty nie muszą być rozwiązywalne, a rzeczywiste znaczenie zawartości labiryntu jest nieistotne.

• + będą stosowane do komórek ściany, w których znajduje się co najmniej jedna komórka ściany sąsiadująca poziomo i co najmniej jedna komórka ściany sąsiadująca pionowo.
• | będą stosowane do komórek ściany, w których znajduje się co najmniej jedna pionowo sąsiadująca komórka ściany, ale nie ma komórek sąsiadujących poziomo.
• - będą stosowane do komórek ściany, w których jest co najmniej jedna komórka ściany sąsiadująca poziomo, ale nie ma komórek ściany sąsiadujących pionowo
• # będzie stosowany tylko w przypadku komórek ściany, które nie są ortogonalnie sąsiadujące z innymi komórkami ściany.

Wszystkie labirynty są prostokątne, ale niekoniecznie mają regularne wyrównanie do siatki / ściany.

Labirynty do kompresji

Labirynt 1

+----+----
|  o |    |
| -- | o--+
|    | |  $
 --^-+-+---

Labirynt 2

+-----+---+
|  a  |   |
^ +-+-+ # |
| | |  B  |
| | | --+ |
|   c   | $
+-------+--

Labirynt 3

----------+-+-+-----+-+
^         | | |     | |
+-- --+R #  | |p| | | |
|     | |       | |   |
+---+ +-+-+-- +-+ | | |
|  m| | | |   |   | | |
| +-+ | | | | | --+ | |
| | |    h  | |   | | |
| | | | | |  #  --+-+ |
|     | | | | |  S|   $
+-----+-+-+-+-+---+----

Labirynt 4

+-----+---+-+---+-------^-----+
|     |x  | |   |     tsrq    |
+-+-- +-- | +--  #  --+---- --+
| |   |           |   |       |
| | | | | +-+-+---+ | +-- | +-+
| | | u | | | |     | |   | | |
| +-+ | | | | +---- +-+---+ | |
| |   | |   |    y  |       w |
| | --+ | --+ +-- | +---- | | |
|     | |   | |   | |     | | |
+-- --+ +-+ | | | | +-- | +-+-+
|     | | |   | | | |   |     |
$ | --+-+ | --+-+ | +-+-+-- --+
| |   |      z|   |   |    v  |
+-+---+-------+---+---+-------+

Labirynt 5

++ -----------+
++-       Beep|
$  ----+---+--+
+-+boop|   |  |
| +--- | | | ++
|      | |  +++
+------+-+--+ ^

Labirynt 6

+-$---------------+-+--
|                 | |j 
| |l ---- # ---+ |  |  
| | |       m  | +--+ |
| | | +-+---- #       |
| | | | |      +----+ |
|o| | | | +----+    | |
|       | |    | -- | |
| | | | | | -+ |    | |
| | | | |  | | +--- | |
| | | | +- | | |   | ++
+-+ |n| |  | ++ +--+ | 
    | |   -+- | |  | +-
+---+ +---    |  | |  ^
|    |     --+ --+ | | 
| -- | |  k  |     | ++
|    | |      +--- | ++
|    |      | |    |  |
+-- -+----  | +----+--+

Labirynt 7

+---+-+-------------+-+^+-----+-------+---+-+---+-+---+-+---+
|   |c|             | | |  c  |       |   | |   | |   |c|   |
+-- | | +-- +-- # | | | +-- --+ +---- +-- | +-+ | | +-+ | --+
|       |   |     | |           |         |   | |c| |       |
| | +-- | +-+-- +-+ +-- # +- # -+-- +-- | | --+ | | | | --+C|
|c| |   | | c   |         |         |c  |             |   | |
+-+-+---+-+-----+---------+---------+---+-------------+---+$|

Labirynt 8

------+-+-+---+-+---+-----------+---+-----+---------------+-+
^     | | |   | |   |           |   |     |      r        | |
+-- | | | t | | +-- +----- # ---+-- +-- --+-- ----+-+ --+ | |
|   |   | | |   |   |         r |   |             | |   |   |
| | | | | +-+ --+ --+-- --------+-- | ----+ --+ | | | --+ | |
| |r| |            rotation               |   | |   |   | | $
+-+-+-+-----------------------------------+---+-+---+---+-+--

Labirynt 9

|$|^--+-+---+-----+-+---+-+-+---+---+-+---+-----+
| |   | |   |     | |   | | | f |   | |   |     |
| +-+ | | # +-+ --+ +-+ | | | # | +-+ +-- | ----+
|   |       | |    f| |           | | |   |   f |
| |F+-+ | | | | +---+ | | | ----+-+ | | --+ --+-+
| |   | | |     |     | | |   f |   |         | |
| | | | +-+-+---+-- | | | +-+-+-+ +-+ +--- # -+ |
| | | |     |   |   |   | | | |   | | |         |
+-+-+ | +---+ --+ | +---+-+ | | --+ f | | | | --+
|     | |         |                 | | | | |   |
| --+f| | | +-- --+--f--+ --+ | ----+ | +-+ +---+
|   |     | |     |     |   | |           |     |
+---+-----+-+-----+-----+---+-+-----------+-----+

Labirynt 10

+-----+-+-----------+
|  q  | |         q |
|Q+-+ | +-+-+-+---- |
$ | |     | | |  q  |
+-+ | | | | | +-- +-+
| |   | |     |   | |
| +-- +-+ |q| +-+ | |
|    q|   | |   |   |
| | | +-- | +-+ | --+
| | | |   | | |     |
+-+-+-+ +-+-+ +-- | |
|       |         | |
+--- # -+ | | +-- | |
|  q      | | |   | ^
+-+ +-- | | +-+ | +-+
| | |   | |q|   |   |
| +-+-+ | +-+-- | | |
|     | | |     | | |
| | | +-+-+-- +-+ +-+
| | |         | q   |
+-+-+---------+-----+

Zasady, założenia, punktacja

• Standardowe luki są zabronione
  • Napisz ogólny program, a nie taki, który działa tylko dla dziesięciu przypadków testowych. Musi być w stanie obsłużyć dowolny dowolny labirynt.
• Możesz założyć, że będzie dokładnie jedno wejście i jedno wyjście. Wejścia i wyjścia zawsze będą na granicy labiryntu.
• Możesz założyć, że wszystkie dane wejściowe wykorzystują ściany zgodne z zasadami wymienionymi powyżej. Twój algorytm kompresji nie musi działać w przypadku labiryntów zawierających ściany, które naruszają te reguły.
• Labirynty wejściowe mogą, ale nie muszą być rozwiązane.
• Możesz założyć, że labirynt będzie miał nie więcej niż 100 znaków w obu kierunkach.
• Możesz założyć, że litery nie pojawią się na krawędzi labiryntu. (ponieważ tak jest w przypadku podanych przykładów)
• Twój wynik to całkowity rozmiar wszystkich skompresowanych labiryntów w bajtach (oktetach).
  • Możesz użyć szesnastkowego, base64, ciągów binarnych lub dowolnego podobnego formatu jako reprezentacji dla skompresowanego labiryntu, jeśli uznasz to za wygodniejsze. Nadal powinieneś policzyć wynik w całych oktetach, zaokrąglonych w górę dla każdego labiryntu (np. 4 cyfry base64 to 3 bajty, 2 cyfry szesnastkowe to 1 bajt, 8 cyfr binarnych to 1 bajt itp.)
  • Najniższy wynik wygrywa!

JavaScript (Node.js) , wynik =  586 541 503 492  479 bajtów

Ściany są przechowywane jako zakodowany przez Huffmana strumień bitów opisujących, czy funkcja predykcji zwraca prawidłowe domysły, czy nie.

Znaki specjalne są przechowywane jako $(d, c)$, gdzie $d$ to odległość od poprzedniego znaku specjalnego i $c$ to kod ASCII.

Wypróbuj online!

Wspólny

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];
}

Kompresja

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')
  );
}

Dekompresja

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');
}

W jaki sposób?

Labirynt jest kodowany jako strumień bitów, który ostatecznie jest konwertowany na ciąg znaków.

nagłówek

Nagłówek składa się z:

• szerokość $w$ na 7 bitach
• wysokość $h$ na 7 bitach

Dane ścienne

Przechodzimy przez cały labirynt i próbujemy przewidzieć, czy następna komórka jest ścianą, czy nie, na podstawie wcześniej napotkanych komórek. Emitujemy$0$ jeśli mamy rację, lub $1$ jeśli się mylimy

Powoduje to sekwencję bitów korekcyjnych z (miejmy nadzieję) znacznie więcej $0$jest niż $1$„s. Ta sekwencja jest podzielona na skrypty i przechowywana za pomocą zakodowanych na stałe kodów Huffmana:

• 00 → 0000
• 010 → 0001
• 1001 → 0010
• 11100 → 0011
• 011 → 0100
• itp.

Aby odkodować ścianę $W_n$, procedura dekompresji oblicza tę samą prognozę $P_n$ i przełącza wynik w razie potrzeby za pomocą bitu korekcji $C_n$:

Ostateczne kształty ścian są wydedukowane w sposób podobny do odpowiedzi Nicka Kennedy'ego .

Znaki specjalne

Każdy znak specjalny jest kodowany jako:

• Odległość minus $1$ od ostatniego znaku specjalnego (ignorując ściany):

  • na 6 bitach, jeśli jest mniejszy niż $63$
  • lub jako $111111$ + 14 bitów inaczej (nigdy nie używane w testach, ale wymagane teoretycznie)

• Kod znaku:

  • 5 bitów, czy to ^, $, #lub[a-z]
  • lub $11110$ + 4 bity dla [A-O]
  • lub $11111$ + 4 bity dla [P-Z]

R, wynik 668 bajtów

Wykorzystuje to fakt, że charakter ściany zależy od jej otoczenia. Jako takie, znaki ścienne mogą być kodowane jako bity. Pozostałe informacje, które muszą być przechowywane, to wymiary labiryntu, pozycje początku i końca oraz pozycje innych nieściennych postaci. Ponieważ znaki nie będące ścianami są ASCII, użyłem najbardziej znaczącego bitu każdego bajtu, aby wskazać, czy po nim jest inny znak, aby niektóre słowa w labiryncie nie musiały mieć położenia każdego znaku osobno. Należy również zauważyć, że w przypadku labiryntów mniejszych lub równych 256 znaków (np. Do 16 x 16 lub równoważnych labiryntów prostokątnych) pozycje mogą być przechowywane w jednym bajcie, podczas gdy w przypadku większych labiryntów pozycje wymagają dwóch bajtów.

Funkcje użytkowe

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))
    )
  }
}

Algorytm kompresji

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)
}

Algorytm dekompresyjny

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 = "")
}

Wypróbuj online!