Solve a traffic intersection

Question

The task

Write a program or function that takes a traffic intersection structure and outputs the sequence, in which vehicles will pass.

The output should contain at most four lines with the following format #. x->y\n, where # is a sequence number number, followed by the dot ., x and y are characters ["N", "E", "S", "W"]. They should be separated by characters ->. If you do not return an array of strings, each line must end with a \n (new line character) or equivalent to your system.

The input should take the following form:

• Part 1: four characters, each having the destination road for the source roads in order N, E, S, W (clockwise). The allowed characters are N, S, W, E or . Space means that there is no vehicle on particular road. For example string S WE means, that N vehicle wishes to go South, space means that there is no E vehicle, W means that S wishes to go West, E means West wishes to go East.
• Part 2 - a space or a single letter meaning which one is of the emergency vehicle.
• Part 3 - two characters determining which two roads have priority (eg. NE means that North and East both have higher priorities than both South and West). If it is easier for you, you may take lower priority roads (in that case SW).

In an unsolvable situation you are allowed to return a one-line string which is clear to the user, like unsolvable, no solution and similar. JavaScript users may take built-in undefined constant.

This is a code-golf, so the shortest answer in bytes wins.

The rules of traffic

Please note that some of the rules may not follow your country traffic rules. Some of them have been simplified to make the challenge easier. Do not use this question as a guide for real life traffic system.

1. For the challenge you are allowed to use only right-side traffic.
2. The traffic intersection consists of exactly four roads which meet in one point. They are marked N (as for "North"), S, W, E. These letters should be used instead of x and y in the output example above.

3. On each road there is at most one vehicle. It is not guaranteed that there is a vehicle on each road. Each vehicle can drive in any of four directions, ie. turn left, turn right, go straight or make a U-turn.

4. If paths of two vehicles do not intersect (they do not collide), they can go at the very same moment. Paths do not collide, if two vehicles (the list might not be complete, but this is intentional, just to give you a clue):
   • come from opposite directions and both go straight, or at least one of them turns right,
   • come from opposite directions and both turn left,
   • come from opposite directions and one of them turns in any direction or makes the U-turn, while the other makes the U-turn,
   • come from orthogonal directions, the one to the left is turning right and the other does not make the U-turn

     Some examples of not colliding paths below. Please note that on the third drawing any path of N would collide with the path of E, even if N makes a U-turn.

5. If two paths collide, it is necessary to use other rules. If two vehicles are on the same priority road (see below), the right of way is given to the vehicle that:
   • is comes from the road on the right side, if they come from orthogonal directions
   • turns right if the other turns left
   • goes straight or turns right if the other makes a U-turn.

     In both examples below the E vehicle has right of way over the vehicle S.

In the example below first goes W, then N, then E and last goes S.

For this particular case the output of your program should be:

1. W->S
2. N->S
3. E->S
4. S->S

6. All drivers use turn signals and know where all others want to go to (for simplicity we assume that it is possible to distinguish between the left turn and the U-turn).

7. Sometimes roads are given priority signs, which are more important that the rules above. A road with higher priority has a priority sign (priority sign image). If the priority road does not go straight, also additional signs are used, like this one. The roads with lower priority have a yield sign or a stop sign (they are equivalent). None or exactly two different roads will have higher priority. The user of your program should be able to enter which roads have higher (or lower) priorities.

8. A vehicle that comes from the road with higher priority has the right of way over a vehicle coming from lower priority road, even if it is on its left side.
9. If paths of two vehicles coming from the roads with the same priority collide, above right-side rules are active.

   On the example below roads S and W have priority signs, which means that vehicles on N and E should give them the way. The S vehicle has the priority over the W vehicle, because it is on its right side, so goes first. Then goes W, because it is on the road of higher priority than E. The vehicle N has right of way from E, because it is on its right side. As the last goes E.

For this particular case the output of your program should be:

1. S->W
2. W->N
3. N->S
4. E->W

10. It is possible that one (and no more) vehicle is an emergency vehicle, which has the priority regardless to which direction it comes from or goes to, and what sign it has (it always goes first). The program should allow the user to enter, which vehicle is an emergency vehicle. Considering that on the last example N is an emergency vehicle, N goes first, then S, W and as the last E.

For this particular case with an emergency vehicle at N the output of your program should be:

1. N->S
2. S->W
3. W->N
4. E->W

11. If two vehicles are allowed to go at the very same moment (their paths do not collide and they do not have to give way to other vehicles), your program should find this out and return them as having the same sequence number

    On the example below paths of N and E as well as E and S or W and E do not collide. Because S has to give way to N and W give way to S, S cannot go simultaneously with E, etc. The N and E can. So at first N and E go together, than goes S, and W as the last.

The proper output of your program should be:

1. N->W
1. E->E
2. S->W
3. W->N

You are free to choose the order of lines 1 (N->W / E->E is equivalent to E->E / N->W)

12. Sometimes the traffic may lead to unsolvable situation, that does not allow any vehicle to go. In real life it is solved when one of the drivers voluntarily resigns from his right of way. Here, your program should output unsolvable etc., as mentioned in the first part of the question.

    Below is an example of unsolvable situation. E should give way to W, W should give way to S, and S should give way to E.

Answer 1

Q, 645 Bytes

