24
\$\begingroup\$

Given a string and the characters used to encode it, you need to compress the string by only using as many bits as each character needs. You will return the character codes for each character needed to create a compressed string.

For example, given the string "the fox" and the encoder characters " abcdefghijklmnopqrstuvwxyz", the output should be [170, 76, 19, 195, 32].

How, though?

First, you need to map each encoder character to some bits. If we have the encoder characters abc, then we can map the characters to bits, by mapping the character to the position of the character in binary, like this:

a => 01
b => 10
c => 11

With 13579, we would map it like this:

1 => 001
3 => 010
5 => 011
7 => 100
9 => 101

Note that we pad zeros at the beginning as many as necessary.

Next, we would go through the string, and for each character, we would get the corresponding bits for that character. Then join all the bits together, and then convert to chunks of 8 to get the bytes. If the last byte is not 8 bits long, add zeros at the end till it is 8 bits long. Lastly, convert each byte to its decimal representation.

Reverse challenge is here.

Test cases

String: "the fox", encoder characters: " abcdefghijklmnopqrstuvwxyz" => [170, 76, 19, 195, 32]
String: "971428563", encoder characters: "123456789" => [151, 20, 40, 86, 48]
String: "the quick brown fox jumps over the lazy dog", encoder characters: " abcdefghijklmnopqrstuvwxyz" => [170, 76, 25, 89, 68, 96, 71, 56, 97, 225, 60, 50, 21, 217, 209, 160, 97, 115, 76, 53, 73, 130, 209, 111, 65, 44, 16]
String: "abc", encoder characters: "abc" => [108]
String: "aaaaaaaa", encoder characters: "a" => [255]
String: "aaaabbbb", encoder characters: "ab" => [85, 170]

Rules

  • Inputs can be a string, list, or even list of character codes. It doesn't matter, I/O is very flexible for this challenge.
  • Input will always be valid, e.g. the string will never include characters not in the encoder characters, etc.
  • Encoder characters will always contain **less than 256 characters.
  • Neither input will ever be empty.
  • This is , so the shortest answer in bytes for each language wins.
  • Standard I/O rules apply.
  • Default loopholes are forbidden.

Reference implementation in JavaScript

function encode(str, encoderChars) {
  const maxBitCount = Math.ceil(Math.log2(encoderChars.length + 1));
  const charToBit = Object.fromEntries(encoderChars.map((c, i) => [c, (i + 1).toString(2).padStart(maxBitCount, "0")]));
  const bits = [...str].map((c) => charToBit[c]).join("");
  const bytes = bits.match(/.{1,8}/g) || [];
  return bytes.map((x) => parseInt(x.padEnd(8, '0'), 2));
}

Attempt This Online!

\$\endgroup\$
6
  • \$\begingroup\$ I wanna see the decompression function. \$\endgroup\$
    – Joshua
    May 8, 2022 at 3:18
  • 3
    \$\begingroup\$ @Joshua Here you go. I had it prepared. \$\endgroup\$
    – naffetS
    May 8, 2022 at 3:20
  • 1
    \$\begingroup\$ suggested test cases: "aaaaaaaa","a" and "aaaaaaaa","ab" to check that maxBitCount is correctly calculated \$\endgroup\$
    – MarcMush
    May 9, 2022 at 12:57
  • \$\begingroup\$ May I assume the encoder string contains less than 256 chars? \$\endgroup\$
    – tsh
    May 9, 2022 at 14:15
  • 1
    \$\begingroup\$ To tag along with @MarcMush , test case "aaaaaaaa","ab" -> [85, 85] should be added. \$\endgroup\$
    – Giuseppe
    May 24, 2022 at 13:15

17 Answers 17

11
\$\begingroup\$

Vyxal, 19 bytes

¹żb:∩L∆ZĿf8ẇR8∆ZRvB

Try it Online!

        Ŀ           # Replace each element of <the key> in <the input>
                    # with the corresponding value of...
¹ż                  # 1...len(key)
  b                 # Convert each to binary
      ∆Z            # left-pad each with zeroes to length
   :∩L              # The maximum length - the length when transposed
         f8ẇ        # Reshape into chunks of 8
            R   R   # With each reversed...
             8∆Z    # Left-pad to length 8 (so right-pad)
                 vB # Convert each back from binary
