La tarea

Escriba un programa o función que tome una estructura de intersección de tráfico y genere la secuencia en la que pasarán los vehículos.

La salida debe contener como máximo cuatro líneas con el siguiente formato #. x->y\n, donde #es un número de secuencia, seguido del punto ., xy yson caracteres ["N", "E", "S", "W"]. Deben estar separados por caracteres ->. Si no devuelve una matriz de cadenas, cada línea debe terminar con un \n(nuevo carácter de línea) o equivalente a su sistema.

La entrada debe tomar la siguiente forma:

• Parte 1: cuatro caracteres, cada uno con el camino de destino para los caminos de origen en orden N, E, S, W (en sentido horario). Los caracteres permitidos son N, S, W, Eo . El espacio significa que no hay vehículo en una carretera en particular. Por ejemplo, cadena S WEsignifica que ese vehículo N desea ir hacia el sur, el espacio significa que no hay vehículo E, Wsignifica que S desea ir hacia el oeste, Esignifica que Occidente desea ir hacia el este.
• Parte 2: un espacio o una letra que significa cuál es el vehículo de emergencia.
• Parte 3: dos caracteres que determinan qué dos caminos tienen prioridad (por ejemplo, NEsignifica que Norte y Este tienen prioridades más altas que Sur y Oeste). Si es más fácil para usted, puede tomar carreteras de menor prioridad (en ese caso SW).

En una situación sin solución se le permite devolver una cadena de una línea que es claro para el usuario, como unsolvable, no solutiony similares. Los usuarios de JavaScript pueden tener undefinedconstante incorporado .

Este es un código de golf, por lo que gana la respuesta más corta en bytes.

Las reglas del trafico

Tenga en cuenta que algunas de las reglas pueden no seguir las reglas de tráfico de su país. Algunos de ellos se han simplificado para facilitar el desafío. No utilice esta pregunta como guía para el sistema de tráfico de la vida real.

1. Para el desafío, solo puede usar el tráfico del lado derecho.
2. La intersección de tráfico consta de exactamente cuatro caminos que se encuentran en un punto. Están marcados N(como para "Norte"), S, W, E. Estas letras deben usarse en lugar de xy yen el ejemplo de salida anterior.

3. En cada camino hay como máximo un vehículo. No se garantiza que haya un vehículo en cada carretera. Cada vehículo puede conducir en cualquiera de las cuatro direcciones, es decir. gire a la izquierda, gire a la derecha, siga recto o haga un cambio de sentido .

4. Si las rutas de dos vehículos no se cruzan (no chocan), pueden ir en el mismo momento. Las rutas no chocan si dos vehículos (la lista puede no estar completa, pero esto es intencional, solo para darle una pista):
   • provienen de direcciones opuestas y ambas van rectas, o al menos una de ellas gira a la derecha,
   • vienen de direcciones opuestas y ambos giran a la izquierda,
   • provienen de direcciones opuestas y uno de ellos gira en cualquier dirección o da la vuelta en U, mientras que el otro da la vuelta en U,
   • provienen de direcciones ortogonales, la de la izquierda gira a la derecha y la otra no gira en U

     Algunos ejemplos de caminos que no chocan a continuación. Tenga en cuenta que en el tercer dibujo cualquier camino de N colisionaría con el camino de E, incluso si N hace un giro en U.

5. Si dos caminos chocan, es necesario usar otras reglas. Si dos vehículos están en la misma carretera de prioridad (ver más abajo), se otorga el derecho de paso al vehículo que:
   • viene de la carretera del lado derecho, si vienen de direcciones ortogonales
   • gira a la derecha si la otra gira a la izquierda
   • va derecho o gira a la derecha si el otro hace un cambio de sentido.

     En los dos ejemplos a continuación, el vehículo E tiene derecho de paso sobre el vehículo S.

En el siguiente ejemplo, primero va W, luego N, luego E y el último va S.

Para este caso particular, la salida de su programa debe ser:

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

6. Todos los conductores usan señales de giro y saben a dónde quieren ir todos los demás (por simplicidad, suponemos que es posible distinguir entre el giro a la izquierda y el giro en U).

7. A veces, las carreteras reciben señales de prioridad, que son más importantes que las reglas anteriores. Una carretera con mayor prioridad tiene una señal de prioridad ( imagen de señal de prioridad ). Si el camino prioritario no va recto, también se utilizan señales adicionales, como esta . Las carreteras con menor prioridad tienen una señal de rendimiento o una señal de stop (son equivalentes). Ninguna o exactamente dos carreteras diferentes tendrán mayor prioridad. El usuario de su programa debe poder ingresar qué caminos tienen prioridades más altas (o más bajas).

