Pi Alam # 1 - Pasir

9

Tujuan

Hasilkan ( N) segmen garis acak dengan panjang seragam ( l), periksa apakah mereka melintasi tgaris paralel yang sama ( ).

Simulasi

Apa yang kita simulasikan? Jarum Buffon . Menghaluskan pasir di kotak pasir Anda, menggambar satu set garis paralel sama spasi (panggilan jarak di antara t). Ambil tongkat panjang lurus ldan jatuhkan Nkali ke dalam kotak pasir. Biarkan berapa kali melewati batas c. Lalu Pi = (2 * l * n) / (t * c)!

Bagaimana kita mensimulasikan ini?

  • Ambil input N,t,l
  • Dengan N, t, lsemua bilangan bulat positif
  • Lakukan waktu berikut N:
    • Hasilkan koordinat bilangan bulat acak yang seragam x,y
    • Dengan 1 <= x, y <= 10^6
    • x,y adalah pusat segmen garis panjang l
    • Hasilkan bilangan bulat acak seragam a
    • Dengan 1 <= a <= 180
    • Membiarkan Pmenjadi titik di mana segmen garis akan melintasi sumbu x
    • Lalu aadalah sudutnya(x,y), P, (inf,0)
  • Hitung jumlah, csegmen segmen yang melewati garis x = i*tuntuk bilangan bulat apa puni
  • Kembali (2 * l * N) / (t * c)

masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

Spesifikasi

  • Memasukkan
    • Fleksibel, mengambil input dengan cara standar apa pun (misalnya parameter fungsi, STDIN) dan dalam format standar apa pun (mis. String, Binary)
  • Keluaran
    • Fleksibel, memberikan hasil dengan cara standar apa pun (mis. Mengembalikan, mencetak)
    • Ruang putih, trailing dan ruang putih utama dapat diterima
    • Akurasi, harap berikan setidaknya 4 tempat desimal akurasi (yaitu 3.1416)
  • Mencetak gol
    • Kode terpendek menang!

Uji Kasus

Output Anda mungkin tidak sejalan dengan ini, karena kebetulan acak. Tetapi rata-rata, Anda harus mendapatkan akurasi sebanyak ini untuk nilai yang diberikan N, t, l.

Input (N,t,l)    ->  Output 
-----------        ------
10,10,5          -> ?.????
10,100,50        -> ?.????
1000,1000,600    -> 3.????
10000,1000,700   -> 3.1???
100000,1000,700  -> 3.14??

TL; DR

Tantangan-tantangan ini adalah simulasi algoritma yang hanya membutuhkan alam dan otak Anda (dan mungkin beberapa sumber daya yang dapat digunakan kembali) untuk memperkirakan Pi. Jika Anda benar-benar membutuhkan Pi selama kiamat zombie, metode ini tidak membuang - buang amunisi ! Ada sembilan tantangan total.

Buah Nonlinier
sumber
Saya pikir Anda sudah melakukan nomor 1?
Conor O'Brien
1
@ ConorO'Brien Saya nol-indeksnya XD
NonlinearFruit
masalah dengan ini adalah, dalam bahasa tanpa angka kompleks, Anda perlu mengubah angka 0..180 menjadi 0..pi, yang agak mengalahkan tujuan percobaan jarum buffon.
Level River St
@ NonlinearFruit dapatkah arahan ajuga dibuat dengan metode lain, jika seragam? (memikirkan Bubble Gauss 2D)
Karl Napf
1
Bisakah diasumsikan demikian t > l? Dua solusi di bawah ini membuat asumsi ini, yang menyederhanakan pemeriksaan untuk persimpangan cukup sedikit.
Primo

Jawaban:

9

R, 113 100 75 70 68 67 65 59 63 57 byte

Sebagai bahasa pemrograman statistik dan fungsional, tidak mengherankan bahwa R cukup cocok untuk tugas semacam ini. Fakta bahwa sebagian besar fungsi dapat mengambil input vektor sangat membantu untuk masalah ini, karena alih-alih mengulangi Niterasi, kami hanya membagikan vektor ukuran N. Terima kasih kepada @Billywob untuk beberapa saran yang mengarah pada pemotongan 4 byte Banyak terima kasih kepada @Primo karena dengan sabar menjelaskan kepada saya bagaimana kode saya tidak berfungsi untuk kasus-kasus di mana t > l, yang sekarang sudah diperbaiki.

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))

