Saya membaca tentang lingkaran di suatu tempat, dan baru saja belajar tentang cakram ( itu sebenarnya konsep yang cukup umum ) dan berpikir tentang codegolf.

Tugas Anda adalah untuk mengacak satu titik / beberapa titik pada disk dengan jari-jari 1.

Aturan:

• Semua poin harus memiliki probabilitas yang sama untuk dihasilkan
• Koordinat titik apung harus digunakan; persyaratan minimum adalah dua desimal (misalnya poin (0.12, -0.45)atau (0.00, -1.00)valid)
• Anda mendapatkan -20 byte jika program Anda benar-benar menampilkan lingkaran pembatas dan titik yang dihasilkan di dalamnya. Koordinat masih harus valid tetapi tidak ditampilkan, dan gambar yang dihasilkan harus berukuran paling tidak 201 x 201 piksel
• Anda mendapatkan -5 byte jika program Anda mengambil jumlah poin yang akan dihasilkan sebagai input pada stdin
• Jika Anda memutuskan untuk tidak memplot lingkaran pembatas dan titik, program Anda harus menampilkan titik yang dihasilkan pada format (x, y)atau (x,y)pada stdout
• Jika Anda memutuskan untuk mengambil jumlah titik yang dihasilkan sebagai input, tetapi tidak untuk memplotnya - program Anda harus menampilkan semua titik acak pada format yang disebutkan di atas dengan atau tanpa satu ruang di antaranya.

Pengajuan terpendek dalam byte menang!

Pyth, 26 - 5 = 21 byte

VQp(sJ*@OZ2^.n1*yOZ.l_1)eJ

Mengambil jumlah koordinat untuk dihasilkan pada stdin, dan mengeluarkannya pada stdout seperti:

(-0.5260190768964058, -0.43631187015380823)(-0.12127959509302746, -0.08556306418467638)(-0.26813756369750996, -0.4564539715526493)

Menggunakan strategi yang mirip dengan @ MartinBüttner, menghasilkan koordinat kutub dan jari-jari, kecuali itu menggunakan eksponensial kompleks.

CJam, 28 27 byte

PP+mr_mc\ms]1.mrmqf*"(,)".\

Solusi ini bukan berbasis penolakan. Saya menghasilkan titik dalam koordinat kutub, tetapi dengan distribusi yang tidak seragam dari jari-jari untuk mencapai kerapatan titik yang seragam.

Uji di sini.

Penjelasan

PP+     e# Push 2π.
mr_     e# Get a random float between 0 and 2π, make a copy.
mc\     e# Take the cosine of one copy and swap with the other.
ms]     e# Take the sine of the other copy and wrap them in an array.
        e# This gives us a uniform point on the unit circle.
1.mr    e# Get a random float between 0 and 1.
mq      e# Take the square root. This is the random radius.
f*      e# Multiply x and y by this radius.
"(,)".\ e# Put the resulting numbers in the required format.

Mengapa ini berhasil? Pertimbangkan anulus jari-jari sempit rdan lebar (kecil)dr . Daerah tersebut kira-kira 2π*r*dr(jika annulus sempit, keliling bagian dalam dan luar hampir identik, dan kelengkungan dapat diabaikan, sehingga daerah tersebut dapat diperlakukan sebagai bidang segi empat dengan panjang sisi keliling dan lebar kelengkungan). annulus). Jadi area bertambah secara linear dengan jari-jari. Ini berarti bahwa kami juga menginginkan distribusi linear dari jari-jari acak, untuk mencapai kerapatan konstan (pada radius dua kali, ada area dua kali lebih banyak untuk diisi, jadi kami ingin dua kali lebih banyak titik di sana).

Bagaimana kita menghasilkan distribusi acak linier dari 0 ke 1? Mari kita lihat kasus diskritnya terlebih dahulu. Katakanlah, kami memiliki distribusi yang diinginkan dari 4 nilai, seperti {0.1, 0.4, 0.2, 0.3}(yaitu kami ingin 1menjadi 4 kali lebih umum 0, dan dua kali lebih umum 2; kami ingin 3tiga kali lebih umum 0):

Bagaimana cara memilih satu dari empat nilai dengan distribusi yang diinginkan? Kita dapat menumpuknya, mengambil nilai acak seragam antara 0 dan 1 pada sumbu y dan memilih segmen pada titik itu:

Ada cara berbeda untuk memvisualisasikan pemilihan ini. Sebagai gantinya, kami dapat mengganti setiap nilai distribusi dengan akumulasi nilai hingga saat itu:

