Buat Jalan Permutasi

20

Bayangkan diagram berikut ini sebagai kumpulan tabung silang vertikal.

1 2    1 2    1 2 3 4
\ /    \ /    \ / \ /
 X      |      |   |
/ \    / \    / \ / \
2 1    1 2   |   X   |
              \ / \ /
               X   X
              / \ / \
              3 1 4 2

Di diagram paling kiri, 1dan 2geser ke bawah garis miring masing-masing, silangkan di X, dan keluar di sisi yang berlawanan dari tempat mereka mulai.

Itu ide yang sama di diagram tengah, tetapi |menandakan bahwa jalur tidak bersilangan, jadi tidak ada yang berubah.

Diagram menunjukkan paling kanan tabung yang lebih kompleks routing yang yang permutes 1 2 3 4menjadi 3 1 4 2.

Tujuan

Tujuan Anda dalam tantangan golf kode ini adalah untuk menggambar "diagram rute tabung" ini dengan permutasi seperti 3 1 4 2. Program terpendek dalam byte akan menang.

Detail

  1. Input berasal dari stdin karena permutasi angka dari 1 hingga n dipisahkan oleh spasi, di mana n adalah bilangan bulat positif. Anda dapat mengasumsikan semua input terbentuk dengan baik.
  2. Output diagram perutean menuju ke stdout.

    • "Menjatuhkan" angka 1 hingga n agar ke atas diagram akan menghasilkan permutasi input yang keluar di bagian bawah. (Atas dan bawah selalu merupakan lapisan garis miring.)
    • Diagram tidak perlu kecil secara optimal. Mungkin level sebanyak yang diperlukan selama itu benar.
    • Diagram hanya boleh berisi karakter \/ X|dan juga baris baru (tidak ada angka).
    • |harus selalu digunakan pada persimpangan terluar karena menggunakan Xtidak masuk akal.
    • Beberapa ruang awal atau akhir tidak apa-apa asalkan diagramnya disusun dengan benar.

Contohnya

Input dari 3 1 4 2mungkin menghasilkan (sama seperti di atas)

 \ / \ /
  |   | 
 / \ / \
|   X   |
 \ / \ /
  X   X 
 / \ / \

Input dari 1mungkin menghasilkan

 \
  |
 /
|
 \
  |
 /

Input dari 3 2 1mungkin menghasilkan

 \ / \
  X   |
 / \ /
|   X
 \ / \
  X   |
 / \ /

Input dari 2 1 3 4 6 5mungkin menghasilkan

\ / \ / \ /
 X   |   X
/ \ / \ / \
Hobi Calvin
sumber
4
Pertanyaan bagus! Saya tidak percaya baru dua minggu Anda bergabung - Anda sepertinya ada di mana-mana.
xnor
@ xnor: D Terima kasih banyak. Tapi sungguh aku sudah menghabiskan terlalu banyak waktu di sini ...
Calvin Hobbies
Bisakah sebuah Xterhubung langsung dengan |cara yang /dilakukannya? Ke yang lain X?
xnor
1
@xnor No Ini harus selalu di row of slashes, row of X's and |'s, row of slashes, row of X's and |'s, ... Format.
Hobi Calvin
Bisa nlebih besar dari 10?
Kamis

Jawaban:

4

Python 2, 218 219 220 222 224 227 243 247 252 259 261 264

l=map(int,raw_input().split())
f=n=len(l)
o=s=n*' \ /'
while f+n%2:
 f-=1;i=f+n&1;a=s[2*i:][:2*n]+'\n|   '[::2-i]
 while~i>-n:a+='|X'[l[i+1]<l[i]]+'   ';l[i:i+2]=sorted(l[i:i+2]);i+=2
 o=a+f%2*'|'+'\n'+o
print o[:-2*n]

Saya mengambil pendekatan yang sedikit berbeda: Saya menemukan swap yang diperlukan untuk mengurutkan input, kemudian secara vertikal membalikkan itu untuk mendapatkan swap yang diperlukan untuk mengubah daftar yang diurutkan menjadi input. Sebagai bonus tambahan dari pendekatan ini, dapat mengambil daftar angka yang berubah-ubah dan memberikan jalur permutasi untuk mengubah jenis input menjadi input.

Contoh:

$ python sort_path.py <<< '3 1 4 5 9 2 6 8 7'
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   |   |   |   |   
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   |   |   |   |   
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   X   |   |   X   
 \ / \ / \ / \ / \
  |   X   |   X   |
 / \ / \ / \ / \ /
