Bongkar tali itu!

20

Diberikan string sebagai input, output satu atau lebih varian string sehingga:

  • Tidak ada karakter di posisi aslinya
  • Tidak ada karakter yang berdekatan dengan karakter yang semula berbatasan dengannya

Anda dapat mengasumsikan ini akan selalu dimungkinkan untuk string yang diberikan, dan hanya akan berisi karakter alfabet huruf tunggal ( [a-z]atau [A-Z]jika Anda suka)

Perhatikan bahwa duplikat dengan karakter yang sama tidak dianggap unik.

Misalnya, dengan diberi input programming, output tidak boleh mengandung karakter mat the 7th atau 8th, dan tidak bisa mengandung a gat the 4th atau 11th character (1 diindeks)

Contoh:

Ambil talinya abcdef

Berikut ini adalah output yang valid: daecfb

Namun berikut ini tidak valid: fdbcaeseperti dalam contoh ini cdan bmasih berdekatan.

Adjacency juga membungkus, artinya Anda tidak bisa melakukan apa- fdbecaapa fdan amasih berdekatan.

Testcases:

Perhatikan ini bukan satu - satunya output yang valid untuk input yang diberikan

Ditulis sebagai input -> output:

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

Mencetak:

Ini adalah sehingga byte paling sedikit di setiap bahasa menang!

Skidsdev
sumber
No character is adjacent to a character that it was originally adjacent to. Apakah pesanan tidak penting untuk kedekatan? Jadi masukan "abcd" tidak dapat memiliki "ab" di mana saja, dan tidak dapat memiliki "ba" di mana pun?
DrZ214
@ DrZ214 itu benar
Skidsdev

Jawaban:

5

Jelly , 24 23 byte

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

Cobalah online!

Sangat lama karena aku buruk di Jelly, tapi akhirnya berhasil, setidaknya ... masih dalam proses bermain 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
Gagang pintu
sumber
Diuji dengan semua testcases dalam OP, bekerja untuk semuanya
Skidsdev
Ini mungkin sangat panjang untuk Jelly, tetapi sangat pendek untuk semua yang lain (dengan pengecualian 05AB1E, dan beberapa bahasa golf gila lainnya.)
Gryphon - Reinstate Monica
ya itu gila-gilaan singkat, saya tidak berharap bahkan Jelly melakukannya golfily, bahkan solusi 05AB1E yang salah yang tidak memeriksa posisi char asli adalah 45 byte
Skidsdev
Ada mod lain, rusak oleh Jelly. Sedihnya.
caird coinheringaahing
3

Python 2 , 185 byte

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]

Cobalah online!
Mencetak semua string yang valid

tongkat
sumber
diuji untuk mayube, stephensdan helowi, tampaknya bekerja untuk semua 3. Saya perlu membuat validator keluaran untuk melakukan beberapa pengujian yang lebih intensif
Skidsdev
Habis waktu untuk aabcdeffghij, tetapi itu tidak berarti itu tidak berhasil, hanya saja dibutuhkan lebih dari satu menit untuk input itu
Skidsdev
Butuh waktu lama untuk menjalankan "aabcdeffghij" di komputer saya. Sejauh ini> 2 menit. Sepertinya ini mencetak lebih dari satu permutasi, yang tidak sesuai dengan spesifikasi.
Bukan berarti Charles
Rod - Anda dapat menyimpan beberapa byte denganprint 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))))
Bukan Charles
@NotthatCharles Anda lupa `l`[2::5]
batang
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

Gunakan jarak levenshtein alih-alih cara 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 Online

PHP , 217 byte

Versi di bawah 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;

Cobalah online!

Jörg Hülsermann
sumber
Oh my god it works
Skidsdev
Mengapa itu tidak berhasil? Saya membuat setiap kemungkinan regex. Jika itu cocok, kocok senar sampai tidak cocok
Jörg Hülsermann
tunggu, gagal aktif helowi, keluaran ioewlh, idan hberdekatan
Skidsdev
@ Mayube Oke itu seharusnya sekarang membuat case terakhir aman
Jörg Hülsermann
Yup, diuji dengan semua testcases di OP, semuanya bekerja
Skidsdev
3

Brachylog , 21 byte

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

Cobalah online!

Penjelasan

Saya benar-benar ingin p.;?z≠ᵐ&j¬{s₂p~s~j}bekerja kurang dari 2 byte, tetapi tampaknya ~jtidak cukup pintar ...

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

PHP 7.1, 136 131 byte

terinspirasi oleh solusi 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;

Jalankan sebagai pipa dengan -ratau uji secara online . (Pastikan PHP versi 7.1 atau lebih tinggi dipilih)

Membutuhkan PHP 7.1; tambahkan 14 byte untuk PHP yang lebih lama: Ganti $k-1dengan ($k?:strlen($a))-1;
(dua byte lebih untuk PHP <5.3: $k?$k-1:strlen($a)-1)

kerusakan

# 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
sumber
@ JörgHülsermann lebih banyak;)
Titus
@ JörgHülsermann Pembungkus ditangani dalam iterasi pertama ( $c=$a[$k=0], $d=$a[$k-1]) via $s.$s.
Titus
Oke trik yang bagus
Jörg Hülsermann
1

PHP 7.1, 187 185 172 178 143 byte

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;

Jalankan sebagai pipa dengan -ratau uji secara online . (Pastikan PHP versi 7.1.0 atau lebih tinggi dipilih!)

kerusakan

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
sumber
Gagal pada input mayube, output yeuamb, mdan aberdekatan
Skidsdev
1
Juga tester daring Anda tampaknya tidak terlalu bagus, setiap testcase yang saya coba hanya habis setelah 3 detik
Skidsdev
@ Mayube Saya lupa menyebutkan: Gunakan PHP versi 7.1
Titus
1

Ruby, 110 97 102 byte

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

Cobalah online!

daniero
sumber
Ini tidak mengikuti aturan kedekatan "membungkus"; misalnya, saya mendapat 3594817062sebagai output pada tautan TIO Anda.
Gagang Pintu
@ Doorknob diperbaiki!
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
sumber
1

Stax , 23 21 byte

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

Jalankan dan debug online!

Terima kasih karena @recursive karena menyimpan 2 byte.

Butuh waktu sangat lama untuk berlari. Versi yang lebih masuk akal / layak adalah (hanya 2 byte lebih lama)

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

Jalankan dan debug online!

Penjelasan

Gunakan versi yang belum dibongkar untuk menjelaskan.

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
sumber
Bagus. Ada peningkatan yang bisa Anda lakukan menggunakan G. Anda lakukan {...}X!...x!untuk mengeksekusi blok yang sama dua kali. Secara umum, Anda dapat menulis ulang ini sebagai G...G dengan }... di akhir program, seperti ini .
rekursif
Terima kasih. Saya telah melihat Anda gunakan Gdalam pos lain untuk menyimpan satu byte dengan mengganti {...}*dengan D.... Saya kira saya masih belum terbiasa dengan hal itu ...
Weijun Zhou