Self-unshuffling strings

Question

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 code-golf, 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...

Some invariant words under this transformation: ace, bug, dark, road, board, bread, diners, shield. — Arnauld
– Arnauld, Commented Dec 20, 2021 at 15:32

Luis Mendo · Accepted Answer · 2021-12-19 17:31:48Z

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)

Luis Mendo · Accepted Answer · 2021-12-19 11:08:48Z

5

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.

edited Dec 19, 2021 at 11:08

Luis Mendo

107k10 gold badges139 silver badges382 bronze badges

answered Dec 19, 2021 at 7:27

Jonah

34.1k4 gold badges41 silver badges95 bronze badges

Add a comment |

Neil · Accepted Answer · 2021-12-19 00:19:46Z

Charcoal, 47 bytes

≔⪪Ｓ¹θＷ⌊⁻θυＦ№θι⊞υιＷυ«≔℅⊟υι≔§θιη§≔θι§θＬυ§≔θＬυη»↑θ

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

≔⪪Ｓ¹θ

Split the input string into characters.

Ｗ⌊⁻θυＦ№θι⊞υι

Sort them in ascending order.

Ｗυ«

Process the sorted characters.

≔℅⊟υι

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

≔§θιη§≔θι§θＬυ§≔θＬυη

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.

Dominic van Essen · Accepted Answer · 2021-12-19 20:26:41Z

3

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!

answered Dec 19, 2021 at 20:26

Dominic van Essen

37.2k2 gold badges24 silver badges61 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2025-01-31 07:02:08Z

Vyxal, 12 bytes

Cs₅%ėṘ(ns⁽Ṙ¢

Try it Online!

Quite possibly the first time I've used ė (enumerate). Output as a char list.

 s           # Sort
C            # the input's charcodes
   %         # And modulo them by
  ₅          # the input's length
    ė        # enumerate, zipping with [0...len(input)] to result in a list of pairs of swaps
     Ṙ(      # and apply the swaps reversed:
           ¢ # In the current value, apply over the indices
       ns    # of the current swap, sorted (shouldn't be necessary, but there's a bug)
         ⁽Ṙ  # Reverse, swapping the two characters

Ajax1234 · Accepted Answer · 2021-12-19 14:56:54Z

2

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!

answered Dec 19, 2021 at 14:56

Ajax1234

8,9391 gold badge16 silver badges29 bronze badges

Add a comment |

Hjulle · Accepted Answer · 2021-12-20 04:10:39Z

2

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.

answered Dec 20, 2021 at 4:10

Hjulle

5392 silver badges8 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-12-20 11:12:12Z

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.

G B · Accepted Answer · 2021-12-21 14:53:34Z

2

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!

answered Dec 21, 2021 at 14:53

G B

23.4k1 gold badge24 silver badges55 bronze badges

Add a comment |

cubic lettuce · Accepted Answer · 2021-12-27 10:24:57Z

2

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!

edited Dec 27, 2021 at 10:24

answered Dec 19, 2021 at 12:50

cubic lettuce

7593 silver badges6 bronze badges

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
– user

2021-12-24 21:37:36 +00:00
Commented Dec 24, 2021 at 21:37

Add a comment |

jeptguy · Accepted Answer · 2022-01-04 20:40:07Z

2

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!

answered Jan 4, 2022 at 20:40

jeptguy

1414 bronze badges

Add a comment |

janMakoso · Accepted Answer · 2025-01-31 21:43:10Z

2

Uiua, 18 bytes

∧⍜⊏⇌⇌≡⊟°⊏◿⊸⧻⍆⊸-@\0

Try it in the pad!

Exaplanation

Port of the MATL answer

∧⍜⊏⇌⇌≡⊟°⊏◿⊸⧻⍆⊸-@\0
             ⊸-@\0 # Covert to codepoints
            ⍆      # Sort
         ◿⊸⧻       # Modulus by length
     ≡⊟°⊏          # Zip with enumerate
    ⇌              # Reverse
∧⍜⊏⇌               # Swap each pair

answered Jan 31 at 21:43

janMakoso

6011 silver badge5 bronze badges

Add a comment |

lyxal · Accepted Answer · 2021-12-18 23:55:10Z

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.

\$\begingroup\$ ಠ_ಠ Why do you need the : at the start \$\endgroup\$

emanresu A
– emanresu A

2021-12-19 07:44:32 +00:00
Commented Dec 19, 2021 at 7:44 — emanresu A
– emanresu A, Commented Dec 19, 2021 at 7:44

Visckmart · Accepted Answer · 2021-12-20 02:51:31Z

1

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!

edited Dec 20, 2021 at 2:51

answered Dec 19, 2021 at 22:33

Visckmart

3611 silver badge4 bronze badges

Add a comment |

coltim · Accepted Answer · 2023-11-04 15:18:26Z

1

K (ngn/k), 36 34 bytes

{x{x[y]:x@|y;x}/|+(!#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;x} swap the pair of elements of this current iteration, returning the modified list

edited Nov 4, 2023 at 15:18

answered Dec 21, 2021 at 21:38

coltim

6,1838 silver badges13 bronze badges

Add a comment |

Xcali · Accepted Answer · 2025-01-31 19:10:12Z

1

Perl 5 `-F`, 64 bytes

$i=@F;@F[$i,$_]=@F[$_,--$i]for reverse map{(ord)%@F}sort@F;say@F

Try it online!

answered Jan 31 at 19:10

Xcali

17k2 gold badges17 silver badges42 bronze badges

Add a comment |

TKDKid1000 · Accepted Answer · 2025-02-01 03:31:32Z

1

Javascript (ES6), 146 Bytes

s=>[...s].map(c=>c.charCodeAt(0)).sort((a,b)=>a-b).map(i=>i%s.length).reduceRight((c,a,i)=>{let t=c[i];c[i]=c[a];c[a]=t;return c},[...s]).join("")

Explanation

Uses the MATL answer's idea of just reversing the order of the swapping, but it utilizes array reduction.

answered Feb 1 at 3:31

TKDKid1000

5974 silver badges11 bronze badges

Add a comment |

Stack Exchange Network

Self-unshuffling strings

Task

Test cases

17 Answers 17

MATL, 19 bytes

Explanation

J, ^{34 32} 31 bytes

Charcoal, 47 bytes

R, 104 bytes

Vyxal, 12 bytes

Python3, 155 bytes:

Brachylog, 82 bytes

05AB1E, 16 bytes

Ruby, 70 bytes

Scala, 101 92 bytes

Python 3, 143 bytes

Uiua, 18 bytes

Exaplanation

Vyxal, 30 bytes

Explained

Lua, 231 220 bytes

K (ngn/k), 36 34 bytes

Perl 5 `-F`, 64 bytes

Javascript (ES6), 146 Bytes

Explanation

Your Answer

Linked

Hot Network Questions

Self-unshuffling strings

Task

Test cases

17 Answers 17

MATL, 19 bytes

Explanation

J, 34 32 31 bytes

Charcoal, 47 bytes

R, 104 bytes

Vyxal, 12 bytes

Python3, 155 bytes:

Brachylog, 82 bytes

05AB1E, 16 bytes

Ruby, 70 bytes

Scala, 101 92 bytes

Python 3, 143 bytes

Uiua, 18 bytes

Exaplanation

Vyxal, 30 bytes

Explained

Lua, 231 220 bytes

K (ngn/k), 36 34 bytes

Perl 5 -F, 64 bytes

Javascript (ES6), 146 Bytes

Explanation

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

J, ^{34 32} 31 bytes

Perl 5 `-F`, 64 bytes