# Garble that string!

Given a string as input, output one or more variants of the string such that:

• No character is in it's original position
• No character is adjacent to a character that it was originally adjacent to

You can assume this will always be possible for the given string, and will only contain single case alphabetical characters ([a-z] or [A-Z] if you prefer)

Note that duplicates of the same character are not considered unique.

For example, given the input programming, the output cannot contain an m at the 7th or 8th character, and cannot contain a g at the 4th or 11th character (1 indexed)

## Example:

Take the string abcdef

The following would be a valid output: daecfb

However the following would be invalid: fdbcae as in this example c and b are still adjacent.

Adjacency also wraps, meaning you could not do fdbeca as f and a are still adjacent.

## Testcases:

Note these are not the only valid outputs for the given inputs

Written as input -> output:

helowi -> ioewhl
mayube -> euabmy
stephens -> nhseespt
aabcdeffghij -> dbfhjfigaeca


## Scoring:

This is so fewest bytes in each language wins!

• No character is adjacent to a character that it was originally adjacent to. Does order not matter for adjacency? So input "abcd" cannot have "ab" anywhere, and cannot have "ba" anywhere either? – DrZ214 Jun 9 '17 at 7:03
• @DrZ214 that is correct – Skidsdev Jun 9 '17 at 8:00

# Jelly, 24 23 bytes

ẋ2ṡ2Ṣ€
Ç³Ç¤œ&¬ɓ³=Sȯ
ẊÇ¿


Try it online!

Extremely long by virtue of my being awful at Jelly, but it finally works, at least... still in the process of golfing.

link that generates a list of sorted adjacent pairs:
ẋ2            duplicate argument ("abc" -> "abcabc")
ṡ2          slices of 2 (-> "ab","bc","ca","ab","bc")
Ṣ€        sort each

link that tests for invalid permutations:
Ç             get sorted adjacent pairs of argument
³Ç¤          do the same for the original input
œ&        set intersection, then...
¬       ...inverse; i.e. do they have no elements in common
ɓ   ȯ  logical OR the result of that with...
³=    elementwise equality with original input, and...
S   ...sum; i.e. are some characters in the same position

Ẋ             shuffle the input list
¿           while
Ç            the result of the previous link is truthy

• Tested with all testcases in OP, works for all of them – Skidsdev Jun 8 '17 at 16:25
• This might be really long for Jelly, but its extremely short for everything else (with the possible exception of 05AB1E, and a few other insane golfing languages.) – Gryphon Jun 8 '17 at 16:33
• yeah it's insanely short, I didn't expect even Jelly to do it this golfily, even 05AB1E's wrong solution that didn't check original char position was 45 bytes – Skidsdev Jun 8 '17 at 16:34
• There goes another mod, corrupted by Jelly. How sad. – caird coinheringaahing Jun 8 '17 at 23:00

# Python 2, 185 bytes

from itertools import*
x=input()
g=lambda m:set(zip(m*2,(m*2)[1:]))
for l in permutations(x):
if not((g(l)|g(l[::-1]))&(g(x)|g(x[::-1]))or any(a==b for a,b in zip(x,l))):printl[2::5]


Try it online!
Prints all valid strings

• tested for mayube, stephens and helowi, seems to work for all 3. I need to make an output validator to do some more intensive testing though – Skidsdev Jun 8 '17 at 16:17
• Timed out for aabcdeffghij, but that doesn't mean it doesn't work, just that it takes longer than a minute for that input – Skidsdev Jun 8 '17 at 16:20
• It takes a LONG time to run "aabcdeffghij" on my machine. So far >2min. Also looks like this prints more than one permutation, which is not according to spec. – Not that Charles Jun 8 '17 at 17:06
• Rod - You may save some bytes with print next(l for l in permutations(x) if not((g(l)|g(l[::-1]))&(g(x)|g(x[::-1]))or any(a==b for a,b in zip(x,l)))) – Not that Charles Jun 8 '17 at 17:08
• @NotthatCharles you forgot the l[2::5] =/ – Rod Jun 8 '17 at 17:36

