20
\$\begingroup\$

To shuffle a string \$s\$, Alice applies the following algorithm:

  • She takes the ASCII code of each character, e.g. "GOLF"\$[ 71, 79, 76, 70 ]\$
  • She sorts this list from lowest to highest: \$[ 70, 71, 76, 79 ]\$
  • She reduces each value modulo the length of the string (4 in this case), leading to the list \$A = [ 2, 3, 0, 3 ]\$
  • For each character at position \$n\$ (0-indexed) in the original string, she exchanges the \$n\$-th character with the \$A[n]\$-th character:
    • exchange \$s[0]\$ with \$s[2]\$: "GOLF" is turned into "LOGF"
    • exchange \$s[1]\$ with \$s[3]\$: "LOGF" is turned into "LFGO"
    • exchange \$s[2]\$ with \$s[0]\$: "LFGO" is turned into "GFLO"
    • exchange \$s[3]\$ with \$s[3]\$: this one doesn't change anything

She then sends the shuffled string "GFLO" to Bob.

Task

Your task is to help Bob understand Alice's message by applying the reverse algorithm: given a shuffled string as input, output the original string.

The input string is guaranteed to contain only printable ASCII characters (codes 32 to 126).

This is , so the shortest answer wins.

Test cases

Input:

AAA
GFLO
ron'llckR'o
Br b,!mn oGognooid
eAies a.turel vee.st hnrw .v

Output:

AAA
GOLF
Rock'n'roll
Good morning, Bob!
As we travel the universe...
\$\endgroup\$
1
  • \$\begingroup\$ Some invariant words under this transformation: ace, bug, dark, road, board, bread, diners, shield. \$\endgroup\$
    – Arnauld
    Dec 20 '21 at 15:32

13 Answers 13

7
\$\begingroup\$

MATL, 19 bytes

tStn\Q!tfhP!"t@)@P(

Try it online! Or verify all test cases.

Explanation

The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order.

t       % Input (implicit): string s of length N (row vector of chars of size 1×N)
S       % Sort (by ASCII codes)
tn      % Duplicate, number of elements: gives N
\       % Modulo (of ASCII codes), element-wise. Gives a 1×N numeric vector
Q       % Add 1 (because MATL uses 1-based indexing)
!       % Transpose into a column vector, of size N×1
tf      % Duplicate, find. Gives the N×1 column vector [1; 2; ...; N]
h       % Concatenate horizontally. Gives an N×2 matrix
P       % Flip vertically (for N=1 flips horizontally, but that still works)
!       % Transpose into a 2×N matrix 
!"      % For each column
  t     %   Duplicate the (partially processed) string: (*)
  @     %   Push current column: 2×1 vector of the form [s(k); k]: (**)
  )     %   Read elements (**) from string (*). Gives 2×1 char vector: (***)
  @P    %   Push current column, flip: gives [k; s(k)]: (****)
  (     %   Write (***) into (*) at positions (****)
        % End (implicit)
        % Display (implicit)
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 47 bytes

≔⪪S¹θW⌊⁻θυF№θι⊞υιWυ«≔℅⊟υι≔§θιη§≔θι§θLυ§≔θLυη»↑θ

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

≔⪪S¹θ

Split the input string into characters.

W⌊⁻θυF№θι⊞υι

Sort them in ascending order.

Wυ«

Process the sorted characters.

≔℅⊟υι

Get the ASCII code of the next character in reverse order.

≔§θιη§≔θι§θLυ§≔θLυη

Swap the character at the current index with the character at that position (cyclically reduced modulo the length of the string).

»↑θ

Output the final character array vertically so it prints as a string.

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

J, 34 32 31 bytes

<(C.>)/@,~i.@#;&~./@,.#|3 u:/:~

Try it online!

Uses Luis Mendo's insight "The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order."

After that, we turn the problem into a single fold of all the swaps, using J's "Permute" verb C., which can implement swaps directly. The only hiccup is that it doesn't allow self swaps, so we have to turn cases like 3 3 C. 'GOLF' into 3 C. 'GOLF', which we do by call unique &~. while creating the swap pair.

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

R, 104 bytes

function(s){i=sort(v<-utf8ToInt(s))%%(n=nchar(s))+1
for(j in n:1)v[rev(w)]=v[w<-c(j,i[j])]
intToUtf8(v)}

Try it online!

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

Python3, 155 bytes:

def g(s,x,l):
 for i in range(l):h=s[(j:=(l-1-i))];s[j]=s[x[j]];s[x[j]]=h;
def f(s):
 s=[*s];g(s,[ord(i)%(t:=len(s))for i in sorted(s)],t);return''.join(s)

Try it online!

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

Scala, 101 92 bytes

s=>(s.sorted.map(_%s.size).zipWithIndex:\s){case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))}

Saved 9 bytes thanks to @user.

Straightforward monadic-style implementation:

  • (s.sorted.map(_%s.size).zipWithIndex:\s) creates the array "A" and traverses its elements (incl. corresponding index) from right to left via folding (:\ = foldRight, accumulator initialized by input string s)
  • {case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))} updates the accumulator value b by swapping b(i) and b(c). This part is quite verbose, since there is no b.swap(c,i) built-in.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can use (s.sorted...zipWithIndex:\s){case...} instead of foldRight btw. Also, you can drop the . on the second call to updated. \$\endgroup\$
    – user
    Dec 24 '21 at 21:37
