Schedule a 4-way stop

A bunch of cars are lined up at a 4-way stop sign waiting to proceed. Everyone is confused about who gets to go next, who is going which way, etc. Clearly suboptimal.

You receive as input 4 strings of turn requests, one for each of the four cardinal directions. Each request is either L for left, S for straight, or R for right.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL


The first row is the lineup at the North entrance to the intersection. The first car in line wishes to turn left (that is, exit East). The subsequent rows are for the incoming East, South, and West entrances. So the first car coming from the West wishes to exit South.

Traffic moves in a series of steps. At each step, you must choose a subset of the cars at the head of their lines to proceed. The cars chosen must not interfere with each other. Two cars interfere if they exit the same direction or if they must cross each other's path (given standard right-hand driving rules). So two opposite cars both wishing to go straight may go at the same step. So may 4 cars all wishing to turn right. Two opposite cars can both turn left simultaneously.

Your job is to schedule the intersection in a minimum series of steps. For each step, output a line with the incoming cars' compass direction(s) listed. For the example above, the minimal schedule is 14 steps. One minimal schedule is:

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]


Your program should be able to handle 50 cars in each line in under 1 minute. Input of the 4 strings and output of the schedule may be in any convenient manner for your language.

Shortest program wins.

A larger example:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL


which requires a minimum of 38 rounds. One possible solution:

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

• May 19 '15 at 16:01
• How did you calculate the minimal schedule for the first example? I think this is a valid 13-step schedule: NSW, NSW, ESW, EW, EW, NES, NE, EW, NE, NEW, NS, ES, E Jul 14 '15 at 19:58
• @ESultanik: your 4th step, EW, has East going straight, West turning left. That is not an allowed configuration. Jul 15 '15 at 4:48
• @Fatalize: I have a program which does it using dynamic programming. Jul 15 '15 at 4:48
• Ah yeah, sorry about that. I had a bug in my program. I'll be posting an answer shortly… Jul 15 '15 at 14:09

Python, 1219 Bytes

I didn't spend very much time/effort trying to golf this, but I might improve it if other answers start popping up. I use A* search with an admissible heuristic, guaranteeing optimality. I am pretty sure (although I haven't bothered to confirm) that the heuristic is also consistent, meaning that it is O(dynamic programming).

The program reads in four lines from STDIN in the format you have specified, and prints the result to STDOUT, also in the format you specified.

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)])
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


Example usage:

\$ 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