Tugas

Tulis program atau fungsi yang mengambil struktur persimpangan lalu lintas dan menampilkan urutannya, di mana kendaraan akan lewat.

Output harus mengandung paling banyak empat baris dengan format berikut #. x->y\n, di mana #adalah nomor urut nomor, diikuti oleh titik ., xdan ykarakter ["N", "E", "S", "W"]. Mereka harus dipisahkan oleh karakter ->. Jika Anda tidak mengembalikan array string, setiap baris harus diakhiri dengan \n(karakter baris baru) atau setara dengan sistem Anda.

Masukan harus berupa:

• Bagian 1: empat karakter, masing-masing memiliki jalan tujuan untuk jalan sumber dalam urutan N, E, S, W (searah jarum jam). Karakter yang diizinkan adalah N, S, W, Eatau . Ruang berarti bahwa tidak ada kendaraan di jalan tertentu. Misalnya string S WEberarti, bahwa kendaraan N ingin pergi ke Selatan, ruang berarti bahwa tidak ada kendaraan E, Wberarti S ingin pergi ke Barat, Eberarti Barat ingin pergi ke Timur.
• Bagian 2 - spasi atau satu huruf yang berarti kendaraan darurat.
• Bagian 3 - dua karakter menentukan dua jalan mana yang mendapat prioritas (mis. NEBerarti Utara dan Timur keduanya memiliki prioritas lebih tinggi daripada Selatan dan Barat). Jika lebih mudah bagi Anda, Anda dapat mengambil jalan dengan prioritas lebih rendah (dalam hal ini SW).

Dalam situasi yang tidak dapat dipecahkan, Anda diizinkan untuk mengembalikan string satu baris yang jelas bagi pengguna, seperti unsolvable, no solutiondan sejenisnya. Pengguna JavaScript dapat menggunakan undefinedkonstanta bawaan.

Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang.

Aturan lalu lintas

Harap perhatikan bahwa beberapa aturan mungkin tidak mengikuti aturan lalu lintas negara Anda. Beberapa dari mereka telah disederhanakan untuk membuat tantangan lebih mudah. Jangan gunakan pertanyaan ini sebagai panduan untuk sistem lalu lintas kehidupan nyata.

1. Untuk tantangan, Anda hanya diizinkan menggunakan lalu lintas sisi kanan.
2. Persimpangan lalu lintas terdiri dari empat jalan yang bertemu dalam satu titik. Mereka ditandai N(seperti untuk "Utara"), S, W, E. Surat-surat ini harus digunakan sebagai ganti xdan ydalam contoh output di atas.

3. Di setiap jalan ada paling banyak satu kendaraan. Tidak dijamin ada kendaraan di setiap jalan. Setiap kendaraan dapat berkendara di salah satu dari empat arah, yaitu. belok kiri, belok kanan, lurus atau putar balik .

4. Jika jalur dua kendaraan tidak berpotongan (mereka tidak bertabrakan), mereka dapat pergi pada saat yang sama. Jalan tidak bertabrakan, jika dua kendaraan (daftar mungkin tidak lengkap, tetapi ini disengaja, hanya untuk memberi Anda petunjuk):
   • datang dari arah yang berlawanan dan keduanya lurus, atau setidaknya salah satu dari mereka berbelok ke kanan,
   • datang dari arah yang berlawanan dan keduanya belok kiri,
   • datang dari arah yang berlawanan dan salah satu dari mereka berbelok ke arah mana pun atau berbelok, sedangkan yang lain berbelok,
   • datang dari arah ortogonal, yang ke kiri berbelok ke kanan dan yang lain tidak membuat U-turn

     Beberapa contoh tidak bertabrakan jalur di bawah ini. Harap dicatat bahwa pada gambar ketiga setiap jalur N akan bertabrakan dengan jalur E, bahkan jika N berbelok-U.

5. Jika dua jalur bertabrakan, perlu untuk menggunakan aturan lain. Jika dua kendaraan berada di jalan prioritas yang sama (lihat di bawah), hak jalan diberikan kepada kendaraan yang:
   • adalah berasal dari jalan di sisi kanan, jika mereka datang dari arah ortogonal
   • belok kanan jika yang lain belok kiri
   • lurus atau berbelok ke kanan jika yang lain putar balik.

     Dalam kedua contoh di bawah ini, kendaraan E memiliki hak jalan di atas kendaraan S.

Dalam contoh di bawah ini, pertama pergi W, lalu N, lalu E dan terakhir pergi S.

Untuk kasus khusus ini, output dari program Anda harus:

1. W->S
2. N->S
3. E->S
4. S->S

6. Semua driver menggunakan sinyal belok dan tahu ke mana semua orang ingin pergi (untuk kesederhanaan kami mengasumsikan bahwa mungkin untuk membedakan antara belok kiri dan belokan U).