for($a=$argn,$r="^$a[-1].*$a[0]$",$k=0;$v=$a[$k];)$r.="|^.{{$k}}$v|$v".($l=$a[$k++-1])."|$l$v";for(;preg_match("#$r#",$s=str_shuffle($a)););echo$s;  PHP Sandbox Online # PHP>=7.1, 184 Bytes Use the levenshtein distance instead of a Regex way for($a=$argn;$v=$a[$k];$r[]=$l.$v)$r[]=$v.($l=$a[$k++-1]);for(;!$t&&$s=str_shuffle($a);)for($t=1,$i=0;$v=$s[$i];$t*=$v!=$a[$i++])foreach($r as$x)$t*=levenshtein($x,$s[$i-1].$v);echo$s;


PHP Sandbox Online

# PHP, 217 bytes

Version under 7.1

for($l=strlen($a=$argn),$r=$a[$k=0].$a[$l-1]."|".$a[$l-1]."$a[0]|^{$a[$l-1]}.*$a[0]$";$v=$a[$k];!$k?:$r.="|$v".$a[$k-1],++$k<$l?$r.="|$v".$a[$k]:0)$r.="|^.{{$k}}$v";for(;preg_match("#$r#",$s=str_shuffle($a)););echo$s;


Try it online!

• Oh my god it works – Skidsdev Jun 8 '17 at 16:12
• Why should it not work? I make every possible regex. If it match shuffle the string till it not match – Jörg Hülsermann Jun 8 '17 at 16:14
• wait, fails on helowi, outputs ioewlh, i and h are adjacent – Skidsdev Jun 8 '17 at 16:14
• @Mayube Okay that should now make the last case safe – Jörg Hülsermann Jun 8 '17 at 16:21
• Yup, tested with all testcases in the OP, they all work – Skidsdev Jun 8 '17 at 16:23

# Brachylog, 21 bytes

p.jP;?z≠ᵐ&j¬{s₂p~s}P∧


Try it online!

## Explanation

I really would have wanted for p.;?z≠ᵐ&j¬{s₂p~s~j} to work for 2 bytes less, but it seems ~j is not smart enough...

p.jP;?z≠ᵐ&j¬{s₂p~s}P∧  Input is a string, say ? = "asdfgha"
p                      Take a permutation of ?, say "sfagadh".
.                     It is the output.
P                   Call that string P.
z                Zip, repeating elements of the longer string:
[["s","a"],["f","s"],["a","d"],...,["a","g"],["d","h"],["h","a"]]
≠ᵐ              Each pair must have different elements.
&             Start new predicate
j            Concatenate ? to itself: "asdfghaasdfgha"
¬{     }    The following cannot be satisfied:
s₂        Take a substring of length 2
p       and permute it.
~s     It is a substring of
P   P.
∧  Do not unify P with the output.


# PHP 7.1, 136 131 bytes

inspired by Jörg´s solution:

for($a=$argn;$c=$a[$k];)$r.="|$c".($d=$a[$k-1])."|$d$c|^.{".+$k++."}$c";while(preg_match("#$a$r#",($s=str_shuffle($a)).$s));echo$s;


Run as pipe with -r or test it online. (Make sure that PHP version 7.1 or above is selected)

Requires PHP 7.1; add 14 bytes for older PHP: Replace $k-1 with ($k?:strlen($a))-1; (two more bytes for PHP<5.3: $k?$k-1:strlen($a)-1)

breakdown

