16
\$\begingroup\$

The JavaScript compressor RegPack uses a very simple string compression algorithm. Given a piece of code, it will make a list of characters that aren't used in that code and use them to delimit repeated strings that are inserted back into the string.

To show how strings are compressed, it's necessary to show how the decompressor works. If you give RegPack the tongue-twister How much wood would a woodchuck chuck if a woodchuck could chuck wood?, it will spit out How much } w|a }~~if a }~c|~}?~chuck }wood|ould along with the list of characters |}~.

The decompressor starts by splitting this string on the first character in the char list, |, resulting in ["How much } w", "a }~~if a }~c", "~}?~chuck }wood", "ould "]. It then pops the last item, "ould ", and joins what remains by this, resulting in "How much } would a }~~if a }~could ~}?~chuck }wood".

It then does the same thing for }, replacing } with wood to result in "How much wood would a wood~~if a wood~could ~wood?~chuck ", and finally replaces ~ with "chuck " to result in the whole thing, How much wood would a woodchuck chuck if a woodchuck could chuck wood?.

The advantage of this algorithm is that it's very simple and short to implement. RegPack itself implements it in 39 bytes of JavaScript: for(i of<chars>)with(_.split(i))_=join(pop()) (where <chars> is a hardcoded char list), which basically performs the steps described above.

Your challenge is to, given a compressed string and a list of characters, decompress it using the above algorithm.

Testcases

'a|b|c|hello', '|' => ahellobhelloc
'He||o, wor|d!|l', '|' => Hello, world!
'| | & &&|house|green', '|&' => green green greenhouse greenhouse
'N~give}up,n~let}down~ever gonna } you ', '}~' => Never gonna give you up,never gonna let you down
'How much } w|a }~~if a }~c|~}?~chuck }wood|ould ', '|}~' => How much wood would a woodchuck chuck if a woodchuck could chuck wood?
'She sells~ells by the~ore~ sea sh', '~' => She sells sea shells by the sea shore
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Rick Rolled by test cases :-) \$\endgroup\$ Oct 4 at 2:11
  • \$\begingroup\$ Does the encoding guarantees that no characters in the second string will be "0"? \$\endgroup\$
    – Kaddath
    Oct 4 at 10:53
  • \$\begingroup\$ @Kaddath Nope, there are no guarantees about the contents of the string \$\endgroup\$
    – emanresu A
    Oct 4 at 19:01

14 Answers 14

6
\$\begingroup\$

05AB1E, 6 5 bytes

-1 thanks to @KevinCruijssen

vy¡`ý

Try it online!

Explanation

v      # for each char in the char list
 y      # push it
 ¡      # split the current string by it
 `      # dump the parts to stack
 ý      # join the stack by the last part
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte if you replace Áć with `: try it online. It will join the items on the stack with the top item as delimiter. \$\endgroup\$ Oct 4 at 8:32
5
\$\begingroup\$

Husk, 7 bytes

F(↔ΓJx↔

Try it online!

Explanation

F(↔ΓJx↔
F        For each character in the character list:
      ↔    flip the string
     x     split it on the given character
   ΓJ      use the first element to join the rest of the list
  ↔        flip the string back

Why all that flipping back and forth? Because in Husk it's often easier to operate on the first element of a list than the last (Γ here does exactly that). We could manually take the last element and everything except that, but the program would have the same length: F(§J→hx

We could solve the challenge in 5 bytes (F(ΓJx) if we were allowed to operate on the reversed string, or to have the changes listed at the beginning of the string.

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

Retina 0.8.2, 45 bytes

+`(?=.*¶(.))\1((?=.*\1(.+))|.+)|(?<=¶).|¶$
$3

Try it online! No test suite because I can't think of a good separator between the two strings. Explanation:

+`

Repeat for each character in the list.

(?=.*¶(.))\1((?=.*\1(.+))|.+)|(?<=¶).|¶$
$3

Search the string for occurrences of the first character in the list, and try to replace it with the word after the last occurrence, otherwise delete the last occurrence and the word after it. Finish by deleting the character from the list and the list itself once the last character has been processed.

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

Ruby, 41 bytes

->s,l{l.chars{|x|*k,w=s.split x;s=k*w};s}

Try it online!

Not particularly original, I guess.

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by taking an array for l and another couple by using _1 in place of x, which TiO still doesn't like. ato.pxeger.com/… \$\endgroup\$
    – Jordan
    Oct 4 at 16:54
3
\$\begingroup\$

Jelly, 6 bytes

ṣjṪ$¥ƒ

Try it online!

Takes the delimiters on the left and the compressed string on the right.

    ¥ƒ    Reduce the delimiters by, starting with the compressed string:
ṣ         Split on the delimiter
 j        and join that on
  Ṫ$      its last element (removed).
\$\endgroup\$
2
\$\begingroup\$

PowerShell Core, 74 bytes

param($t)$args|%{$j=($o=$t|% S*t $_)[-1]
$t=$o[0..($o.Count-2)]-join$j}
$t

Try it online!

Or using ""::Join

Or using $ofs

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

Go, 121 bytes

import."strings"
type S=string
func f(s,c S)S{for _,r:=range c{L:=Split(s,S(r))
l:=len(L)-1
s=Join(L[:l],L[l])}
return s}

Attempt This Online!

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

Perl 5 -lp, 64, 61 bytes

s/(\S+) //;for$c($1=~/./g){@a=split/\Q$c/;$_=join pop(@a),@a}

Try it online!

Another using regex

Perl 5 -lp, 64, 54 bytes

s/^(\S)(?|.*\K\1(?=.*\1(.*)$)|(.*)\1.*)/$2/&&redo;s; ;

Try it online!

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

Java 10, 121 101 99 bytes

a->s->{int i;for(var c:a)s=s.substring(0,i=s.lastIndexOf(c)).replace(c,s.substring(i+1));return s;}

-17 bytes (and an additional -3 implicit) thanks to @NahuelFouilleul by using substrings instead of split to an array.
-2 bytes thanks to @ceilingcat.

Try it online.

Explanation:

a->s->{                    // Method with String-array & String parameters and String return
  int i;                   //  Index-integer `i`, starting uninitialized
  for(var c:a)             //  Loop over the input-characters:
    s=                     //   Overwrite String `s` with:
      s.substring(0,i=s.lastIndexOf(c))
                           //    A substring until (excluding) the last occurrence of the
                           //    current character (and also set `i` to this last index
                           //    of the character at the same time)
       .replace(c,         //    From which the current character is replaced with
         s.substring(i+1));//    the trailing substring after index `i`
  return s;}               //  Return the modified `s` as result-String
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -17 b ? \$\endgroup\$ Oct 4 at 12:20
  • \$\begingroup\$ @NahuelFouilleul Ah, of course. Thanks! :) \$\endgroup\$ Oct 4 at 12:59
1
\$\begingroup\$

Charcoal, 16 bytes

Fη«≔⪪θιυ≔⪫υ⊟υθ»θ

Try it online! Link is to verbose version of code. Explanation: Charcoal doesn't have a good way to refer to the split string twice, so it costs a block and an assignment.

Fη«

Loop over the list of characters.

≔⪪θιυ

Split the string.

≔⪫υ⊟υθ

Join it on the popped element.

»θ

Output the final result.

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

Python, 59 bytes

lambda x,y:[x:=(z:=x.split(i)).pop().join(z)for i in y][-1]

Attempt This Online!

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

R, 95 bytes

f=\(s,L,`?`=length,x=el(strsplit(s,L[1],T)),t=?x)`if`(?L,f(paste(x[-t],collapse=x[t]),L[-1]),s)

Attempt This Online!

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

Haskell, 89 85 bytes

f=foldl(\s c->(\(a,b)->reverse$tail b>>=(\x->last$[x]:[a|x==c])).span(c/=)$reverse s)

Try it online!

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

R, 81 bytes

\(x,y)Reduce(\(x,y)paste(head(a<-el(strsplit(x,y,T)),-1),collapse=tail(a,1)),y,x)

Attempt This Online!

Port of unrelated string's Jelly answer.

\$\endgroup\$

Your Answer

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

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