7. Terkadang jalan diberi rambu prioritas, yang lebih penting daripada aturan di atas. Jalan dengan prioritas lebih tinggi memiliki tanda prioritas ( gambar tanda prioritas ). Jika jalan prioritas tidak lurus, juga rambu-rambu tambahan digunakan, seperti ini . Jalan dengan prioritas lebih rendah memiliki tanda hasil atau tanda berhenti (mereka setara). Tidak ada atau persis dua jalan yang berbeda akan memiliki prioritas lebih tinggi. Pengguna program Anda harus dapat memasuki jalan mana yang memiliki prioritas lebih tinggi (atau lebih rendah).

8. Kendaraan yang berasal dari jalan dengan prioritas lebih tinggi memiliki hak jalan di atas kendaraan yang berasal dari jalan dengan prioritas lebih rendah, walaupun berada di sisi kiri.
9. Jika lintasan dua kendaraan yang datang dari jalan dengan prioritas yang sama bertabrakan, aturan sisi kanan di atas aktif.

   Pada contoh di bawah ini, jalan S dan W memiliki tanda-tanda prioritas, yang berarti bahwa kendaraan di N dan E harus memberi mereka jalan. Kendaraan S memiliki prioritas di atas kendaraan W, karena berada di sisi kanan, demikian seterusnya. Kemudian lanjutkan W, karena berada di jalan dengan prioritas lebih tinggi daripada E. Kendaraan N memiliki hak jalan dari E, karena berada di sisi kanannya. Sebagai yang terakhir berjalan E.

Untuk kasus khusus ini, output dari program Anda harus:

1. S->W
2. W->N
3. N->S
4. E->W

10. Ada kemungkinan bahwa satu (dan tidak ada lagi) kendaraan adalah kendaraan darurat , yang memiliki prioritas terlepas dari arah mana ia datang atau pergi ke, dan apa tanda itu (selalu lebih dulu). Program harus memungkinkan pengguna untuk masuk, kendaraan mana yang merupakan kendaraan darurat. Mempertimbangkan bahwa pada contoh terakhir N adalah kendaraan darurat, N pergi dulu, lalu S, W dan sebagai E. terakhir

Untuk kasus khusus ini dengan kendaraan darurat di N, output program Anda harus:

1. N->S
2. S->W
3. W->N
4. E->W

11. Jika dua kendaraan dibiarkan melaju pada saat yang sama (jalurnya tidak bertabrakan dan mereka tidak harus memberi jalan kepada kendaraan lain), program Anda harus mengetahui hal ini dan mengembalikannya dengan nomor urut yang sama.

    Pada contoh di bawah ini jalur N dan E serta E dan S atau W dan E tidak bertabrakan. Karena S harus memberi jalan kepada N dan W memberi jalan ke S, S tidak bisa bersamaan dengan E, dll. N dan E bisa. Jadi pada awalnya N dan E berjalan bersama, daripada pergi S, dan W sebagai yang terakhir.

Output yang tepat dari program Anda harus:

1. N->W
1. E->E
2. S->W
3. W->N

Anda bebas memilih urutan garis 1( N->W / E->Esetara dengan E->E / N->W)

12. Kadang-kadang lalu lintas dapat menyebabkan situasi yang tidak dapat diselesaikan, yang tidak memungkinkan kendaraan untuk pergi. Dalam kehidupan nyata itu diselesaikan ketika salah satu pengemudi secara sukarela mengundurkan diri dari hak jalannya. Di sini, program Anda harus menampilkan unsolvabledll, seperti yang disebutkan di bagian pertama dari pertanyaan.

    Di bawah ini adalah contoh situasi yang tidak dapat diselesaikan. E harus memberi jalan ke W, W harus memberi jalan ke S, dan S harus memberi jalan ke E.

Q, 645 Bytes

