Hintergrund

Sie sind ein reicher Manager eines Softwareimperiums. Ihre Zeit ist viel Geld wert. Aus diesem Grund müssen Sie immer auf der effizientesten Route fahren. Als Führungskraft verbringen Sie jedoch viel Zeit damit, an wichtigen Telefonanrufen teilzunehmen. Es ist von größter Wichtigkeit, dass Sie niemals Anrufe abweisen. Fahren Sie also niemals durch Gebiete, in denen kein Mobilfunk verfügbar ist!

Die Herausforderung

Sie erhalten eine Liste mit drei Tupeln, von denen jedes die Position und die Leistung eines Zellturms darstellt. Als Beispiel [50, 25, 16]würde ein Zellturm dargestellt, der sich <x,y> = <50, 25>mit einem Kreis mit dem Radius 16 befindet, der seinen Einflusskreis darstellt. In Anbetracht dieser Liste müssen Sie von Ihrem Startort <0, 0>bis zu Ihrem Zielort <511, 511>in der kürzestmöglichen Entfernung reisen , ohne den Mobilfunkdienst zu verlieren. Das ist Code-Golf , also gewinnt der kürzeste Code!

Input-Output

Es steht Ihnen frei, die Eingabe in ein Formular zu ändern eval, das das Lesen erleichtert, z. B. in einer Datei oder als verschachteltes Array über STDIN usw. Sie können die Eingabe fest codieren , sofern Ihr Code für andere Eingaben wie z Gut. Die genauen Zeichen, mit denen die Eingabe fest codiert wurde, werden nicht gezählt, der Variablenname und die Zuweisungszeichen jedoch. Sie sollten nicht davon ausgehen, dass sich die Eingabe in einer bestimmten Reihenfolge befindet oder dass jeder Zellturm für das Problem relevant ist. Wenn Sie Fragen haben, hinterlassen Sie bitte einen Kommentar und ich werde versuchen, es zu klären.

Die Ausgabe soll eine Liste von Koordinaten sein, die Punkte markieren, die, wenn sie verbunden sind, einen Pfad zum Ausgang bilden. Die Genauigkeit muss nur auf die nächste ganze Zahl gerundet werden, und wenn Sie 1-2 Einheiten von dem abweichen, was ich in meinem Ausgabebeispiel habe, ist das in Ordnung. Ich habe Bilder unten aufgenommen, um dies zu verdeutlichen.

Viel Glück!

Beispiele

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

Der vorherige Pfad ist blau hervorgehoben, aber Sie können sehen, dass das Hinzufügen von mehr Türmen eine optimalere Route ermöglicht.

Python, 1,291 1,271 1.225 Bytes

Wie Martin bemerkte, kann dieses Problem weitgehend auf seine hervorragende Gummiband-Herausforderung reduziert werden . Unter Verwendung der Terminologie dieser Herausforderung können wir als zweiten Satz von Nägeln die Schnittpunkte zwischen den Kreisen an der Grenze des umschlossenen Bereichs nehmen:

Als Gummiband können wir einen beliebigen Pfad P zwischen den beiden Endpunkten nehmen, der innerhalb des umschlossenen Bereichs verläuft. Wir können dann eine Lösung für das Gummibandproblem aufrufen, um einen (lokal) minimalen Pfad zu erzeugen. Die Herausforderung besteht natürlich darin, einen solchen Pfad P zu finden , oder genauer gesagt, genügend Pfade zu finden , so dass mindestens einer von ihnen den global minimalen Pfad erzeugt (beachten Sie, dass wir im ersten Testfall mindestens einen Pfad zu benötigen decken Sie alle Möglichkeiten ab, und im zweiten Testfall mindestens zwei.)

Ein naiver Ansatz wäre, einfach alle möglichen Pfade auszuprobieren: Nehmen Sie für jede Folge benachbarter (dh sich schneidender) Kreise, die die beiden Endpunkte verbinden, den Pfad entlang ihrer Zentren (wenn sich zwei Kreise schneiden, befindet sich das Segment zwischen ihren Zentren immer innerhalb ihrer Vereinigung) .) Obwohl dieser Ansatz technisch korrekt ist, kann er zu einer lächerlich großen Anzahl von Pfaden führen. Während ich den ersten Testfall mit diesem Ansatz in wenigen Sekunden lösen konnte, dauerte der zweite ewig. Dennoch können wir diese Methode als Ausgangspunkt nehmen und versuchen, die Anzahl der zu testenden Pfade zu minimieren. Das ist was folgt.

