Randomiser des points sur un disque

14

J'ai lu quelque chose sur les cercles quelque part, et je viens d'apprendre les disques ( c'est en fait un concept assez courant ) et j'ai pensé au codegolf.

Votre tâche consiste à randomiser un point / plusieurs points sur un disque avec le rayon 1.

Règles:

  • Tous les points doivent avoir une probabilité égale pour être générés
  • Des coordonnées en virgule flottante doivent être utilisées; l'exigence minimale est de deux décimales (par exemple, les points (0.12, -0.45)ou (0.00, -1.00)sont valides)
  • Vous obtenez -20 octets si votre programme affiche réellement le cercle de délimitation et le ou les points générés dans celui-ci. Les coordonnées doivent toujours être valides mais ne sont pas affichées, et l'image générée doit avoir une taille d'au moins 201 x 201 pixels
  • Vous obtenez -5 octets si votre programme prend le nombre de points à générer en entrée sur stdin
  • Si vous décidez de ne pas tracer le cercle de délimitation et le (s) point (s), votre programme doit sortir le (s) point (s) généré (s) sur le format (x, y)ou (x,y)sur stdout
  • Si vous décidez de prendre le nombre de points générés en entrée, mais pas de le tracer - votre programme doit sortir tous les points aléatoires au format indiqué ci-dessus avec ou sans un espace entre les deux.

La soumission la plus courte en octets gagne!

patate douce
la source
1
@sweerpotato Oui, veuillez préciser que tous les points dans et sur le cercle sont valides. Je ne savais pas que tu voulais dire les deux. En outre, cette question semble correspondre à un défi de golf de code mieux qu'un concours de popularité, mais c'est juste mon opinion.
cole
5
" Faites XYZ de manière créative " est la classique Bad Popcon Question ™. Ce qu'une personne considère comme créatif est ce qu'une autre personne considère comme la manière la plus évidente.
Peter Taylor
Par curiosité, pourquoi une exigence de sortie de 201x201 pixels pour les tracés?
JohnE
@JohnE J'ai suggéré 201x201 pixels car il correspond à la précision de 2 décimales requise
trichoplax
Pouvons-nous sortir les coordonnées sous forme de nombres complexes? Par exemple: 0.3503082505747327+0.13499221288682994j.
orlp

Réponses:

5

Pyth, 26 - 5 = 21 octets

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

Prend le nombre de coordonnées à générer sur stdin et les affiche sur stdout comme ceci:

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

Utilise une stratégie similaire à @ MartinBüttner, générant des coordonnées polaires et des rayons, sauf qu'il le fait en utilisant une exponentiation complexe.

orlp
la source
Vous pouvez supprimer le p, n'est-ce pas? Il modifie simplement la sortie sur des lignes distinctes.
PurkkaKoodari
@ Pietu1998 Ce n'est pas autorisé, voir les commentaires sur la question principale.
orlp
Ah très bien.
PurkkaKoodari
16

CJam, 28 27 octets

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

Cette solution n'est pas basée sur le rejet. Je génère les points en coordonnées polaires, mais avec une distribution non uniforme des rayons pour obtenir une densité uniforme des points.

Testez-le ici.

Explication

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.

Pourquoi ça marche? Considérons un espace étroit de rayon ret de (petite) largeurdr . La zone est approximativement 2π*r*dr(si l'espace annulaire est étroit, la circonférence intérieure et extérieure sont presque identiques, et la courbure peut être ignorée, de sorte que la zone peut être traitée comme celle d'un rectangle avec des longueurs latérales de la circonférence et la largeur de la anneau). La zone augmente donc linéairement avec le rayon. Cela signifie que nous voulons également une distribution linéaire des rayons aléatoires, afin d'atteindre une densité constante (à deux fois le rayon, il y a deux fois plus de surface à remplir, donc nous voulons deux fois plus de points là-bas).

Comment générer une distribution aléatoire linéaire de 0 à 1? Regardons d'abord le cas discret. Disons, nous avons une distribution souhaitée de 4 valeurs, comme {0.1, 0.4, 0.2, 0.3}(c'est-à-dire que nous voulons 1être 4 fois plus communs que 0, et deux fois plus communs que 2; nous voulons 3trois fois plus communs que 0):

entrez la description de l'image ici

Comment choisir l'une des quatre valeurs avec la distribution souhaitée? Nous pouvons les empiler, choisir une valeur uniformément aléatoire entre 0 et 1 sur l'axe des y et choisir le segment à ce point:

entrez la description de l'image ici

Il existe cependant une manière différente de visualiser cette cueillette. On pourrait plutôt remplacer chaque valeur de la distribution par l'accumulation des valeurs jusqu'à ce point:

entrez la description de l'image ici

