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 caseSW
).
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.
- For the challenge you are allowed to use only right-side traffic.
- 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 ofx
andy
in the output example above.
- 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.
- 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.
- 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
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).
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.
- 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.
- 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
- 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
- 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 toE->E / N->W
)
- 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.