Di mana saya harus meletakkan restoran saya?

15

Anda adalah pemilik restoran. Anda membuka di daerah baru di Cartesia di mana hanya ada satu jalan utama, yang dikenal sebagai sumbu y. Anda ingin menempatkan restoran Anda sedemikian rupa sehingga Anda meminimalkan jarak total dari restoran Anda dan setiap rumah di daerah itu.

Masukan :

Inputnya adalah

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

di mana setiap rumah adalah koordinat dalam bentuk x y. Setiap unit mewakili satu kilometer.

Anda dapat mengambil input sebagai string atau menyediakan fungsi yang mengambil input, dalam format apa pun yang Anda pilih, sebagai argumennya.

Output : Koordinat-y dari restoran Anda (ingat, itu akan terletak pada sumbu-y). Sebenarnya, itu akan terletak di sisi jalan, tetapi perbedaannya dapat diabaikan.

Pada dasarnya, jika nth house adalah h_ndan Dmerupakan fungsi jarak, maka Anda ingin mencari kyang D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k))diminimalkan.

Perhatikan bahwa jarak dihitung seolah-olah pelanggan bepergian dalam garis yang persis lurus dari rumah mereka ke restoran. Itu adalah jarak dari (x, y)ke restoran Anda sqrt(x^2 + (y - k)^2).

Keluaran harus akurat untuk setidaknya 2 tempat desimal.

Output dapat dicetak sebagai string atau dapat dikembalikan dari fungsi.

Contoh input / output:

Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

Total jarak dalam contoh ini adalah sekitar 15.4003kilometer.

Ini kode golf - kode terpendek menang.

PS Saya juga tertarik pada solusi matematika yang bukan hanya kekerasan. Itu tidak akan memenangkan kode golf tetapi akan mendapatkan beberapa upvotes. Berikut adalah contoh masalah yang saya lakukan:

Biarkan titik A berada di A (5.7, 3.2) dan B di B (8.9, 8.1). Biarkan titik solusi di (0, k) menjadi C. Refleksikan A di atas sumbu y untuk membuat A 'di (-5.7, 3.2). Jarak dari A 'ke C sama dengan jarak dari A ke C. Oleh karena itu, masalahnya dapat dikurangi ke titik C sehingga A'C + CB diminimalkan. Jelas, ini akan menjadi titik C yang terletak pada garis A'B.

Saya tidak tahu apakah ini akan digeneralisasi dengan baik menjadi 3 poin atau lebih.

soktinpk
sumber
Metrik apa yang digunakan untuk fungsi jarak D? Euclidean?
Reto Koradi
1
Meskipun hanya ada satu jalan utama, apakah kita berasumsi bahwa seorang pelanggan bepergian dalam garis lurus dari rumah mereka ke restoran? Atau apakah mereka melakukan perjalanan langsung ke sumbu y terlebih dahulu? (Atau dengan kata lain, apakah kita menggunakan Euclidean atau jarak Manhattan untuk D?)
trichoplax
1
(Ini dapat dikerjakan dari contoh tetapi akan lebih baik jika dinyatakan secara eksplisit.)
trichoplax
@trichoplax Euclidean? Apakah Euclidean berarti sqrt(diffX^2 + diffY^2)? Kemudian Euclidean. Saya tahu itu tidak cocok dengan skenario tetapi menganggap bahwa pelanggan bepergian dalam garis lurus entah bagaimana dari rumahnya.
soktinpk
5
Apakah menerima masukan sebagai daftar bilangan kompleks yang mewakili posisi rumah di bidang kompleks dapat diterima?
lirtosiast

Jawaban:

27

C, 315 302 byte

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;}

Ini jauh dari cantik, dan juga tidak pendek. Saya pikir karena saya tidak akan memenangkan kontes panjang, saya dapat mencoba untuk memenangkan kontes akurasi (teoritis)! Kode mungkin urutan besarnya atau dua lebih cepat dari solusi bruteforce, dan bergantung pada sedikit tindakan gila-gilaan matematis.

Kami mendefinisikan fungsi g(N,S)yang mengambil input jumlah rumah N,, dan array rumah S[][2].