Dan sekarang kita memperlakukan baris teratas dari bagan ini sebagai fungsi f(x) = ydan membalikkannya untuk mendapatkan fungsi , yang dapat kita terapkan pada nilai acak seragam di :g(y) = f-1(y) = xy ∈ [0,1]

Keren, jadi bagaimana memanfaatkan ini untuk menghasilkan distribusi linear jari-jari? Ini adalah distribusi yang kami inginkan:

Langkah pertama adalah mengakumulasi nilai-nilai distribusi. Tetapi distribusi ini kontinu, jadi alih-alih menjumlahkan semua nilai sebelumnya, kami mengambil integral dari 0ke r. Kita dapat dengan mudah memecahkan analitis bahwa: . Namun, kami ingin ini dinormalisasi, yaitu untuk mengalikannya dengan konstanta sehingga memberikan nilai maksimum , jadi yang benar-benar kita inginkan adalah :∫0r r dr = 1/2 r21rr2

Dan akhirnya, kita membalikkan ini untuk mendapatkan fungsi yang dapat kita terapkan pada nilai yang seragam [0,1], yang dapat kita lakukan lagi secara analitis: hanya saja r = √y, di mana yadalah nilai acak:

Ini adalah teknik yang cukup berguna yang sering dapat digunakan untuk menghasilkan distribusi sederhana dengan tepat (ini berfungsi untuk distribusi apa pun, tetapi untuk yang rumit, dua langkah terakhir mungkin harus diselesaikan secara numerik). Namun, saya tidak akan menggunakannya dalam kasus khusus ini dalam kode produksi, karena akar kuadrat, sinus dan kosinus sangat mahal: menggunakan algoritma berbasis penolakan rata-rata jauh lebih cepat, karena hanya membutuhkan penambahan dan perkalian.

Mathematica, 68 44 - 20 = 24 byte

Terima kasih banyak untuk David Carraher karena memberi tahu saya RandomPoint, yang menyelamatkan 24 (!) Byte. Mathematica memang memiliki built-in untuk semuanya.

Graphics@{Circle[],Point@RandomPoint@Disk[]}

Ini menentukan titik dan lingkaran terikat untuk memenuhi syarat untuk bonus:

Hasilnya adalah gambar vektor, sehingga spesifikasi ukuran 201x201 piksel tidak benar-benar masuk akal, tetapi secara default itu membuat lebih besar dari itu.

CJam, 31 26 byte

{];'({2dmr(_}2*@mhi}g',\')

Ini berfungsi dengan berulang kali menghasilkan titik acak dalam kuadrat panjang sisi 2 dan menjaga titik pertama yang berada di dalam disk unit.

Terima kasih kepada @ MartinBüttner untuk bermain golf 3 byte!

Cobalah online di penerjemah CJam .

Bagaimana itu bekerja