Cobalah online!

Output sampel:

N=1000, t=1000, l=500
3.037975

N=10000, t=1000, l=700
3.11943

N=100000, t=1000, l=700
3.140351

Penjelasan

Masalahnya adalah untuk menentukan apakah dua xnilai jarum berada di kedua sisi garis paralel. Ini memiliki beberapa konsekuensi penting:

  1. y-nilai tidak relevan
  2. Lokasi absolut pada x-axis tidak relevan, hanya posisi relatif terhadap garis paralel terdekat.

Pada dasarnya ini adalah tugas dalam ruang 1-dimensi, di mana kami menghasilkan garis dengan panjang dalam [0, l] (sudut amenentukan panjang ini), dan kemudian kami memeriksa untuk melihat berapa kali panjang ini melebihi t. Algoritma kasarnya adalah:

  1. x1Nilai sampel dari [0, 1000000]. Karena garis paralel terjadi pada setiap ttitik sepanjang x-axis, posisi relatifnya xadalah xmodulo t.
  2. Cicipi sudut a.
  3. Hitung x2posisi berdasarkan a.
  4. Periksa berapa kali x1+x2cocok t, yaitu mengambil lantai (x1+x2)/t.

Pengambilan Nangka angka dalam [0, 1e6] modulo tsetara dengan hanya pengambilan sampel Nangka dalam [0, t]. Karena (x1+x2)/tsama dengan x1/t + x2/t, langkah pertama menjadi pengambilan sampel dari [0, t] / t, yaitu [0, 1]. Beruntung bagi kami, itu adalah rentang default untuk runiffungsi R , yang mengembalikan Nbilangan real dari 0 ke 1 dari distribusi yang seragam.

                          runif(N)

Kami ulangi langkah ini untuk menghasilkan a, sudut jarum.

                                         runif(N)

Angka-angka ini ditafsirkan sebagai setengah putaran (yaitu .590 derajat). (OP meminta derajat dari 1 hingga 180, tetapi dalam komentar itu diklarifikasi bahwa metode apa pun diperbolehkan jika itu sebagai atau lebih tepat.) Untuk sudut θ, sin(θ)memberi kita jarak sumbu x antara ujung-ujung jarum. (Biasanya Anda akan menggunakan cosinus untuk sesuatu seperti ini; tetapi dalam kasus kami, kami mempertimbangkan sudut θsebagai relatif terhadap sumbu y, bukan sumbu x (yaitu, nilai 0 derajat naik , bukan kanan ), dan oleh karena itu kami menggunakan sinus, yang pada dasarnya fase-menggeser angka.) Dikalikan dengan lini memberi kita xlokasi ujung jarum.

                                   sinpi(runif(N))*l

Sekarang kita bagi tdan tambahkan x1nilainya. Ini menghasilkan (x1+x2)/t, yang sejauh mana jarum menonjol dari x1, dalam hal jumlah garis paralel. Untuk mendapatkan bilangan bulat dari berapa banyak garis yang dilintasi, kita ambil floor.

                    floor(runif(N)+sinpi(runif(N))*l/t)

Kami menghitung jumlahnya, memberi kami hitungan cberapa banyak garis yang dilintasi oleh jarum.

                sum(floor(runif(N)+sinpi(runif(N))*l/t))

Sisa kode hanya mengimplementasikan rumus untuk perkiraan pi, yaitu (2*l*N)/(t*c),. Kami menyimpan beberapa byte pada tanda kurung dengan mengambil keuntungan dari kenyataan bahwa (2*l*N)/(t*c) == 2*l*N/t/c:

        2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t))