Ini dia terurai, dengan test case:

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;
}

Output yang mana:

5.11301369863013732697

Peringatan: Pengetahuan tentang beberapa kalkulus mungkin diperlukan untuk pemahaman yang lengkap!

Jadi, mari kita bicara soal matematika.

Kita tahu jarak dari titik (0, k)dan rumah yang kita inginkan i:

Definisi D_i

Dan dengan demikian total jarak Ddari nrumah dapat didefinisikan sebagai berikut:

Definisi D

Yang ingin kami lakukan adalah meminimalkan fungsi ini dengan mengambil turunan sehubungan dengan kdan menyetelnya dengan 0. Ayo kita coba. Kita tahu bahwa turunan dari Ddapat digambarkan sebagai berikut:

Derivatif D

Tapi turunan parsial pertama dari masing-masing Dicukup buruk ...

Derivatif 1 dari Di

Sayangnya, bahkan dengan n == 2, mengatur turunan 0dan penyelesaian ini kmenjadi bencana sangat cepat. Kita membutuhkan metode yang lebih kuat, bahkan jika itu membutuhkan perkiraan.

Masukkan Taylor Polynomials.

Jika kita mengetahui nilai D(k0)serta semua Dturunannya di k0, kita dapat menulis ulang Dsebagai Seri Taylor:

Definisi oleh Taylor Series

Sekarang, formula ini memiliki banyak hal di dalamnya, dan turunannya dapat menjadi sangat sulit, tetapi kita sekarang memiliki perkiraan polinomial D !

Melakukan sedikit kalkulus, kami menemukan dua turunan berikutnya Ddengan mengevaluasi turunannya Di, sama seperti sebelumnya:

Derivatif 2 dari Di

Derivatif 3 dari Di

Dengan memotong dan mengevaluasi turunannya, kami sekarang dapat memperkirakan Dsebagai polinomial tingkat 3 dari formulir:

Perkiraan bentuk D

Di mana A, B, C, Dbilangan real hanya nyata.

Sekarang ini kita bisa meminimalkan. Ketika kita mengambil turunan dan menyetelnya sama dengan 0, kita akan berakhir dengan persamaan bentuk:

Perkiraan D '

Melakukan kalkulus dan substitusi, kami datang dengan formula ini untuk a, b, and c:

Nilai a

Nilai b

Nilai c

Sekarang masalah kita memberi kita 2 solusi yang diberikan oleh rumus kuadratik:

Nilai k

Seluruh rumus untuk kakan menjadi beban besar untuk menulis, jadi kami melakukannya dalam potongan-potongan di sini dan dalam kode.

Karena kita tahu bahwa semakin tinggi kakan selalu menghasilkan jarak minimum perkiraan kami D(saya punya bukti yang sangat bagus tentang ini, yang margin makalah ini tidak cukup mengandung ...) kita bahkan tidak perlu mempertimbangkan yang lebih kecil dari solusinya.

Masih ada satu masalah terakhir. Untuk tujuan keakuratan, kita perlu memulai dengan k0yang setidaknya berada di stadion baseball di mana kita mengharapkan jawabannya. Untuk tujuan ini, kode saya memilih rata-rata geometrik dari nilai-y dari setiap rumah.

Sebagai gagal-aman, kami mengulangi seluruh masalah lagi 9 kali, menggantikannya k0dengan ksetiap iterasi, untuk memastikan akurasi.

Saya belum melakukan perhitungan matematika tentang berapa banyak iterasi dan berapa banyak turunan yang benar-benar diperlukan, tetapi saya telah memilih untuk berbuat salah di sisi kehati-hatian sampai saya dapat mengkonfirmasi keakuratan.

Jika Anda berhasil melewati itu dengan saya, terima kasih banyak! Saya harap Anda mengerti, dan jika Anda menemukan kesalahan (yang kemungkinan besar banyak, saya sangat lelah), beri tahu saya!