{                  }g       Do:
 ];'(                         Clear the stack and push a left parenthesis.
     {      }2*               Do twice:
      2dmr                      Randomly select a Double between 0 and 2.
          (_                    Subtract 1 and push a copy.
               @              Rotate the copy of the first on top of the stack.
                mh            Compute the Euclidean norm of the vector consisting
                              of the two topmost Doubles on the stack.
                  i           Cast to integer.
                            If the result is non-zero, repeat the loop.
                     ',\    Insert a comma between the Doubles.
                        ')  Push a right parenthesis.

iKe , 53 51 byte

Tidak ada yang istimewa, tapi saya kira kita harus memiliki setidaknya satu solusi grafis:

,(80+160*t@&{.5>%(x*x)+y*y}.+t:0N 2#-.5+?9999;cga;3)

Cobalah di browser Anda .

Sunting: Saya dapat memotong dua byte dengan menerapkan pendekatan @ MartinBüttner untuk memodifikasi distribusi koordinat kutub. Saya pikir ini juga sedikit lebih langsung:

,(80*1+(%?c){x*(cos y;sin y)}'6.282*?c:9999;cga;3)

Perl, 59 Bytes

while(($x=1-rand 2)**2+($y=1-rand 2)**2>1){};print"($x,$y)"

Ini hanyalah solusi sederhana, menghasilkan poin dalam kotak dan menolak yang terlalu jauh. Trik golf tunggal saya adalah memasukkan tugas di dalam kondisi.

Sunting: Dalam proses bermain golf, saya menemukan cara yang menarik untuk mencetak poin acak pada sebuah lingkaran .

use Math::Trig;$_=rand 2*pi;print"(",sin,",",cos,")"

Oktaf, 24 53 - 20 = 33 byte

polar([0:2e-3:1,rand]*2*pi,[ones(1,501),rand^.5],'.')

Menghasilkan 501 nilai theta dengan jarak yang sama ditambah satu angka acak dan menskalakan semuanya menjadi [0..2π]. Kemudian menghasilkan 501 1 untuk jari-jari lingkaran, ditambah jari-jari acak untuk titik dan mengambil akar kuadrat untuk memastikan distribusi seragam pada disk. Kemudian plot semua titik sebagai koordinat polar.

Berikut ini adalah demonstrasi cepat distribusi (tanpa lingkaran unit):

polar(2*pi*rand(99),rand(99).^.5,'.')

Oktaf / Matlab, 74 64 byte

Metode penolakan , 64 byte:

u=1;v=1;while u^2+v^2>1
u=rand;v=rand;end
sprintf('(%f,%f)',u,v)

Metode langsung , 74 byte (terima kasih kepada Martin Büttner karena membantu saya memperbaiki dua kesalahan):

t=rand*2*pi;r=1-abs(1-sum(rand(2,1)));sprintf('(%f,%f)',r*cos(t),r*sin(t))

R, 99 95 81-20 = 79 75 61 Bytes

symbols(0,0,1,i=F,asp=1,ylim=c(-1,1));points(complex(,,,runif(9),runif(9,-1)*pi))

Gunakan konstruksi bilangan kompleks untuk membangun x / y dari koordinat kutub. Mengambil input agak mahal dan mungkin ada cara yang lebih baik untuk melakukan ini. The ylim danxlim adalah untuk memastikan seluruh lingkaran diplot danasp tanda titik ditampilkan di bawah simbol lingkaran.

Terima kasih kepada @jbaums dan @flodel untuk penghematannya

Coba di sini

Memproses / Java 141 byte-20 = 121

persyaratan untuk 201 * 201 sebagai ukuran minimum mengharuskan saya untuk memasukkan setupmetode sejak Processing.org default ke 200x200 :(

void setup(){noFill();size(201,201);}void draw(){float f=10,a=PI*2*random(),r=random();point(f+f*sin(a)*r,f+f*cos(a)*r);ellipse(f,f,f*2,f*2)}

QBasic, 138 byte - 20 - 5 = 113

INPUT n
r=200
SCREEN 12
RANDOMIZE TIMER
CIRCLE(r,r),r
PAINT(r,r)
FOR i=1TO n
DO
x=RND*r*2
y=RND*r*2
LOOP UNTIL POINT(x,y)
PSET(x,y),1
NEXT

Mengambil input pengguna dan menggambar disk dan poin. Diuji pada QB64 .

Ini adalah strategi "lempar ke papan dart dan simpan tongkat apa yang cukup mendasar". Tangkapannya adalah bahwa "tongkat apa" tidak ditentukan secara matematis tetapi secara grafis: cakram putih diplot pada latar belakang hitam, dan kemudian titik-titik yang dihasilkan secara acak ditolak sampai tidak hitam. Poin-poin itu sendiri digambar dengan warna biru (meskipun sulit untuk mengetahui kapan mereka memiliki piksel tunggal - klik pada gambar untuk memperbesar).

awk - 95 - 5 = 90

{
    for(;$1--;printf"("(rand()<.5?x:-x)","(rand()<.5?y:-y)")")
        while(1<(x=rand())^2+(y=rand())^2);
}

Karena saya tidak begitu yakin tentang rand () <. 5 bagian, saya melakukan beberapa pengujian distribusi dengan ini, menggunakan skrip ini:

BEGIN{ srand() }
{ 
    split("0 0 0 0", s)
    split("0 0 0 0", a)

    for(i=$1; i--; )
    {
        while( 1 < r2 = ( x=rand() )^2 + ( y=rand() )^2 );

        x = rand()<.5 ? x : -x
        y = rand()<.5 ? y : -y

        ++s[ x>=0 ? y>=0 ? 1 : 4 : y>=0 ? 2 : 3 ]

        ++a[ r2>.75 ? 1 : r2>.5 ? 2 : r2>.25 ? 3 : 4]
    }

    print "sector distribution:"
        for(i in s) print "sector " i ": " s[i]/$1

    print "quarter area distribution:"
        for(i in a) print "ring " i ":   " a[i]/$1
}

yang untuk input 1e7 memberi saya hasil ini, setelah saya menyesap kopi sekali atau dua kali:

1e7
sector distribution:
sector 1: 0.250167
sector 2: 0.249921
sector 3: 0.249964
sector 4: 0.249948
quarter area distribution:
ring 1:   0.24996
ring 2:   0.25002
ring 3:   0.250071
ring 4:   0.249949

yang menurut saya cukup baik.

Penjelasan kecil:
Setelah menulis sebentar ternyata, jika Anda ingin membagi disk menjadi empat cincin dengan luas yang sama, jari-jari di mana Anda harus memotong adalah sqrt (1/4), sqrt (1/2) ) dan sqrt (3/4). Karena jari-jari aktual dari pengujian titik saya adalah sqrt (x ^ 2 + y ^ 2), saya dapat melewatkan rooting persegi secara bersamaan. "Kebetulan" 1/4, 2/4, 3/4 mungkin terkait dengan apa yang ditunjukkan M. Buettner sebelumnya.

HPPPL , 146 (171-20-5) byte

EXPORT r(n)BEGIN LOCAL R,A,i,Q;RECT();Q:=118.;ARC_P(Q,Q,Q);FOR i FROM 1 TO n DO R:=√RANDOM(1.);A:=RANDOM(2*π);PIXON_P(G0,IP(Q+Q*R*COS(A)),IP(Q+Q*R*SIN(A)));END;FREEZE;END;

Contoh untuk 10000 poin (termasuk penghitungan waktu dalam detik untuk perangkat nyata):

Fungsi itu sendiri dipanggil oleh r(n) . Sisanya pada gambar di atas hanya untuk tujuan pengaturan waktu.

Hasil (diameter disk adalah 236 piksel):

Versi di atas tidak menyimpan titik koordinat, jadi saya menulis versi yang mengambil dua parameter r(n,p). nadalah jumlah poin dan p=0mengembalikan poin ke terminal, p=1plot poin dan disk), dalam kasus menyimpan koordinat adalah wajib. Versi ini panjangnya 283 (308-20-5) byte:

EXPORT r(n,p)BEGIN LOCAL R,A,j,Q,x,y;Q:=118.0;CASE IF p==0 THEN print() END IF p==1 THEN RECT();ARC_P(Q,Q,Q) END END;FOR j FROM 1 TO n DO R:=√RANDOM(1.0);A:=RANDOM(2*π);x:=R*COS(A);y:=R*SIN(A);CASE IF p==0 THEN print("("+x+", "+y+")") END IF p==1 THEN PIXON_P(G0,IP(Q+Q*x),IP(Q+Q*y)) END END;END;FREEZE;END;

Versi ungolfed:

EXPORT r(n,p)
BEGIN
LOCAL R,A,j,Q,x,y;
  Q:=118.0;
  CASE
    IF p==0 THEN print() END
    IF p==1 THEN RECT();ARC_P(Q,Q,Q) END
  END;
  FOR j FROM 1 TO n DO
    R:=√RANDOM(1.0);
    A:=RANDOM(2*π);
    x:=R*COS(A);
    y:=R*SIN(A);
    CASE
      IF p==0 THEN print("("+x+", "+y+")") END
      IF p==1 THEN PIXON_P(G0,IP(Q+Q*x),IP(Q+Q*y)) END
    END;
  END;
  FREEZE;
END;

Output terminal untuk r(10,0):

r(10,1) menunjukkan disk dengan titik-titik, seperti yang ditunjukkan di atas.

JavaScript, 75 byte

Berbasis penolakan:

do x=(r=()=>4*Math.random()-2)(),y=r()
while(x*x+y*y>1)
alert(`(${[x,y]})`)

Metode langsung (80 byte):

alert(`(${[(z=(m=Math).sqrt((r=m.random)()))*m.sin(p=m.PI*2*r()),z*m.cos(p)]})`)

Python, 135 130 byte

from random import*
def r():return uniform(-1,1)
p=[]
while not p:
    x,y=r(),r()
    if x**2+y**2<=1:p=x,y
print'(%.2f, %2f)'%p

Menghapus **0.5terima kasih atas saran @ jimmy23013 (karena ini adalah lingkaran satuan, saya sekarang memeriksa apakah jarak kuadrat antara (x, y) dan (0, 0) sama dengan 1 ^2. Ini adalah hal yang sama).

Ini juga membebaskan saya untuk menghapus tanda kurung.