18
\$\begingroup\$

Given a compressed string \$s\$ made of printable ASCII characters (32 to 126), your task is to print or return the original text by applying this simple decompression algorithm:

  1. Start with \$k=0\$
  2. Look for the first occurrence of the digit \$k\$ in \$s\$ and the sub-string \$s'\$ consisting of the \$2\$ characters preceding it. If the pattern is not found, stop here.
  3. Remove the first occurrence of the digit \$k\$. Replace all other occurrences with \$s'\$.
  4. Increment \$k\$. If it's less than or equal to \$9\$, resume at step \$2\$.

Example 1

Input: bl3a2h1 00001!

  1. The first occurrence of "0" is preceded by "1 ". We remove the first occurrence of "0" and replace all other ones with "1 ", leading to "bl3a2h1 1 1 1 1!".

  2. We do the same thing for "1", with the sub-string "2h". This gives "bl3a2h 2h 2h 2h 2h!".

  3. We do the same thing for "2", with the sub-string "3a". This gives "bl3ah 3ah 3ah 3ah 3ah!".

  4. We do the same thing for "3", with the sub-string "bl". This gives "blah blah blah blah blah!", which is the final output because there are no more digits in \$s\$.

Example 2

Input: Peter Pipe1r pick0ed a 10 of pi0led 1p1rs.

The first step uses the sub-string "ck" and gives:

Peter Pipe1r picked a 1ck of pickled 1p1rs.

The second and final step uses the sub-string "pe" and gives:

Peter Piper picked a peck of pickled peppers.

Rules

  • The input string is guaranteed to be valid. In particular, there will always be at least 2 characters before the first occurrence of a digit.
  • However, the input string may not be compressed at all, in which case it must be returned as-is.
  • The uncompressed text is guaranteed not to contain any digit.
  • This is .

Test cases

Input

Short test cases (one per line):

Hello, World!
antidis0establ0hmentarian0m
bl3a2h1 00001!
A AB4 43C22D11E00F0FG
Peter Pipe1r pick0ed a 10 of pi0led 1p1rs.
The 7first 9rul7of Fi6g5h98C3l2ub1 is: You4 do no9talk ab495210. Th7second rul7of 50 is: Y4 do no9talk ab4950.

Longer test case (first paragraph of the Adventures of Sherlock Holmes / A Scandal in Bohemia, from Project Gutenberg):

To Sher6lock Holmes 3she 9i3a8lway3_the_ woman. I h4av9seldom4eard4im mention246 und68ny oth6 name. In4i3eye3sh9eclipses8nd predomin5ate3t7h19whol9of46 sex. It 0wa3not1at49felt8ny emoti28k57o lov9for Iren9Adl6. All emoti2s,8nd1a029particularly, w69abhorrent7o4i3cold, precise, but8dmirably balanced m5d. H9was, I7ak9it,19mos0p6fec0reas25g8nd obs6v5g mach59that19world4a3seen; but,8s8 lov6,49would4av9placed4imself 58 fals9positi2. H9nev6 spok9of19soft6 passi2s, sav9with8 gib9and8 sne6. They w69admirabl9th5g3for19obs6v6--excellen0for draw5g19veil from men'3motives8nd8cti2s. Bu0for19tra5ed reas267o8dmi0such 5trusi235to4i3own delicat9and f5ely8djusted7emp6amen0was7o 5troduc9a distract5g factor which might1row8 doub0up28ll4i3mental results. Gri058 sensitiv95strument, or8 crack 5 29of4i3own4igh-pow6 lenses, would no0b9mor9disturb5g1an8 str2g emoti2 58 natur9such8s4is. And yet169wa3bu029woman7o4im,8nd1a0woman was19lat9Iren9Adl6, of dubious8nd questi2abl9memory.

Output

Hello, World!
antidisestablishmentarianism
blah blah blah blah blah!
A AB ABC ABCD ABCDE ABCDEF ABCDEFG
Peter Piper picked a peck of pickled peppers.
The first rule of Fight Club is: You do not talk about Fight Club. The second rule of Fight Club is: You do not talk about Fight Club.

Longer one:

To Sherlock Holmes she is always _the_ woman. I have seldom heard him mention her under any other name. In his eyes she eclipses and predominates the whole of her sex. It was not that he felt any emotion akin to love for Irene Adler. All emotions, and that one particularly, were abhorrent to his cold, precise, but admirably balanced mind. He was, I take it, the most perfect reasoning and observing machine that the world has seen; but, as a lover, he would have placed himself in a false position. He never spoke of the softer passions, save with a gibe and a sneer. They were admirable things for the observer--excellent for drawing the veil from men's motives and actions. But for the trained reasoner to admit such intrusions into his own delicate and finely adjusted temperament was to introduce a distracting factor which might throw a doubt upon all his mental results. Grit in a sensitive instrument, or a crack in one of his own high-power lenses, would not be more disturbing than a strong emotion in a nature such as his. And yet there was but one woman to him, and that woman was the late Irene Adler, of dubious and questionable memory.
\$\endgroup\$
  • 1
    \$\begingroup\$ What happens if there are not two characters before a digit? Something like "a0bd000"? \$\endgroup\$ – Xcali Apr 1 at 15:27
  • \$\begingroup\$ @Xcali This would be an invalid input. So you don't have to support that. \$\endgroup\$ – Arnauld Apr 1 at 15:29
  • 1
    \$\begingroup\$ Shouldn't the k = 0 initial condition be k = '0' (the ASCII character for the digit 0), not the integer zero? I had to look at the examples to figure out what the rules were saying because the type mismatch between integers and strings was confusing. \$\endgroup\$ – Peter Cordes Apr 2 at 7:35
  • 1
    \$\begingroup\$ @MitchellSpector Good catch! Now fixed. \$\endgroup\$ – Arnauld Apr 2 at 18:21
  • 1
    \$\begingroup\$ @Jonah In theory, it should be returned unaltered. But because the uncompressed text is guaranteed not to contain any digit, this is actually an invalid input and you don't have to support it. \$\endgroup\$ – Arnauld Apr 3 at 16:19

14 Answers 14

11
\$\begingroup\$

Python 3, 74 bytes

s=input()
for k in'0123456789':a,*b=s.split(k);s=a+a[-2:].join(b)
print(s)

Try it online!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Retina, 36 bytes