BrainSteel
sumber
2
Saya, untuk satu, akan senang melihat penjelasan matematika Anda.
DLosc
2
@Dosc Permintaan Anda adalah perintah saya.
BrainSteel
4
Itu benar-benar luar biasa. Saya mempertimbangkan untuk mencoba Metode Newton, tetapi tidak memikirkan seri Taylor.
DLosc
5
Saya berharap saya bisa lebih mengangkat ini.
Alex A.
@AlexA. Saya berharap Anda bisa lebih meningkatkan saya juga; D Dalam satu hari atau lebih, saya akan menghapus referensi teorema terakhir Fermat dan menggantinya dengan bukti. Segera setelah saya menemukan satu.
BrainSteel
13

TI-BASIC, 20

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

Mengambil input pada homescreen kalkulator TI-83 atau 84 series Anda dalam formulir ini (Anda dapat mengetik yang 2:pertama, yang akan diabaikan):

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

Jika rumah-rumah selalu kurang dari satu miliar km jauhnya dari asalnya, E99 dapat diganti dengan E9 untuk ukuran 18 byte.

Jika ada bahasa golf berdasarkan Mathematica, itu bisa memenangkan tantangan ini dalam 10-14 byte.

lirtosiast
sumber
10

Mathematica, 42 byte

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

Ini adalah fungsi anonim mengambil daftar pasangan sebagai koordinat rumah dan mengembalikan koordinat y yang diinginkan.

Ini implementasi yang cukup mudah. Kami memetakan Norm[#-{0,k}]&ke masing-masing koordinat rumah (yang menghitung jarak ke titik yang tidak ditentukan {0,k}pada sumbu y) dan menjumlahkannya dengan Tr[...](untuk jejak, yang setara dengan Totaluntuk daftar 1-d). Kemudian kami menggunakan cara yang mudah Minimizeuntuk menemukan minimum jumlah ini k. Ini memberikan hasil dari formulir {distance, {k -> position}, jadi kita perlu k/.Last@mengekstrak yang positionkita cari.

Martin Ender
sumber
6

Pyth, 33 byte

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

Ini adalah solusi brute force: Ini memesan semua lokasi yang memungkinkan restoran, dengan resolusi 0,001 km, dengan total jarak mereka dari rumah-rumah, lalu memilih satu dengan jarak total paling sedikit. Dibutuhkan lokasi rumah sebagai daftar 2 daftar entri mengapung di STDIN.

Demonstrasi.

Resolusi dapat diatur di mana saja dari 1e-2 km ke 1e-10 km pada panjang kode yang sama, tetapi dengan perlambatan eksponensial dalam runtime.

Saya merasa seperti ini bisa bermain golf lagi, saya akan melihatnya lagi nanti.

isaacg
sumber
2
Lol! Apakah Anda menyalin solusi saya? ;-)
Jakube
@ Jakube Pencocokan ^T3ini sangat mengesankan.
isaacg
Kami benar-benar membutuhkan rentang mengambang.
Maltysen
3

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
pelaku diet
sumber
3

R, 145 143 126

Saya kira ada banyak ruang golf yang tersisa. Cukup banyak metode kekerasan. Saya ingin mencari cara yang lebih baik untuk melakukan ini. Saya pikir Cara Geometrik mungkin membantu, tapi sayangnya tidak.

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

Uji coba

> 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
> 

Yang menarik, jika hanya ada dua rumah untuk dipertimbangkan berikut ini akan mengembalikan hasil yang dapat diterima. Namun jatuh pada tiga. Saya tidak dapat mengambilnya lebih jauh saat ini, tetapi saya pikir beberapa otak di sini mungkin dapat melakukan sesuatu dengannya.

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

MATLAB, 42

Jika OK untuk mengambil input sebagai

I=[5.7 3.2
    8.9 8.1]

maka pernyataan ini

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

kembali 5.113014445748538.

Tanpa malu-malu mencuri metode Thomas Kwa, Anda bisa mendapatkannya hingga setidaknya 30:

I=[5.7+3.2i 8.9+8.1i];
fminunc(@(y)sum(abs(I-i*y)),0)
David
sumber
1
Bisakah diperpanjang untuk bekerja dengan njumlah rumah? Karena pertanyaan itulah yang ditanyakan.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
Ya itu bekerja dengan sejumlah baris I.
David