Dan semuanya dibungkus menjadi fungsi anonim:

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))
rturnbull
sumber
@ Artbullull Bagus! Bukankah seharusnya kamu bisa melewati tanda kurung di awal? (2*l*N) => 2*l*N?
Billywob
@Billywob Terlihat dengan baik! Terima kasih.
rturnbull
@ Arturnbull Oh dan omong-omong, (2*l*N)/(t*c) = 2*l*N/t/cjadi Anda bisa menyimpan dua byte lagi dengan melewatkan tanda kurung di bagian terakhir juga.
Billywob
@Billywob Lagi, terlihat bagus! Terima kasih lagi.
rturnbull
1
@ primo Terima kasih lagi, ini harus diperbaiki sekarang.
rturnbull
6

Perl, 97 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)-$a..$x+($a=$'/$&/2*sin~~rand(180)*71/4068)-1}1..$_

Menghitung shebang sebagai satu, input diambil dari stdin, dipisahkan oleh ruang. Jika nilai acak non-integer diizinkan, ini bisa menjadi lebih pendek.

Saya telah mengambil satu kebebasan, kira-kira π / 180 sebagai 71/4068 , yang akurat dalam 1,48 · 10 -9 .

Contoh Penggunaan

$ echo 1000000 1000 70000 | perl pi-sand.pl
3.14115345174061

Pergantian matematis yang kurang lebih setara

Dengan asumsi koordinat x mewakili titik paling kiri dari jarum, bukan di tengahnya, seperti yang ditentukan dalam deskripsi masalah:

89 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

Masalahnya menentukan bahwa xyang akan dijadikan sampel sebagai integer acak. Jika kita memproyeksikan garis spasi untuk jeda satu, ini akan meninggalkan kita dengan nilai-nilai dari bentuk n/tdengan 0 <= n < t, belum tentu seragam, jika ttidak merata membagi 1e6. Dengan asumsi bahwa distribusi seragam tetap dapat diterima:

76 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=rand)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

Perhatikan bahwa karena randakan selalu kurang dari satu (dan karena itu terpotong ke nol), maka tidak perlu pada awal rentang:

70 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+($'/$&*sin~~rand(180)*71/4068)}1..$_

Dengan asumsi bahwa sudut jarum tidak harus berupa bilangan bulat, tetapi hanya acak acak:

59 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin rand$`}1..$_

Dengan asumsi sudut dapat berupa distribusi yang seragam:

52 byte

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin}1..$_

Di atas adalah simulasi yang tepat secara matematis dari Jarum Buffon. Namun, pada titik ini saya pikir kebanyakan orang akan setuju bahwa ini sebenarnya bukan pertanyaan yang ditanyakan.


Benar-benar mendorongnya

Kita bisa membuang setengah dari kasus uji, setiap kali titik akhir kedua adalah di sebelah kiri yang pertama (daripada menukar mereka):

47 byte

#!perl -p
/ \d+/;$_*=$'/$&/map{1..(rand)+$'/$&*sin}1..$_

Perhatikan bahwa nilai-nilai tdan ltidak penting untuk hasil percobaan. Kita bisa mengabaikannya (secara implisit menganggapnya sama):

28 byte

#!perl -p
$_/=map{1..(rand)+sin}1..$_

Jelas tidak bersaing, tetapi Anda harus mengakui, itu memang memiliki keanggunan tertentu untuk itu.

primo
sumber
4

Python 2, 141 byte

pelabuhan rtumbull yang tak tahu malu, sudah terlewati ykarena sama sekali tidak diperlukan.

from math import*
from random import*
lambda N,t,l:(2.*l*N)/(t*sum(randint(1,1e6)%t+abs(cos(randint(1,180)*pi/180))*l>t for _ in range(N)))

Masalahnya hanya, pi itu sudah dikenal dalam program.

Ini dia (golf) dengan pi yang tidak diketahui dan tidak ada fungsi trigonometri

def g(N,t,l):
 c=0
 for _ in range(N):
    x,y=gauss(0,1),gauss(0,1);c+=randint(1,1e6)%t+abs(x/sqrt(x*x+y*y))*l>t
 return(2.*l*N)/(t*c)

x,ydi ghanya untuk arah.

Karl Napf
sumber
Membutuhkan from random import randint;from math import cos,pi. Gagal untuk t < l, mis 1000000,1000,70000.
Primo