Compress 8 bits to 6 when certain bit patterns will never occur

Question

Consider an eight bit number in which an even position bit will never be 1 if one of its neighbors is 0 (considering MSB and LSB as neighbors). There are fewer than 64 such numbers, so there is at least some reversible mapping of them to 6 bit numbers.

Your task is to write a pair of functions (or code blocks or your language equivalent), one of which takes an 8-bit number and returns a 6-bit number, the other which reverses the process. "Numbers" here can be literal numbers or a list of booleans or even a string of Xs and Os.

Put another way, the following bit patterns will never occur:

......01
.....10.
....01..
...10...
..01....
.10.....
01......
0......1

PS: I'd really love to see an answer in Lua :)

PPS: Bonus imaginary internet points if you can pack the 47 valid values into a 6-bit number with a maximum of value of 47

Answer 1

Python, 60 bytes

l=[n^170for n in range(256)if n&n*2<1]
l.index,l.__getitem__

Try it online!

l.index compresses and l.__getitem__ decompresses. We just make a list l of all valid patterns as 8-bit numbers, except we ignore wrapping around, which still leaves 55 options which fits in 6 bits.

A useful idea is that if we flip the bits at even positions, which ^170 does, then the condition just becomes "no two 1's are (cyclically) adjacent". This is easy to check without wrapping around using the bit condition n&(n*2)==0, or shorter, n&n*2<1.

Fibonacci numbers

Binary strings with no adjacent ones have interesting connections to Fibonacci numbers. The number of such 8-bit numbers is 55, a Fibonacci number, following the general result. Moreover, Zeckendorf's Theorem tell us that each number can be uniquely expressed in the Fibonacci base without using a pair of adjacent ones, that is as a sum of distinct Fibonacci numbers without two consecutive ones, as these can be merged into the next Fibonacci number.

Perhaps a base conversion to the Zeckendorf Representation can be used for a less brute-force answer than the one here. We've had challenges to convert from and to the Zeckendorf representation, which could be used as the basis of a decoder-encoder pair.

Bonus: 64 bytes

For imaginary internet points, we can tweak the algorithm to accounts for cyclically adjacent ones, so as to limit the compression to 48 valid bit patterns from 55. We do this by modifying the bit check to n&n*2%255<1, at the cost of 4 extra bytes.

64 bytes

l=[n^170for n in range(256)if n&n*2%255<1]
l.index,l.__getitem__

Try it online!

The modulo 255 changes the bit-shift n*2 to a cyclic shift

abcdefgh -> bcdefgha

by moving the post-doubling place value of 256*a to just a. This is, except for n=255, which where n*2%255 is zero, giving a false positive at 255^170=85. But, since the bonus for imaginary internet points gives use one spare slot, with 48 slots for 47 values, we can just live with this hole.

Answer 2

K (ngn/k), 25 bytes (or 23 without imaginary internet points)

a:&&/1_|':9#2!(!8)+!8#2
a?

Try it online!

8#2 is the list 2 2 2 2 2 2 2 2

!8#2 generates an 8x256 matrix whose columns represent the bits of 0,1,..,255

!8 is 0 1 2 3 4 5 6 7

(!8)+ we add these to the corresponding rows in the matrix

2! mod 2

9# reshape to 9 rows, i.e. copy the first row after the last to ensure wrap-around (for internet points!)

|': boolean or each row with the row above it; with implicit 0 before the first

1_ drop the first

&/ boolean and-reduce over the rows - the result is a boolean mask of the encodable numbers

& where are the 1s in this mask - return list of ints

a: assign to a. the k language makes no distinction between function calls and list indexing, so a can act as the decompress function like this: a 26 -> 171

a? is a function that looks up the position of its argument in a. this is our compress function: a?171 -> 26

Answer 3

Ruby, 131 68 bytes

