Résoudre une intersection de circulation

26

La tâche

Écrivez un programme ou une fonction qui prend une structure d'intersection de trafic et génère la séquence dans laquelle les véhicules passeront.

La sortie doit contenir au maximum quatre lignes au format suivant #. x->y\n, où #est un numéro de numéro de séquence, suivi du point ., xet ysont des personnages ["N", "E", "S", "W"]. Ils doivent être séparés par des caractères ->. Si vous ne renvoyez pas un tableau de chaînes, chaque ligne doit se terminer par un \n(nouveau caractère de ligne) ou équivalent à votre système.

L'entrée doit prendre la forme suivante:

  • Partie 1: quatre caractères, chacun ayant la route de destination pour les routes sources dans l'ordre N, E, S, W (dans le sens des aiguilles d'une montre). Les caractères autorisés sont N, S, W, Eou . L'espace signifie qu'il n'y a pas de véhicule sur une route particulière. Par exemple, une chaîne S WEsignifie que N véhicule souhaite aller vers le Sud, l'espace signifie qu'il n'y a pas de véhicule E, Wsignifie que S souhaite aller vers l'Ouest, Esignifie que l'Ouest souhaite aller vers l'Est.
  • Partie 2 - un espace ou une seule lettre signifiant lequel est du véhicule d'urgence.
  • Partie 3 - deux caractères déterminant quelles routes sont prioritaires (p. Ex. NESignifie que le nord et l'est ont tous deux des priorités plus élevées que le sud et l'ouest). Si c'est plus facile pour vous, vous pouvez emprunter des routes moins prioritaires (dans ce cas SW).

Dans une situation sans solution , vous êtes autorisé à retourner une chaîne d' une ligne qui est clair pour l'utilisateur, comme unsolvable, no solutionet similaire. Les utilisateurs de JavaScript peuvent prendre une undefinedconstante intégrée .

Il s'agit d'un code-golf, donc la réponse la plus courte en octets l'emporte.

Les règles de circulation

Veuillez noter que certaines règles peuvent ne pas suivre les règles de circulation de votre pays. Certains d'entre eux ont été simplifiés pour faciliter le défi. N'utilisez pas cette question comme guide pour un système de circulation réel.

  1. Pour le défi, vous êtes autorisé à utiliser uniquement le trafic à droite.
  2. L'intersection de la circulation se compose exactement de quatre routes qui se rejoignent en un point. Ils sont marqués N(comme pour « Nord »), S, W, E. Ces lettres doivent être utilisées à la place de xet ydans l'exemple de sortie ci-dessus.

Une intersection

  1. Sur chaque route, il y a au plus un véhicule. Il n'est pas garanti qu'il y ait un véhicule sur chaque route. Chaque véhicule peut conduire dans n'importe laquelle des quatre directions, c.-à-d. tourner à gauche, tourner à droite, aller tout droit ou faire demi-tour .