Wir konstruieren unsere Pfade, indem wir im Prinzip eine Tiefensuche im Kreisgraphen durchführen. Wir suchen nach einer Möglichkeit, potenzielle Suchrichtungen bei jedem Schritt der Suche zu eliminieren.

Angenommen, wir befinden uns irgendwann auf einem Kreis A , der zwei benachbarte Kreise B und C hat , die ebenfalls nebeneinander liegen. Wir können von A nach C gelangen, indem wir B besuchen (und umgekehrt), so dass wir denken, dass es unnötig ist , sowohl B als auch C direkt von A aus zu besuchen . Dies ist leider falsch, wie diese Abbildung zeigt:

Wenn die Punkte in der Abbildung die beiden Endpunkte sind, können wir sehen, dass wir einen längeren Pfad erhalten , wenn wir von A nach C durch B gehen.

Wie wäre es damit: Wenn wir beide Züge A → B und A → C testen, ist es nicht erforderlich, A → B → C oder A → C → B zu testen , da sie nicht zu kürzeren Wegen führen können. Wieder falsch:

Der Punkt ist, dass die Verwendung von rein auf Nachbarschaft basierenden Argumenten nicht schadet. Wir müssen auch die Geometrie des Problems verwenden. Gemeinsam ist den beiden obigen Beispielen (sowie dem zweiten Testfall in größerem Maßstab), dass sich im umschlossenen Bereich ein "Loch" befindet. Es manifestiert sich in der Tatsache, dass einige der Schnittpunkte an der Grenze - unsere "Nägel" - innerhalb des Dreiecks ABC liegen, dessen Eckpunkte die Zentren der Kreise sind:

In diesem Fall besteht die Möglichkeit, dass der Wechsel von A nach B und von A nach C zu unterschiedlichen Pfaden führt. Noch wichtiger ist, wenn dies nicht der Fall ist (dh wenn es keine Lücke zwischen A , B und C gab ), wird garantiert, dass alle Pfade, die mit A → B → C und mit A → C beginnen und ansonsten äquivalent sind, resultieren auf demselben lokal minimalen Pfad, wenn wir also B besuchen, müssen wir C nicht direkt von A aus besuchen .

Dies führt uns zu unserer Eliminierungsmethode: Wenn wir uns in einem Kreis A befinden , führen wir eine Liste H der benachbarten Kreise, die wir besucht haben. Diese Liste ist zunächst leer. Wir besuchen einen benachbarten Kreis B, wenn sich in allen Dreiecken, die aus den Mittelpunkten von A , B und einem der Kreise in H neben B bestehen, "Nägel" befinden . Diese Methode reduziert die Anzahl der zu testenden Pfade drastisch auf 1 im ersten Testfall und 10 im zweiten.

Noch ein paar Anmerkungen:

• Es ist möglich, die Anzahl der Pfade, die wir testen, weiter zu verringern, aber diese Methode ist gut genug für das Ausmaß dieses Problems.

• Ich habe den Algorithmus von meiner Lösung bis zur Gummiband-Herausforderung verwendet. Da dieser Algorithmus inkrementell ist, kann er ziemlich einfach in den Pfadfindungsprozess integriert werden, sodass wir den Pfad auf ein Mindestmaß beschränken, während wir fortfahren. Da sich viele Pfade ein Startsegment teilen, kann dies die Leistung erheblich verbessern, wenn wir viele Pfade haben. Es kann auch die Leistung beeinträchtigen, wenn es viel mehr Sackgassen als gültige Pfade gibt. In jedem Fall ist es für die gegebenen Testfälle gut genug, den Algorithmus für jeden Pfad separat durchzuführen.

• Es gibt einen Randfall, bei dem diese Lösung fehlschlägt: Wenn einer der Punkte an der Grenze der Schnittpunkt zweier Tangentialkreise ist, kann das Ergebnis unter bestimmten Umständen falsch sein. Dies liegt an der Funktionsweise des Gummiband-Algorithmus. Mit einigen Modifikationen ist es möglich, auch diese Fälle zu behandeln, aber zum Teufel ist es schon lang genug.

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

Die Eingabe erfolgt über die Variable Ials Tupelmenge, ((x, y), r)wobei (x, y)sich der Mittelpunkt des Kreises und rsein Radius befinden. Die Werte müssen floats sein, nicht ints. Das Ergebnis wird nach STDOUT gedruckt.

Beispiel

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