Mach die Saite kaputt!

20

Wenn Sie eine Zeichenfolge als Eingabe angeben, geben Sie eine oder mehrere Varianten der Zeichenfolge so aus, dass:

  • Kein Charakter befindet sich an seiner ursprünglichen Position
  • Zu einem Zeichen, zu dem es ursprünglich gehörte, ist kein Zeichen benachbart

Sie können davon ausgehen, dass dies für die angegebene Zeichenfolge immer möglich ist und nur alphabetische Zeichen in Groß- und Kleinschreibung enthält ( [a-z]oder [A-Z]wenn Sie dies vorziehen).

Beachten Sie, dass Duplikate desselben Zeichens nicht als eindeutig gelten.

Beispiel: Bei der Eingabe programmingdarf die Ausgabe mbeim 7. oder 8. Zeichen kein und gbeim 4. oder 11. Zeichen kein (1 indiziert) enthalten.

Beispiel:

Nimm die Schnur abcdef

Folgendes wäre eine gültige Ausgabe: daecfb

Folgendes wäre jedoch ungültig: fdbcaewie in diesem Beispiel cund bimmer noch benachbart.

Adjacency auch Wraps, das heißt , Sie nicht tun konnte , fdbecawie fund asind noch immer nebeneinander.

Testfälle:

Beachten Sie, dass dies nicht die einzigen gültigen Ausgaben für die angegebenen Eingaben sind

Geschrieben als input -> output:

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

Wertung:

Dies ist so dass die wenigsten Bytes in jeder Sprache gewinnen!

Skidsdev
quelle
No character is adjacent to a character that it was originally adjacent to. Ist Ordnung nicht wichtig für die Nachbarschaft? Die Eingabe "abcd" kann also nirgendwo "ab" und auch nirgendwo "ba" enthalten?
DrZ214
@ DrZ214 das ist richtig
Skidsdev

Antworten:

5

Gelee , 24 23 Bytes

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

Probieren Sie es online!

Extrem lang, weil ich mich in Jelly schrecklich fühle, aber es funktioniert endlich, zumindest ... immer noch beim Golfen.

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
Türknauf
quelle
Getestet mit allen Testfällen in OP, funktioniert für alle
Skidsdev
Das mag für Jelly sehr lang sein, aber für alles andere ist es extrem kurz (mit der möglichen Ausnahme von 05AB1E und ein paar anderen verrückten Golfsprachen.)
Gryphon - Reinstate Monica
Ja, es ist wahnsinnig kurz. Ich hatte nicht einmal erwartet, dass Jelly es so golfen würde. Sogar 05AB1Es falsche Lösung, die die ursprüngliche Zeichenposition nicht überprüfte, war 45 Bytes
Skidsdev
Da geht ein anderer Mod, der von Jelly korrumpiert wurde. Wie traurig.
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]

Probieren Sie es online!
Gibt alle gültigen Zeichenfolgen aus

Stange
quelle
getestet mayube, stephensund helowischeint für alle 3. Ich muss arbeiten , eine Ausgabe Validator machen etwas intensivere Tests zu tun , obwohl
Skidsdev
Ausgelaufen für aabcdeffghij, aber das heißt nicht, dass es nicht funktioniert, nur dass es länger als eine Minute dauert für diesen Eingang
Skidsdev
Es dauert lange, bis "aabcdeffghij" auf meinem Computer ausgeführt wird. Bisher> 2min. Sieht auch so aus, als würde mehr als eine Permutation gedruckt, was nicht der Spezifikation entspricht.
Nicht dass Charles
Rod - Sie können einige Bytes speichern mitprint 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))))
Nicht dass Charles
@NotthatCharles du hast den `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 Online

PHP> = 7.1, 184 Bytes

Verwenden Sie den levenshtein-Abstand anstelle eines Regex-Weges

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 unter 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;

Probieren Sie es online!

Jörg Hülsermann
quelle
Oh mein Gott, es funktioniert
Skidsdev
Warum sollte es nicht funktionieren? Ich mache jeden möglichen Regex. Wenn es passt, mische die Saite, bis es nicht mehr passt
Jörg Hülsermann
warten, nicht auf helowi, Ausgänge ioewlh, iund hbenachbart sind
Skidsdev
@ Mayube Okay, das sollte jetzt den letzten Fall sicher machen
Jörg Hülsermann
Yup, getestet mit allen Testfällen im OP, sie alle funktionieren
Skidsdev
3

Brachylog , 21 Bytes

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

Probieren Sie es online!

Erläuterung

Ich hätte wirklich gerne p.;?z≠ᵐ&j¬{s₂p~s~j}für 2 Bytes weniger gearbeitet, aber es scheint ~jnicht schlau genug zu sein ...

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
quelle
2

PHP 7.1, 136 131 Bytes

inspiriert von Jörgs Lösung :

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;

Laufen Sie als Pipe mit -roder testen Sie es online . (Stellen Sie sicher, dass PHP Version 7.1 oder höher ausgewählt ist.)

Benötigt PHP 7.1; Addiere 14 Bytes für älteres PHP: Ersetze $k-1mit ($k?:strlen($a))-1;
(zwei weitere Bytes für PHP <5.3: $k?$k-1:strlen($a)-1)

Nervenzusammenbruch

# 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
quelle
@ JörgHülsermann viel mehr;)
Titus
@ JörgHülsermann Der Umhüllungsfall wird in der ersten Iteration ( $c=$a[$k=0], $d=$a[$k-1]) über behandelt $s.$s.
Titus
Okay, schöner Trick
Jörg Hülsermann
1

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;

Laufen Sie als Pipe mit -roder testen Sie es online . (Stellen Sie sicher, dass PHP Version 7.1.0 oder höher ausgewählt ist!)

Nervenzusammenbruch

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
quelle
Schlägt auf Eingang mayube, Ausgänge yeuamb, mund abenachbart sind
Skidsdev
1
Auch Ihr Online-Tester scheint nicht sehr gut zu sein, jeder Testfall, den ich gerade ausprobiert habe, hat nach 3 Sekunden ein
Timeout
@ Mayube Ich habe vergessen zu erwähnen: Verwenden Sie PHP-Version 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*''}

Probieren Sie es online!

daniero
quelle
Dies folgt nicht der Regel des "Umwickelns" der Nachbarschaft; zum beispiel habe ich 3594817062als ausgang auf deinen tio link bekommen.
Türklinke
@Doorknob behoben!
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
quelle
1

Stax , 23 21 Bytes

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

Online ausführen und debuggen!

Vielen Dank für @recursive für das Speichern von 2 Bytes.

Es dauert sehr lange zu laufen. Eine vernünftigere / ausführbarere Version ist (nur 2 Bytes länger)

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

Online ausführen und debuggen!

Erläuterung

Verwendet die entpackte Version, um zu erklären.

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
quelle
Nett. Es gibt eine Verbesserung, die Sie mit machen können G. Sie {...}X!...x!führen denselben Block zweimal aus. Im Allgemeinen können Sie dies als umschreiben G...G mit }... am Ende des Programms, wie diese .
rekursiver
Vielen Dank. Ich habe Sie verwendet gesehen Gin einem anderen Beitrag durch das Ersetzen ein Byte speichern {...}*mit D.... Ich denke, ich bin es einfach noch nicht ganz
gewöhnt