35
\$\begingroup\$

This is the inverse of Let's do some "deciph4r4ng"


In this challenge, your task is to encipher a string. Luckily, the algorithm is pretty simple: reading from left to right, each typical writing character (ASCII range 32-126) must be replaced by a number N (0-9) to indicate that it is the same as the character N+1 positions before it. The exception is when the character does not appear within the previous 10 positions in the original string. In that case, you should simply print the character again. Effectively, you should be able to reverse the operation from the original challenge.

Example

The input string "Programming" would be encoded this way:

Example1

Hence, the expected output is "Prog2am0in6".

Clarifications and rules

  • The input string will contain ASCII characters in the range 32 - 126 exclusively. You can assume that it will never be empty.
  • The original string is guaranteed not to contain any digit.
  • Once a character has been encoded, it may in turn be referenced by a subsequent digit. For instance, "alpaca" should be encoded as "alp2c1".
  • References will never wrap around the string: only previous characters can be referenced.
  • You can write either a full program or a function, which either prints or outputs the result.
  • This is code golf, so the shortest answer in bytes wins.
  • Standard loopholes are forbidden.

Test cases

Input : abcd
Output: abcd

Input : aaaa
Output: a000

Input : banana
Output: ban111

Input : Hello World!
Output: Hel0o W2r5d!

Input : this is a test
Output: this 222a19e52

Input : golfing is good for you
Output: golfin5 3s24o0d4f3r3y3u

Input : Programming Puzzles & Code Golf
Output: Prog2am0in6 Puz0les7&1Cod74G4lf

Input : Replicants are like any other machine. They're either a benefit or a hazard.
Output: Replicants 4re3lik448ny3oth8r5mac6in8.8T64y'r371it9376a1b5n1fit7or2a1h2z17d.
\$\endgroup\$
  • 6
    \$\begingroup\$ I see that your test cases always use the lowest digit possible for any substitution. Is this required behavior, or can we use higher digits too, when there's more than one possibility? \$\endgroup\$ – Leo Apr 7 '17 at 15:54
  • \$\begingroup\$ @Leo You can use any single digit you want 0-9 so long as it's valid. \$\endgroup\$ – Engineer Toast Apr 7 '17 at 16:04
  • \$\begingroup\$ This is like a move-to-front encoder, except without the moving :) \$\endgroup\$ – pipe Apr 8 '17 at 17:28

17 Answers 17

6
\$\begingroup\$

05AB1E, 20 19 18 bytes

-2 Thanks to Emigna

õ¹vDyåiDykëy}?yìT£

Try it online!

õ                  # Push an empty string
 ¹v y              # For each character in input
   D               # Duplicate the string on the stack (call this S)
     åi            # If this character is in S
       Dyk         #   Push the index of that that character 
          ë }      # Else
           y       #   Push the character 
             ?     # Print without newline
              yì   # Prepend this character to S
                T£ # Remove all but the first 10 elements from S
\$\endgroup\$
  • \$\begingroup\$ I think )¹vDyåiDykëy}?y¸ìT£ works as well. \$\endgroup\$ – Emigna Apr 7 '17 at 16:15
  • \$\begingroup\$ Actually, combining your answer with mine gives õIvDyåiDykëy}?yìT£ for 18 :) \$\endgroup\$ – Emigna Apr 7 '17 at 16:21
  • \$\begingroup\$ @Emigna Feel free to update yours with that :) \$\endgroup\$ – Riley Apr 7 '17 at 16:25
  • \$\begingroup\$ I wouldn't have thought of it if not for your answer, so you should have it. Good job! \$\endgroup\$ – Emigna Apr 7 '17 at 16:26
  • \$\begingroup\$ @Emigna I guess that's fair. Thanks! \$\endgroup\$ – Riley Apr 7 '17 at 16:28
12
\$\begingroup\$

Retina, 24 23 bytes

(.)(?<=\1(.{0,9}).)
$.2

Try it online!

A fairly simple regex substitution. We match each character and try to find a copy of it 0-9 characters before it. If we find it, we replace the character with the number of characters we had to match to get to the copy.

The results don't quite match the test cases, because this one uses the largest possible digit instead of the smallest possible one.

\$\endgroup\$
  • 4
    \$\begingroup\$ Variable length look-behind is cheating :p \$\endgroup\$ – Dada Apr 7 '17 at 16:02
  • 8
    \$\begingroup\$ @Dada Variable-length lookbehind is the way of enlightenment. \$\endgroup\$ – Martin Ender Apr 7 '17 at 16:03
  • \$\begingroup\$ Sadly it is... If you're bored, feel free to implement them inside Perl! \$\endgroup\$ – Dada Apr 7 '17 at 16:12
  • \$\begingroup\$ As per OP's comment on the original task, "You can use any single digit you want 0-9 so long as it's valid."... so largest possible should be valid \$\endgroup\$ – Doktor J Apr 8 '17 at 0:47
  • \$\begingroup\$ @DoktorJ yes, I changed it after the OP added that clarification. \$\endgroup\$ – Martin Ender Apr 8 '17 at 7:33
