Contexte

Vous êtes un riche dirigeant d'un empire logiciel. Votre temps vaut beaucoup d'argent. En tant que tel, vous devez toujours voyager sur l'itinéraire le plus efficace possible. Cependant, en tant que cadre, vous passez beaucoup de temps à participer à des appels téléphoniques importants. Il est primordial que vous ne perdiez jamais d'appels, vous ne devez donc jamais voyager dans des zones qui n'ont pas de service cellulaire!

Le défi

Vous recevrez une liste de trois tuples, chacun représentant l'emplacement et la puissance d'une tour de cellule. Par exemple, [50, 25, 16]représenterait une tour de cellule située à <x,y> = <50, 25>un cercle de rayon 16 représentant son cercle d'influence. Avec cette liste à l'esprit, vous devez voyager de votre position de départ <0, 0>à votre destination à <511, 511>, sur la distance la plus courte possible sans perdre le service cellulaire. C'est le code-golf , donc le code le plus court gagne!

Entrée sortie

Vous êtes libre de manipuler l'entrée dans un formulaire qui la rend facile à lire, comme dans un fichier, ou sous forme de tableau imbriqué via STDIN eval, etc. Vous pouvez coder en dur l'entrée, tant que votre code fonctionne pour d'autres entrées comme bien. Les caractères exacts utilisés pour coder en dur l'entrée ne seront pas comptés, mais le nom de la variable et les caractères d'affectation le seront. Vous ne devez pas supposer que l'entrée est dans un ordre spécifique ou que chaque tour de cellule est pertinente pour le problème. Si vous avez des questions, veuillez laisser un commentaire et je vais essayer de le clarifier.

La sortie doit être une liste de coordonnées, marquant les points qui, une fois connectés, forment un chemin vers la sortie. La précision n'a besoin d'être arrondie qu'à l'entier le plus proche, et si vous êtes à 1-2 unités de ce que j'ai en exemple de sortie, c'est très bien. J'ai inclus des images ci-dessous pour clarifier cela.

Bonne chance!

Exemples

input:
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]

output:
0 0
154 139
169 152
189 153
325 110
381 110
400 120
511 511

input2
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]
[180, 230,  39]
[162, 231,  39]
[157, 281,  23]
[189, 301,  53]
[216, 308,  27]
[213, 317,  35]
[219, 362,  61]
[242, 365,  42]
[288, 374,  64]
[314, 390,  53]
[378, 377,  30]
[393, 386,  34]

output2:
0 0
247 308
511 511

Le chemin précédent est surligné en bleu, mais vous pouvez voir que l'ajout de plus de tours permet un itinéraire plus optimal.

Python, 1 291 1 271 1 225 octets

Comme Martin l'a noté, ce problème peut être largement réduit à son excellent défi d'élastique . En utilisant la terminologie de ce défi, nous pouvons prendre comme deuxième ensemble de clous les points d'intersection entre les cercles à la limite de la zone fermée:

En tant qu'élastique, nous pouvons prendre n'importe quel chemin P entre les deux points d'extrémité qui s'étend à l'intérieur de la zone fermée. Nous pouvons alors invoquer une solution au problème de l'élastique pour produire un chemin minimal (local). Le défi est, bien sûr, de trouver un tel chemin P , ou plus précisément, de trouver suffisamment de chemins pour qu'au moins l'un d'eux produise le chemin globalement minimal (notez que dans le premier cas de test, nous avons besoin d'au moins un chemin pour couvrir toutes les possibilités, et dans le deuxième cas de test au moins deux.)

Une approche naïve serait d'essayer simplement tous les chemins possibles: pour chaque séquence de cercles adjacents (c'est-à-dire qui se croisent) qui relie les deux points d'extrémité, prenez le chemin le long de leurs centres (lorsque deux cercles se croisent, le segment entre leurs centres est toujours dans leur union .) Bien que cette approche soit techniquement correcte, elle peut conduire à un nombre ridiculement élevé de chemins. Alors que j'ai pu résoudre le premier cas de test en utilisant cette approche en quelques secondes, le second a pris une éternité. Néanmoins, nous pouvons prendre cette méthode comme point de départ et essayer de minimiser le nombre de chemins à tester. Voici ce qui suit.

Nous construisons nos chemins en effectuant essentiellement une recherche en profondeur d'abord sur le graphique des cercles. Nous recherchons un moyen d'éliminer les directions de recherche potentielles à chaque étape de la recherche.

