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.
Your job is to schedule the traffic at the stop sign in an optimal fashion.
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 LLLRRRSSRSLRSSSSLLRRRR
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