r:{(1_x),*x}                                                    /rot
R:{x 3,!3}                                                      /-rot
A:4 4#/:@[16#0;;:;]'[(&0100011001111100b;&0001111101100010b;&0010001111000100b;0);(&0 6 2;&0 1 7;&0 3 3;0)]
K:,/{,'/A x}'3 R\3 0 2 1                                        /Konflick matrix
G:3 R\|E:"NESW"                                                 /E:NESW  G:WSEN NWSE ENWS SENW    
m:{x-y*_x%y}                                                    /mod
t:{1=+/m'[_x%4;2]}                                              /orthogonal
w:{-1($x),". ",y[0],"->",y 1;}                               /write
b:{_x%4}                                                        /n-> base dir.
g:m[;4]                                                         /n-> turn
e:(!4)in                                                        /exists
d:{s:r a:e b x;R s&~a}                                       /right free
I:{(G[a]?x 1)+4*a:E?*x}                                         /"dd"->n
O:{E[a],G[a:b x]g x}                                            /n-> "dd"
P:{N::(y=4)&z~4 4;a@&0<a:(@[4#0;b x;:;4-g x])+(5*d x)+(24*e z)+99*e y}          /priority
H:{a::K ./:/:x,/:\:x; if[N&2 in *a;:,0N]; x@&{~|/x[;z]'y}[a]'[!:'u+1;u:!#x]}    /each set of concurrent movements
f:{i:I'(E,'a)@&~^a:4#x; i:i@p:>P[i;E?x 4;E?x 5 6]; {0<#x 1}{a:H x 1;$[a~,0N;-1"unsolvable";w[*x]'O'a];$[a~,0N;(0;());(1+*x;x[1]@&~x[1] in a)]}/(1;i);}

KOMENTAR

Secara pasti, ini bukan kode pendek (atau sederhana). Ini dapat (sangat) dipadatkan, tetapi dibiarkan sebagai latihan untuk pembaca (saya telah mendedikasikan terlalu banyak waktu untuk masalah ini).

Saya telah menyertakan solusi komentar multiline, tetapi menganggap baris baru sebagai 1 Byte dan membuang komentar (dari / ke ujung baris) untuk menghitung ukuran

Kesulitan utama adalah untuk sepenuhnya memahami semua aturan. Optimalisasi awal panjang kode tidak kompatibel dengan pengembangan solusi untuk masalah yang kompleks. Pendekatan bottom-up atau top-down tidak cocok dengan kode yang tidak dapat dibaca.

Akhirnya, saya mengembangkan tabel decission (konflik matrix) dengan 16 baris dan 16 kolom (untuk setiap arah dikombinasikan dengan setiap kemungkinan belokan). Nilai item adalah 0 (kompatibilitas), 1 (preferensi untuk baris), atau 2 (preferensi untuk kolom). Itu memuaskan semua tes, oleh saya tidak yakin bahwa semua situasi yang mungkin tercakup dengan baik

File sumber harus memiliki ekstensi k. Mulai interpreter interaktif (gratis untuk penggunaan non-komersial, kx.com) dan evaluasi saat diminta (seperti yang ditunjukkan pada paragraf 'uji')

UJI

q)f " WN    "
1. E->W
2. S->N

q)f " SW    "
1. E->S
2. S->W

q)f "SSSS   "
1. W->S
2. N->S
3. E->S
4. S->S

q)f "SWWN WS"
1. S->W
2. W->N
3. N->S
4. E->W

q)f "SWWNNWS"
1. N->S
2. S->W
3. W->N
4. E->W

q)f "WEWN   "
1. N->W
1. E->E
2. S->W
3. W->N

q)f " SWE   "
unsolvable

PENJELASAN

Struktur dasar adalah 'matriks prioritas'

   N       E       S       W   
   W S E N N W S E E N W S S E N W
NW 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
 S 0 0 0 0 0 1 1 0 0 0 1 1 2 2 2 2
 E 0 0 0 0 0 1 1 1 2 2 0 0 0 2 2 0
 N 0 0 0 0 2 2 0 0 0 2 0 0 0 0 2 0
EN 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0
 W 2 2 2 2 0 0 0 0 0 1 1 0 0 0 1 1
 S 0 2 2 0 0 0 0 0 0 1 1 1 2 2 0 0
 E 0 0 2 0 0 0 0 0 2 2 0 0 0 2 0 0
SE 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
 N 0 0 1 1 2 2 2 2 0 0 0 0 0 1 1 0
 W 2 2 0 0 0 2 2 0 0 0 0 0 0 1 1 1
 S 0 2 0 0 0 0 2 0 0 0 0 0 2 2 0 0
WS 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
 E 0 1 1 0 0 0 1 1 2 2 2 2 0 0 0 0
 N 0 1 1 1 2 2 0 0 0 2 2 0 0 0 0 0
 W 2 2 0 0 0 2 0 0 0 0 2 0 0 0 0 0

Arti (dengan contoh)

• m[NW][SE] memiliki nilai 0 (kedua gerakan kompatibel -concurrent-)
• m[EW][SN] memiliki 1 nilai (EW memiliki prioritas di atas SN) CATATAN.- faktor prioritas lainnya dapat mengubah kalimat ini (kendaraan darurat, jalan prioritas, ..)
• m[NE][SE] memiliki 2 nilai (SE memiliki prioritas di atas NE) CATATAN.- faktor prioritas lainnya dapat mengubah kalimat ini (kendaraan darurat, jalan prioritas, ..)

Matriks dapat dibangun menggunakan empat jenis submatrix (4x4)

  NESW  A    B    C    D
N DACB  0100 0001 0010 0000
E BDAC  0110 2222 0011 0000
S CBDA  0111 0220 2200 0000
W ACBD  2200 0020 0200 0000

Matriks ini dilengkapi dengan fungsi yang memberikan prioritas untuk setiap gerakan. Fungsi itu memperhitungkan kendaraan darurat, jalan prioritas, arah ortogonal, jenis belokan dan kendaraan 'datang dari kanan'

Kami mengurutkan gerakan berdasarkan prioritas dan menerapkan nilai matriks. Submatrix yang dihasilkan termasuk konflik dan prioritas setiap gerakan.

• kami menganalisis kasus yang tidak dapat diselesaikan (konflik timbal balik)
• jika tidak, kami memilih sebagian besar item prioritas dan semua gerakan yang kompatibel dengannya dan tidak kompatibel dengan gerakan sebelumnya yang tidak kompatibel, dan membuat serangkaian gerakan yang diizinkan untuk berjalan secara bersamaan
• Tuliskan seperangkat gerakan itu dan ulangi kandidat lainnya