Fondo

Eres un rico ejecutivo de un imperio de software. Tu tiempo vale mucho dinero. Como tal, siempre debe viajar en la ruta más eficiente posible. Sin embargo, como ejecutivo, pasa mucho tiempo participando en llamadas telefónicas importantes. ¡Es de suma importancia que nunca cuelgue llamadas, por lo que nunca debe viajar a través de áreas que no tienen servicio celular!

El reto

Se le dará una lista de tres tuplas, cada una de las cuales representa la ubicación y el poder de una torre celular. Como ejemplo, [50, 25, 16]representaría una torre celular ubicada <x,y> = <50, 25>con un círculo de radio 16 que representa su círculo de influencia. Con esta lista en mente, debe viajar desde su posición inicial <0, 0>a su destino <511, 511>en la distancia más corta posible sin perder el servicio celular. Este es el código de golf , ¡el código más corto gana!

De entrada y salida

Usted es libre de manipular la entrada en un formulario que lo haga fácil de leer, como en un archivo, o como una matriz anidada a través de STDIN eval, etc. Puede codificar la entrada, siempre que su código funcione para otras entradas como bien. No se contarán los caracteres exactos utilizados para codificar la entrada, pero sí el nombre de la variable y los caracteres de asignación. No debe suponer que la entrada está en un orden específico, o que cada torre celular es relevante para el problema. Si tiene alguna pregunta, deje un comentario y trataré de aclararlo.

La salida debe ser una lista de coordenadas, marcando puntos que, cuando se conectan en orden, forman un camino hacia la salida. La precisión solo necesita redondearse al entero más cercano, y si está a 1-2 unidades de lo que tengo en mi ejemplo de salida, está bien. He incluido imágenes a continuación para aclarar esto.

¡La mejor de las suertes!

Ejemplos

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

La ruta anterior se resalta en azul, pero puede ver que la adición de más torres permite una ruta más óptima.

Pitón, 1,291 1,271 1,225 bytes

Como señaló Martin, este problema puede reducirse en gran medida a su excelente desafío de la banda de goma . Usando la terminología de ese desafío, podemos tomar como segundo conjunto de clavos los puntos de intersección entre los círculos en el límite del área cerrada:

Como banda elástica, podemos tomar cualquier camino P entre los dos puntos finales que se extiende dentro del área cerrada. Entonces podemos invocar una solución al problema de la banda elástica para producir una ruta mínima (localmente). El desafío es, por supuesto, encontrar tal ruta P , o más precisamente, encontrar suficientes rutas para que al menos una de ellas produzca la ruta global mínima (tenga en cuenta que en el primer caso de prueba necesitamos al menos una ruta para cubra todas las posibilidades, y en el segundo caso de prueba al menos dos.)

Un enfoque ingenuo sería probar todas las rutas posibles: para cada secuencia de círculos adyacentes (es decir, de intersección) que conectan los dos puntos finales, tome la ruta a lo largo de sus centros (cuando dos círculos se cruzan, el segmento entre sus centros siempre está dentro de su unión .) Aunque este enfoque es técnicamente correcto, puede conducir a un número ridículamente grande de caminos. Si bien pude resolver el primer caso de prueba usando este enfoque en unos segundos, el segundo tardó una eternidad. Aún así, podemos tomar este método como punto de partida e intentar minimizar la cantidad de rutas que tenemos que probar. Esto es lo que sigue.

Construimos nuestros caminos básicamente realizando una búsqueda profunda en la gráfica de círculos. Estamos buscando una manera de eliminar posibles direcciones de búsqueda en cada paso de la búsqueda.

Supongamos que en algún momento estamos en un círculo A , que tiene dos círculos adyacentes B y C , que también están adyacentes entre sí. Podemos ir de A a C visitando B (y viceversa), por lo que podríamos pensar que visitar B y C directamente desde A es innecesario. Desafortunadamente, esto está mal, como muestra esta ilustración:

Si los puntos en la ilustración son los dos puntos finales, podemos ver que yendo de A a C a través de B obtenemos un camino más largo.

Qué tal este: si estamos probando los movimientos A → B y A → C , entonces no es necesario probar A → B → C o A → C → B , ya que no pueden dar como resultado rutas más cortas. Nuevamente incorrecto:

El punto es que el uso de argumentos puramente adyacentes no lo va a cortar; también tenemos que usar la geometría del problema. Lo que los dos ejemplos anteriores tienen en común (así como el segundo caso de prueba a mayor escala) es que hay un "agujero" en el área cerrada. Se manifiesta en el hecho de que algunos de los puntos de intersección en el límite, nuestras "uñas", están dentro del triángulo △ ABC cuyos vértices son los centros de los círculos:

Cuando esto sucede, existe la posibilidad de que ir de A a B y de A a C resulte en diferentes caminos. Más importante aún, cuando no sucede (es decir, si no hubiera una brecha entre A , B y C ), se garantiza que todas las rutas que comiencen con A → B → C y con A → C y que de otro modo sean equivalentes resultarán en el mismo camino localmente mínima, por lo tanto, si volvemos a visitar B no necesitamos también de visitar C directamente a partir de una .

Esto nos lleva a nuestro método de eliminación: cuando estamos en un círculo A , mantenemos una lista H de los círculos adyacentes que hemos visitado. Esta lista está inicialmente vacía. Visitamos un círculo adyacente B si hay algún "clavos" en todos los triángulos formados por los centros de A , B y cualquiera de los círculos en H adyacentes a B . Este método reduce drásticamente el número de rutas que tenemos que probar a solo 1 en el primer caso de prueba y 10 en el segundo.

Algunas notas más:

• Es posible disminuir el número de rutas que probamos aún más, pero este método es lo suficientemente bueno para la escala de este problema.

• Utilicé el algoritmo de mi solución para el desafío de la banda elástica. Dado que este algoritmo es incremental, puede integrarse con bastante facilidad en el proceso de búsqueda de ruta, de modo que minimicemos la ruta a medida que avanzamos. Dado que muchas rutas comparten un segmento inicial, esto puede mejorar significativamente el rendimiento cuando tenemos muchas rutas. También puede perjudicar el rendimiento si hay muchos más callejones sin salida que rutas válidas. De cualquier manera, para los casos de prueba dados, realizar el algoritmo para cada ruta por separado es lo suficientemente bueno.

• Hay un caso límite en el que esta solución puede fallar: si alguno de los puntos en el límite es el punto de intersección de dos círculos tangentes, entonces, en algunas condiciones, el resultado puede ser incorrecto. Esto se debe a la forma en que funciona el algoritmo de banda elástica. Con algunas modificaciones también es posible manejar estos casos, pero, demonios, ya es lo suficientemente largo.

# 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])

La entrada se da a través de la variable Icomo un conjunto de tuplas ((x, y), r)donde (x, y)está el centro del círculo y rsu radio. Los valores deben ser floats, no ints. El resultado se imprime en STDOUT.

Ejemplo

# 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.        ]]