|   |   X   X   |   
 \ / \ / \ / \ / \
  X   |   X   |   |
 / \ / \ / \ / \ /
|   |   |   |   X   
 \ / \ / \ / \ / \

Perbaikan:

264 -> 261: Mengganti loop luar dari untuk sementara.

261 -> 259: Digunakan f%2sebagai ganti (c^m), karena dalam operator aritmatika python memiliki prioritas lebih tinggi daripada operator bitwise.

259 -> 252: Mengganti loop dalam dari untuk sementara. Gabungan idan cvariabel.

252 -> 247: Build yang diubah kemudian mundur menjadi hanya build dengan urutan terbalik.

247 -> 243: Menambahkan baris baru secara manual, alih-alih menggunakan gabungan.

243 -> 227: Metode grc yang diadopsi untuk generasi garis miring (terima kasih grc!) Dan ditambahkan s.

227 -> 224: Memindahkan generasi garis miring ke sebelum bagian dalam sementara loop untuk menghapus a %4dan menyimpan karakter dengan menggunakan irisan yang diperluas.

224 -> 222: Dihapus m.

222 -> 220: f%2+n%2->f+n&1

220 -> 219: | 1<n-1|-> |~i>-n|(ruang terdepan dihapus)

219 -> 218: Gabungan inisialisasi odan sdan memindahkan slice ke ujung.

isaacg
sumber
9

Python, 290

def g(o,u=1):
 s=['|']*o
 for i in range(o,n-1,2):v=r[i+1]in a[:a.index(r[i])]*u;s+=['|X'[v]];r[i:i+2]=r[i:i+2][::1-2*v]
 print'  '*(1-o)+'   '.join(s+['|']*(o^n%2))*u+'\n'*u+(' / \\'*n)[2*o:][:n*2]
a=map(int,raw_input().split())
n=len(a)
r=range(1,n+1)
o=1
g(1,0)
g(0)
while r!=a:g(o);o^=1

Saya pergi untuk pendekatan yang cukup mendasar, tetapi ternyata sedikit lebih lama dari yang saya harapkan. Ini mempertimbangkan daftar berpasangan dan memutuskan apakah akan menukar masing-masing pasangan. Ini diulangi untuk setiap baris yang memotong sampai daftar cocok dengan input.

Contoh:

$ python path.py
5 3 8 1 4 9 2 7 6
 \ / \ / \ / \ / \
  |   |   |   X   |
 / \ / \ / \ / \ /
|   X   X   X   X
 \ / \ / \ / \ / \
  X   X   X   X   |
 / \ / \ / \ / \ /
|   X   X   |   X
 \ / \ / \ / \ / \
  X   X   X   |   |
 / \ / \ / \ / \ /
|   |   |   X   |
 \ / \ / \ / \ / \
grc
sumber
2

JavaScript HTML, 553 419

Terima kasih kepada @izlin dan @TomHart karena menunjukkan kesalahan saya.

p=prompt();b=p.split(" "),l=b.length,d=l%2,o="",s=["","","\\/"],n="\n",a=[];for(i=0;i<l;i++){a[b[i]-1]=i+1;s[1]+=" "+s[2][i%2];s[0]+=" "+s[2][(i+1)%2];o+=" "+(i+1)}s[1]+=n,s[0]+=n;o+=n+s[1];f=1,g=2;do{var c="";for(var i=(f=f?0:1);i<l-1;i+=2)if(a[i]>a[i+1]){c+="  x ";g=2;t=a[i];a[i]=a[i+1];a[i+1]=t;}else c+="  | ";if(g==2){o+=(d?(f?"| "+c:c+"  |"):(f?"| "+c+"  |":c))+n;o+=(s[f]);}}while(--g);o+=" "+p;alert(o);

Uji di sini: http://goo.gl/NRsXEj
masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

JeffSB
sumber
Anda membuat satu kesalahan kecil: baris pertama harus angka yang diurutkan dan baris terakhir harus menjadi input Anda seperti pada contoh di atas.
izlin
Kamu benar. Terima kasih. Saya melihat output @ grc dan berpikir angkanya adalah posisi awal. Ups.
JeffSB
Saya mungkin melihat ini salah, tetapi di kedua gambar yang Anda poskan, bukankah baris terakhir mubazir karena tidak ada perubahan?
TMH
Ya kamu benar. Saya tahu ini adalah konsensus bagaimana saya melakukannya. Tapi mungkin tidak harus begitu. Saya akan memikirkan ini. Terima kasih atas komentarnya.
JeffSB
@izlin - Terima kasih telah memperhatikan ini. Saya memperbaiki kesalahan ini.
JeffSB
1

