Tantangan

Rancang algoritme kompresi yang dikhususkan untuk menekan labirin ASCII. Anda perlu membuat algoritma kompresi dan algoritma dekompresi. Skor Anda akan didasarkan pada ukuran labirin terkompresi Anda.

Labirin

Labirin ini dibuat terutama dari karakter (lantai), +, -, |, dan #(dinding), dan tepat satu masing-masing ^(mulai) dan $(end). Mereka juga dapat berisi surat ASCII, yang dihitung sebagai ubin lantai. Untuk tujuan tantangan ini, labirin tidak harus dipecahkan dan makna sebenarnya dari konten labirin tidak relevan.

• + akan digunakan untuk sel-sel dinding di mana setidaknya ada satu sel dinding yang berdekatan secara horizontal dan setidaknya satu sel dinding yang berdekatan secara vertikal.
• | akan digunakan untuk sel-sel dinding di mana setidaknya ada satu sel dinding yang berdekatan secara vertikal, tetapi tidak ada sel-sel dinding yang berdekatan secara horizontal.
• - akan digunakan untuk sel-sel dinding di mana setidaknya ada satu sel dinding yang berdekatan secara horizontal, tetapi tidak ada sel-sel dinding yang berdekatan secara vertikal
• # hanya akan digunakan untuk sel-sel dinding yang tidak berdekatan secara ortogonal dengan sel-sel dinding lainnya.

Semua labirin berbentuk persegi panjang, tetapi tidak harus memiliki perataan grid / dinding biasa.

Labirin Untuk Kompres

Labirin 1

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

Labirin 2

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

Labirin 3

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

Labirin 4

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

Labirin 5

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

Labirin 6

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

Labirin 7

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

Labirin 8

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

Labirin 9

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

Labirin 10

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

Aturan, Asumsi, Penilaian

• Celah standar dilarang
  • Tulis program umum, bukan program yang hanya berfungsi untuk sepuluh kasus uji. Itu harus mampu menangani labirin yang sewenang-wenang.
• Anda mungkin berasumsi akan ada persis satu pintu masuk dan satu pintu keluar. Pintu masuk dan keluar akan selalu berada di perbatasan labirin.
• Anda dapat mengasumsikan bahwa semua input menggunakan dinding yang mengikuti aturan yang disebutkan di atas. Algoritma kompresi Anda tidak harus bekerja untuk labirin yang berisi dinding yang melanggar aturan tersebut.
• Labirin input mungkin atau mungkin tidak bisa dipecahkan.
• Anda dapat mengasumsikan labirin tidak akan lebih besar dari 100 karakter di kedua arah.
• Anda dapat berasumsi bahwa surat tidak akan muncul di tepi labirin. (Karena ini adalah kasus untuk contoh yang diberikan)
• Skor Anda adalah ukuran total, dalam byte (oktet), dari semua labirin terkompresi.
  • Anda dapat menggunakan hex, base64, string biner, atau format serupa lainnya sebagai representasi untuk labirin terkompresi jika Anda merasa lebih nyaman. Anda masih harus menghitung hasilnya dalam seluruh oktet, dibulatkan untuk setiap labirin (mis. 4 basis64 digit adalah 3 byte, 2 digit hex adalah 1 byte, 8 digit biner adalah 1 byte, dll ...)
  • Menang skor terendah!

JavaScript (Node.js) , skor =  586 541 503 492  479 byte

Dinding disimpan sebagai aliran bit berkode Huffman yang menjelaskan apakah fungsi prediksi mengembalikan tebakan yang benar atau tidak.

$(d, c)$$d$$c$

Cobalah online!

Umum

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

Kompresi

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

Dekompresi

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

Bagaimana?

Labirin dikodekan sebagai aliran bit yang akhirnya dikonversi menjadi string.

Header

Header terdiri dari:

• $w$
• $h$

Data dinding

$0$$1$

$0$$1$

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

$W_n$$P_n$$C_n$

Bentuk dinding terakhir disimpulkan dengan cara yang mirip dengan jawaban Nick Kennedy .

Karakter spesial

Setiap karakter khusus dikodekan sebagai:

• $1$

  • $63$
  • $111111$

• Kode karakter:

  • pada 5 bit jika itu ^, $, #atau[a-z]
  • $11110$[A-O]
  • $11111$[P-Z]

R, skor 668 byte

Ini mengambil keuntungan dari kenyataan bahwa karakter dinding ditentukan oleh lingkungannya. Dengan demikian, karakter dinding dapat dikodekan sebagai bit. Info yang tersisa yang perlu disimpan adalah dimensi labirin, posisi awal dan akhir, serta posisi karakter non-dinding lainnya. Karena karakter non-dinding adalah ASCII, saya telah menggunakan bit paling signifikan dari setiap byte untuk menunjukkan apakah ada karakter lain yang mengikuti sehingga beberapa kata di labirin tidak harus memiliki lokasi setiap karakter disimpan terpisah. Perhatikan juga bahwa untuk labirin kurang dari atau sama dengan 256 karakter (misalnya hingga 16x16 atau labirin persegi panjang setara), posisi dapat disimpan dalam satu byte, sedangkan untuk labirin yang lebih besar posisi membutuhkan dua byte.

Fungsi utilitas

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

Algoritma kompresi

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

Algoritma dekompresi

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

Cobalah online!