Zaplanuj 4-kierunkowy postój

Kilka samochodów ustawionych w kolejce na 4-kierunkowym znaku stopu czeka na kontynuację. Wszyscy są zdezorientowani, kto będzie następny, kto idzie w którą stronę itp. Wyraźnie nieoptymalny.

Twoim zadaniem jest optymalne zaplanowanie ruchu na znaku stop.

Otrzymujesz jako dane wejściowe 4 ciągi żądań zwrotu, po jednym dla każdego z czterech głównych kierunków. Każde żądanie dotyczy Llewej, Sprostej lub Rprawej.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

Pierwszy rząd to skład przy północnym wejściu do skrzyżowania. Pierwszy samochód w kolejce chce skręcić w lewo (czyli zjechać na wschód). Kolejne rzędy dotyczą nadchodzących wejść na wschód, południe i zachód. Tak więc pierwszy samochód jadący z Zachodu chce zjechać na południe.

Ruch odbywa się w szeregu kroków. Na każdym kroku musisz wybrać podzbiór samochodów na początku ich linii, aby kontynuować. Wybrane samochody nie mogą kolidować ze sobą. Dwa samochody przeszkadzają, jeśli wyjeżdżają w tym samym kierunku lub muszą się przeciąć. Tak więc dwa przeciwległe samochody, oba chcące jechać prosto, mogą przejść ten sam krok. Może 4 samochody, które chcą skręcić w prawo. Dwa przeciwne samochody mogą jednocześnie skręcić w lewo.

Twoim zadaniem jest zaplanowanie skrzyżowania w minimalnej serii kroków. Dla każdego kroku wypisz linię z podanymi kierunkami kompasu przychodzących samochodów. W powyższym przykładzie minimalny harmonogram wynosi 14 kroków. Jeden minimalny harmonogram to:

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]

Twój program powinien być w stanie obsłużyć 50 samochodów w każdej linii w czasie krótszym niż 1 minuta. Wprowadzanie 4 ciągów i wyjście harmonogramu może być dowolne dla twojego języka.

Najkrótszy program wygrywa.

Większy przykład:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

co wymaga minimum 38 rund. Jedno możliwe rozwiązanie:

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 bajtów

Nie spędziłem dużo czasu / wysiłku próbując zagrać w golfa, ale mogę to poprawić, jeśli pojawią się inne odpowiedzi. Korzystam z wyszukiwania A * z dopuszczalną heurystyką , co gwarantuje optymalność. Jestem całkiem pewien (chociaż nie zawracałem sobie głowy potwierdzeniem), że heurystyka jest również spójna , co oznacza, że ​​jest to O (programowanie dynamiczne).

Program odczytuje w czterech wierszach STDIN w określonym formacie i drukuje wynik do STDOUT, również w określonym formacie.

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

Przykładowe użycie:

$ 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