17
\$\begingroup\$

Swap encoding is an encoding method where you iterate through a string, reversing sections of it between pairs of identical characters.

The basic algorithm

For each character in the string:

Check: Does the string contain the character again, after the instance you found?

If so, then modify the string by reversing the section between the character and the next instance, inclusive.

Otherwise do nothing.

Example

Start with the string 'eat potatoes'.

e is found again, so reverse that section: eotatop taes
o is found again, so reverse that section (doing nothing as it is palindromic)
t is found again, so reverse that section (doing nothing as it is palindromic)
a is found again, so reverse that section: eotat potaes
t is found again, so reverse that section: eotatop taes
None of 'op taes' are found again, so eotatop taes is our final string!

Your challenge

Your challenge is to make a program or function that takes a string as input and returns it encoded as above. Capital letters and lowercase letters are treated as different, and all characters, including spaces, can be swapped.

Testcases

Sandbox for Proposed Challenges => SahC Pr foropox dbosenallednges
Collatz, Sort, Repeat => CoS ,ztrollaepeR ,tat
Write a fast-growing assembly function => Wrgnufa ylbme asa f g-tesstcnoritiwoin
Decompress a Sparse Matrix => Dera aM ssrtapmocese Sprix
Rob the King: Hexagonal Mazes => Rog: Kinob eH lagnaM thezaxes
Determine if a dot(comma) program halts => Detoc(tlamarommi finerp ha mrgod a) ets
Closest Binary Fraction => CloinosestiB Fry tcaran
Quote a rational number => Qunatebmuoiton re al ar
Solve the Alien Probe puzzle => SorP Alveht en eilzzup elobe

Yes I just took the titles of various sandboxed challenges for the testcases.

My reference implementation is available here if anyone wants it.

This is actually an encoding as reverse(swap(reverse(string))) decodes it.

Improve this question
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Derived challenge: given \$s\$, find \$k>0\$ such that \$f^k(s)=s\$. \$\endgroup\$
    – Arnauld
    Commented May 1, 2021 at 13:10
  • \$\begingroup\$ @Arnauld Posting that tommorow, although that's fastest-code. \$\endgroup\$
    – emanresu A
    Commented May 1, 2021 at 21:10

14 Answers 14

Reset to default
6
\$\begingroup\$

JavaScript (ES6), 67 bytes

f=([c,...a])=>c?c+f([...a.splice(0,a.indexOf(c)).reverse(),...a]):a

Try it online!

How?

a.splice(0, n) removes and returns the first \$n\$ entries in a[] if \$n\ge1\$ or removes nothing and returns an empty array if \$n<1\$. If c is not found in a[], a.indexOf(c) returns \$-1\$ and we just pass a[] unchanged to the next iteration.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python 3, 98 92 89 bytes

def f(s):
 if s:t=s[1:];i=t.find(s[0]);return s[0]+f([t,s[i::-1]+t[i+1:]][i>0])
 return s

Try it online!

Thanks to this question, I am now absolutely confident of the usage of Python slices, which I had never remembered the off-by-one rules, especially when the step-size is negative.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Suggest f([t,s[i::-1]+t[i+1:]][i>0]) instead of f(s[i::-1]+t[i+1:]if i>0else t) saves 3 bytes. \$\endgroup\$
    – Noodle9
    Commented May 1, 2021 at 15:06
  • \$\begingroup\$ @Noodle9 Thanks for the tip! \$\endgroup\$
    – Trebor
    Commented May 1, 2021 at 15:10
  • \$\begingroup\$ This would be 87 bytes, but fails with endless recursion... I can't figure out why. Explanation, anyone? tinyurl.com/tdf8fbw9 \$\endgroup\$
    – movatica
    Commented May 1, 2021 at 19:36
3
\$\begingroup\$

J, 39 38 bytes

-1 thanks to Jonah!

0}:@{&|:(}.(|.@{.,}.)~<:@#|}.i.{.)^:a:

Try it online!

0}:@{&|:(}.(|.@{.,}.)~<:@#|}.i.{.)^:a:
                                  ^:a: repeat until result does not change,
                                        keeping the results
                           }.i.{.      index of first character in the tail
                      <:@#|            if not found, set to 0
         }.(        )~                 call with index and the tail
            |.@{.                      rotate up to the index
                 ,}.                   append after the index unchanged
      |:                               transpose,
