20
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – DrZ214 Jun 9 '17 at 7:03
  • \$\begingroup\$ @DrZ214 that is correct \$\endgroup\$ – Skidsdev Jun 9 '17 at 8:00
5
\$\begingroup\$

Jelly, 24 23 bytes

ẋ2ṡ2Ṣ€
dzǤœ&¬ɓ³=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

main link:
Ẋ             shuffle the input list
  ¿           while
 Ç            the result of the previous link is truthy
\$\endgroup\$
  • \$\begingroup\$ Tested with all testcases in OP, works for all of them \$\endgroup\$ – Skidsdev Jun 8 '17 at 16:25
  • \$\begingroup\$ 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.) \$\endgroup\$ – Gryphon Jun 8 '17 at 16:33
  • \$\begingroup\$ 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 \$\endgroup\$ – Skidsdev Jun 8 '17 at 16:34
  • \$\begingroup\$ There goes another mod, corrupted by Jelly. How sad. \$\endgroup\$ – caird coinheringaahing Jun 8 '17 at 23:00
3
\$\begingroup\$

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))):print`l`[2::5]

Try it online!
Prints all valid strings

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Skidsdev Jun 8 '17 at 16:17
  • \$\begingroup\$ Timed out for aabcdeffghij, but that doesn't mean it doesn't work, just that it takes longer than a minute for that input \$\endgroup\$ – Skidsdev Jun 8 '17 at 16:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Not that Charles Jun 8 '17 at 17:06
  • \$\begingroup\$ 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)))) \$\endgroup\$ – Not that Charles Jun 8 '17 at 17:08
  • \$\begingroup\$ @NotthatCharles you forgot the `l`[2::5] =/ \$\endgroup\$ – Rod Jun 8 '17 at 17:36
3
\$\begingroup\$

PHP>=7.1, 147 Bytes

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!

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

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.
  j                    Concatenate it to itself: "sfagadhsfagadh"
   P                   Call that string P.
    ;?                 Pair P with the input: ["sfagadhsfagadh","asdfgha"]
      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.
\$\endgroup\$
2
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ @JörgHülsermann a lot more ;) \$\endgroup\$ – Titus Jun 8 '17 at 18:21
  • \$\begingroup\$ @JörgHülsermann The wrapping case is handled in the first iteration ($c=$a[$k=0], $d=$a[$k-1]) via $s.$s. \$\endgroup\$ – Titus Jun 8 '17 at 22:37
  • \$\begingroup\$ Okay nice trick \$\endgroup\$ – Jörg Hülsermann Jun 8 '17 at 23:00
1
\$\begingroup\$

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

Ruby, 110 97 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!

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

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'));

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

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – recursive Mar 9 '18 at 2:45
  • \$\begingroup\$ 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 ... \$\endgroup\$ – Weijun Zhou Mar 9 '18 at 3:00

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.