Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die eine Verkehrskreuzungsstruktur verwendet und die Reihenfolge ausgibt, in der Fahrzeuge vorbeifahren.

Die Ausgabe sollte mit folgendem Format höchstens vier Zeilen enthalten #. x->y\n, wobei #eine Sequenznummer Zahl ist, durch den Punkt gefolgt ., xund ysind Zeichen ["N", "E", "S", "W"]. Sie sollten durch Zeichen getrennt sein ->. Wenn Sie kein Array von Zeichenfolgen zurückgeben, muss jede Zeile mit einem \n(Zeichen für eine neue Zeile) oder einem ähnlichen Zeichen wie Ihr System enden .

Die Eingabe sollte folgende Form haben:

• Teil 1: vier Zeichen mit jeweils der Zielstraße für die Quellstraßen in der Reihenfolge N, E, S, W (im Uhrzeigersinn). Die erlaubten Zeichen sind N, S, W, Eoder . Platz bedeutet, dass sich kein Fahrzeug auf einer bestimmten Straße befindet. Zum Beispiel S WEbedeutet string , dass N Fahrzeuge nach Süden wollen, space bedeutet, dass es kein E-Fahrzeug gibt, Wbedeutet, dass S nach Westen wollen, Ebedeutet , dass West nach Osten wollen.
• Teil 2 - Ein Leerzeichen oder ein einzelner Buchstabe, der angibt, welcher Buchstabe zum Einsatzfahrzeug gehört.
• Teil 3 - zwei Zeichen, die bestimmen, welche zwei Straßen Priorität haben (z. B. NEbedeutet, dass Nord und Ost höhere Prioritäten haben als Süd und West). Wenn es für Sie einfacher ist, können Sie (in diesem Fall SW) Straßen mit niedrigerer Priorität nehmen .

In einer unlösbaren Situation sind Sie eine einzeilige Zeichenfolge zurückkehren , die für den Benutzer klar ist, wie unsolvable, no solutionund ähnliche. JavaScript-Benutzer können eingebaute undefinedKonstanten verwenden.

Dies ist ein Code-Golf, also gewinnt die kürzeste Antwort in Bytes.

Die Regeln des Verkehrs

Bitte beachten Sie, dass einige der Regeln möglicherweise nicht den Verkehrsregeln Ihres Landes entsprechen. Einige von ihnen wurden vereinfacht, um die Herausforderung zu vereinfachen. Verwenden Sie diese Frage nicht als Leitfaden für das reale Verkehrssystem.

1. Für die Challenge dürfen Sie nur Rechtsverkehr verwenden.
2. Die Verkehrskreuzung besteht aus genau vier Straßen, die sich an einem Punkt treffen. Sie sind gekennzeichnet N(wie „Nord“) S, W, E. Diese Buchstaben sollten anstelle von xund yim obigen Ausgabebeispiel verwendet werden.

3. Auf jeder Straße befindet sich höchstens ein Fahrzeug. Es kann nicht garantiert werden, dass sich auf jeder Straße ein Fahrzeug befindet. Jedes Fahrzeug kann in eine von vier Richtungen fahren, dh. Biegen Sie links ab, biegen Sie rechts ab, fahren Sie geradeaus oder wenden Sie .

4. Wenn sich die Wege zweier Fahrzeuge nicht kreuzen (sie kollidieren nicht), können sie im selben Moment fahren. Pfade kollidieren nicht, wenn zwei Fahrzeuge (die Liste ist möglicherweise nicht vollständig, aber dies ist beabsichtigt, nur um Ihnen einen Hinweis zu geben):
   • aus entgegengesetzten Richtungen kommen und beide geradeaus fahren, oder mindestens einer von ihnen biegt nach rechts ab,
   • kommen aus entgegengesetzten Richtungen und beide biegen links ab,
   • kommen aus entgegengesetzten Richtungen und einer von ihnen dreht sich in eine beliebige Richtung oder macht die Kehrtwende, während der andere die Kehrtwende macht,
   • kommen aus orthogonalen Richtungen, der eine nach links dreht sich nach rechts und der andere macht keine Kehrtwende

     Nachfolgend einige Beispiele für nicht kollidierende Pfade. Bitte beachten Sie, dass in der dritten Zeichnung jeder Pfad von N mit dem Pfad von E kollidieren würde, selbst wenn N eine Kehrtwende macht.

