Zadanie

Napisz program lub funkcję, która pobiera strukturę skrzyżowania i generuje sekwencję, w której przejeżdżają pojazdy.

Wyjście powinno zawierać co najwyżej cztery linie z następującym formacie #. x->y\n, gdzie #jest liczbą numer porządkowy, a po nim kropkę ., xi yto znaki ["N", "E", "S", "W"]. Powinny być oddzielone znakami ->. Jeśli nie zwrócisz tablicy ciągów, każda linia musi kończyć się \n(nowym znakiem linii) lub odpowiednikiem twojego systemu.

Dane wejściowe powinny przyjąć następującą formę:

• Część 1: cztery znaki, każdy mający drogę docelową dla dróg źródłowych w kolejności N, E, S, W (zgodnie z ruchem wskazówek zegara). Dozwolone znaki to N, S, W, Elub . Przestrzeń oznacza, że ​​na danej drodze nie ma pojazdu. Na przykład string S WEoznacza, że ​​pojazd N chce jechać na południe, spacja oznacza, że ​​nie ma pojazdu E, Woznacza, że ​​S chce jechać na zachód, Eoznacza , że Zachód chce jechać na wschód.
• Część 2 - spacja lub pojedyncza litera oznaczająca, który pojazd awaryjny.
• Część 3 - dwa znaki określające, które dwie drogi mają pierwszeństwo (np. NEOznacza, że ​​północ i wschód mają wyższy priorytet niż zarówno południe, jak i zachód). Jeśli jest ci łatwiej, możesz wybrać drogi o niższym priorytecie (w takim przypadku SW).

W nierozwiązywalnym sytuacji masz prawo do zwrotu ciąg jednego wiersza, który jest jasne dla użytkownika, jak unsolvable, no solutioni podobne. Użytkownicy JavaScript mogą pobierać wbudowaną undefinedstałą.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach.

Zasady ruchu

Pamiętaj, że niektóre zasady mogą być niezgodne z przepisami ruchu drogowego obowiązującymi w Twoim kraju. Niektóre z nich zostały uproszczone, aby ułatwić wyzwanie. Nie używaj tego pytania jako przewodnika dla prawdziwego systemu ruchu drogowego.

1. Do wyzwania możesz używać wyłącznie ruchu po prawej stronie.
2. Skrzyżowanie ruchu składa się z dokładnie czterech dróg, które spotykają się w jednym punkcie. Są one oznaczone N(jak na „Północ”), S, W, E. Te litery powinny być użyte zamiast xiw ypowyższym przykładzie wyjściowym.

3. Na każdej drodze znajduje się najwyżej jeden pojazd. Nie ma gwarancji, że na każdej drodze znajduje się pojazd. Każdy pojazd może jechać w dowolnym z czterech kierunków, tj. skręć w lewo, skręć w prawo, idź prosto lub zawróć .

4. Jeśli ścieżki dwóch pojazdów się nie przecinają (nie zderzają), mogą jechać w tym samym momencie. Ścieżki nie kolidują, jeśli dwa pojazdy (lista może nie być kompletna, ale jest to celowe, aby dać ci wskazówkę):
   • pochodzą z przeciwnych kierunków i oba idą prosto, lub przynajmniej jeden z nich skręca w prawo,
   • pochodzą z przeciwnych kierunków i oba skręcają w lewo,
   • pochodzą z przeciwnych kierunków i jeden z nich skręca w dowolnym kierunku lub wykonuje zawracanie, a drugi wykonuje zawracanie,
   • wychodzą z ortogonalnych kierunków, jeden w lewo skręca w prawo, a drugi nie zawraca

     Poniżej kilka przykładów nie kolidujących ścieżek. Należy pamiętać, że na trzecim losowaniu każda ścieżka N zderzyłaby się ze ścieżką E, nawet jeśli N wykona zawrót.

5. Jeśli dwie ścieżki kolidują, konieczne jest użycie innych reguł. Jeżeli dwa pojazdy znajdują się na tej samej drodze priorytetowej (patrz poniżej), pierwszeństwo ma pojazd, który:
   • pochodzi z drogi po prawej stronie, jeśli pochodzą z kierunków ortogonalnych
   • skręca w prawo, jeśli drugi skręca w lewo
   • idzie prosto lub skręca w prawo, jeśli drugi wykonuje zawracanie.

     W obu poniższych przykładach pojazd E ma pierwszeństwo przejazdu nad pojazdem S.

W poniższym przykładzie najpierw idzie W, potem N, następnie E, a ostatni S.

W tym konkretnym przypadku dane wyjściowe Twojego programu powinny wynosić:

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

6. Wszyscy kierowcy używają kierunkowskazów i wiedzą, dokąd zmierzają wszyscy inni (dla uproszczenia zakładamy, że można odróżnić skręt w lewo od skrętu w prawo).

7. Czasami drogi otrzymują znaki pierwszeństwa, które są ważniejsze niż powyższe zasady. Droga o wyższym priorytecie ma znak priorytetu ( obraz znaku priorytetu ). Jeśli droga priorytetowa nie prowadzi prosto, stosowane są również dodatkowe znaki, takie jak ta . Drogi o niższym priorytecie mają znak wydajności lub znak stopu (są one równoważne). Żadna lub dokładnie dwie różne drogi nie będą miały wyższego priorytetu. Użytkownik Twojego programu powinien mieć możliwość wprowadzenia, które drogi mają wyższy (lub niższy) priorytet.