Supposons qu'à un moment donné, nous soyons dans un cercle A , qui a deux cercles adjacents B et C , qui sont également adjacents l'un à l'autre. Nous pouvons aller de A à C en visitant B (et vice versa), donc nous pourrions penser que visiter B et C directement de A n'est pas nécessaire. Malheureusement, c'est faux, comme le montre cette illustration:

Si les points dans l'illustration sont les deux points de terminaison, nous pouvons voir qu'en allant de A à C en passant par B, nous obtenons un chemin plus long.

Qu'en est-il de celui-ci: si nous testons les mouvements A → B et A → C , alors il n'est pas nécessaire de tester A → B → C ou A → C → B , car ils ne peuvent pas entraîner des chemins plus courts. Encore faux:

Le fait est que l'utilisation d'arguments purement basés sur la contiguïté ne va pas le couper; nous devons également utiliser la géométrie du problème. Ce que les deux exemples ci-dessus ont en commun (ainsi que le deuxième cas de test à plus grande échelle), c'est qu'il y a un "trou" dans la zone fermée. Elle se manifeste dans le fait que certains des points d'intersection sur la frontière - nos «clous» - se trouvent dans le triangle △ ABC dont les sommets sont les centres des cercles:

Lorsque cela se produit, il y a une chance que le passage de A à B et de A à C entraîne des chemins différents. Plus important encore, lorsque cela ne se produit pas (c'est-à-dire s'il n'y avait pas d'écart entre A , B et C ), il est garanti que tous les chemins commençant par A → B → C et avec A → C et qui sont par ailleurs équivalents entraîneront dans le même chemin minimal localement, donc si nous visitons B on n'a pas besoin de visiter également C directement de A .

Cela nous amène à notre méthode d'élimination: lorsque nous sommes dans un cercle A , nous conservons une liste H des cercles adjacents que nous avons visités. Cette liste est initialement vide. Nous nous rendons un cercle adjacent B s'il y a des « clous » dans tous les triangles formés par les centres A , B et l' un des cercles en H adjacents à B . Cette méthode réduit considérablement le nombre de chemins que nous devons tester à seulement 1 dans le premier cas de test et 10 dans le second.

Quelques notes supplémentaires:

• Il est possible de réduire encore le nombre de chemins que nous testons, mais cette méthode est assez bonne pour l'ampleur de ce problème.

• J'ai utilisé l'algorithme de ma solution au défi de l'élastique. Étant donné que cet algorithme est incrémentiel, il peut être assez facilement intégré dans le processus de recherche de chemin, afin de minimiser le chemin au fur et à mesure. Étant donné que de nombreux chemins partagent un segment de départ, cela peut améliorer considérablement les performances lorsque nous avons beaucoup de chemins. Cela peut également nuire aux performances s'il y a beaucoup plus d'impasses que de chemins valides. Quoi qu'il en soit, pour les cas de test donnés, l'exécution de l'algorithme pour chaque chemin séparément est suffisamment bonne.

• Il y a un cas où cette solution peut échouer: si l'un des points sur la frontière est le point d'intersection de deux cercles tangents, dans certaines conditions, le résultat peut être faux. Cela est dû au fonctionnement de l'algorithme élastique. Avec quelques modifications, il est également possible de gérer ces cas, mais, bon sang, c'est déjà assez long.

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}

from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
 for C,R in I:
  v=V(C)-c;d=L(v)
  if d:
    a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
    if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
 try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
 except:return[[]]*2
def P(I,c,r,A):
 H=[];M=[""]
 if L(c-e)>r*r:
    for C,R in I:
     if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
    return M
 A+=[e]*2;W=[.5]*len(A)
 try:
  while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
 except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])

L'entrée est donnée par la variable Icomme un ensemble de tuples ((x, y), r)où (x, y)est le centre du cercle et rson rayon. Les valeurs doivent être floats, pas ints. Le résultat est imprimé sur STDOUT.

Exemple

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}

[[   0.            0.        ]
 [ 154.58723733  139.8329183 ]
 [ 169.69950891  152.76985495]
 [ 188.7391093   154.02738541]
 [ 325.90536774  109.74141936]
 [ 382.19108518  109.68789517]
 [ 400.00362897  120.91319495]
 [ 511.          511.        ]]