# A: loop through input to collect sub-expressions
for($a=$argn;$c=$a[$k];)$r.="|$c".($d=$a[$k-1])     # 1. pair of characters
."|$d$c"                # 2. reversed pair
."|^.{".+$k++."}$c";    # 3. $c is at k-th position # B: shuffle input until regex does not match the result while(preg_match("#$a$r#",($s=str_shuffle($a)).$s));    # (input as dummy sub-expression)
# C: print result
echo$s;  • @JörgHülsermann a lot more ;) – Titus Jun 8 '17 at 18:21 • @JörgHülsermann The wrapping case is handled in the first iteration ($c=$a[$k=0], $d=$a[$k-1]) via $s.$s. – Titus Jun 8 '17 at 22:37 • Okay nice trick – Jörg Hülsermann Jun 8 '17 at 23:00 # PHP 7.1, 187 185 172 178 143 bytes do for($r=str_shuffle($s=$argn),$p=$i=0;$c=$s[$i];$p+=($c==$z)+preg_match("#$a|$b#",$s.$s))$b=strrev($a=$r[$i-1].$z=$r[$i++]);while($p);echo$r;  Run as pipe with -r or test it online. (Make sure that PHP version 7.1.0 or above is selected!) breakdown do for($r=str_shuffle($s=$argn),   # 2. shuffle input
$p=$i=0;$c=$s[$i]; # 3. loop through input$p+=($c==$z)                        # 2. set $p if char is at old position +preg_match("#$a|$b#",$s.$s) # or if adjacency occurs in input )$b=strrev($a=$r[$i-1].$z=$r[$i++]); # 1. concat current with previous character
while($p); # 1. loop until$p is falsy
echo\$r;                             # 4. print

• Fails on input mayube, outputs yeuamb, m and a are adjacent – Skidsdev Jun 8 '17 at 16:00
• Also your online tester doesn't seem to be very good, every testcase I've tried just timesout after 3 seconds – Skidsdev Jun 8 '17 at 16:03
• @Mayube I forgot to mention: Use PHP version 7.1 – Titus Jun 8 '17 at 16:22

# Ruby, 11097 102 bytes

->s{x=s.chars
t=s*2
x.shuffle!while s.size.times.any?{|i|a,b=(x*2)[i,2];a==s[i]||t[a+b]||t[b+a]}
x*''}


Try it online!

• This does not follow the rule of "wrapping" adjacency; for example, I got 3594817062 as an output on your TIO link. – Doorknob Jun 8 '17 at 21:21
• @Doorknob fixed! – daniero Jun 9 '17 at 19:59

# JavaScript 6, 116 Bytes

f=x=>(h=[...x].sort(_=>Math.random(z=0)-.5)).some(y=>y==x[z]||(x+x).match(y+(q=h[++z]||h[0])+'|'+q+y))?f(x):h.join


f=x=>(h=[...x].sort(_=>Math.random(z=0)-.5)).some(y=>y==x[z]||(x+x).match(y+(q=h[++z]||h[0])+'|'+q+y))?f(x):h.join

console.log (f('abcdef'));

# Stax, 23 21 bytes

å╘┤‼¬½P¥ë└w↕⌐î◘E{╟u!Ö


Run and debug online!

Thanks for @recursive for saving 2 bytes.

Takes a very long time to run. A more reasonable/feasible version is (just 2 bytes longer)

Ç≡╨áiS║çdèû.#-Gî☺└╨◙σφ+


Run and debug online!

## Explanation

Uses the unpacked version to explain.

w|Nc_:=nGyG|*{E-!f+}ch+2B
w                            Loop anything before } while
|N                          Next permutation (starting from the input)
c_:=                      Index where the current array has the same element as the input (*)
}ch+2B    Define a block that finds all contiguous pairs in current string, including the pair [last element, first element]
nG                    Apply the defined block to current string
yG                  Do the same for the input
|*                Outer product, contains pairs (which themselves are pairs) constructed from the last two array.
{   f           Only keep pairs
E-!            whose two elements have the same set of characters
+          Prepend the array at step (*).
This is used as the condition for the while loop

• Nice. There's an improvement you can make using G. You are doing {...}X!...x! to execute the same block twice. In general, you can rewrite this as G...G  with }... at the end of the program, like this. – recursive Mar 9 '18 at 2:45
• Thank you. I have seen you used G in another post to save one byte by replacing {...}* with D.... I guess am just still not quite used to it ... – Weijun Zhou Mar 9 '18 at 3:00