8
\$\begingroup\$

JavaScript (ES6), 74 57 54 bytes

Saved 3 bytes thanks to ETHproductions with the brilliant p=/./g instead of p={} (inspired by Neil)

s=>s.replace(p=/./g,(c,i)=>(i=p[c]-(p[c]=i))>-11?~i:c)

Test cases

let f =

s=>s.replace(p=/./g,(c,i)=>(i=p[c]-(p[c]=i))>-11?~i:c)

console.log(f("abcd"));
console.log(f("aaaa"));
console.log(f("banana"));
console.log(f("Hello World!"));
console.log(f("this is a test"));
console.log(f("golfing is good for you"));
console.log(f("Programming Puzzles & Code Golf"));
console.log(f("Replicants are like any other machine. They're either a benefit or a hazard."));

\$\endgroup\$
  • \$\begingroup\$ As the string is guaranteed not to contain a digit, can you use s instead of p? \$\endgroup\$ – Neil Apr 7 '17 at 17:37
  • \$\begingroup\$ (I was able to outgolf your original find version by using lastIndexOf, which is slightly surprising given that it's 11 letters long....) \$\endgroup\$ – Neil Apr 7 '17 at 17:39
  • \$\begingroup\$ @Neil I'm not in front of a computer right now but I don't think that would work since JS strings are immutable. \$\endgroup\$ – Arnauld Apr 7 '17 at 17:45
  • 2
    \$\begingroup\$ I can confirm that setting properties on string literals doesn't work. But... it looks like it does work with regex, so I think you could possibly do s=>s.replace(p=/./g,(c,i)=>(i=p[c]-(p[c]=i))>-10?~i:c) to save 3 bytes. \$\endgroup\$ – ETHproductions Apr 7 '17 at 18:04
  • 1
    \$\begingroup\$ @YOU I don't really know what happened here, but it turns out that I introduced a bug for all browsers on my last edit. This is now fixed. Thanks for noticing! \$\endgroup\$ – Arnauld Apr 9 '17 at 10:56
7
\$\begingroup\$

Haskell, 72 66 bytes

Thanks to Laikoni for golfing 6 bytes!

(a:r)%s=last(a:[n|(n,b)<-zip['0'..'9']s,b==a]):r%(a:s)
e%s=e
(%"")

Try it online!

The function % keeps the partially processed string in reverse in its second argument, so it's able to search the first 10 elements of this string for occurences of the character it's examinating. The submission consists of the unnamed function (%"") which calls the previous function with the empty string as its second argument.

\$\endgroup\$
  • \$\begingroup\$ f(a:s)=f s++(last$[a]:[show n|(n,b)<-zip[0..9]s,b==a]) saves two bytes. \$\endgroup\$ – Laikoni Apr 7 '17 at 18:24
  • \$\begingroup\$ Wait, f(a:s)=f s++[last$a:[n|(n,b)<-zip['0'..'9']s,b==a]] saves even more. \$\endgroup\$ – Laikoni Apr 7 '17 at 18:25
  • \$\begingroup\$ Reversing on the go instead of using reverse saves one further byte: Try it online! \$\endgroup\$ – Laikoni Apr 7 '17 at 18:58
  • \$\begingroup\$ @Laikoni Thank you, that's wonderful! \$\endgroup\$ – Leo Apr 8 '17 at 12:24
5
\$\begingroup\$

Python 2, 64 bytes

s=''
for c in input():d=s[:~10:-1].find(c);s+=-d*c or`d`
print s

Try it online!

\$\endgroup\$
  • \$\begingroup\$ What's the point of using ~10 cant you just use -11? \$\endgroup\$ – Keatinge Apr 9 '17 at 22:32
3
\$\begingroup\$

Perl 5, 36 bytes

35 bytes of code + -p flag.

s/(\D)(.{0,9})\K\1/length$2/e&&redo

Try it online!

Some explanations:
The goal is to replace a non-digit character (\D but it correspond to the backreference \1 in my regex) that is preceded by less than 10 characters (.{0,9}) and the same character ((\D)...\1) by the length of the .{0,9} group (length$2). And redo while characters get replaced.

\$\endgroup\$
  • \$\begingroup\$ apparently the .* isn't required, any valid char in the range before the replaced digit is ok. \$\endgroup\$ – colsw Apr 7 '17 at 16:08
  • \$\begingroup\$ @ConnorLSW Yup, I just saw that update of the challenge and modified my answer, thanks for pointing it out. \$\endgroup\$ – Dada Apr 7 '17 at 16:09
3
\$\begingroup\$

Python 2, 89 84 bytes

m=input()[::-1];j=1;t=''
for i in m:s=m[j:].find(i);t=[i,`s`][0<s<10]+t;j+=1
print t

Try it Online!

Iterates throught the string in reverse, and builds a new string with the correct numbers inserted.

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

Japt, 18 bytes

£¯Y w bX s r"..+"X

Try it online!

Explanation

£   ¯  Y w bX s r"..+"X
mXY{s0,Y w bX s r"..+"X}
                          // Implicit: U = input string
mXY{                   }  // Replace each char X and index Y in U by this function:
    s0,Y                  //   Take U.slice(0,Y), the part of U before this char.
         w bX             //   Reverse, and find the first index of X in the result.
                          //   This gives how far back this char last appeared, -1 if never.
              s           //   Convert the result to a string.
                r"..+"X   //   Replace all matches of /..+/ in the result with X.
                          //   If the index is -1 or greater than 9, this will revert to X.
                          // Implicit: output result of last expression
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 100 80 bytes

x=>x.split``.map((c,b,a)=>{for(i=0;i++<=9&&a[b-i]!=c;);return i>9?c:i-1}).join``

Try it online!

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

05AB1E, 20 bytes

õIv¹N£RT£©yåi®ykëy}J

