Sie sind der Besitzer eines Restaurants. Sie eröffnen ein neues Gebiet in Cartesia, wo es nur eine Hauptstraße gibt, die als y-Achse bezeichnet wird. Sie möchten Ihr Restaurant so platzieren, dass Sie die Gesamtentfernung von Ihrem Restaurant und jedem der Häuser in diesem Bereich minimieren.

Eingabe :

Die Eingabe wird sein

n, the number of houses
house1
house2
house3
...
houseN

wo jedes Haus eine Koordinate in der Form ist x y. Jede Einheit entspricht einem Kilometer.

Sie können Eingaben als Zeichenfolge verwenden oder eine Funktion bereitstellen, die die Eingabe in einem beliebigen Format als Argument verwendet.

Ausgabe : Die y-Koordinate Ihres Restaurants (denken Sie daran, dass sie sich auf der y-Achse befindet). Eigentlich wird es am Straßenrand liegen, aber der Unterschied ist vernachlässigbar.

Wenn n-tes Haus die Entfernungsfunktion ist h_nund Dist, möchten Sie im Wesentlichen eine ksolche finden , D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k))die minimiert ist.

Beachten Sie, dass die Entfernung so berechnet wird, als ob der Kunde in einer genau geraden Linie von seinem Haus zum Restaurant fährt. Das ist die Entfernung von (x, y)zu Ihrem Restaurant sqrt(x^2 + (y - k)^2).

Die Ausgabe sollte auf mindestens 2 Dezimalstellen genau sein.

Die Ausgabe kann als Zeichenfolge gedruckt oder von der Funktion zurückgegeben werden.

Beispiel Ein- / Ausgabe:

Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

Die Gesamtentfernung in diesem Beispiel beträgt ungefähr 15.4003Kilometer.

Dies ist Code Golf - der kürzeste Code gewinnt.

PS Ich interessiere mich auch für eine mathematische Lösung, die nicht nur brachial ist. Es wird nicht den Code Golf gewinnen, aber es wird einige positive Stimmen bekommen. Hier ist, wie ich das Beispielproblem gemacht habe:

Sei Punkt A bei A (5.7, 3.2) und B bei B (8.9, 8.1). Der Lösungspunkt bei (0, k) sei C. Reflektiere A über die y-Achse, um A 'bei (-5.7, 3.2) zu erhalten. Der Abstand von A 'zu C ist gleich dem Abstand von A zu C. Daher kann das Problem auf den Punkt C reduziert werden, so dass A'C + CB minimiert wird. Offensichtlich wäre dies der Punkt C, der auf der Linie A'B liegt.

Ich weiß nicht, ob dies gut auf 3 oder mehr Punkte verallgemeinern würde.

C 315 302 Bytes

t,i;double o,w,h,x,y,k,a,b,c;double g(N,S)double N,S[][2];{for(t=0;t<N;t++)k+=S[t][1];k/=N;for(i=0;i<9;i++){o=w=h=0;for(t=0;t<N;t++)x=S[t][0],y=S[t][1],a=y-k,c=k*k-2*k*y+x*x+y*y,o+=-a/sqrt(x*x+a*a),w+=x*x/pow(c,1.5),h+=3*x*x*a/pow(c,2.5);a=h/2;b=w-h*k;c=o-w*k+a*k*k;k=(-b+sqrt(b*b-4*a*c))/h;}return k;}

Das ist alles andere als hübsch und auch nicht zu kurz. Ich dachte, da ich den Längenwettbewerb nicht gewinnen werde, kann ich versuchen, den (theoretischen) Genauigkeitswettbewerb zu gewinnen! Der Code ist wahrscheinlich ein oder zwei Zehnerpotenzen schneller als die Bruteforce-Lösung und stützt sich auf ein bisschen mathematischen Blödsinn.

Wir definieren eine Funktion, g(N,S)die die Anzahl der Häuser Nund eine Reihe von Häusern als Eingabe verwendet S[][2].

Hier ist es mit einem Testfall enträtselt:

t,i;
double o,w,h,x,y,k,a,b,c;
double g(N,S)double N,S[][2];{
    /* Initially, let k hold the geometric mean of given y-values */
    for(t=0;t<N;t++)
        k+=S[t][1];
    k/=N;

    /* We approximate 9 times to ensure accuracy */
    for(i=0;i<9;i++){
        o=w=h=0;
        for(t=0;t<N;t++)
            /* Here, we are making running totals of partial derivatives */
            /* o is the first, w the second, and h the third*/
            x=S[t][0],
            y=S[t][1],
            a=y-k,
            c=k*k-2*k*y+x*x+y*y,
            o+=-a/sqrt(x*x+a*a),
            w+=x*x/pow(c,1.5),
            h+=3*x*x*a/pow(c,2.5);
        /* We now use these derivatives to find a (hopefully) closer k */
        a=h/2;
        b=w-h*k;
        c=o-w*k+a*k*k;
        k=(-b+sqrt(b*b-4*a*c))/h;
    }
    return k;
}
/* Our testing code */
int main(int argc, char** argv) {
    double test[2][2] = {
        {5.7, 3.2},
        {8.9, 8.1}
    };    
    printf("%.20lf\n", g(2, test));
    return 0;
}

Welche Ausgänge:

5.11301369863013732697

Warnung: Für ein umfassendes Verständnis sind möglicherweise Kenntnisse in einigen Berechnungen erforderlich!

Reden wir also über die Mathematik.

Wir kennen die Entfernung von unserem gewünschten Punkt (0, k)und einem Haus i:

Und so kann die Gesamtentfernung Dvon nHäusern wie folgt definiert werden:

Wir möchten diese Funktion minimieren, indem wir eine Ableitung in Bezug auf nehmen kund gleich setzen 0. Lass es uns versuchen. Wir wissen, dass die Derivate von Dwie folgt beschrieben werden können:

Aber die erste Teilableitung von jedem Diist ziemlich schlecht ...

Leider wird es auch mit sehr schnell katastrophal n == 2, diese Derivate zu setzen 0und nach ihnen kzu suchen. Wir brauchen eine robustere Methode, auch wenn sie eine Annäherung erfordert.

Geben Sie Taylor-Polynome ein.

Wenn wir den Wert D(k0)sowie alle DDerivate von kennen k0, können wir Dals Taylor-Serie umschreiben :

Nun, diese Formel enthält eine Menge Dinge, und ihre Ableitungen können ziemlich unhandlich werden, aber wir haben jetzt eine polynomielle Approximation von D !

Wenn wir ein wenig rechnen, finden wir die nächsten zwei Ableitungen von, Dindem wir die Ableitungen von Diwie zuvor auswerten :

Durch Abschneiden und Auswerten der Ableitungen können wir uns nun Deinem Polynom 3. Grades der Form annähern :

Wo A, B, C, D sind einfach reelle Zahlen.

Nun können wir dies minimieren. Wenn wir eine Ableitung nehmen und gleich 0 setzen, erhalten wir eine Gleichung der Form:

Unter Berücksichtigung von Kalkül und Substitutionen finden wir diese Formeln für a, b, and c:

Jetzt gibt unser Problem uns 2 Lösungen, die durch die quadratische Formel gegeben sind:

Die gesamte Formel für k wäre eine enorme Belastung für das Ausschreiben, also machen wir es hier und im Code in Stücken.

Da wissen wir das umso höher k immer den Mindestabstand unserer Näherung ergibt D(ich habe einen wirklich wunderbaren Beweis dafür, für den der Rand dieses Papiers nicht ausreicht ...), müssen wir nicht einmal den kleineren berücksichtigen Die Lösungen.

Ein letztes Problem bleibt bestehen. Aus Gründen der Genauigkeit ist es erforderlich, dass wir mit a beginnenk0 , das sich zumindest in dem Bereich befindet, in dem wir die Antwort erwarten. Zu diesem Zweck wählt mein Code das geometrische Mittel der y-Werte jedes Hauses.

Aus Sicherheitsgründen wiederholen wir das gesamte Problem neunmal und ersetzen es k0durchk , bei jeder Iteration Genauigkeit zu gewährleisten.

Ich habe nicht nachgerechnet, wie viele Iterationen und wie viele Ableitungen wirklich notwendig sind, aber ich habe mich entschieden, auf Nummer sicher zu gehen, bis ich die Genauigkeit bestätigen kann.

Wenn Sie das mit mir geschafft haben, vielen Dank! Ich hoffe, Sie haben verstanden, und wenn Sie Fehler bemerken (von denen es wahrscheinlich viele gibt, bin ich sehr müde), lassen Sie es mich bitte wissen!