0   {&                                 get the first char of each iteration
 }:@                                   and drop the last space
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Nice. I took a shot at this and best I could do was save 1 byte: 0}:@{&|:(}.(|.@{.,}.)~<:@#|}.i.{.)^:a:. Taking the first column of the accumulated result was clever. This is one of those "should be easier" problems where J seems to perform poorly. Would love to know if there's a significantly simpler approach. \$\endgroup\$
    – Jonah
    Commented May 1, 2021 at 20:15
  • 1
    \$\begingroup\$ @Jonah Thanks! Such inherently imperative algorithms are always tricky. Wished there was a dyadic fold f (y = inital data to operate on, x = data for each step), but they can have different types. So basically instead of (]&.>/@|.@; <"0@#\) 'foo' a simple (]f~ #\). This would make it cleaner. Another wish is to have a more powerful &.: 2 |.&.{. 1 2 3 4 would take the first two elements, reverse them, but then put them back in the list, so 2 1 3 4. Together this would end up with ~25b. One far away day I'll try to implement these. :-) \$\endgroup\$
    – xash
    Commented May 2, 2021 at 14:39
  • \$\begingroup\$ Yes, good ideas. There are the F. Family of verbs in latest J but when I’ve looked at them they felt a bit cumbersome and not too helpful for golfing \$\endgroup\$
    – Jonah
    Commented May 2, 2021 at 14:47
3
\$\begingroup\$

K (ngn/k), 35 31 bytes

-4 bytes thanks to @coltim

*'{1<#x}{{(|x),y}.(1|2#*=x)_x}\

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 104 103 bytes

Edit: -1 byte thanks to Kirill L.

function(s,t=utf8ToInt(s)){for(i in seq(t))if(e<-match(t[i],t[-1:-i],0))t[i+0:e]=t[i+e:0];intToUtf8(t)}

Try it online!

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Is ! necessary in seq(!t)? I think it should work just fine without it, even on length 1 case. \$\endgroup\$
    – Kirill L.
    Commented May 3, 2021 at 16:03
  • \$\begingroup\$ @KirillL. - You're right. Thanks! \$\endgroup\$
    – Dominic van Essen
    Commented May 3, 2021 at 21:20
2
\$\begingroup\$

Charcoal, 25 bytes

ＰθＷＫＫ«→≔⪫ＫＤＬθ→ωη¿ηＰ⮌…η⌕ηι

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

Ｐθ

Print the input string to the canvas without moving the cursor.

ＷＫＫ«

Repeat while the cursor is above a character of the input string:

→

Move to the next character.

≔⪫ＫＤＬθ→ωη

Get the current suffix.

¿ηＰ⮌…η⌕ηι

Print the reverse of the prefix of the suffix up to the first occurrence of the character that was moved away from, or the empty string if no such occurrence exists. (I need to check that the suffix is not empty because the CycleChop function fails for empty strings.)

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C (clang), 98 96 87 bytes

i;j;t;f(char*s){for(;*s;++s)for(i=0,j=index(s+1,*s)-s;j>i;s[j--]=t)t=s[i],s[i++]=s[j];}

Try it online!

Inputs a pointer to a string and swap encodes the string in place.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 67 65 bytes

f=lambda s:s and s[0]+f(s[(j:=abs(s.find(s[0],1)))-1:0:-1]+s[j:])

Try it online!

-2 bytes thanks to @defald0r! Always adds a (possibly empty) reversed prefix to a (possibly empty) suffix after chopping off the first element.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Brilliant! 65 bytes by replacing max(1,...) with abs(...). \$\endgroup\$
    – Delfad0r
    Commented May 1, 2021 at 21:23
  • \$\begingroup\$ Good catch! I had thought about using abs but discarded it back when I had a version with max(0,...) and it didn't work, but now it does! \$\endgroup\$
    – kops
    Commented May 2, 2021 at 0:10
2
\$\begingroup\$

Ruby -p, 63 58 bytes

$_.size.times{|i|$_[/(?<=^#{?.*i})(.).*?\1/]&&=$&.reverse}

Try it online!

Thanks to G B for -5 bytes.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ for 60 bytes: use $& for reversing - then you cut 2 bytes by not using "r=" \$\endgroup\$
    – G B
    Commented May 3, 2021 at 12:55
1
\$\begingroup\$

Retina 0.8.2, 56 bytes

^
¶¶
{`¶¶(.*?(.))(.*?)\2
$1¶$3¶$2
}+`¶(.)(.*¶)
¶$2$1
¶¶

Try it online! Link includes test cases. Explanation:

^
¶¶

Insert two blank lines so that there are now three lines: the output area, the reversing area and the input area.

{`
}`

Repeat until there are no duplicate characters in the input area.

¶¶(.*?(.))(.*?)\2
$1¶$3¶$2

Move the text up to and including the first duplicate into the output area and the text from after the first duplicate up to the second duplicate into the reversing area, leaving the second duplicate in the input area.

+`¶(.)(.*¶)
¶$2$1

Reverse the text between the duplicates and move it back to the input area.

¶¶

Join the output area with any remaining text in the input area.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 62 bytes

f(h:t)|(a,u:v)<-span(/=h)t=u:f(reverse a++h:v)|0<1=h:f t
f e=e

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL(Dyalog Unicode), 29 bytes SBCS

{⌽@(⍳(≢c)|c⍳⍞←⍵∩⍨⊃⍵)⊢c←1↓⍵}⍣≡

Try it on APLgolf!

A dfn submission which takes the string as argument and outputs to STDOUT.

Shortened from 32 with Bubbler's help.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PHP, 121 bytes

for($a=$argn;$c=$a[$i++];)for($j=0;2*$j<-$i+$p=strpos($a,$c,$i);$a[$p-$j]=$b){$b=$a[$j+$i];$a[$j+$i]=$a[$p-++$j];}echo$a;

Try it online!

PHP still competing for one of the worse golfing language with brio!

For the record, my best version with appropriate string functions is just the same number of bytes:

PHP, 121 bytes

for($a=$argn;$c=$a[$i++];)if($p=strpos($a,$c,$i))$a=substr_replace($a,strrev(substr($a,$i-1,$l=$p-$i+2)),$i-1,$l);echo$a;

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 3.8, 96 bytes

f=lambda s,i=0:i<len(s)and f(i<(j:=s[i+1:].find(s[i])+i+1)and s[:i]+s[j:i:-1]+s[j:]or s,i+1)or s

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

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

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