Try it online!

Explanation

õ                     # push an empty string
 Iv                   # for each [index,char] [N,y] in input
   ¹N£                # push the first N characters of input
      R               # reverse
       T£             # take the first 10 characters of this string
         ©            # save a copy in register
          yåi         # if y is in this string
             ®yk      #   push the index of y in the string in register
                ë     # else 
                 y    #   push y
                  }   # end if
                   J  # join stack as one string
\$\endgroup\$
2
\$\begingroup\$

Python 3, 125 118 bytes

def p(x):print(x,end='')
l={}
for i,c in enumerate(input()):
 if l.get(c,i+9)<i+9:
  p(i-l[c]-1)
 else:
  p(c)
 l[c]=i

Try it online!

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

C (tcc), 113 bytes

Since the function creates a copy of an input string, the maximum size of input is 98 characters (more than enough to fit the longest test input). Of course, this can be changed to any other value.

i,j;f(char*s){char n[99];strcpy(n,s);for(i=1;s[i];i++)for(j=i-1;j>-1&&i-j<11;j--)if(n[i]==n[j])s[i]=47+i-j;j=-1;}

Try it online!

Edit

-15 bytes. Thanks Johan du Toit.

\$\endgroup\$
  • \$\begingroup\$ Agh! Limit the input to 98 character and save yourself a byte! \$\endgroup\$ – pipe Apr 8 '17 at 17:30
  • \$\begingroup\$ Nice solution but you can save another 15 bytes: i,j;f(char*s){char n[99];strcpy(n,s);for(i=1;s[i];i++)for(j=i-1;j>-1&&i-j<11;j--)if(n[i]==n[j])s[i]=47+i-j,j=-1;} \$\endgroup\$ – Johan du Toit Apr 10 '17 at 10:50
  • \$\begingroup\$ @JohanduToit Thanks! I have one question. How exactly does s[i] work as a condition of the for loop? I've seen it a lot of times in other people's answers on this website. \$\endgroup\$ – Maxim Mikhaylov Apr 10 '17 at 21:07
  • \$\begingroup\$ @Max Lawnboy. You originally had the following: ‘s[i]^'\0'’ which shorthand for ‘s[i] != '\0'’. The ‘\0’ character literal is equal to zero so you can write it like this: ‘s[i] != 0’. The if statement in C only tests if the value evaluates to zero or non-zero so the ‘!=0’ is not necessary. \$\endgroup\$ – Johan du Toit Apr 11 '17 at 7:20
  • \$\begingroup\$ 100 bytes \$\endgroup\$ – ceilingcat Aug 25 at 6:31
2
\$\begingroup\$

Java 7, 102 101 bytes

void a(char[]a){for(int b=a.length,c;--b>0;)for(c=b;c-->0&c+11>b;)if(a[c]==a[b])a[b]=(char)(b-c+47);}

Try it online!

-1 byte thanks to Kevin Cruijssen. I always enjoy an excuse to use the goes-to operator.

