15
\$\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.

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\$
5
  • \$\begingroup\$ I wanna see the decompression function. \$\endgroup\$
    – Joshua
    May 8 at 3:18
  • 2
    \$\begingroup\$ @Joshua Here you go. I had it prepared. \$\endgroup\$
    – Steffan
    May 8 at 3:20
  • \$\begingroup\$ suggested test cases: "aaaaaaaa","a" and "aaaaaaaa","ab" to check that maxBitCount is correctly calculated \$\endgroup\$
    – MarcMush
    May 9 at 12:57
  • \$\begingroup\$ May I assume the encoder string contains less than 256 chars? \$\endgroup\$
    – tsh
    May 9 at 14:15
  • \$\begingroup\$ @tsh Yes, that's fine. \$\endgroup\$
    – Steffan
    May 9 at 16:26

13 Answers 13

10
\$\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\$
1
  • 3
    \$\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\$
    – Steffan
    May 6 at 22:35
6
\$\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\$
4
\$\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 at 21:27
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\$

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\$
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\$
    – Steffan
    May 6 at 22:49
  • \$\begingroup\$ @Steffan Thanks! :D \$\endgroup\$
    – Noodle9
    May 6 at 22:54
  • \$\begingroup\$ index can also be replaced with find for -1 byte :) \$\endgroup\$
    – friddo
    May 6 at 23:06
  • \$\begingroup\$ @friddo Just did that, thanks anyway! :) \$\endgroup\$
    – Noodle9
    May 6 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\$

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\$
1
\$\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 at 13:11
1
\$\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\$
4
  • \$\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\$
    – Steffan
    May 9 at 18:08
  • \$\begingroup\$ Actually 119 bytes. \$\endgroup\$
    – Steffan
    May 9 at 18:10
  • \$\begingroup\$ btw you forgot to remove the statement that the character codes should be in variable s and etc \$\endgroup\$
    – Steffan
    May 9 at 18:18
  • \$\begingroup\$ @Steffan the format of the two parameters of the lambda is still important \$\endgroup\$
    – SztupY
    May 9 at 18:19
0
\$\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, privacy policy and cookie policy

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