Planifier un arrêt à 4 voies

Un tas de voitures sont alignées à un panneau d'arrêt à 4 voies en attente de continuer. Tout le monde est confus quant à savoir qui va ensuite, qui va dans quel sens, etc. Clairement sous-optimal.

Votre travail consiste à planifier le trafic au stop de manière optimale.

Vous recevez en entrée 4 chaînes de demandes de virage, une pour chacune des quatre directions cardinales. Chaque demande est soit Lpour gauche, Spour droite ou Rpour droite.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

La première rangée est l'alignement à l'entrée nord de l'intersection. La première voiture en ligne souhaite tourner à gauche (c'est-à-dire, sortie Est). Les lignes suivantes concernent les entrées entrantes Est, Sud et Ouest. La première voiture venant de l'Ouest souhaite donc sortir vers le Sud.

Le trafic se déplace en une série d'étapes. À chaque étape, vous devez choisir un sous-ensemble de voitures en tête de leurs lignes pour continuer. Les voitures choisies ne doivent pas interférer entre elles. Deux voitures interfèrent si elles sortent dans la même direction ou si elles doivent se croiser (compte tenu des règles de conduite à droite standard). Donc, deux voitures opposées qui souhaitent aller tout droit peuvent aller au même pas. Alors que 4 voitures souhaitent toutes tourner à droite. Deux voitures opposées peuvent tourner à gauche simultanément.

Votre travail consiste à planifier l'intersection en une série minimale d'étapes. Pour chaque étape, affichez une ligne avec la ou les directions de la boussole des voitures entrantes répertoriées. Pour l'exemple ci-dessus, la planification minimale est de 14 étapes. Un calendrier minimal est:

N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

Votre programme devrait être capable de gérer 50 voitures sur chaque ligne en moins d'une minute. L'entrée des 4 chaînes et la sortie de la programmation peuvent être de n'importe quelle manière pratique pour votre langue.

Le programme le plus court gagne.

Un exemple plus large:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

qui nécessite un minimum de 38 tours. Une solution possible:

E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

Python, 1219 octets

Je n'ai pas passé beaucoup de temps / d'efforts à essayer de jouer au golf, mais je pourrais l'améliorer si d'autres réponses commencent à apparaître. J'utilise la recherche A * avec une heuristique admissible , garantissant l'optimalité. Je suis assez sûr (même si je n'ai pas pris la peine de confirmer) que l'heuristique est également cohérente , ce qui signifie qu'il s'agit de O (programmation dynamique).

Le programme lit en quatre lignes à partir de STDIN dans le format que vous avez spécifié et imprime le résultat sur STDOUT, également dans le format que vous avez spécifié.

from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

Exemple d'utilisation:

$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total