\$\endgroup\$
  • \$\begingroup\$ Why the --c>=0? You can replace it with c-->0 to save a byte. \$\endgroup\$ – Kevin Cruijssen Apr 11 '17 at 8:39
  • \$\begingroup\$ @KevinCruijssen I somehow had it in my head that I needed to predecrement otherwise the actual computation would be wrong... Nice catch! \$\endgroup\$ – Poke Apr 11 '17 at 13:13
1
\$\begingroup\$

MATL, 31 30 bytes

&=R"X@@f-t10<)l_)t?qV}xGX@)]&h

Try it at MATL Online!

Explanation

        % Implicitly grab input as a string
&=      % Perform element-wise comparison with automatic broadcasting.
R       % Take the upper-triangular part of the matrix and set everything else to zero
"       % For each column in this matrix
X@      % Push the index of the row to the stack
@f      % Find the indices of the 1's in the row. The indices are always sorted in
        % increasing order
-       % Subtract the index of the row. This result in an array that is [..., 0] where
        % there is always a 0 because each letter is equal to itself and then the ...
        % indicates the index distances to the same letters
t10<)   % Discard the index differences that are > 9
l_)     % Grab the next to last index which is going to be the smallest value. If the index
        % array only contains [0], then modular indexing will grab that zero
t?      % See if this is non-zero...
  qV    % Subtract 1 and convert to a string
}       % If there were no previous matching values
  x     % Delete the item from the stack
  GX@)  % Push the current character
]       % End of if statement
&h      % Horizontally concatenate the entire stack
        % Implicit end of for loop and implicit display
\$\endgroup\$
  • \$\begingroup\$ You might be a bit off but I super cannot tell where. The input this is a test yields this 222a1te52 instead of this 222a19e52. The second t is not converted to 9. \$\endgroup\$ – Engineer Toast Apr 11 '17 at 19:14
  • \$\begingroup\$ @EngineerToast Haha thanks. I'll take a look. \$\endgroup\$ – Suever Apr 11 '17 at 19:15
1
\$\begingroup\$

PHP, 104 Bytes

forward solution

for($i=0;$i<strlen($a=&$argn);$f[$l]=$i++)$a[$i]=is_int($f[$l=$a[$i]])&($c=$i-$f[$l]-1)<10?$c:$l;echo$a;

Backwards solutions

Online Versions

PHP, 111 Bytes

for(;++$i<$l=strlen($a=&$argn);)!is_int($t=strrpos($argn,$a[-$i],-$i-1))?:($p=$l-$i-$t-1)>9?:$a[-$i]=$p;echo$a;

PHP, 112 Bytes

for(;++$i<$l=strlen($a=&$argn);)if(false!==$t=strrpos($argn,$a[-$i],-$i-1))($p=$l-$i-$t-1)>9?:$a[-$i]=$p;echo$a;

Online Version

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

REXX, 124 125 bytes

a=arg(1)
b=a
do n=1 to length(a)
  m=n-1
  c=substr(a,n,1)
  s=lastpos(c,left(a,m))
  if s>0&m-s<=9 then b=overlay(m-s,b,n)
  end
say b
\$\endgroup\$
  • \$\begingroup\$ You might be a bit off. I don't know REXX but I presume the error is in line 7 where it has s<9 instead of s<10 or s<=9. The input this is a test yields this 222a1te52 instead of this 222a19e52. The second t is not converted to 9. Try it online \$\endgroup\$ – Engineer Toast Apr 11 '17 at 19:16
  • \$\begingroup\$ Thank you, it was a stupid attempt to shave off one byte. The code has been fixed. \$\endgroup\$ – idrougge Apr 12 '17 at 9:58
1
\$\begingroup\$

C (gcc), 117 103 bytes

i,j;f(char*s){for(i=strlen(s)-1;s[i];i--)for(j=i-1;s[j]&&i-j<11;j--)if(s[i]==s[j]){s[i]=47+i-j;break;}}

Try it online!

103 bytes without string.h import, works w/ warning. If this is against the rules, I'll pull it

Pretty Code:

i,j;
f(char *s) {
    // Chomp backwards down the string
    for(i=strlen(s)-1; s[i]; i--)
        // for every char, try to match the previous 10
        for(j=i-1; s[j] && i-j < 11; j--)
            // If there's a match, encode it ('0' + (i-j))
            if (s[i] == s[j]) {
                s[i] = 47+i-j;
                break;
            }
}

Edits:

  • Changed from LLVM to gcc to allow implicit i,j declaration, removed lib import.
  • Added function wrapper for compliance
\$\endgroup\$
  • \$\begingroup\$ Suggest (i=strlen(s);s[--i];) instead of (i=strlen(s)-1;s[i];i--) \$\endgroup\$ – ceilingcat Apr 26 at 17:17

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.