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)
4what's the relationship with lua? the challenge looks lang-netural – ngn – 2020-02-07T05:26:13.743
2@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 – Sparr – 2020-02-07T05:56:55.050
19just make a lookup table... codegolf solution will be terrible – Sopel – 2020-02-07T11:41:43.027
@Sopel the codegolf solution is to make a lookup table :P – John Dvorak – 2020-02-07T13:52:53.220
1@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! ;) – Kevin Cruijssen – 2020-02-07T14:16:29.653
Is the upper bound of $48$ for the bonus another constraint of your project? Otherwise, why not $46$ (0-indexed) or $47$ (1-indexed)? – Arnauld – 2020-02-07T16:32:08.467
@Sopel While I do agree in this particular case, it may occasionally be more efficient both size-wise and speed-wise to do some bitwise magic instead of using a lookup table if the code is executed on a platform where accessing memory is much slower than using the CPU registers. (It was especially true back in the day when there was no CPU cache.) – Arnauld – 2020-02-07T16:49:19.293
@Arnauld I would be REALLY surprised if this has a reasonable solution using only bitwise arithmetic – Sopel – 2020-02-07T17:00:39.277
@Sopel the environment I will be applying this algorithm to has limits on code size (and code tokens) that are far more restrictive than its limits on memory or runtime, so constructing a lookup table (as many of the answers do) is a great solution for me. – Sparr – 2020-02-07T20:01:00.707
@Arnauld 48 as a maximum was a mistake, it should have been 48 values and thus a max of 47 (zero indexed) all along. The motivation being to save another "half bit" that I could use to store additional information. Squeezing out a single additional value (to get to 47 total values instead of 48) would be almost useless to me. – Sparr – 2020-02-07T20:04:00.050
@Sopel: Keep in mind that some modern x86 CPUs include things like the
– Peter Cordes – 2020-02-07T20:25:32.730pext
parallel bit-extract instruction. I think a LUT is still probably best for this complicated a pattern, especially if you use it often enough to be likely to be in L2 cache at least, or for OoO exec to hide most of the cache miss latency, but It's harder to rule out bit-hack being possible. (Unfortunately only Intel CPUs have efficient implementations; AMD's pext is pretty slow. And also even modern Pentium/Celeron chips lack BMI2, making baseline BMI1/2 no closer :(This is basically xor 170 and list unique values in base phi... but I don't know an esolang that has the right builtin. – jimmy23013 – 2020-02-09T05:04:54.993
1@S.S.Anne point rewards for stretch goals are discouraged. Either they end up being irrelevant for good score, or mandatory. – John Dvorak – 2020-02-09T10:49:14.497