TI-BASIC, 20

fMin(sum(abs(iX-Ans)),X,~E99,E99

Übernimmt Eingaben auf dem Homescreen Ihres Taschenrechners der Serie TI-83 oder 84 in dieser Form (Sie können eine 2:erste eingeben, die ignoriert wird):

{5.7+3.2i,8.9+8.1i}:[program name]

Wenn die Häuser immer weniger als eine Milliarde Kilometer vom Ursprung entfernt sind, kann E99 durch E9 mit einer Größe von 18 Byte ersetzt werden.

Gab es eine auf Mathematica basierende Golfsprache, konnte sie diese Herausforderung in 10-14 Bytes gewinnen.

Mathematica, 42 Bytes

k/.Last@Minimize[Tr[Norm[#-{0,k}]&/@#],k]&

Dies ist eine anonyme Funktion, die eine Liste von Paaren als Hauskoordinaten verwendet und die gewünschte y-Koordinate zurückgibt.

Es ist eine ziemlich einfache Implementierung. Wir mappen Norm[#-{0,k}]&auf jede Hauskoordinate (die den Abstand zu einem unbestimmten Punkt {0,k}auf der y-Achse berechnet ) und summieren sie alle mit Tr[...](für trace, was Totalfür 1-d-Listen äquivalent ist ). Dann verwenden wir die Bequemlichkeit Minimize, um das Minimum dieser Summe in zu finden k. Dies ergibt ein Ergebnis des Formulars. Daher {distance, {k -> position}müssen wir das Gesuchte k/.Last@extrahieren position.

Pyth, 33 Bytes

hosm.a,d,0NQcR^T3rhKSms*^T3ekQheK

Dies ist die Brute-Force-Lösung: Sie ordnet alle möglichen Standorte des Restaurants mit einer Auflösung von 0,001 km nach der Gesamtentfernung zu den Häusern und wählt dann den Standort mit der geringsten Gesamtentfernung aus. Es nimmt die Hausstandorte als Liste von 2 Eintragslisten von Floats auf STDIN.

Demonstration.

Die Auflösung kann bei gleicher Codelänge zwischen 1e-2 km und 1e-10 km eingestellt werden, jedoch mit exponentiellen Verzögerungen in der Laufzeit.

Ich habe das Gefühl, das könnte noch etwas mehr sein, ich werde es mir später noch einmal ansehen.

Python 2, 312

from math import*;A,L,p=[map(float,raw_input().split()) for i in range(input())],lambda a:a[1],0.001
def R(m,M,s):
 while m<=M:yield m;m+=s
m=min(A,key=L)[1];M=max(A,key=L)[1];r=(m+M)/2;s=r-m
while s>p:D={y:sum([sqrt(X*X+(Y-y)**2)for X,Y in A])for y in R(r-s,r+s,s*p)};r=min(D,key=D.get);s*=p;m=r-s;M=r+s
print r

R 145 143 126

Ich vermute, hier ist noch viel Platz zum Golfen. So ziemlich eine Brute-Force-Methode. Ich würde gerne einen schöneren Weg finden, dies zu tun. Ich dachte, geometrische Mittel könnten helfen, aber leider nein.

r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]

Testlauf

> r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]
1: 5.7 3.2
3: 8.9 8.1
5: 
Read 4 items
[1] 5.113
> 

Wenn nur zwei Häuser in Betracht gezogen werden müssen, liefert das Folgende ein akzeptables Ergebnis. Es fällt jedoch auf drei. Ich kann es im Moment nicht weiter verfolgen, aber ich dachte, einige der Gehirne hier könnten etwas damit anfangen.

p=matrix(scan(),nr=2);weighted.mean(p[2,],sum(p[1,])-p[1,])

MATLAB, 42

Wenn es in Ordnung ist, die Eingabe als zu übernehmen

I=[5.7 3.2
    8.9 8.1]

dann diese Aussage

fminunc(@(y)sum(hypot(I(:,1),I(:,2)-y)),0)

kehrt zurück 5.113014445748538.

Wenn man Thomas Kwas Methode schamlos stiehlt, könnte man sie auf mindestens 30 reduzieren:

I=[5.7+3.2i 8.9+8.1i];
fminunc(@(y)sum(abs(I-i*y)),0)