Saya terkejut ini belum pernah diposting sebelumnya!
The Konsisten Overhead Byte Stuffing (tongkol) algoritma yang digunakan untuk membatasi byte stream.
Kami memilih penanda bingkai (kami akan menggunakan 0x00) dan di mana pun 0x00 terjadi dalam aliran itu diganti dengan jumlah byte hingga 0x00 berikutnya terjadi (kami akan menyebutnya tonggak sejarah). Ini mengurangi rentang nilai dari 0..255 ke 1..255, memungkinkan 0x00 untuk membatasi bingkai di aliran secara jelas.
Pada tonggak sejarah, jika 255B berikutnya tidak mengandung 0x00 ini melebihi panjang tonggak maksimum - algoritma harus 'berhenti' di 255B dan meletakkan tonggak lain. Ini adalah 'overhead yang konsisten'.
Byte pertama akan menjadi tonggak pertama, tonggak terakhir akan menjadi jumlah byte sampai penanda bingkai.
Beberapa contoh dari Wikipedia (terbaik untuk membaca artikel di mana mereka diwarnai):
0x00 as frame marker
Unencoded data (hex) Encoded with COBS (hex)
00 01 01 00
00 00 01 01 01 00
11 22 00 33 03 11 22 02 33 00
11 22 33 44 05 11 22 33 44 00
11 00 00 00 02 11 01 01 01 00
01 02 03 ... FD FE FF 01 02 03 ... FD FE 00
00 01 02 ... FC FD FE 01 FF 01 02 ... FC FD FE 00
01 02 03 ... FD FE FF FF 01 02 03 ... FD FE 02 FF 00
02 03 04 ... FE FF 00 FF 02 03 04 ... FE FF 01 01 00
03 04 05 ... FF 00 01 FE 03 04 05 ... FF 02 01 00
Tantangan: untuk mengimplementasikan ini dalam program terpendek.
- Input adalah byte stream / array yang tidak di-encode, output adalah byte stream / array yang di-encode
- Gunakan segala macam input / output standar biner
- Penanda bingkai akhir tidak perlu
- Program dapat mengembalikan array yang terlalu besar
- Aliran yang diakhiri dengan 254 byte bukan nol tidak memerlukan 0x00 tambahan
Catatan
- Panjang pengembalian terburuk adalah
numBytes + (numBytes / 254) + 1
Contoh
Kami memiliki array byte
[0] 0x01
[1] 0x02
[2] 0x00
[3] 0x03
[4] 0x04
[5] 0x05
[6] 0x00
[7] 0x06
Untuk masing-masing 0x00
kita perlu menyatakan (dalam tonggak sejarah) di mana yang berikutnya 0x00
akan.
[0] 0x03 #Milestone. Refers to the original [2] - "The next 0x00 is in 3B"
[1] 0x01 #Original [0]
[2] 0x02 #Original [1]
[3] 0x04 #Milestone. Refers to the original [6] - "The next 0x00 is in 4B"
[4] 0x03 #
[5] 0x04 #
[6] 0x05 # Originals [3..5]
[7] 0x02 #Milestone. Refers to the end frame marker
[8] 0x06 #Original [7]
[9] 0x00 #Optional. End frame marker.
sumber
01
tetapi ada dua01
s di yang kesembilan (di mana ada 254 byte non-nol diikuti oleh nol).Jawaban:
JavaScript (Node.js) , 114 byte
Cobalah online!
sumber
Java (JDK) , 143 byte
Cobalah online!
sumber
Python 2 , 125 byte
Cobalah online!
sumber
Jelly , 27 byte
Cobalah online!
Tautan monadik yang mengambil larik byte yang tidak dilodekan sebagai input dan mengembalikan larik byte yang disandikan. Sesuai aturan, penanda bingkai akhir dihilangkan.
Penjelasan
sumber
Elixir , 109 byte
Cobalah online!
sumber
J , 103 karakter
Perhatikan hasil dari test case terakhir berbeda dari wiki dan bahasa lainnya. Ini disebabkan oleh penunjuk ini ke 254 byte nol di batas. Banyak hal menjadi lebih mudah, jika ini tidak diperlakukan sebagai kasus khusus.
Cobalah secara Online
sumber