Et maintenant, nous traitons la ligne supérieure de ce graphique comme une fonction f(x) = yet l'inversons pour obtenir une fonction , que nous pouvons appliquer à une valeur uniformément aléatoire dans :g(y) = f-1(y) = xy ∈ [0,1]

entrez la description de l'image ici

Cool, alors comment utiliser cela pour générer une distribution linéaire des rayons? Voici la distribution que nous voulons:

entrez la description de l'image ici

La première étape consiste à accumuler les valeurs de la distribution. Mais la distribution est continue, donc au lieu de résumer toutes les valeurs précédentes, nous prenons une intégrale de 0à r. On peut facilement résoudre ce analytiquement: . Cependant, nous voulons que cela soit normalisé, c'est-à-dire le multiplier par une constante telle que cela donne la valeur maximale de , donc ce que nous voulons vraiment, c'est :0r r dr = 1/2 r21rr2

entrez la description de l'image ici

Et enfin, nous inversons cela pour obtenir une fonction que nous pouvons appliquer à une valeur uniforme [0,1], que nous pouvons à nouveau faire analytiquement: c'est juste r = √y, où yest la valeur aléatoire:

entrez la description de l'image ici

Il s'agit d'une technique assez utile qui peut souvent être utilisée pour générer exactement des distributions simples (elle fonctionne pour n'importe quelle distribution, mais pour les plus compliquées, les deux dernières étapes peuvent devoir être résolues numériquement). Cependant, je ne l'utiliserais pas dans ce cas particulier dans le code de production, car la racine carrée, le sinus et le cosinus sont d'un coût prohibitif: l'utilisation d'un algorithme basé sur le rejet est en moyenne beaucoup plus rapide, car il n'a besoin que d'addition et de multiplication.

Martin Ender
la source
1
Très belle explication!
sweerpotato
2
Images Mmm: D
Beta Decay
12

Mathematica, 68 44-20 = 24 octets

Merci beaucoup à David Carraher de m'avoir informé RandomPoint, qui a économisé 24 (!) Octets. Mathematica ne possède un pour tout intégré.

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

Cela trace le point et le cercle de délimitation pour se qualifier pour le bonus:

entrez la description de l'image ici

Le résultat est une image vectorielle, donc la spécification de taille de 201x201 pixels n'a pas vraiment de sens, mais par défaut, elle est plus grande que cela.

Martin Ender
la source
Et alors Graphics[{Circle[], Point@RandomPoint@Disk[]}]?
DavidC
Soit mon invité. Aussi, pour économiser 1 octet ...Graphics@{Circle[], Point@RandomPoint@Disk[]}
DavidC
@DavidCarraher Merci beaucoup! :)
Martin Ender
Je ne connais pas la syntaxe Mathematica mais vous pouvez sûrement enregistrer un autre octet en supprimant l'espace après le ,?
duveteux
@fluffy Je l'ai déjà fait dans la version publiée
Martin Ender
9

CJam, 31 26 octets

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

Cela fonctionne en générant à plusieurs reprises des points aléatoires dans un carré de longueur de côté 2 et en conservant le premier qui tombe à l'intérieur du disque de l'unité.

Merci à @ MartinBüttner pour avoir joué au golf sur 3 octets!

Essayez-le en ligne dans l' interpréteur CJam .

Comment ça fonctionne

{                  }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.
Dennis
la source
8

iKe , 53 51 octets

Rien de particulièrement spécial, mais je suppose que nous devrions avoir au moins une solution graphique:

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

terrain

Essayez-le dans votre navigateur .

Edit: je peux raser deux octets en appliquant l'approche de @ MartinBüttner pour modifier la distribution des coordonnées polaires. Je pense que c'est aussi un peu plus direct:

,(80*1+(%?c){x*(cos y;sin y)}'6.282*?c:9999;cga;3)
JohnE
la source
3
Si vous dessiniez également le cercle de délimitation, vous auriez droit à -20.
orlp
1
iKe dispose d'un modèle de dessin raster, ce qui rend cette exigence plutôt injuste. Je pense qu'il en coûterait un peu plus de 20 caractères pour rendre une approximation d'un cercle de délimitation également.
JohnE
7

Perl, 59 octets

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

C'est juste une solution simple, générer des points dans un carré et rejeter ceux trop loin. Mon astuce de golf singulière consiste à inclure les affectations à l'intérieur de la condition.

Edit: En cours de golf, j'ai trouvé un moyen intéressant d'imprimer des points aléatoires sur un cercle .

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

Octave, 24 53-20 = 33 octets

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

Génère 501 valeurs thêta également espacées plus un nombre aléatoire et les met à l'échelle à [0..2π]. Génère ensuite 501 1 pour le rayon du cercle, plus un rayon aléatoire pour le point et prend la racine carrée pour assurer une distribution uniforme sur le disque. Trace ensuite tous les points sous forme de coordonnées polaires.

entrez la description de l'image ici


Voici une rapide démonstration de la distribution (sans le cercle unitaire):

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

9801 Points

gobelet
la source
5

Octave / Matlab, 74 64 octets

Méthode de rejet , 64 octets:

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

Méthode directe , 74 octets (merci à Martin Büttner de m'avoir aidé à corriger deux erreurs):

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

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

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

Utilisez la construction de nombres complexes pour construire les x / y à partir des coordonnées polaires. Prendre l'entrée était un peu cher et il y a probablement une meilleure façon de le faire. Le ylim et permetxlim de s'assurer que l'ensemble du cercle est tracé et le aspassure que les points sont affichés sous le symbole du cercle.

Merci à @jbaums et @flodel pour les économies

Essayez-le ici

MickyT
la source
runif(9,0,1)peut être simplifié enrunif(9)
jbaums
@jbaums, merci ... une des choses que j'ai toujours l'air d'oublier :)
MickyT
Peut se raser 14:symbols(0,0,1,i=F,asp=1,ylim=c(-1,1));points(complex(,,,runif(9),runif(9,-1)*pi))
flodel
@flodel très gentil merci.
MickyT
Une autre petite économie: ylitravaille à la place de ylim.
jbaums
4

Traitement / Java 141 octets-20 = 121

l'exigence de 201 * 201 étant la taille minimale m'oblige à mettre dans la setupméthode depuis Processing.org par défaut à 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)}
Timothy Groote
la source
Je ne savais pas que le traitement / java était autorisé, soigné!
J Atkin
4

QBasic, 138 octets - 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

Prend l'entrée de l'utilisateur et dessine le disque et les points. Testé sur QB64 .

C'est une stratégie assez simple de "lancer sur le jeu de fléchettes et de garder ce qui colle". Le hic, c'est que "ce qui colle" n'est pas déterminé mathématiquement mais graphiquement: un disque blanc est tracé sur un fond noir, puis les points générés aléatoirement sont rejetés jusqu'à ce qu'ils ne soient pas noirs. Les points eux-mêmes sont dessinés en bleu (bien qu'il soit difficile de dire quand ce sont des pixels uniques - cliquez sur l'image pour l'agrandir).

DLosc
la source
3

awk - 95 - 5 = 90

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

Comme je n'étais pas tout à fait sûr de la partie rand () <. 5, j'ai fait quelques tests de distribution avec cela, en utilisant ce script:

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
}

qui pour une entrée de 1e7 me donne ce résultat, après avoir bu une ou deux fois à mon café:

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

qui je pense est tout à fait bien.

Une petite explication:
après avoir griffonné pendant un certain temps, il s'est avéré que si vous voulez diviser le disque en quatre anneaux de surface égale, les rayons où vous devriez couper sont sqrt (1/4), sqrt (1/2 ) et sqrt (3/4). Comme le rayon réel du point que je teste serait sqrt (x ^ 2 + y ^ 2), je peux ignorer l'enracinement carré. La "coïncidence" 1/4, 2/4, 3/4 pourrait être liée à ce que M. Buettner a souligné plus tôt.

Cabbie407
la source
3

HPPPL , 146 (171-20-5) octets

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;

Exemple pour 10000 points (y compris le chronométrage en secondes pour le vrai appareil):

Aléatoire points sur un disque, timing

La fonction elle-même est appelée par r(n). Le reste de l'image ci-dessus est uniquement à des fins de synchronisation.

Résultat (le diamètre du disque est de 236 pixels):

entrez la description de l'image ici

La version ci-dessus ne stocke pas les coordonnées du point, j'ai donc écrit une version qui prend deux paramètres r(n,p) . nest le nombre de points et p=0renvoie les points au terminal, p=1trace les points et le disque), dans le cas où le stockage des coordonnées est obligatoire. Cette version fait 283 (308-20-5) octets de long:

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;

La version non golfée:

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;

Sortie borne pour r(10,0) :

Randomiser les points sur une sortie de borne de disque

r(10,1) montre le disque avec les points, comme indiqué ci-dessus.

ML
la source
2

JavaScript, 75 octets

Basé sur le rejet:

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

Méthode directe (80 octets):

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

Python, 135 130 octets

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

Suppression des **0.5remerciements à la suggestion de @ jimmy23013 (car il s'agit d'un cercle unité, je vérifie maintenant si la distance au carré entre (x, y) et (0, 0) est égale à 1 2. C'est la même chose).

Cela m'a également libéré pour supprimer les parenthèses.

JF
la source
Je pense que vous n'en avez pas besoin **0.5.
jimmy23013
@ jimmy23013 Merci! supprimé.
JF