2
\$\begingroup\$

Python 3, 143 bytes

def u(i):
 m=len(i);p=list;i=p(i);a=[x%m for x in sorted(p(map(ord,i)))]
 for l in range(1-m,1):i[-l],i[a[-l]]=i[a[-l]],i[-l]
 return''.join(i)

I found it easiest to transform the input to a list and then back again, but I wouldn't be surprised if there is a more compact way to accomplish this.

Try it online!

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

Vyxal, 30 bytes

:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹

Try it Online!

What a mess of 30 bytes. Probably gonna be outgolfed by better stack control.

Explained

:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹
:                              # Push two copies of the input string
 C                             # and get the character code of each letter in the second copy
  ₌sL                          # push that sorted and it's length (parallel apply)
     :‹£                       # place the length of the string - 1 into the register - this will keep track of the nth character we're getting
        %Ṙ                     # reverse the list of each character code modulo the length of the string - this gets us our modulo indices (A[n])
          (                    # for each index n in that list:
           :                   #   The top of the stack is the first copy of the input string from earlier - we want to preserve this because we're modifying it with assignment, so make another copy to extract characters from
            ¥n"İ               #  that string's (register)th and nth character
                n¥"            #  push the list [n, register]
                   $Z          #  and then push zipped([n, register], [(register)th char, nth char]) - this allows us to create a list of [index to assign, character to assign]
                     ÷→        #  Place the last pair into the ghost variable for a bit, as we need to focus on the first pair of assignment.
                       ÷Ȧ      #  string[n] = (register)th char
                         ←÷Ȧ   #  string[register] = nth char
                            &‹ #  Increment the register to swap the next character position.
                               # After all that, the final string is implicitly printed.
\$\endgroup\$
1
  • \$\begingroup\$ ಠ_ಠ Why do you need the : at the start \$\endgroup\$
    – emanresu A
    Dec 19 '21 at 7:44
1
\$\begingroup\$

Lua, 231 220 bytes

s=...t={}s:gsub(".",load('table.insert(t,(...):byte())u=s.sub'))table.sort(t)for i=#t,1,-1 do a=t[i]%#t+1 i,j=math.min(a,i),math.max(a,i)s=u(s,1,i-1)..u(s,j,j)..u(s,i+1,j-1)..(i~=j and u(s,i,i)..u(s,j+1)or"")end print(s)

Try it online!

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

Brachylog, 82 bytes

lL∧L⟦₅R⁰∧?oạ%ᵐ↙L;R⁰z↔I∧?g,I↰ˡ↙1c
g;R⁰z{[[X,[A,B]],R]∧(A R∧X∋↙B.∨B R∧X∋↙A.∨X∋↙R.)}ᵐ

Try it online!

I couldn't find any reasonable way to swap 2 elements by index in Brachylog, so the second line is a verbose and ugly implementation of that.

Since Brachylog is prolog based, I could have applied the transform forwards and let it calculate the inverse automatically, but it was easier to just reverse the list.

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

05AB1E, 16 bytes

Ç{Dg%ā<øRvDyèyRǝ

Try it online or verify all test cases.

The shuffle method described in the challenge description would be this:

Ç{Dg%ā<øvDyèyRǝ

Try it online or verify all test cases.

And the top program simply reverses the list of indices to unshuffle.

We can add a trailing = after the programs above to see the intermediate steps: try it online.

Explanation:

Ç          # Convert the (implicit) input to a list of codepoint-integers
 {         # Sort them from lowest to highest
  Dg       # Duplicate, pop and push the length
    %      # Modulo the codepoints by this length
     ā     # Push a list in the range [1,length] (without popping)
      <    # Decrease each by 1 to make the range [0,length)
       ø   # Create pairs of the two lists
        R  # Reverse this list of pairs
v          # Loop over each pair of indices `y` of this list:
 D         #  Duplicate the current string
           #  (which is the implicit input in the first iteration)
  yè       #  Pop one string, and get the character-pair at indices `y`
    yRǝ    #  Insert them at back in the string at the reversed indices-pair `y`
           # (after the loop, the resulting string is output implicitly)

The swapping portion is taken from my answer here.

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

Ruby, 70 bytes

->s{r=0;s.bytes.sort.reverse.map{|c|s[c],s[r]=s[r-=1],s[c%=s.size]};s}

Try it online!

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

K (ngn/k), 36 bytes

{x{@[x;y;:;x@|y]}/|+(!#x;(#x)!x@<x)}

Try it online!

As with the other answers, applies the swaps in the opposite order.

  • (...;(#x)!x@<x) mod the sorted ASCII character codes by the length of the input
  • (!#x;...) generate indices from 0..len(input)
  • |+ transpose this pair of lists into a list of pairs, then reverse its order
  • x{...}/ set up a fold, seeded with x (the original input), and this list of pairs indicating the order of the swaps
    • {@[x;y;:;x@|y]} swap the pair of elements of this current iteration
\$\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.