\$\endgroup\$
2
  • 5
    \$\begingroup\$ That surprised me when I clicked on bytes, lol. i honestly thought that if it didn't go to the codepage, it would be a rickroll \$\endgroup\$
    – naffetS
    May 6, 2022 at 22:35
  • \$\begingroup\$ damn we got chat-rolled \$\endgroup\$
    – zoomlogo
    May 24, 2022 at 15:13
8
\$\begingroup\$

JavaScript (ES7),  124 122  117 bytes

Expects (encoder_characters)(string), where string is passed as an array of characters.

(b,o=k=[],i=32)=>g=a=>(i+=~Math.log2(b.length),k|=b.indexOf(a.shift())+1<<i)?g(a,i<25&&(o.push(k>>>24),k<<=8,i+=8)):o

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Jelly, 21 bytes

JBUz0ZU⁸,yFŻ8¡s8z0ZḊḄ

Try It Online!

JBUz0ZU⁸,yFŻ8¡s8z0ZḊḄ  Main Link
J                      Generate [1, 2, ...] as long as the encoding list
 B                     Convert to binary
  Uz0ZU                Reverse, transpose padding with 0, transpose, reverse (*)
       ⁸,              Pair the encoding list with the padded binary list
         y             Use this to translate the message into binary strings
          F            Flatten
           Ż8¡         Prepend 0 8 times (in case the list is shorter than 8)
              s8       Slice into blocks of 8
                z0Z    Transpose padding with 0, transpose (**)
                   Ḋ   Remove the block of 8 zeroes at the start
                    Ḅ  Convert from binary into numbers

(*)  this is a common pattern used to left-pad everything to the same length
(**) this is a common pattern used to right-pad everything to the same length -
     because we prepended a block of 8 zeroes, there is at least one sublist
     of length 8, so everything will be padded to length 8
\$\endgroup\$
1
  • \$\begingroup\$ Enumerating all of the encodings then translating is a brilliant way to make sure they're all the right length! I was trying iⱮ;L{’ lmao \$\endgroup\$ May 6, 2022 at 21:27
4
\$\begingroup\$

Python, 115 bytes

lambda s,e,o=0:[*sum(-~e.find(x)<<8*(L:=(l:=len(f"{len(e):b}"))*len(s)+7>>3)-(o:=o+l)for x in s).to_bytes(L,'big')]

Attempt This Online!

Old Python, 122 bytes

def f(s,e,o=0):
 for x in s:o<<=(l:=len(f"{len(e):b}"));o-=~e.find(x)
 l*=len(s);return[*(o<<-l%8).to_bytes(l+7>>3,'big')]

Attempt This Online!

\$\endgroup\$
3
\$\begingroup\$

Retina, 90 bytes

L$`(.?)(?=.*(¶.*)(?!$)\1)
$.2*
+`(_+)\1
$1 
 _
_
P^`.+
.+$
7* 
¶

L`.{8}
_
 _
+`_ 
 __
%`_

Try it online! Explanation:

L$`(.?)(?=.*(¶.*)(?!$)\1)
$.2*

Get the 1-indexed indices of all of the input string's characters in the encoder characters, plus the number of encoder characters.

+`(_+)\1
$1 
 _
_

Convert to binary using the custom base conversion characters _.

P^`.+

Left-pad all of the binary strings to the width of the binary number of encoder characters.

.+$
7* 

Replace the binary number of encoder characters with seven spaces.

Join the binary strings together.

L`.{8}

Split into strings of length 8, ignoring any trailing spaces.

_
 _
+`_ 
 __
%`_

Convert from the custom binary to decimal.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 128 120 118 bytes

First attempt, probably some ways to make it more optimal

->s,x{s.map{(x.index(_1)+1).to_s(2).rjust Math.log2(x.size+1).ceil,?0}.join.scan(/.{1,8}/).map{_1.ljust(8,?0).to_i 2}}

s should be the character codes of the input string and x should be the character codes of the encoder. Returns an array of character codes.

Attempt this online!

\$\endgroup\$
3
  • \$\begingroup\$ Per the current consensus, taking input from a variable is not allowed. However, you can just use an anonymous function for 129 bytes, and with some golfs, 121 bytes. \$\endgroup\$
    – naffetS
    May 9, 2022 at 18:08
  • \$\begingroup\$ Actually 119 bytes. \$\endgroup\$
    – naffetS
    May 9, 2022 at 18:10
  • \$\begingroup\$ @Steffan the format of the two parameters of the lambda is still important \$\endgroup\$
    – SztupY
    May 9, 2022 at 18:19
