Jadwalkan pemberhentian 4 arah

Sekelompok mobil berbaris di tanda berhenti 4 arah menunggu untuk melanjutkan. Semua orang bingung tentang siapa yang harus pergi berikutnya, siapa yang pergi ke arah lain, dll.

Tugas Anda adalah menjadwalkan lalu lintas di tanda berhenti secara optimal.

Anda menerima sebagai input 4 string permintaan belokan, satu untuk masing-masing dari empat arah mata angin. Setiap permintaan dapat berupa Lkiri, Skanan, atau Rkanan.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

Baris pertama adalah barisan di pintu masuk Utara ke persimpangan. Mobil pertama yang mengantri ingin berbelok ke kiri (yaitu, keluar ke Timur). Baris berikutnya adalah untuk pintu masuk Timur, Selatan, dan Barat yang masuk. Jadi mobil pertama yang datang dari Barat ingin keluar Selatan.

Lalu lintas bergerak dalam serangkaian langkah. Pada setiap langkah, Anda harus memilih subset dari mobil di garis depan mereka untuk melanjutkan. Mobil-mobil yang dipilih tidak boleh saling mengganggu . Dua mobil mengganggu jika mereka keluar dari arah yang sama atau jika mereka harus melintasi jalur masing-masing (diberikan aturan mengemudi kanan). Jadi dua mobil yang berlawanan yang ingin lurus mungkin berjalan pada langkah yang sama. Jadi semoga 4 mobil semua ingin berbelok ke kanan. Dua mobil yang berlawanan dapat berbelok ke kiri secara bersamaan.

Tugas Anda adalah menjadwalkan persimpangan dalam serangkaian langkah minimum. Untuk setiap langkah, output garis dengan arah kompas mobil yang masuk terdaftar. Untuk contoh di atas, jadwal minimal adalah 14 langkah. Satu jadwal minimal adalah:

N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

Program Anda harus dapat menangani 50 mobil di setiap baris dalam waktu kurang dari 1 menit. Input dari 4 string dan output dari jadwal mungkin dengan cara yang nyaman untuk bahasa Anda.

Kemenangan program terpendek.

Contoh yang lebih besar:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

yang membutuhkan minimal 38 putaran. Satu solusi yang mungkin:

E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

Python, 1219 Bytes

Saya tidak menghabiskan banyak waktu / upaya untuk mencoba golf ini, tetapi saya mungkin memperbaikinya jika jawaban lain mulai bermunculan. Saya menggunakan pencarian A * dengan heuristik yang dapat diterima , menjamin optimalitas. Saya cukup yakin (walaupun saya tidak pernah repot untuk mengkonfirmasi) bahwa heuristik juga konsisten , yang berarti bahwa itu adalah O (pemrograman dinamis).

Program membaca dalam empat baris dari STDIN dalam format yang Anda tentukan, dan mencetak hasilnya ke STDOUT, juga dalam format yang Anda tentukan.

from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

Contoh penggunaan:

$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total