Planen Sie einen 4-Wege-Stopp

Ein paar Autos stehen an einem 4-Wege-Stoppschild und warten darauf, weiterzufahren. Jeder ist verwirrt darüber, wer als nächstes gehen darf, wer in welche Richtung geht usw. Ganz klar suboptimal.

Ihre Aufgabe ist es, den Verkehr am Stoppschild optimal einzuplanen.

Sie erhalten als Eingabe 4 Folgen von Turn-Requests, eine für jede der vier Himmelsrichtungen. Jede Anfrage ist entweder Lfür links, Sfür gerade oder Rfür rechts.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

Die erste Reihe ist die Aufstellung am Nordeingang der Kreuzung. Das erste Auto in der Reihe möchte nach links abbiegen (dh Ausfahrt Ost). Die folgenden Zeilen beziehen sich auf die ankommenden Eingänge Ost, Süd und West. Das erste Auto, das aus dem Westen kommt, möchte also den Süden verlassen.

Der Verkehr bewegt sich in mehreren Schritten. Bei jedem Schritt müssen Sie eine Teilmenge der Autos am Anfang ihrer Linien auswählen, um fortzufahren. Die gewählten Autos dürfen sich nicht gegenseitig stören . Zwei Autos stören sich, wenn sie die gleiche Richtung verlassen oder wenn sie sich überqueren müssen (vorgegebene Standardregeln für Rechtslenker). Also können zwei entgegengesetzte Autos, die beide geradeaus fahren wollen, den gleichen Schritt machen. Also können 4 Autos alle rechts abbiegen wollen. Zwei gegenüberliegende Autos können gleichzeitig links abbiegen.

Ihre Aufgabe ist es, die Kreuzung in einer minimalen Anzahl von Schritten zu planen. Geben Sie für jeden Schritt eine Zeile mit den aufgeführten Kompassrichtungen der ankommenden Autos aus. Für das obige Beispiel beträgt der minimale Zeitplan 14 Schritte. Ein minimaler Zeitplan ist:

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]

Ihr Programm sollte in weniger als 1 Minute 50 Autos in jeder Linie bewältigen können. Die Eingabe der 4 Zeichenfolgen und die Ausgabe des Zeitplans kann für Ihre Sprache beliebig erfolgen.

Kürzeste Sendung gewinnt.

Ein größeres Beispiel:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

Das erfordert mindestens 38 Runden. Eine mögliche Lösung:

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

Ich habe nicht viel Zeit und Mühe darauf verwendet, Golf zu spielen, aber ich könnte es verbessern, wenn andere Antworten auftauchen. Ich benutze eine A * Suche mit einer zulässigen Heuristik , die die Optimalität garantiert. Ich bin mir ziemlich sicher (obwohl ich mich nicht darum gekümmert habe zu bestätigen), dass die Heuristik auch konsistent ist , was bedeutet, dass es sich um O (dynamische Programmierung) handelt.

Das Programm liest vier Zeilen aus STDIN in dem von Ihnen angegebenen Format ein und gibt das Ergebnis in dem von Ihnen angegebenen Format an STDOUT aus.

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

Anwendungsbeispiel:

$ 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