2
\$\begingroup\$

Factor, 123 bytes

[ dup length [1,b] dup last log2 1 + '[ >bin _ 48 pad-head ] map zip substitute concat 8 group [ 8 48 pad-tail bin> ] map ]

Try it online!

Explanation

Takes the string as an array of codepoints and the encoder characters as a string.

                        ! { 57 55 49 52 50 56 53 54 51 } "123456789"
dup                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" "123456789"
length                  ! { 57 55 49 52 50 56 53 54 51 } "123456789" 9
[1,b]                   ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 }
dup                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } { 1 2 3 4 5 6 7 8 9 }
last                    ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 9
log2                    ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 3
1 +                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } 4
'[ >bin _ 48 pad-head ] ! { 57 55 49 52 50 56 53 54 51 } "123456789" { 1 2 3 4 5 6 7 8 9 } [ >bin 4 48 pad-head ]
map                     ! { 57 55 49 52 50 56 53 54 51 } "123456789" { "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" }
zip                     ! { 57 55 49 52 50 56 53 54 51 } { { 49 "0001" } { 50 "0010" } { 51 "0011" } { 52 "0100" } { 53 "0101" } { 54 "0110" } { 55 "0111" } { 56 "1000" } { 57 "1001" }
substitute              ! { "1001" "0111" "0001" "0100" "0010" "1000" "0101" "0110" "0011" }
concat                  ! "100101110001010000101000010101100011"
8 group                 ! { "10010111" "00010100" "00101000" "01010110" "0011" }
[ 8 48 pad-tail bin> ]  ! { "10010111" "00010100" "00101000" "01010110" "0011" } [ 8 48 pad-tail bin> ]
map                     ! { 151 20 40 86 48 }
\$\endgroup\$
2
\$\begingroup\$

Python 3, 133 132 131 bytes

def f(s,e):w=len(f"{len(e):b}");return[int((''.join(f'{e.find(c)+1:0{w}b}'for c in s)+8*'0')[i:i+8],2)for i in range(0,len(s)*w,8)]

Try it online!

Saved a byte thanks to Steffan!!!

\$\endgroup\$
4
  • \$\begingroup\$ well u can remove the space after return (sorry for fgitw lol) \$\endgroup\$
    – naffetS
    May 6, 2022 at 22:49
  • \$\begingroup\$ @Steffan Thanks! :D \$\endgroup\$
    – Noodle9
    May 6, 2022 at 22:54
  • \$\begingroup\$ index can also be replaced with find for -1 byte :) \$\endgroup\$
    – friddo
    May 6, 2022 at 23:06
  • \$\begingroup\$ @friddo Just did that, thanks anyway! :) \$\endgroup\$
    – Noodle9
    May 6, 2022 at 23:25
2
\$\begingroup\$

Charcoal, 26 bytes

IE⪪⭆θ◧⍘⊕⌕ηι !L↨L粦⁸⍘◨ι⁸ !

Try it online! Link is to verbose version of code. Explanation:

    θ                       Input string
   ⭆                        Map over characters and join
         η                  Encoder characters
        ⌕                   Find 0-based index of
          ι                 Current character
       ⊕                    Incremented
      ⍘                     Custom base conversion using
            !               Literal string ` !`
     ◧                      Left-padded to length
                η           Encoder characters
               L            Length
              ↨             Converted to base
                 ²          Literal integer `2`
             L              Length
  ⪪                         Split into substrings of length
                   ⁸        Literal integer `8`
 E                          Map over substrings
                      ι     Current substring
                     ◨      Right-padded to length
                       ⁸    Literal integer `8`
                    ⍘       Custom base conversion using
                         !  Literal string ` !`
I                           Cast to string
                            Implicitly print
\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 45 bytes

Prompts for string followed by encoder characters:

2⊥⍉(m,8)⍴(8×m←⌈(⍴n)÷8)↑n←,⍉((⌈2⍟⌈/n)⍴2)⊤n←⎕⍳⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
1
  • \$\begingroup\$ there is an error for "aa","a" and no output for "aa","ab" \$\endgroup\$
    – MarcMush
    May 9, 2022 at 13:11