8. Un vehículo que viene de la carretera con mayor prioridad tiene el derecho de paso sobre un vehículo que viene de una carretera de menor prioridad, incluso si está en su lado izquierdo.
9. Si las rutas de dos vehículos que vienen de las carreteras con la misma prioridad chocan, las reglas de arriba a la derecha están activas.

   En el ejemplo a continuación, las carreteras S y W tienen señales de prioridad, lo que significa que los vehículos en N y E deberían darles el camino. El vehículo S tiene prioridad sobre el vehículo W, ya que está en su lado derecho, por lo que va primero. Luego va W, porque está en el camino de mayor prioridad que E. El vehículo N tiene derecho de paso desde E, porque está en su lado derecho. Como va el último E.

Para este caso particular, la salida de su programa debe ser:

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

10. Es posible que un vehículo (y no más) sea un vehículo de emergencia , que tiene la prioridad independientemente de la dirección de donde viene o va, y qué señal tiene (siempre va primero). El programa debe permitir al usuario ingresar, qué vehículo es un vehículo de emergencia. Considerando que en el último ejemplo N es un vehículo de emergencia, N va primero, luego S, W y como el último E.

Para este caso particular con un vehículo de emergencia en N, la salida de su programa debe ser:

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

11. Si se permite que dos vehículos vayan en el mismo momento (sus caminos no chocan y no tienen que ceder el paso a otros vehículos), su programa debería descubrirlo y devolverlos con el mismo número de secuencia

    En el siguiente ejemplo, las rutas de N y E, así como E y S o W y E no chocan. Debido a que S tiene que dar paso a N y W a S, S no puede ir simultáneamente con E, etc. Los N y E sí pueden. Entonces, al principio, N y E van juntos, que S y W son los últimos.

El resultado adecuado de su programa debe ser:

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

Usted es libre de elegir el orden de las líneas 1( N->W / E->Ees equivalente a E->E / N->W)

12. A veces, el tráfico puede conducir a una situación insoluble, que no permite que ningún vehículo vaya. En la vida real se resuelve cuando uno de los conductores renuncia voluntariamente a su derecho de paso. Aquí, su programa debería generar unsolvableetc., como se menciona en la primera parte de la pregunta.

    A continuación se muestra un ejemplo de situación insoluble. E debería dar paso a W, W debería dar paso a S y S debería dar paso a E.

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

COMENTARIOS

Definitivamente, no es un código corto (ni simple). Se puede compactar (severamente), pero se deja como ejercicio al lector (he dedicado demasiado tiempo a este problema).

He incluido una solución comentada multilínea, pero asumo las nuevas líneas como 1 byte y descarto los comentarios (desde / hasta el final de la línea) para contar el tamaño

La principal dificultad es comprender completamente todas las reglas. La optimización temprana de la longitud del código es incompatible con el desarrollo de una solución para un problema complejo. Ni el enfoque ascendente o descendente se adapta bien al código ilegible.

Finalmente, desarrollé una tabla de decisión (matriz de conflicto) con 16 filas y 16 columnas (para cada dirección combinada con cada posible turno). Los valores de los elementos son 0 (compatibilidad), 1 (preferencia por fila) o 2 (preferencia por columna). Satisface todas las pruebas, ya que no estoy seguro de que todas las situaciones posibles estén bien cubiertas

El archivo fuente debe tener una extensión k. Inicie el intérprete interactivo (gratuito para uso no comercial, kx.com) y evalúe en la solicitud (como se muestra en el párrafo 'prueba')

PRUEBA

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

EXPLICACIÓN

La estructura base es la 'matriz de precedencia'

   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

Significado (por ejemplo)

• m[NW][SE] tiene valor 0 (ambos movimientos son compatibles -concurrentes-)
• m[EW][SN] tiene 1 valor (EW tiene prioridad sobre SN) NOTA.- otros factores de prioridad pueden alterar esta oración (vehículos de emergencia, carretera de prioridad, ..)
• m[NE][SE] tiene valor 2 (SE tiene prioridad sobre NE) NOTA.- otros factores de prioridad pueden alterar esta oración (vehículos de emergencia, carretera de prioridad, ..)

La matriz se puede construir utilizando cuatro tipos de submatrices (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

La matriz se complementa con una función que asigna una prioridad a cada movimiento. Esa función tiene en cuenta los vehículos de emergencia, las carreteras prioritarias, las direcciones ortogonales, el tipo de giro y los vehículos que "vienen de la derecha".

Ordenamos los movimientos por prioridad y aplica valores de matriz. La submatriz resultante incluye conflictos y prioridad de cada movimiento.

• Analizamos casos irresolubles (conflictos mutuos)
• si no, seleccionamos el ítem más prioritario y todos los movimientos compatibles con él y no incompatibles con movimientos incompatibles anteriores, y creamos un conjunto de movimientos permitidos para ir simultáneamente
• Escribe ese conjunto de movimientos e itera sobre el resto de candidatos