27
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ what's the relationship with lua? the challenge looks lang-netural \$\endgroup\$ – ngn Feb 7 at 5:26
  • 2
    \$\begingroup\$ @ngn I actually need a solution in lua for a real project. I can port one of the other answers, but I figured I'd at least give a small nudge in that direction in case it inspired anyone \$\endgroup\$ – Sparr Feb 7 at 5:56
  • 19
    \$\begingroup\$ just make a lookup table... codegolf solution will be terrible \$\endgroup\$ – Sopel Feb 7 at 11:41
  • 1
    \$\begingroup\$ @JohnDvorak Although true, it's probably both easier and less confusing to have a hard-coded look-up table (with some comments explaining it) in the real-life Lua project than anything a code-golf answer would come up with. Code-golf is all about saving bytes, so things like readability, comments, coding standards, getting rid of warnings/errors, performance, and more are all irrelevant as long as we can save a single byte and it still gives the same results. If a byte can be saved but in the process the execution time goes from 0.1 sec. to 10 min., we don't care, because: yay, 1 less byte! ;) \$\endgroup\$ – Kevin Cruijssen Feb 7 at 14:16
  • 1
    \$\begingroup\$ @S.S.Anne point rewards for stretch goals are discouraged. Either they end up being irrelevant for good score, or mandatory. \$\endgroup\$ – John Dvorak Feb 9 at 10:49

12 Answers 12

20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ shouldn't len(l) be 47? \$\endgroup\$ – ngn Feb 7 at 5:13
  • \$\begingroup\$ I'm using the longer list which doesn't count wraparound, which is a superset. But I guess for checking let me use the correct l. \$\endgroup\$ – xnor Feb 7 at 5:15
  • \$\begingroup\$ no bonus points though :) \$\endgroup\$ – ngn Feb 7 at 5:22
6
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ If you toggle every second bit, you only have to check for a double zero (or a zero at each end): "%08b"%(i^85)!~/00|^0.*0$/ \$\endgroup\$ – G B Feb 7 at 7:53
  • \$\begingroup\$ Even shorter: "%08b"%(x^85)*2!~/00/ \$\endgroup\$ – G B Feb 7 at 8:08
  • \$\begingroup\$ Or even x.to_s(4)!=/1|30/ (without bonus) \$\endgroup\$ – G B Feb 7 at 12:29
  • \$\begingroup\$ @GB I should have looked at this sooner lol \$\endgroup\$ – Value Ink Feb 13 at 23:03
2
\$\begingroup\$

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:

\$\endgroup\$
  • 1
    \$\begingroup\$ -1 byte by switching to the legacy version and removing the D in the decompression-program, since the N is output implicitly after the µ. Every builtin used was already available in the legacy version in both the compression and decompression programs by the looks of it. \$\endgroup\$ – Kevin Cruijssen Feb 7 at 13:52
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might be able to squeeze a few more out by defining i and j at the class scope. Stinks that the return trick doesn't work here. \$\endgroup\$ – S.S. Anne Feb 7 at 18:06
  • \$\begingroup\$ 146 bytes \$\endgroup\$ – S.S. Anne Feb 7 at 18:13
  • \$\begingroup\$ @S.S.Anne Clever use of class scope - thanks! :-) \$\endgroup\$ – Noodle9 Feb 7 at 18:17
  • \$\begingroup\$ @S.S.Anne Check it out, the return trick does work here! :-) \$\endgroup\$ – Noodle9 Feb 8 at 0:13
  • \$\begingroup\$ It didn't when I tried it. \$\endgroup\$ – S.S. Anne Feb 8 at 0:34
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)         
\$\endgroup\$
  • \$\begingroup\$ a=(6..51).map{...}<<170 saves 1 byte. I really like the way you encoded everything in a different order than normal! Also, I'm sorry to inform you that after implementing GB's suggestions on my Ruby answer you are unfortunately no longer the shortest with imaginary points ;) \$\endgroup\$ – Value Ink Feb 13 at 23:09
1
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to the site. It is nice to see people using Haskell, but this is a code-golf competition. Just as it is rude to show up to a soccer game and decide you are going pursue the maximum number passes rather than goals, we ask that you make an attempt at the scoring provided. You can still write fast answers, but you need to put in a show of good faith towards the scoring criterion. \$\endgroup\$ – Post Rock Garf Hunter Feb 10 at 0:54
  • \$\begingroup\$ I agree with @PostRockGarfHunter on this one. May I suggest trying to write a golfed answer in Haskel, putting it first in your answer, and then putting the fast answer, as it in fact may be of interest to OP, but shouldn't be the main point of your answer. \$\endgroup\$ – Mr Redstoner Feb 10 at 12:08
  • \$\begingroup\$ Where did the original poster requested a solution with a minimal number of characters of the program? \$\endgroup\$ – Lemming Feb 10 at 12:20
  • \$\begingroup\$ It seems there is a pretty narrow understanding of Code Golf. What is the discipline to find speedy or ressource saving or otherwise elegant solutions to a problem? \$\endgroup\$ – Lemming Feb 10 at 12:28
  • \$\begingroup\$ The OP should have indicated this in their question directly, but instead left the code-golf tag to indicate. I am of the opinion that this sort of behavior is unnecessarily hostile to newcomers, as it obscures what the challenge is actually about. But some users do it so you do have to check the tags. To answer your other question speediness is generally fastest-code but this is much harder to measure than code length so there are objectivity issues. \$\endgroup\$ – Post Rock Garf Hunter Feb 10 at 14:02
0
\$\begingroup\$

Charcoal, 54 bytes

F²⁵⁶F¬&ι⊗ι⊞υ⁻|ι¹⁷⁰&ι¹⁷⁰I⌕υN

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

F²⁵⁶F¬&ι⊗ι⊞υ⁻|ι¹⁷⁰&ι¹⁷⁰I§υN

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

Just the usual table-driven lookup approach. Explanation:

F²⁵⁶

Loop over the 256 binary values.

F¬&ι⊗ι

Check that no two adjacent bits are set.

⊞υ⁻|ι¹⁷⁰&ι¹⁷⁰

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

I⌕υN

Look up the index of the input in the table.

I§υN

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:

≔⁰η≔⁰ζW⁻⁻|η¹⁷⁰&η¹⁷⁰θ«≦⊕ζ≔⊕|η÷η²ι≧&±ιι≔×ι⊕÷ηιη»Iζ
≔⁰ηFN«≔⊕|η÷η²ι≧&±ιι≔×ι⊕÷ηιη»I⁻|η¹⁷⁰&η¹⁷⁰

Explanation:

≔⁰η

Initialise the Fibbinary number h to 0.

≔⁰ζW⁻⁻|η¹⁷⁰&η¹⁷⁰θ«≦⊕ζ

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

FN«

(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.

Iζ

(Encoder) Output the number of loops taken.

I⁻|η¹⁷⁰&η¹⁷⁰

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.