2
\$\begingroup\$

05AB1E, 17 bytes

āb¤g°+€¦‡¾8׫8ô¨C

Inputs in reversed order, with the encoding string as first input.

Try it online or verify all test cases.

Explanation:

ā          # Push a list in the range [1, (implicit) first input-length]
 b         # Convert each to a binary string
  ¤g°+€¦   # Right-pad with 0s to make them all the same length:
  ¤        #  Push the last/longest binary-string
   g       #  Pop and push its length
    °      #  Pop and push 10 to the power this length
     +     #  Add it to each binary
      €¦   #  Remove the leading 1 from each
‡          # Transliterate all characters in the first input to these
           # binary-strings in the second (implicit) input
 ¾8×       # Push a string of 8 0s: "00000000"
    «      # Append the strings together
     8ô    # Split it into parts of size 8
       ¨   # Remove the trailing part
        C  # Convert all binary-strings to integers
           # (after which it is output implicitly as result)

¤g°+€¦ could alternatively be ¤gjð0: for the same byte-count:

  ¤g       #  Same as above to get the length
    j      #  Pad each with leading spaces up to this length
     ð0:   #  Replace all spaces with 0s
\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 116 bytes

lambda s,e,j=''.join:map(lambda*a:int(j(a),2),*[iter(j(f"{e.find(c)+1:0{len(bin(len(e)))-2}b}"for c in s)+7*'0')]*8)

Try it online!

Using xnor's zip/iter trick for chunkification (but with map instead).

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

PARI/GP, 90 bytes

f(s,e)=digits(fromdigits([[i|i<-[1..#e],e[i]==c][1]|c<-s],2^l=#binary(#e))<<(-l*#s%8),256)

Attempt This Online!

Inputs lists of characters.

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

Desmos, 304 265 bytes

g=[1...Q][c=s[floor(i/q)+1]][1]
Q=c.length+1
q=ceil(log_2Q)
l=[floor(log_2g)...0]
k=\{q=l[1]+1:[],[2...q-l[1]]0\}
d=[join(k,mod(floor(g/2^l),2))[mod(i,q)+1]fori=[0...qs.length-1]]
v=join(d,[1...8]0)[8u-7...8u]
f(s,c)=[total(2^{[7...0]}v)foru=[1...ceil(d.length/8)]]

Both inputs are list of codepoints, as is output. This took me a long time.

Try it on Desmos!

-39 bytes thanks to Aiden Chow

\$\endgroup\$
5
  • \$\begingroup\$ You can take out the \left and \right in d to save some bytes (don't forget to add a backslash before join, mod, and length). \$\endgroup\$
    – Aiden Chow
    May 23, 2022 at 7:18
  • \$\begingroup\$ Here's a 277 bytes version that seems to work. Also I have to say, this is really impressive, even though I don't have the foggiest idea what the challenge is asking for, or what this code is even doing :P \$\endgroup\$
    – Aiden Chow
    May 23, 2022 at 7:36
  • \$\begingroup\$ This 268 bytes version somehow works... \$\endgroup\$
    – Aiden Chow
    May 23, 2022 at 7:57
  • \$\begingroup\$ 265 bytes \$\endgroup\$
    – Aiden Chow
    May 23, 2022 at 8:01
  • \$\begingroup\$ 256 bytes (Idk how, but I just stumbled across this post again...) \$\endgroup\$
    – Aiden Chow
    Oct 26, 2022 at 7:22
2
\$\begingroup\$

MATL, 17 bytes

&m2Gt&mBwY)!8e!XB

Try it online!

Of note, B returns a matrix with the binary strings as rows, so they are automatically padded to the same length.

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

Uiua, 30 bytes*

or 69 bytes using native UTF-8 encoding

▽±.⍘⋯≡⇌↯⊂¯1 8≡⇌⬚0⊂∶×0⋯⧻∶⋯+1⊗⊙.

Try it!


*See answer to the reverse challenge here and here for a single-byte-character-system (SBCS) encoding.

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

Julia 1.7, 125 bytes

s\e=parse.(Int,only.(eachmatch(r"(.{8})",join(string.(findlast.(s,e);base=2,pad=floor(Int,log2(2length(e)))))*"0"^7)),base=2)

Attempt This Online!

expects s as a list of characters and e a string. Needs Julia 1.7 for only(::RegexMatch)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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