~(`.+
9*
L$`
(?<=(..)$.`.$*)?$.`¶$$1

Try it online! Link includes test cases. Unfortunately Retina does not have a convenient way to access a loop index in its loop construct, so it turns out to be easier to create and evaluate the 179-byte program Retina 0.8.2 would need to solve this. Explanation:

~(`

When the inner program has finished, evaluate the result as a Retina program on the original input.

.+
9*

Replace the input with 9 characters that we can loop over.

L$`

Loop $.` from 0 to 9.

(?<=(..)$.`.$*)?$.`¶$$1

Generate a replacement stage that for each $.` in the input, replaces it with the two characters preceding the first $.`. If the first $.` could not be found then this is the first $.` and it is simply deleted. Expanded for $.` = 0 the code looks like this:

(?<=(..)0.*)?0
$1
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

J, 49 48 bytes

(i.~{2<\.]rplc[;i.~{2]\[,,)&> ::]/@|.@;;/@Num_j_

Try it online!

({~rplc~^:_~>@]{3({:;}:)\_2|.[)i.&Num_j_<^:3@-.#

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "for the time being".. :) \$\endgroup\$ – Jonah Apr 3 at 0:49
  • \$\begingroup\$ Btw, current count should be 49, you didn't subtract the count for f=. \$\endgroup\$ – Jonah Apr 3 at 18:43
  • 1
    \$\begingroup\$ Oh, thank god, fixed \$\endgroup\$ – FrownyFrog Apr 3 at 18:54
  • \$\begingroup\$ So I tried to improve on this, and was not able to. Despite the problem not being a great fit for J, I think this is elegant and as J-like as it could be. Nice work. As an arguably slightly more readable version of the leftmost fork, but for no byte saving, I offer up (;/|.Num_j_) \$\endgroup\$ – Jonah Apr 3 at 19:41
  • 1
    \$\begingroup\$ @Jonah Thank you! \$\endgroup\$ – FrownyFrog Apr 3 at 19:54
3
\$\begingroup\$

Bash + GNU utilities, 113 112 bytes

s=`rev`
for n in {0..9};{ s=`sed "s/\(.*\)$n/\1/;s/$n/$(sed "s/.*$n\(..\).*/\1/"<<<"$s")/g"<<<"$s"`;}
rev<<<"$s"

Try the test suite online!

Input on stdin, output on stdout.

Here's how the program works:

(1) The input is reversed right-to-left, to accommodate sed's greedy regex matching.

(2) Then the reversed string is decompressed using multiple calls to sed (using the mirror image of OP's decompression rules because the string has been reversed).

(3) Finally, the resulting string is reversed again.

Step (2), the mirror-image decompression, is implemented as follows.

For each n from 0 to 9:

(2a) Due to the way bash does its expansions, the inner sed

$(sed "s/.*$n\(..\).*/\1/"<<<"$s")

is evaluated first. Its value is the string consisting of the two characters immediately following the last n. That two-character string replaces the entire string

$(sed "s/.*$n\(..\).*/\1/"<<<"$s")

in its enclosing larger expression, and only then is the larger expression evaluated.

(2b) Now, going back to the first sed, the last n in the string is deleted.

(2c) All the earlier occurrences of n in the string are replaced with the two-character string evaluated in step 2a.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 22 13 12 bytes

9ƒN¡ćDŠ2.£ý«

-1 byte thanks to @CommandMaster.

Try it online or verify all test cases.

Explanation:

9ƒ            # Loop `N` in the range [0,9]:
  N¡          #  Split the string at `N`
              #  (which uses the implicit input in the first iteration)
    ć         #  Extract head; pop and push remainder-list and first item separated
     D        #  Duplicate this head
      Š       #  Triple swap a,b,c to c,a,b on the stack (head, remainder-list, head)
       2.£    #  Pop the head, and only leave its last two characters
          ý   #  Join the remainder-list by this 2-char string as delimiter
           «  #  Append it to the duplicated head
              # (after the loop, the resulting string is output implicitly)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ -1 by using instead of ©s® \$\endgroup\$ – Command Master Apr 4 at 10:25
  • \$\begingroup\$ @CommandMaster Ah, of course. Thanks! :) \$\endgroup\$ – Kevin Cruijssen Apr 4 at 11:05
2
\$\begingroup\$

Perl 5 -p, 53 bytes

for$c(0..9){s/(..)\K$c(.*)/"'$2'=~s|$c|\Q$1\E|gr"/ee}

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 111 \$\cdots\$ 98 97 bytes

Saved 2 10 bytes thanks to Uriel!!!
Save a byte thanks to Surculose Sputum!!!

def f(s):
 for k in'0123456789':i=s.find(k);s=[s,s[:i]+s[i+1:].replace(k,s[i-2:i])][i>0]
 print s

Try it online!

Borrowed test rig from Uriel.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 101 bytes by reversing condition and using OP promise for valid input \$\endgroup\$ – Uriel Apr 1 at 16:01
  • \$\begingroup\$ @Uriel Interesting, missed that rule that the uncompressed output won't have a digit - thanks! :-) \$\endgroup\$ – Noodle9 Apr 1 at 16:09
  • \$\begingroup\$ print s instead of return s saves a byte \$\endgroup\$ – Surculose Sputum Apr 1 at 16:33
  • \$\begingroup\$ @SurculoseSputum Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Apr 1 at 16:40
2
\$\begingroup\$

Red, 94 91 bytes

func[s][foreach k"0123456789"[t: copy/part p: any[find s k""]-2 take p replace/all s k t]s]

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 35 bytes

Fχ«≔⌕θIιη≔⁺…θη⪫⪪✂θ⊕ηLθ¹Iι✂θ⁻η²η¹θ»θ

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

Fχ«

Loop over each digit.

≔⌕θIιη

Find the first digit in the input.

≔⁺…θη⪫⪪✂θ⊕ηLθ¹Iι✂θ⁻η²η¹θ

Replace each digit in its suffix with the last two characters of the prefix, and prepend its prefix.

»θ

After all the digits have been expanded, print the result.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3.8, 93 89 87 bytes

f=lambda s,k=0:(g:=s.find(m:=str(k)))+1and f(s[:g]+s[g+1:].replace(m,s[g-2:g]),k+1)or s

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 121 bytes

s->{int j;for(char i=47;++i<58;s=j>0?s.replaceFirst(""+i,"").replace(""+i,s.substring(j-2,j)):s)j=s.indexOf(i);return s;}

Try it online!

Naive Java implementation.

Credits

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Raku (raku -p), 66 61 58 56 Bytes

my $a=-1;$_=S/(..)$a/{$0}/.subst(/$a/,$0,:g)until ++$a>9

First attempt. I am sure it can be improved

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell, 154 148 bytes

n%c=show n==[c]
n#(a:s@(b:c:_))|n%c=[a,b]|1>0=n#s
_#_=""
f n s|n>9||n#s==[]=s|1>0=f(n+1)$l++r>>= \c->last$[c]:[n#s|n%c]where(l,(_:r))=break(n%)s
f 0

Try it online!

Ungolfed:

digitIsChar :: Int -> Char -> Bool
digitIsChar n c = show n == [c]

getSubStr :: Int -> String -> String
getSubStr n (a:b:c:s)
    | digitIsChar n c = [a,b]
    | otherwise = getSubStr n (b:c:s)
getSubStr _ _ = ""

replaceKey :: Int -> String -> Char -> String
replaceKey n key c
    | digitIsChar n c = key
    | otherwise = [c]

decompress :: Int -> String -> String
decompress n s
    | n >= 10 || null key = s
    | otherwise = decompress (n+1) (lhs ++ replaced)
    where
        key = getSubStr n s
        (lhs, (_:rhs)) = break (digitIsChar n) s
        replaced = rhs >>= replaceKey n key

Edits

  1. -6 bytes (@FrownyFrog)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 124 bytes

(r=StringReplace;s=ToString;i=-1;FixedPoint[(i++;r[r[#,s@i->"",1],s@i->StringCases[#,_~~_~~s@i][[1]]~StringTake~2])&,#,10])&

Try it online!

| improve this answer | |
\$\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.