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_n
dan D
merupakan fungsi jarak, maka Anda ingin mencari k
yang 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.4003
kilometer.
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.
sumber
D
? Euclidean?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.Jawaban:
C,
315302 byteIni 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 rumahN
,, dan array rumahS[][2]
.Ini dia terurai, dengan test case:
Output yang mana:
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 inginkani
:Dan dengan demikian total jarak
D
darin
rumah dapat didefinisikan sebagai berikut:Yang ingin kami lakukan adalah meminimalkan fungsi ini dengan mengambil turunan sehubungan dengan
k
dan menyetelnya dengan0
. Ayo kita coba. Kita tahu bahwa turunan dariD
dapat digambarkan sebagai berikut:Tapi turunan parsial pertama dari masing-masing
Di
cukup buruk ...Sayangnya, bahkan dengan
n == 2
, mengatur turunan0
dan penyelesaian inik
menjadi bencana sangat cepat. Kita membutuhkan metode yang lebih kuat, bahkan jika itu membutuhkan perkiraan.Masukkan Taylor Polynomials.
Jika kita mengetahui nilai
D(k0)
serta semuaD
turunannya dik0
, kita dapat menulis ulangD
sebagai Seri Taylor: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
D
dengan mengevaluasi turunannyaDi
, sama seperti sebelumnya:Dengan memotong dan mengevaluasi turunannya, kami sekarang dapat memperkirakan
D
sebagai polinomial tingkat 3 dari formulir:Di mana
A, B, C, D
bilangan real hanya nyata.Sekarang ini kita bisa meminimalkan. Ketika kita mengambil turunan dan menyetelnya sama dengan 0, kita akan berakhir dengan persamaan bentuk:
Melakukan kalkulus dan substitusi, kami datang dengan formula ini untuk
a, b, and c
:Sekarang masalah kita memberi kita 2 solusi yang diberikan oleh rumus kuadratik:
Seluruh rumus untuk
k
akan menjadi beban besar untuk menulis, jadi kami melakukannya dalam potongan-potongan di sini dan dalam kode.Karena kita tahu bahwa semakin tinggi
k
akan selalu menghasilkan jarak minimum perkiraan kamiD
(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
k0
yang 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
k0
dengank
setiap 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!
sumber
TI-BASIC, 20
Mengambil input pada homescreen kalkulator TI-83 atau 84 series Anda dalam formulir ini (Anda dapat mengetik yang
2:
pertama, yang akan diabaikan):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.
sumber
Mathematica, 42 byte
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 denganTr[...]
(untuk jejak, yang setara denganTotal
untuk daftar 1-d). Kemudian kami menggunakan cara yang mudahMinimize
untuk menemukan minimum jumlah inik
. Ini memberikan hasil dari formulir{distance, {k -> position}
, jadi kita perluk/.Last@
mengekstrak yangposition
kita cari.sumber
Pyth, 33 byte
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.
sumber
^T3
ini sangat mengesankan.Python 2, 312
sumber
R,
145143126Saya 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.
Uji coba
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.
sumber
MATLAB, 42
Jika OK untuk mengambil input sebagai
maka pernyataan ini
kembali
5.113014445748538
.Tanpa malu-malu mencuri metode Thomas Kwa, Anda bisa mendapatkannya hingga setidaknya 30:
sumber
n
jumlah rumah? Karena pertanyaan itulah yang ditanyakan.I
.