5. Wenn zwei Pfade kollidieren, müssen andere Regeln verwendet werden. Befinden sich zwei Fahrzeuge auf derselben vorrangigen Straße (siehe unten), erhält das Fahrzeug Vorfahrt , das:
   • Dies kommt von der Straße auf der rechten Seite, wenn sie aus orthogonalen Richtungen kommen
   • biegt nach rechts ab, wenn der andere nach links abbiegt
   • geht geradeaus oder biegt nach rechts ab, wenn der andere eine Kehrtwende macht.

     In beiden Beispielen unten hat das E-Fahrzeug Vorfahrt über das Fahrzeug S.

Im Beispiel unten geht zuerst W, dann N, dann E und zuletzt geht S.

In diesem speziellen Fall sollte die Ausgabe Ihres Programms sein:

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

6. Alle Fahrer benutzen Blinker und wissen, wohin alle anderen wollen (der Einfachheit halber nehmen wir an, dass es möglich ist, zwischen der Linkskurve und der Kehrtwende zu unterscheiden).

7. Manchmal erhalten Straßen Prioritätszeichen, die wichtiger sind als die oben genannten Regeln. Eine Straße mit höherer Priorität hat ein Prioritätszeichen ( Prioritätszeichenbild ). Wenn die Vorfahrtsstraße nicht gerade verläuft, werden auch zusätzliche Schilder wie dieses verwendet . Die Straßen mit niedrigerer Priorität haben ein Hinweisschild oder ein Stoppschild (sie sind gleichwertig). Keine oder genau zwei verschiedene Straßen haben höhere Priorität. Der Benutzer Ihres Programms sollte in der Lage sein, einzugeben, welche Straßen höhere (oder niedrigere) Prioritäten haben.

8. Ein Fahrzeug, das von einer Straße mit höherer Priorität kommt, hat Vorfahrt vor einem Fahrzeug, das von einer Straße mit niedrigerer Priorität kommt, auch wenn es sich auf der linken Seite befindet.
9. Wenn Pfade von zwei Fahrzeugen kollidieren, die von den Straßen mit der gleichen Priorität kommen, sind die Regeln oben rechts aktiv.

   In dem folgenden Beispiel haben die Straßen S und W Vorrangzeichen, was bedeutet, dass die Fahrzeuge in N und E ihnen den Weg weisen sollen. Das S-Fahrzeug hat Vorrang vor dem W-Fahrzeug, da es sich auf der rechten Seite befindet. Dann geht W, weil es auf der Straße mit höherer Priorität als E ist. Das Fahrzeug N hat Vorfahrt von E, weil es auf seiner rechten Seite ist. Wie das letzte geht E.

In diesem speziellen Fall sollte die Ausgabe Ihres Programms sein:

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

10. Es ist möglich, dass ein (und nicht mehr) Fahrzeug ein Einsatzfahrzeug ist, das Vorrang hat, unabhängig davon, aus welcher Richtung es kommt oder in welche Richtung es fährt und welches Zeichen es hat (es geht immer zuerst). Das Programm sollte es dem Benutzer ermöglichen, das Fahrzeug, bei dem es sich um ein Einsatzfahrzeug handelt, einzugeben. Wenn man bedenkt, dass im letzten Beispiel N ein Rettungsfahrzeug ist, geht N zuerst, dann S, W und als letztes E.

Für diesen speziellen Fall mit einem Einsatzfahrzeug bei N sollte die Ausgabe Ihres Programms sein:

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

11. Wenn zwei Fahrzeuge im selben Moment fahren dürfen (ihre Wege kollidieren nicht und sie müssen anderen Fahrzeugen nicht weichen), sollte Ihr Programm dies herausfinden und sie mit derselben Sequenznummer zurücksenden

    In dem folgenden Beispiel kollidieren die Pfade von N und E sowie von E und S oder von W und E nicht. Weil S N und W S nachgeben muss, kann S nicht gleichzeitig mit E usw. gehen. Die N und E können. Also gehen zuerst N und E zusammen, dann geht S und W als letztes.

