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\$
2
  • \$\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, 2017 at 7:03
  • \$\begingroup\$ @DrZ214 that is correct \$\endgroup\$
    – Mayube
    Jun 9, 2017 at 8:00

9 Answers 9

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\$
4
  • \$\begingroup\$ Tested with all testcases in OP, works for all of them \$\endgroup\$
    – Mayube
    Jun 8, 2017 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, 2017 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\$
    – Mayube
    Jun 8, 2017 at 16:34
  • \$\begingroup\$ There goes another mod, corrupted by Jelly. How sad. \$\endgroup\$ Jun 8, 2017 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\$
6
  • \$\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\$
    – Mayube
    Jun 8, 2017 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\$
    – Mayube
    Jun 8, 2017 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\$ Jun 8, 2017 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\$ Jun 8, 2017 at 17:08
  • \$\begingroup\$ @NotthatCharles you forgot the `l`[2::5] =/ \$\endgroup\$
    – Rod
    Jun 8, 2017 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\$
6
  • \$\begingroup\$ Oh my god it works \$\endgroup\$
    – Mayube
    Jun 8, 2017 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\$ Jun 8, 2017 at 16:14
  • \$\begingroup\$ wait, fails on helowi, outputs ioewlh, i and h are adjacent \$\endgroup\$
    – Mayube
    Jun 8, 2017 at 16:14
  • \$\begingroup\$ @Mayube Okay that should now make the last case safe \$\endgroup\$ Jun 8, 2017 at 16:21
  • \$\begingroup\$ Yup, tested with all testcases in the OP, they all work \$\endgroup\$
    – Mayube
    Jun 8, 2017 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\$
3
  • \$\begingroup\$ @JörgHülsermann a lot more ;) \$\endgroup\$
    – Titus
    Jun 8, 2017 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, 2017 at 22:37
  • \$\begingroup\$ Okay nice trick \$\endgroup\$ Jun 8, 2017 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\$
3
  • \$\begingroup\$ Fails on input mayube, outputs yeuamb, m and a are adjacent \$\endgroup\$
    – Mayube
    Jun 8, 2017 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\$
    – Mayube
    Jun 8, 2017 at 16:03
  • \$\begingroup\$ @Mayube I forgot to mention: Use PHP version 7.1 \$\endgroup\$
    – Titus
    Jun 8, 2017 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\$
2
  • \$\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, 2017 at 21:21
  • \$\begingroup\$ @Doorknob fixed! \$\endgroup\$
    – daniero
    Jun 9, 2017 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\$
0
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\$
2
  • \$\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, 2018 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\$ Mar 9, 2018 at 3:00

Your Answer

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

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