8. Pojazd jadący z drogi o wyższym priorytecie ma pierwszeństwo przejazdu nad pojazdem jadącym z drogi o niższym priorytecie, nawet jeśli znajduje się po jego lewej stronie.
9. Jeśli zderzają się ścieżki dwóch pojazdów jadących z dróg o tym samym priorytecie, obowiązują powyższe reguły po prawej stronie.

   Na poniższym przykładzie drogi S i W mają znaki pierwszeństwa, co oznacza, że ​​pojazdy na drogach N i E powinny dać im drogę. Pojazd S ma pierwszeństwo przed pojazdem W, ponieważ znajduje się po prawej stronie, więc idzie pierwszy. Następnie jedzie W, ponieważ znajduje się na drodze o wyższym priorytecie niż E. Pojazd N ma pierwszeństwo drogi E, ponieważ znajduje się po prawej stronie. W ostatnim odcinku E.

W tym konkretnym przypadku dane wyjściowe Twojego programu powinny wynosić:

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

10. Możliwe jest, że jeden (i nie więcej) pojazd jest pojazdem ratunkowym , który ma priorytet niezależnie od tego, z którego kierunku jedzie lub idzie i jaki ma znak (zawsze idzie pierwszy). Program powinien umożliwić użytkownikowi wprowadzenie, który pojazd jest pojazdem awaryjnym. Biorąc pod uwagę, że w ostatnim przykładzie N jest pojazdem awaryjnym, N najpierw jedzie, a następnie S, W i jako ostatni E.

W tym konkretnym przypadku z pojazdem ratunkowym w punkcie N wynik programu powinien wynosić:

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

11. Jeśli dwa pojazdy mogą jechać w tym samym momencie (ich ścieżki nie kolidują i nie muszą ustępować innym pojazdom), twój program powinien to ustalić i zwrócić je jako mające ten sam numer kolejny

    Na poniższym przykładzie ścieżki N i E oraz E i S lub W i E nie kolidują. Ponieważ S musi ustąpić miejsca N, a W ustąpić miejsca S, S nie może iść jednocześnie z E itp. N i E mogą. Na początku N i E idą razem, a następnie S i W jako ostatnie.

Prawidłowe wyjście twojego programu powinno być:

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

Możesz wybrać kolejność linii 1( N->W / E->Eodpowiada to E->E / N->W)

12. Czasami ruch uliczny może doprowadzić do nierozwiązywalnej sytuacji, która nie pozwala na przejechanie żadnego pojazdu. W prawdziwym życiu rozwiązuje się to, gdy jeden z kierowców dobrowolnie rezygnuje z pierwszeństwa. Tutaj twój program powinien wypisywać unsolvableitp., Jak wspomniano w pierwszej części pytania.

    Poniżej znajduje się przykład nierozwiązywalnej sytuacji. E powinno ustępować W, W powinno ustąpić S, a S powinno ustąpić E.

Q, 645 bajtów

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

KOMENTARZE

Ostatecznie nie jest to krótki (ani prosty) kod. Można go (poważnie) zagęścić, ale pozostawia on czytelnikowi zadanie (zbyt wiele czasu poświęciłem temu problemowi).

Dodałem rozwiązanie z komentarzem wieloliniowym, ale zakładam nowe wiersze jako 1 bajt i odrzucam komentarze (od / do końca wiersza), aby policzyć rozmiar

Główną trudnością jest pełne zrozumienie wszystkich zasad. Wczesna optymalizacja długości kodu jest niezgodna z opracowaniem rozwiązania złożonego problemu. Podejście oddolne i odgórne nie radzi sobie dobrze z nieczytelnym kodem.

Wreszcie opracowałem tabelę decyzyjną (macierz konfliktu) z 16 rzędami i 16 kolumnami (dla każdego kierunku w połączeniu z każdym możliwym zakrętem). Wartości elementów to 0 (zgodność), 1 (preferencja dla wiersza) lub 2 (preferencja dla kolumny). Spełnia wszystkie testy, ponieważ nie jestem pewien, czy wszystkie możliwe sytuacje są dobrze uwzględnione

Plik źródłowy musi mieć rozszerzenie k. Uruchom interaktywnego tłumacza (darmowy do użytku niekomercyjnego, kx.com) i oceniaj natychmiast (jak pokazano w paragrafie „test”)

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

WYJAŚNIENIE

Podstawową strukturą jest „matryca pierwszeństwa”

   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

Znaczenie (przez przykład)

• m[NW][SE] ma wartość 0 (oba ruchy są kompatybilne -prąd-)
• m[EW][SN] ma 1 wartość (EW ma pierwszeństwo przed SN) UWAGA. - inne czynniki mogą zmienić to zdanie (pojazdy ratownicze, droga priorytetowa, ...)
• m[NE][SE] ma wartość 2 (SE ma pierwszeństwo przed NE) UWAGA. - inne czynniki mogą zmienić to zdanie (pojazdy ratownicze, droga priorytetowa, ...)

Matryca może być zbudowana przy użyciu czterech typów submatrix (4x4)

  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

Matryca jest uzupełniona funkcją, która przypisuje priorytet każdemu ruchowi. Ta funkcja uwzględnia pojazdy ratunkowe, priorytetowe drogi, ortogonalne kierunki, rodzaj skrętu i pojazdy „jadące z prawej”

Sortujemy ruchy według priorytetu i stosujemy wartości macierzy. Wynikowa submatrix zawiera konflikty i priorytet każdego ruchu.

• analizujemy nierozwiązywalne przypadki (wzajemne konflikty)
• jeśli nie, wybieramy element priorytetowy i wszystkie ruchy zgodne z nim i niekompatybilne z poprzednimi ruchami niekompatybilnymi i tworzymy zestaw ruchów, które mogą iść jednocześnie
• Napisz ten zestaw ruchów i powtórz resztę kandydatów