Die korrekte Ausgabe Ihres Programms sollte sein:

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

Sie können die Reihenfolge der Zeilen frei wählen 1( N->W / E->Eentspricht E->E / N->W)

12. Manchmal kann der Verkehr zu einer unlösbaren Situation führen, in der kein Fahrzeug fahren kann. Im wirklichen Leben ist es gelöst, wenn einer der Fahrer freiwillig von seinem Wegerecht zurücktritt. Hier sollte Ihr Programm ausgeben, unsolvableusw., wie im ersten Teil der Frage erwähnt.

    Nachfolgend finden Sie ein Beispiel für eine unlösbare Situation. E sollte W weichen, W sollte S weichen und S sollte E weichen.

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);}

BEMERKUNGEN

Es ist definitiv kein kurzer (oder einfacher) Code. Es kann (stark) komprimiert werden, aber es ist eine Übung für den Leser (ich habe zu viel Zeit für dieses Problem aufgewendet).

Ich habe eine Lösung mit mehrzeiligen Kommentaren eingefügt, aber Zeilenumbrüche als 1 Byte angenommen und Kommentare (von / bis zum Zeilenende) verworfen, um die Größe zu zählen

Die Hauptschwierigkeit besteht darin, alle Regeln vollständig zu verstehen. Eine frühzeitige Optimierung der Codelänge ist nicht mit der Entwicklung einer Lösung für ein komplexes Problem vereinbar. Auch ein Bottom-Up- oder Top-Down-Ansatz kommt nicht mit unlesbarem Code zurecht.

Schließlich entwickelte ich eine Entscheidungstabelle (Konfliktmatrix) mit 16 Zeilen und 16 Spalten (für jede Richtung kombiniert mit jeder möglichen Runde). Die Werte der Elemente sind 0 (Kompatibilität), 1 (Präferenz für Zeile) oder 2 (Präferenz für Spalte). Es erfüllt jeden Test, von dem ich nicht sicher bin, ob alle möglichen Situationen gut abgedeckt sind

Die Quelldatei muss die Erweiterung k haben. Starten Sie den interaktiven Interpreter (kostenlos für nicht-kommerzielle Zwecke, kx.com) und werten Sie ihn bei Aufforderung aus (wie im Abschnitt "Test" gezeigt).

PRÜFUNG

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

ERLÄUTERUNG

Die Grundstruktur ist die 'Prioritätsmatrix'

   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

Bedeutung (am Beispiel)

• m[NW][SE] hat 0 wert (beide bewegungen sind kompatibel -concurrent-)
• m[EW][SN] hat 1 Wert (EW hat Vorrang vor SN) HINWEIS.- Andere Vorrangfaktoren können diesen Satz ändern (Einsatzfahrzeuge, Vorrangstraße, ..)
• m[NE][SE] hat 2 Werte (SE hat Vorrang vor NE) HINWEIS.- Andere Vorrangfaktoren können diesen Satz ändern (Einsatzfahrzeuge, Vorrangstraße, ..)

Die Matrix kann unter Verwendung von vier Submatrixtypen (4x4) aufgebaut werden

  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

Die Matrix wird durch eine Funktion ergänzt, die jeder Bewegung eine Priorität zuweist. Diese Funktion berücksichtigt Einsatzfahrzeuge, vorrangige Straßen, orthogonale Richtungen, Art der Abbiegung und Fahrzeuge, die von rechts kommen.

Wir sortieren Bewegungen nach Priorität und wenden Matrixwerte an. Die resultierende Submatrix enthält Konflikte und Prioritäten jeder Bewegung.

• wir analysieren unlösbare Fälle (gegenseitige Konflikte)
• Andernfalls wählen wir das Element mit der höchsten Priorität und alle damit kompatiblen und nicht mit früheren inkompatiblen Bewegungen inkompatiblen Bewegungen aus und erstellen eine Reihe von Bewegungen, die gleichzeitig ausgeführt werden dürfen
• Schreiben Sie diesen Satz von Bewegungen und wiederholen Sie den Rest der Kandidaten