Destinations possibles du véhicule S

  1. Si les trajectoires de deux véhicules ne se croisent pas (elles n'entrent pas en collision), elles peuvent aller au même moment. Les chemins ne se heurtent pas, si deux véhicules (la liste n'est peut-être pas complète, mais c'est intentionnel, juste pour vous donner un indice):
    • viennent de directions opposées et les deux vont tout droit, ou au moins l'un d'eux tourne à droite,
    • viennent de directions opposées et les deux tournent à gauche,
    • viennent de directions opposées et l'un d'eux tourne dans n'importe quelle direction ou fait demi-tour, tandis que l'autre fait demi-tour,
    • proviennent de directions orthogonales, celle de gauche tourne à droite et l'autre ne fait pas demi-tour

      Quelques exemples de chemins non en collision ci-dessous. Veuillez noter que sur le troisième dessin, tout chemin de N entrerait en collision avec le chemin de E, même si N fait demi-tour.

entrez la description de l'image ici entrez la description de l'image ici

entrez la description de l'image ici entrez la description de l'image ici

  1. Si deux chemins entrent en collision, il est nécessaire d'utiliser d'autres règles. Si deux véhicules sont sur la même route prioritaire (voir ci - dessous), le droit de passage est donnée au véhicule:
    • vient de la route du côté droit, si elles viennent de directions orthogonales
    • tourne à droite si l'autre tourne à gauche
    • va tout droit ou tourne à droite si l'autre fait demi-tour.

      Dans les deux exemples ci-dessous, le véhicule E a priorité sur le véhicule S.

entrez la description de l'image ici entrez la description de l'image ici

Dans l'exemple ci-dessous va d'abord W, puis N, puis E et enfin va S.

entrez la description de l'image ici

Dans ce cas particulier, la sortie de votre programme doit être:

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

  1. Tous les conducteurs utilisent des clignotants et savent où tous les autres veulent aller (pour simplifier, nous supposons qu'il est possible de faire la distinction entre le virage à gauche et le demi-tour).

  2. Parfois, les routes reçoivent des signaux prioritaires, qui sont plus importants que les règles ci-dessus. Une route avec une priorité plus élevée a un panneau de priorité ( image du panneau de priorité ). Si la route prioritaire ne va pas tout droit, des panneaux supplémentaires sont également utilisés, comme celui-ci . Les routes de priorité inférieure ont un panneau de rendement ou un panneau d'arrêt (ils sont équivalents). Aucune ou exactement deux routes différentes auront une priorité plus élevée. L'utilisateur de votre programme doit pouvoir saisir les routes qui ont des priorités plus élevées (ou plus basses).

  3. Un véhicule qui vient de la route avec une priorité plus élevée a la priorité sur un véhicule qui vient d'une route de priorité inférieure, même s'il est sur son côté gauche.
  4. Si les trajectoires de deux véhicules venant des routes avec la même priorité entrent en collision, les règles ci-dessus à droite sont actives.

    Dans l'exemple ci-dessous, les routes S et W ont des panneaux de priorité, ce qui signifie que les véhicules sur N et E doivent leur donner le chemin. Le véhicule S a la priorité sur le véhicule W, car il est sur son côté droit, donc va en premier. Vient ensuite W, car il est sur la route de priorité supérieure à E. Le véhicule N a la priorité sur E, car il est sur son côté droit. Comme le dernier va E.

entrez la description de l'image ici

Dans ce cas particulier, la sortie de votre programme doit être:

1. S->W
2. W->N
3. N->S
4. E->W
  1. Il est possible qu'un véhicule (et pas plus) soit un véhicule d'urgence , qui ait la priorité indépendamment de la direction dans laquelle il vient ou va, et quel signe il a (il va toujours en premier). Le programme devrait permettre à l'utilisateur d'entrer, quel véhicule est un véhicule d'urgence. Considérant que sur le dernier exemple N est un véhicule d'urgence, N va d'abord, puis S, W et comme le dernier E.

Pour ce cas particulier avec un véhicule d'urgence à N, la sortie de votre programme devrait être:

1. N->S
2. S->W
3. W->N
4. E->W
  1. Si deux véhicules sont autorisés à partir en même temps (leurs trajectoires ne se heurtent pas et n'ont pas à céder la place à d'autres véhicules), votre programme devrait le savoir et les renvoyer comme ayant le même numéro de séquence

    Dans l'exemple ci-dessous, les chemins de N et E ainsi que E et S ou W et E ne se heurtent pas. Parce que S doit céder la place à N et W céder la place à S, S ne peut pas aller simultanément avec E, etc. Le N et E le peuvent. Donc, au début, N et E vont ensemble, puis S et W en dernier.

entrez la description de l'image ici

La sortie appropriée de votre programme devrait être:

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

Vous êtes libre de choisir l'ordre des lignes 1( N->W / E->Eéquivaut à E->E / N->W)

  1. Parfois, le trafic peut conduire à une situation insoluble, qui ne permet à aucun véhicule de partir. Dans la vraie vie, le problème est résolu lorsqu'un des conducteurs démissionne volontairement de son emprise. Ici, votre programme devrait sortir unsolvableetc., comme mentionné dans la première partie de la question.

    Voici un exemple de situation insoluble. E doit céder la place à W, W doit céder la place à S et S doit céder la place à E.

entrez la description de l'image ici

code-golf Voitcus
la source
3
Je pense qu'un format d'entrée cohérent devrait être défini. "L'entrée peut avoir n'importe quelle structure que vous aimez" est un grand drapeau rouge. L'entrée peut-elle être la solution?
Calvin's Hobbies
@ Calvin'sHobbies J'ai mis à jour la question
Voitcus
Y a-t-il une chance que nous puissions obtenir un exemple d'entrée / sortie pour 1-2 cas?
Charlie Wynn
Donc, la question (et je suppose que la solution) suppose que la ou les routes en question sont à droite?
Tersosauros
C'est exactement comme ça que fonctionne Google Cars
coredump

Réponses:

8

Q, 645 octets

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

COMMENTAIRES

En définitive, ce n'est pas du code court (ni simple). Il peut être (sévèrement) compacté, mais il est laissé au lecteur comme exercice (j'ai consacré trop de temps à ce problème).

J'ai inclus une solution commentée sur plusieurs lignes, mais je suppose que les sauts de ligne sont à 1 octet et rejettent les commentaires (de / à la fin de la ligne) pour compter la taille

La principale difficulté est de bien comprendre toutes les règles. L'optimisation précoce de la longueur du code est incompatible avec le développement d'une solution à un problème complexe. Ni l'approche ascendante ni descendante ne résiste bien au code illisible.

Enfin, j'ai développé une table de décission (matrice de conflits) à 16 lignes et 16 colonnes (pour chaque direction combinée à chaque virage possible). Les valeurs des éléments sont 0 (compatibilité), 1 (préférence pour la ligne) ou 2 (préférence pour la colonne). Il satisfait tous les tests, je ne suis pas sûr que toutes les situations possibles soient bien couvertes

Le fichier source doit avoir l'extension k. Démarrez l'interpréteur interactif (gratuit pour une utilisation non commerciale, kx.com) et évaluez à l'invite (comme indiqué dans le paragraphe «test»)

TESTER

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

EXPLICATION

La structure de base est la «matrice de priorité»

   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

Signification (par exemple)

  • m[NW][SE] a 0 valeur (les deux mouvements sont compatibles -concurrent-)
  • m[EW][SN] a 1 valeur (EW a priorité sur SN) NOTE.- d'autres facteurs de priorité peuvent modifier cette phrase (véhicules d'urgence, route prioritaire, ..)
  • m[NE][SE] a 2 valeurs (SE a priorité sur NE) NOTE.- d'autres facteurs de priorité peuvent modifier cette phrase (véhicules d'urgence, route prioritaire, ..)

La matrice peut être construite à l'aide de quatre types de sous-matrice (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 matrice est complétée par une fonction qui attribue une priorité à chaque mouvement. Cette fonction tient compte des véhicules d'urgence, des routes prioritaires, des directions orthogonales, du type de virage et des véhicules «venant de la droite»

Nous trions les mouvements par priorité et appliquons des valeurs matricielles. La sous-matrice résultante inclut les conflits et la priorité de chaque mouvement.

  • nous analysons les cas insolubles (conflits mutuels)
  • sinon, nous sélectionnons l'élément le plus prioritaire et tous les mouvements compatibles avec lui et non incompatibles avec les mouvements incompatibles précédents, et créons un ensemble de mouvements autorisés à aller simultanément
  • Écrivez cet ensemble de mouvements et parcourez le reste des candidats
J. Sendra
la source