Programe una parada de 4 vías

Un montón de autos están alineados en una señal de alto de 4 vías esperando para continuar. Todos están confundidos acerca de quién irá después, quién irá en qué dirección, etc. Claramente subóptimo.

Su trabajo es programar el tráfico en la señal de stop de manera óptima.

Recibe como entrada 4 cadenas de solicitudes de turno, una para cada una de las cuatro direcciones cardinales. Cada solicitud es Lpara izquierda, Spara recta o Rpara derecha.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

La primera fila es la alineación en la entrada norte a la intersección. El primer automóvil en línea desea girar a la izquierda (es decir, salir hacia el este). Las siguientes filas son para las entradas entrantes Este, Sur y Oeste. Entonces, el primer automóvil que viene del oeste desea salir del sur.

El tráfico se mueve en una serie de pasos. En cada paso, debe elegir un subconjunto de los automóviles en la cabecera de sus líneas para continuar. Los coches elegidos no deben interferir entre sí. Dos autos interfieren si salen en la misma dirección o si deben cruzarse en el camino del otro (dadas las reglas estándar de manejo a la derecha). Entonces, dos autos opuestos que deseen ir en línea recta pueden ir al mismo paso. Entonces, 4 autos que deseen girar a la derecha. Dos autos opuestos pueden girar a la izquierda simultáneamente.

Su trabajo es programar la intersección en una serie mínima de pasos. Para cada paso, muestre una línea con las direcciones de la brújula de los automóviles entrantes enumeradas. Para el ejemplo anterior, el horario mínimo es de 14 pasos. Un horario mínimo es:

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]

Su programa debería poder manejar 50 autos en cada línea en menos de 1 minuto. La entrada de las 4 cadenas y la salida del programa pueden ser de cualquier manera conveniente para su idioma.

El programa más corto gana.

Un ejemplo más amplio:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

que requiere un mínimo de 38 rondas. Una posible solución:

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

No pasé mucho tiempo / esfuerzo tratando de jugar golf, pero podría mejorarlo si otras respuestas comienzan a aparecer. Utilizo la búsqueda A * con una heurística admisible , lo que garantiza la óptima. Estoy bastante seguro (aunque no me he molestado en confirmar) que la heurística también es consistente , lo que significa que es O (programación dinámica).

El programa lee en cuatro líneas desde STDIN en el formato que ha especificado e imprime el resultado en STDOUT, también en el formato que especificó.

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

Ejemplo de uso:

$ 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