r:{(1_x),*x}                                                    /rot
R:{x 3,!3}                                                      /-rot
A:4 4#/:@[16#0;;:;]'[(&0100011001111100b;&0001111101100010b;&0010001111000100b;0);(&0 6 2;&0 1 7;&0 3 3;0)]
K:,/{,'/A x}'3 R\3 0 2 1                                        /Konflick matrix
G:3 R\|E:"NESW"                                                 /E:NESW  G:WSEN NWSE ENWS SENW    
m:{x-y*_x%y}                                                    /mod
t:{1=+/m'[_x%4;2]}                                              /orthogonal
w:{-1($x),". ",y[0],"->",y 1;}                               /write
b:{_x%4}                                                        /n-> base dir.
g:m[;4]                                                         /n-> turn
e:(!4)in                                                        /exists
d:{s:r a:e b x;R s&~a}                                       /right free
I:{(G[a]?x 1)+4*a:E?*x}                                         /"dd"->n
O:{E[a],G[a:b x]g x}                                            /n-> "dd"
P:{N::(y=4)&z~4 4;a@&0<a:(@[4#0;b x;:;4-g x])+(5*d x)+(24*e z)+99*e y}          /priority
H:{a::K ./:/:x,/:\:x; if[N&2 in *a;:,0N]; x@&{~|/x[;z]'y}[a]'[!:'u+1;u:!#x]}    /each set of concurrent movements
f:{i:I'(E,'a)@&~^a:4#x; i:i@p:>P[i;E?x 4;E?x 5 6]; {0<#x 1}{a:H x 1;$[a~,0N;-1"unsolvable";w[*x]'O'a];$[a~,0N;(0;());(1+*x;x[1]@&~x[1] in a)]}/(1;i);}

COMMENTS

Definitively, it's not short (nor simple) code. It can be (severely) compacted, but it's left as excercise to the reader (I've dedicated too much time to this problem).

I've included multiline commented solution, but assume newlines as 1 Byte and discard comments (from / to end of line) to count size

The main difficulty is to fully understand all rules. Early optimization of code length is incompatible with developing a solution for a complex problem. Nor bottom-up or top-down approach copes well with unreadable code.

Finally, I developed a decission table (conflict matrix) with 16 rows and 16 columns (for each direction combined with each possible turn). The values of the items are 0 (compatibility), 1 (preference for row), or 2 (preference for column). It satisfies all test, by I'm not sure that all possible situations are well covered

Source file must have k extension. Start interactive interpreter (free for non-commertial use, kx.com) and evaluate at prompt (as shown in 'test' paragraph)

TEST

q)f " WN    "
1. E->W
2. S->N

q)f " SW    "
1. E->S
2. S->W

q)f "SSSS   "
1. W->S
2. N->S
3. E->S
4. S->S

q)f "SWWN WS"
1. S->W
2. W->N
3. N->S
4. E->W

q)f "SWWNNWS"
1. N->S
2. S->W
3. W->N
4. E->W

q)f "WEWN   "
1. N->W
1. E->E
2. S->W
3. W->N

q)f " SWE   "
unsolvable

EXPLANATION

The base structure is the 'precedence matrix'

   N       E       S       W   
   W S E N N W S E E N W S S E N W
NW 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
 S 0 0 0 0 0 1 1 0 0 0 1 1 2 2 2 2
 E 0 0 0 0 0 1 1 1 2 2 0 0 0 2 2 0
 N 0 0 0 0 2 2 0 0 0 2 0 0 0 0 2 0
EN 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0
 W 2 2 2 2 0 0 0 0 0 1 1 0 0 0 1 1
 S 0 2 2 0 0 0 0 0 0 1 1 1 2 2 0 0
 E 0 0 2 0 0 0 0 0 2 2 0 0 0 2 0 0
SE 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
 N 0 0 1 1 2 2 2 2 0 0 0 0 0 1 1 0
 W 2 2 0 0 0 2 2 0 0 0 0 0 0 1 1 1
 S 0 2 0 0 0 0 2 0 0 0 0 0 2 2 0 0
WS 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
 E 0 1 1 0 0 0 1 1 2 2 2 2 0 0 0 0
 N 0 1 1 1 2 2 0 0 0 2 2 0 0 0 0 0
 W 2 2 0 0 0 2 0 0 0 0 2 0 0 0 0 0

Meaning (by example)

• m[NW][SE] has 0 value (both movements are compatible -concurrent-)
• m[EW][SN] has 1 value (EW has priority over SN) NOTE.- other priority factors may alter this sentence (emergency vehicles, priority road, ..)
• m[NE][SE] has 2 value (SE has priority over NE) NOTE.- other priority factors may alter this sentence (emergency vehicles, priority road, ..)

The matrix can be constructed using four submatrix (4x4) types

  NESW  A    B    C    D
N DACB  0100 0001 0010 0000
E BDAC  0110 2222 0011 0000
S CBDA  0111 0220 2200 0000
W ACBD  2200 0020 0200 0000

The matrix is complemented with a function that assigns a priority to each movement. That function takes account of emergency vehicles, priority roads, orthogonal directions, type of turn and vehicles 'comming from right'

We sort movements by priority and applies matrix values. The resulting submatrix includes conflicts and priority of each movement.

• we analyze unsolvable cases (mutual conflicts)
• if not, we select most priority item and all movements compatible with it and not incompatible with previous incompatible movements, and create a set of movements allowed to go simultaneously
• Write that set of movements and iterate over the rest of candidates