Garble esa cuerda!

20

Dada una cadena como entrada, genera una o más variantes de la cadena de manera que:

  • Ningún personaje está en su posición original
  • Ningún personaje es adyacente a un personaje que originalmente era adyacente a

Puede suponer que esto siempre será posible para la cadena dada, y solo contendrá caracteres alfabéticos de mayúsculas y minúsculas ( [a-z]o [A-Z]si lo prefiere)

Tenga en cuenta que los duplicados del mismo carácter no se consideran únicos.

Por ejemplo, dada la entrada programming, la salida no puede contener un men el 7 ° u 8 ° carácter, y no puede contener un gen el 4 ° u 11 ° carácter (1 indexado)

Ejemplo:

Toma la cuerda abcdef

Lo siguiente sería una salida válida: daecfb

Sin embargo, lo siguiente no sería válido: fdbcaecomo en este ejemplo cyb aún son adyacentes.

La adyacencia también se envuelve, lo que significa que no se puede hacer fdbecacomo fya sigue siendo adyacente.

Casos de prueba:

Tenga en cuenta que estas no son las únicas salidas válidas para las entradas dadas

Escrito como input -> output:

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

Puntuación:

Este es el por lo que gana menos bytes en cada idioma .

Skidsdev
fuente
No character is adjacent to a character that it was originally adjacent to. ¿El orden no importa para la adyacencia? Entonces, ¿la entrada "abcd" no puede tener "ab" en ninguna parte, y tampoco puede tener "ba" en ninguna parte?
DrZ214
@ DrZ214 eso es correcto
Skidsdev

Respuestas:

5

Jalea , 24 23 bytes

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

Pruébalo en línea!

Extremadamente largo en virtud de que soy horrible con Jelly, pero finalmente funciona, al menos ... todavía en el proceso de golf.

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
Pomo de la puerta
fuente
Probado con todos los casos de prueba en OP, funciona para todos ellos
Skidsdev
Esto podría ser muy largo para la jalea, pero su extremadamente corta para todo lo demás (con la posible excepción de 05AB1E, y algunos otros idiomas golf loco.)
Gryphon - Restablecer Mónica
sí, es increíblemente corto, ni siquiera esperaba que Jelly lo hiciera así, incluso la solución incorrecta de 05AB1E que no verificó la posición original del carbón era de 45 bytes
Skidsdev
Ahí va otro mod, corrompido por Jelly. Qué triste.
caird coinheringaahing
3

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]

Pruébalo en línea!
Imprime todas las cadenas válidas

varilla
fuente
probado para mayube, stephensy helowi, parece funcionar para todos 3. Necesito hacer un validador de salida para hacer algunas pruebas más intensas sin embargo
Skidsdev
Se agotó el tiempo de espera aabcdeffghij, pero eso no significa que no funcione, solo que toma más de un minuto para esa entrada
Skidsdev
Lleva mucho tiempo ejecutar "aabcdeffghij" en mi máquina. Hasta ahora> 2min. También parece que esto imprime más de una permutación, que no está de acuerdo con las especificaciones.
No es que Charles
Rod - Puede guardar algunos bytes conprint 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))))
No es que Charles
@NotthatCharles olvidaste el `l`[2::5]= /
Rod
3

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 en línea

PHP> = 7.1, 184 bytes

Use la distancia levenshtein en lugar de una forma Regex

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 en línea

PHP , 217 bytes

Versión bajo 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;

Pruébalo en línea!

Jörg Hülsermann
fuente
Oh, Dios mío, funciona
Skidsdev
¿Por qué no debería funcionar? Hago todas las expresiones regulares posibles. Si coincide, baraja la cuerda hasta que no coincida
Jörg Hülsermann
esperar, falla en helowi, salidas ioewlh, iy hson adyacentes
Skidsdev
@Mayube Ok, eso debería hacer que el último caso sea seguro
Jörg Hülsermann
Sí, probado con todos los casos de prueba en el OP, todos funcionan
Skidsdev
3

Brachylog , 21 bytes

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

Pruébalo en línea!

Explicación

Realmente hubiera querido p.;?z≠ᵐ&j¬{s₂p~s~j}trabajar por 2 bytes menos, pero parece ~jque no es lo suficientemente inteligente ...

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.
Zgarb
fuente
2

PHP 7.1, 136 131 bytes

inspirado en la solución de Jörg :

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;

Ejecutar como tubería con -ro probarlo en línea . (Asegúrese de que PHP versión 7.1 o superior esté seleccionada)

Requiere PHP 7.1; agregue 14 bytes para PHP anterior: Reemplace $k-1con ($k?:strlen($a))-1;
(dos bytes más para PHP <5.3:$k?$k-1:strlen($a)-1 )

Descompostura

# 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;
Titus
fuente
@ JörgHülsermann mucho más;)
Titus
@ JörgHülsermann El caso de envoltura se maneja en la primera iteración ( $c=$a[$k=0], $d=$a[$k-1]) a través de $s.$s.
Titus
Bien, buen truco
Jörg Hülsermann
1

PHP 7.1, 187185172178143 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;

Ejecutar como tubería con -ro probarlo en línea . (¡Asegúrese de que la versión PHP 7.1.0 o superior esté seleccionada!)

Descompostura

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
Titus
fuente
Produce un error en entrada mayube, salidas yeuamb, my ason adyacentes
Skidsdev
1
También su probador en línea no parece ser muy bueno, cada caso de prueba he intentado simplemente timesout después de 3 segundos
Skidsdev
@Mayube Olvidé mencionar: Use PHP versión 7.1
Titus
1

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*''}

Pruébalo en línea!

daniero
fuente
Esto no sigue la regla de "envoltura" de adyacencia; por ejemplo, obtuve 3594817062una salida en su enlace TIO.
Pomo de la puerta
@Doorknob arreglado!
daniero
1

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

l4m2
fuente
1

Stax , 23 21 bytes

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

¡Ejecute y depure en línea!

Gracias por @recursive por guardar 2 bytes.

Lleva mucho tiempo correr. Una versión más razonable / factible es (solo 2 bytes más)

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

¡Ejecute y depure en línea!

Explicación

Utiliza la versión desempaquetada para explicar.

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
Weijun Zhou
fuente
Agradable. Hay una mejora que puedes hacer usando G. Estás haciendo {...}X!...x!ejecutar el mismo bloque dos veces. En general, se puede volver a escribir esto como G...G con }... al final del programa, al igual que este .
recursivo el
Gracias. He visto que usaste Gen otra publicación para guardar un byte reemplazándolo {...}*por D.... Supongo que todavía no estoy acostumbrado ...
Weijun Zhou