Javascript - 395

378 jika saya tidak mencetak angka pada output saya, tetapi terlihat jauh lebih baik dan meningkatkan keterbacaan.
Uji di sini . (dengan versi yang tidak disunat) Versi golf

:

a=prompt(),n=a.split(" "),l=n.length,k=[],s="",i=1;for(j=0;j<l;j++){k[n[j]-1]=j+1;s+=" "+(j+1)}s+="\n";while(i++){for(j=0;j<l;j++)s+=i%2?j%2?" \\":" /":j%2?" /":" \\";for(z=0,y=0;z<l-1;z++)if(k[z]>k[z+1])y=1;if(y==0&&i!=2)break;s+="\n";for(m=i%2;m<l;m+=2){s+=i%2&&m==1?"|":"";if(k[m]>k[m+1]){[k[m],k[m+1]]=[k[m+1],k[m]];s+=i%2?"   X":"  X "}else{s+=i%2?"   |":"  | "}}s+="\n"}s+="\n "+a;alert(s)

Penjelasan

Pertama, saya mengganti input dengan nomor indeks dan mengubah baris pertama dengan hasilnya. Sebagai contoh

3 1 4 2
v v v v substitude with
1 2 3 4

so the first line will become:
1 2 3 4
v v v v
2 4 1 3

sorting 1,2,3,4 to 3,1,4,2 is equivalent to 2,4,1,3 to 1,2,3,4

Dengan substitusi ini saya dapat menggunakan algoritma bubble-sort untuk menyortir 2,4,1,3 ke 1,2,3,4 dan grafik akan menjadi yang sesingkat mungkin yang kami cari.
Jika Anda punya ide bagaimana saya bisa membuat kode lebih kecil hanya komentar :)

Contoh

input: 3 4 2 1 7 5 6
output:
 1 2 3 4 5 6 7
 \ / \ / \ / \
  X   |   |   | 
 / \ / \ / \ /
|   X   |   X
 \ / \ / \ / \
  X   X   X   | 
 / \ / \ / \ /
|   X   |   |
 \ / \ / \ / \
 3 4 2 1 7 5 6

izlin
sumber
(1) Saya melihat bahwa Anda menggunakan tag BR di tiga tempat, sehingga Anda dapat menghemat sedikit dengan meletakkan ini dalam variabel. Anda juga mungkin dapat menggunakan \ n sejak mengeluarkan ke PRE.
JeffSB
(2) Saya telah mencoba berbagai cara untuk menangani JavaScript golf dan juga memiliki input dan output yang nyaman. Saya pikir saya suka metode terbaru saya yang terinspirasi oleh prompt dan lansiran Anda ... Saya menggunakan prompt dan lansiran dalam kode sehingga dapat disisipkan ke konsol dan berfungsi untuk siapa saja. Tapi saya juga membuat halaman web dengan TEXTAREA dan PRE untuk membuatnya berfungsi. Halaman web menimpa prompt dan peringatan untuk menggunakan TEXTAREA dan PRE - jadi itu kode yang sama dan ada lebih sedikit kebingungan - mungkin?
JeffSB
@ JeffSB Saya menggunakan <br>tag dan textarea hanya di jsfiddle, karena terlihat jauh lebih baik. Lansiran tidak memiliki font monospasi sehingga hasilnya terlihat buruk. Dalam Versi golf saya, saya menggunakan lansiran dan \ n. Apakah halaman web Anda publik?
izlin
1

Cobra - 334 344 356 360

class P
    def main
        a,o,n=CobraCore.commandLineArgs[1:],['/','\\'],0
        c,l=a.count,a.sorted
        while (n+=1)%2or l<>a
            p,d='',(~n%4+4)//3
            for i in n%2*(c+1-c%2),p,o=p+o[1]+' ',[o.pop]+o
            for i in 1+d:c-n%2*c:2
                z=if(l[:i]<>a[:i],1,0)
                l.swap(i-z,i)
                p+=' ['|X'[z]]  '
            print[['','| '][d]+[p,p+'|'][d^c%2],p][n%2][:c*2]

Ia bekerja dengan memindahkan setiap elemen ke tempatnya mulai dari kiri. Karena hal ini, seringkali akan dihasilkan path-map yang sangat besar (walaupun masih benar).

Contoh:

3 1 4 2

\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
Suram
sumber