The most trivial answer, which generates all valid numbers (and a few extra values that aren't used) and finding the correct index.

Huge bytesaves thanks to GB, and also realizing I'm allowed to store the numbers list as a separate variable (?)

a=(0..255).select{|i|i.to_s(4)!~/1|30/}
d=->n{a[n]}
c=->n{a.index n}

Try it online!

Imaginary bonus points, 72 bytes

a=(0..255).select{|i|"%08b"%(i^85)*2!~/00/}
d=->n{a[n]}
c=->n{a.index n}

Try it online!

Answer 4

Jelly, 25 17 bytes

⁹Ḷ&Ḥ$Ðḟ^170
ị¢
Ñi

Try it online!

A set of links. The first link is shared and builds the list of possible valid 8-bit integers. The second link is the decompression link and the third handles compression. The footer compresses all the valid integers and then decompresses all the possible compressed values.

Saved 8 bytes by porting xnor’s Python answer with thanks!

Answer 5

Ruby, 89 85 74 bytes

a,b='14-7',"8abef"
f=->n{("%o"%n).tr(a,b).hex}
g=->n{("%x"%n).tr(b,a).oct}

Try it online!

Not going for the bonus points.

How:

Encode and decode using an octal-hexadecimal conversion: since some patterns cannot occur, the only allowed hex digits are [0,2,3,8,a,b,e,f]. So, if we take the hex digits and translate them to their index in the array, we get a 1- or 2-digits octal number, that is in the range 0-63. We can invert the process to decode the number.

Answer 6

05AB1E (legacy), 16 bytes

05AB1E, 17 bytes

Port of xnor's Python answer. -1 byte on legacy thanks to Kevin Cruijssen.

Compression:

ÝƵζ^x&ć¢

Decompression:

µNƵζ^x&_

Modern 05AB1E uses the same compression code, but needs an additional D in the decompression:

µNDƵζ^x&_

TIO links:

• legacy compression
• modern compression
• legacy decompression
• modern decompression

Answer 7

C++ (gcc), ^{187 \$\cdots\$ 138} 128 bytes

Saved 22 bytes thanks to S.S.Anne!!!
Saved 5 bytes thanks to ceilingcat!!!

struct F{int i,j,v[55];F(){for(i=j=0;j<55;++i)i&i*2?:v[j++]=i^170;}int c(int n){for(i=55;v[--i]-n;);n=i;}int d(int n){n=v[n];}};

Try it online!

Is a class F with member functions c and d for compression and decompression.
Uses xnor's algorithm.

Answer 8

JavaScript (ES6), 58 bytes (with bonus: 65 bytes)

I couldn't find anything shorter than a port of xnor's answer with recursive functions.

Encoder (30 bytes)

E=n=>n&&E(n-1)+!((n^=170)&2*n)

Decoder (28 bytes)

D=(n,k=n)=>E(k)^n?D(n,k+1):k

Try it online!

Bonus-compliant version, 65 bytes

With 7 more bytes in the encoder, we can output a value in \$[0..46]\$:

E=n=>n&&E(n-1)+!((n^=170)&2*n|n&n>>7)

Try it online!

---

JavaScript (ES6), 68 bytes

Another version with recursive functions. The encoder is just as long, but the decoder is 10 bytes longer.

Encoder (30 bytes)

E=n=>n&&n%16*17%61%9+8*E(n>>4)

Decoder (38 bytes)

D=n=>n&&596357088>>n%8*4&15|16*D(n>>3)

Try it online!

How?

As already pointed out by G B, there are only 8 valid nibbles for the input. We apply the following formula to map each of them to a unique value in \$[0..7]\$:

$$f(n)=((n\times17)\bmod61)\bmod9$$

Which gives:

 bin  | hex | dec | *17 | mod 61 | mod 9
------+-----+-----+-----+--------+-------
 0000 |  0  |   0 |   0 |    0   |   0
 0010 |  2  |   2 |  34 |   34   |   7
 0011 |  3  |   3 |  51 |   51   |   6
 1000 |  8  |   8 | 136 |   14   |   5
 1010 |  A  |  10 | 170 |   48   |   3
 1011 |  B  |  11 | 187 |    4   |   4
 1110 |  E  |  14 | 238 |   55   |   1
 1111 |  F  |  15 | 255 |   11   |   2

Therefore, the input \$N\$ can be encoded as:

$$f(N\bmod 16) + 8\times f(\lfloor N/16\rfloor)$$

which gives a unique value in \$[0..63]\$.

The decoder retrieves the original nibbles by using the number 0x238BAFE0 (in decimal: \$596357088\$) as a lookup table.

The conversion could also be done with this code:

(n&&n<3?n+9:44/n|4)^4

Try it online!

But this is even longer.

Answer 9

Lua 5.3, 124 122 121 bytes

s,l=string,""for n=0,255 do l=n&n*2<1 and l..s.char(n~170)or l end
f=function(n)return l:find(s.char(n),1,1),l:byte(n)end

Try it online!

Algorithm from xnor, ported to the requested language of Lua. This will only work on 5.3+, but you can get 5.2 compatibility for 24 extra bytes:

s,l=string,""for n=0,255 do l=bit32.band(n,n*2)<1 and l..s.char(bit32.bxor(n,170))or l end
f=function(n)return l:find(s.char(n),1,1),l:byte(n)end

f() does both encoding and decoding; the first return value is for encoding and the second is for decoding. If you want separate functions for both, you can use this instead of the second line (+23 bytes):

e,d=function(n)return l:find(s.char(n),1,1)end,function(n)return l:byte(n)end

This version of the algorithm varies slightly from the original by using a string to store the map rather than a list, which allows using string.find to search for the item. string.char/string.byte also make it easy to switch between number and string formats.

Answer 10

Haskell (85 bytes)

The silly version that maps to at most 54:

import Foreign
p y=2*y.&.y<1
d=filter(p.xor 170)[0..255]
f x=sum[1|y<-d,y<x]
g=(d!!)

f encodes a byte and g decodes.

The next version should be much faster, consists of a bit of bit manipulation, but covers the range from 0 to 63 and requires 92 bytes:

(#)=div
(&)=mod
(k%j)e x=k*e(x#j)&k+e(x&j)&k
f=8%16$(#128).(453*)
g=16%8$(737715168#).(16^)

Here is the expanded, hopefully more comprehensible version:

module Compress8to6Bit where

import Data.Bits (xor, shiftL, shiftR, (.|.), (.&.))
import Data.Word (Word8)

import qualified Test.QuickCheck as QC


{-
> map compressNibble [0,2,3,8,10,11,14,15]
[0,7,2,4,3,6,1,5]
-}
compressNibble :: Int -> Int
compressNibble x = shiftR (453*x) 7 .&. 7

compress :: Int -> Int
compress x =
   shiftL (compressNibble (shiftR x 4)) 3  .|.  compressNibble (x .&. 15)

decompressNibble :: Int -> Int
decompressNibble x = shiftR 0x2BF8A3E0 (x*4) .&. 15

decompress :: Int -> Int
decompress x =
   shiftL (decompressNibble (shiftR x 3)) 4  .|.  decompressNibble (x .&. 7)


inverseProp :: Word8 -> QC.Property
inverseProp byte =
   let k = fromIntegral byte
       kx = xor 0xAA k
   in kx .&. shiftL kx 1 == 0
      QC.==>
      k == decompress (compress k)

How?

I found the multiplication trick of Arnauld interesting and found that you can do without modulo but simple shift and masking when using the factor 453.

But after all you could also encode dictionaries for compression and decompression (on a 32-bit machine you need to use Int64 instead of Int):

compressNibble :: Int -> Int
compressNibble x = shiftR 0o7600540300002100 (x*3) .&. 7

decompressNibble :: Int -> Int
decompressNibble x = shiftR 0xFEBA8320 (x*4) .&. 15

This one only needs 16 bit for the dictionary but requires popCount:

compressNibble :: Int -> Int
compressNibble x = popCount (0x6686 .&. (shiftL 1 x - 1) :: Int)

Answer 11

Ruby, 88 bytes

(with imaginary bonus points)

a=[170]+(6..51).map{|i|"UJEBA@D"[i/8].ord*257>>i%8&255^170}
f=->n{a[n]}
g=->n{a.index n}

76 bytes if it is OK to check the array a directly instead of using f to do it.

Try it online!

I can't beat GB's excellent answer, but this is the shortest Ruby answer claiming the imaginary bonus points so far.

The question asks for all bytes where the even bits are less or equal to than the adjacent odd bits. An equivalent definition is all bytes where the odd bits are greater than or equal to the adjacent even bits, so overall the set is symmetrical.

There is only one possible byte where all even bits are strictly less than the adjacent odd bits, this is 10101010, decimal 170. The other 46 bytes where the even bits are less than or equal to the adjacent odd bits can be found by XORing this number with all possible bytes with no adjacent 1's. These comprise 7 distinct patterns and their bitwise rotations as listed below.

We build an array of the 47 bytes by XORing 10101010 with the patterns below, then use lookup and index functions to carry out the conversion.

Pattern  ASCII number of rotations
01010101  U    2
01001010  J    8
01000101  E    8
01000010  B    8
01000001  A    8
01000000  @    8
01000100  D    4

Total 46 (plus 00000000)         

Answer 12

Charcoal, 54 bytes

Ｆ²⁵⁶Ｆ¬＆ι⊗ι⊞υ⁻｜ι¹⁷⁰＆ι¹⁷⁰Ｉ⌕υＮ

Try the encoder online! Link is to verbose version of code.

Ｆ²⁵⁶Ｆ¬＆ι⊗ι⊞υ⁻｜ι¹⁷⁰＆ι¹⁷⁰Ｉ§υＮ

Try the decoder online! Link is to verbose version of code.

Just the usual table-driven lookup approach. Explanation:

Ｆ²⁵⁶

Loop over the 256 binary values.

Ｆ¬＆ι⊗ι

Check that no two adjacent bits are set.

⊞υ⁻｜ι¹⁷⁰＆ι¹⁷⁰

Flip the odd bits and save the result to the lookup table.

Ｉ⌕υＮ

Look up the index of the input in the table.

Ｉ§υＮ

Look up the input index in the table.

Rather than create a table of Fibbinary numbers by filtering out invalid numbers, I attempted a mathematical approach which calculates successive Fibbinary numbers, but the encoder was 48 bytes and the decoder was 40 bytes:

≔⁰η≔⁰ζＷ⁻⁻｜η¹⁷⁰＆η¹⁷⁰θ«≦⊕ζ≔⊕｜η÷η²ι≧＆±ιι≔×ι⊕÷ηιη»Ｉζ
≔⁰ηＦＮ«≔⊕｜η÷η²ι≧＆±ιι≔×ι⊕÷ηιη»Ｉ⁻｜η¹⁷⁰＆η¹⁷⁰

Explanation:

≔⁰η

Initialise the Fibbinary number h to 0.

≔⁰ζＷ⁻⁻｜η¹⁷⁰＆η¹⁷⁰θ«≦⊕ζ

(Encoder) Initialise the encoding index to 0. Repeat until the desired Fibbinary number is found. Increment the encoding index...

ＦＮ«

(Decoder) Repeat the desired number of times.

≔⊕｜η÷η²ι≧＆±ιι≔×ι⊕÷ηιη»

Find the lowest value of k where h&3<<k is zero. Clear the bottom k bits of h and increment the next bit, which gives the next Fibbinary number.

Ｉζ

(Encoder) Output the number of loops taken.

Ｉ⁻｜η¹⁷⁰＆η¹⁷⁰

(Decoder) Output the XOR of the Fibbinary number with 170.