Pi Natural # 1 - Arena

9

Objetivo

Genere ( N) segmentos de línea aleatorios de longitud uniforme ( l), verifique si cruzan las tlíneas paralelas equidistantes ( ).

Simulación

¿Qué estamos simulando? La aguja de Buffon . Alise la arena en su caja de arena, dibuje un conjunto de líneas paralelas igualmente espaciadas (llame a la distancia intermedia t). Tome un palo recto de longitud ly colóquelo Nen el cajón de arena. Sea el número de veces que cruzó una línea c. Entonces Pi = (2 * l * n) / (t * c)!

¿Cómo estamos simulando esto?

  • Tomar entrada N,t,l
  • Con N, t, ltodos siendo enteros positivos
  • Haz los siguientes Nhorarios:
    • Generar una coordenada entera uniformemente aleatoria x,y
    • Con 1 <= x, y <= 10^6
    • x,y es el centro de un segmento de línea de longitud l
    • Generar un entero uniformemente aleatorio a
    • Con 1 <= a <= 180
    • Sea Pel punto donde el segmento de línea cruzaría el eje x
    • Entonces aes el ángulo(x,y), P, (inf,0)
  • Cuente el número cde segmentos de línea que cruzan la línea x = i*tpara cualquier número enteroi
  • Regreso (2 * l * N) / (t * c)

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Especificación

  • Entrada
    • Flexible, tome la entrada en cualquiera de las formas estándar (por ejemplo, parámetro de función, STDIN) y en cualquier formato estándar (por ejemplo, cadena, binario)
  • Salida
    • Flexible, dé salida en cualquiera de las formas estándar (por ejemplo, devolución, impresión)
    • El espacio en blanco, el espacio en blanco al final y al final es aceptable
    • Precisión, proporcione al menos 4 decimales de precisión (es decir 3.1416)
  • Puntuación
    • ¡El código más corto gana!

Casos de prueba

Es posible que su salida no se alinee con estos, debido a la posibilidad aleatoria. Pero en promedio, debe obtener esta precisión para el valor dado de 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

Estos desafíos son simulaciones de algoritmos que solo requieren la naturaleza y su cerebro (y tal vez algunos recursos reutilizables) para aproximarse a Pi. Si realmente necesitas Pi durante el apocalipsis zombie, ¡estos métodos no desperdician munición ! Hay nueve desafíos en total.

Fruta no lineal
fuente
Pensé que ya hiciste el número 1?
Conor O'Brien el
1
@ ConorO'Brien I lo indexamos a cero XD
NonlinearFruit
El problema con esto es que, en idiomas sin números complejos, debe convertir el número 0..180 en 0..pi, lo que en su lugar anula el propósito del experimento de la aguja del buffon.
Level River St el
@NonlinearFruit ¿se puede crear la dirección atambién por otro método, si es uniforme? (pensando en una burbuja Gauss 2D)
Karl Napf
1
¿Se puede suponer eso t > l? Dos de las siguientes soluciones hacen esta suposición, lo que simplifica bastante la verificación de la intersección.
primo

Respuestas:

9

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

Como lenguaje de programación funcional y estadístico, no es sorprendente que R sea bastante adecuado para este tipo de tarea. El hecho de que la mayoría de las funciones pueden tomar entradas vectorizadas es realmente útil para este problema, ya que en lugar de recorrer las Niteraciones, simplemente pasamos por vectores de tamaño N. Gracias a @Billywob por algunas sugerencias que conducen a cortar 4 bytes. Muchas gracias a @Primo por explicarme pacientemente cómo no funcionaba mi código en los casos en t > lque ahora está solucionado.

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

Pruébalo en línea!

Salida de muestra:

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

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

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

Explicación

El problema se reduce a determinar si los dos xvalores de la aguja están a cada lado de una línea paralela. Esto tiene algunas consecuencias importantes:

  1. y-los valores son irrelevantes
  2. La ubicación absoluta en el x eje es irrelevante, solo la posición relativa a las líneas paralelas más cercanas.

Esencialmente, esta es una tarea en un espacio unidimensional, donde generamos una línea con longitud en [0, l] (el ángulo adetermina esta longitud), y luego verificamos cuántas veces excede esta longitud t. El algoritmo aproximado es entonces:

  1. x1Valores de muestra de [0, 1000000]. Como las líneas paralelas ocurren en cada tpunto a lo largo del xeje, la posición relativa xes xmódulo t.
  2. Muestra un ángulo a.
  3. Calcule la x2posición en función de a.
  4. Compruebe cuántas veces x1+x2cabe t, es decir, tome el piso de (x1+x2)/t.

Los Nnúmeros de muestreo en el módulo [0, 1e6] tson equivalentes a simplemente los Nnúmeros de muestreo en [0, t]. Como (x1+x2)/tes equivalente a x1/t + x2/t, el primer paso se convierte en muestreo de [0, t] / t, es decir, [0, 1]. Por suerte para nosotros, ese es el rango predeterminado para la runiffunción de R , que devuelve Nnúmeros reales de 0 a 1 de una distribución uniforme.

                          runif(N)

Repetimos este paso para generar a, el ángulo de la aguja.

                                         runif(N)

Estos números se interpretan como media vuelta ( .5es decir, son 90 grados). (El OP solicita grados del 1 al 180, pero en los comentarios se aclara que se permite cualquier método si es tan o más preciso). Para un ángulo θ, sin(θ)nos da la distancia del eje x entre los extremos de la aguja. (Normalmente se usaría el coseno para algo como esto, pero en nuestro caso, estamos considerando el ángulo θcomo en relación con el eje y, no en el eje X (es decir, un valor de 0 grados va hacia arriba , no derecha ), y por lo tanto usamos el seno, que básicamente cambia los números de fase.) Multiplicado por lesto nos da la xubicación del extremo de la aguja.

                                   sinpi(runif(N))*l

Ahora dividimos por ty sumamos el x1valor. Esto produce (x1+x2)/t, que es qué tan lejos sobresale la aguja x1, en términos de número de líneas paralelas. Para obtener el número entero de cuántas líneas se cruzaron, tomamos el floor.

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

Calculamos la suma, dándonos el recuento cde cuántas líneas cruzan las agujas.

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

El resto del código es simplemente aplicando la fórmula para aproximar pi, es decir, (2*l*N)/(t*c). Ahorramos algunos bytes entre paréntesis aprovechando el hecho de que (2*l*N)/(t*c) == 2*l*N/t/c:

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

Y todo está envuelto en una función anónima:

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))
rturnbull
fuente
@rturnbull Nice one! ¿No deberías ser capaz de saltarte los paréntesis al principio? (2*l*N) => 2*l*N?
Billywob
@Billywob ¡Bien visto! Gracias.
rturnbull
@rturnbull Ah y, por cierto, (2*l*N)/(t*c) = 2*l*N/t/cpuede guardar otros dos bytes omitiendo los paréntesis en la última parte también.
Billywob
@Billywob ¡Otra vez, bien visto! Gracias de nuevo.
rturnbull
1
@primo Gracias de nuevo, debería arreglarse ahora.
rturnbull
6

Perl, 97 bytes

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

Contando el shebang como uno, la entrada se toma de stdin, separados por espacios. Si se permitieran valores aleatorios no enteros, esto podría ser algo más corto.

Me he tomado una libertad, aproximando π / 180 como 71/4068 , lo cual es exacto dentro de 1.48 · 10 -9 .

Uso de muestra

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

Más o menos sustituciones matemáticamente equivalentes

Suponiendo que la coordenada x representa el punto más a la izquierda de la aguja, en lugar de su centro, como se especifica en la descripción del problema:

89 bytes

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

El problema especifica que xse muestreará como un entero aleatorio. Si proyectamos el espacio entre líneas en un espacio de uno, esto nos dejará con valores de la forma n/tcon 0 <= n < t, no necesariamente uniformes, si tno se divide equitativamente1e6 . Asumiendo que una distribución uniforme es aceptable:

76 bytes

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

Tenga en cuenta que dado randque siempre será menor que uno (y, por lo tanto, truncado a cero), no es necesario al comienzo del rango:

70 bytes

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

Suponiendo que el ángulo de la aguja no necesita ser un grado entero, sino solo un azar uniforme:

59 bytes

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

Suponiendo que el ángulo puede ser cualquier distribución uniforme:

52 bytes

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

Lo anterior es una simulación matemáticamente correcta de la Aguja de Buffon. Sin embargo, en este punto creo que la mayoría de la gente estaría de acuerdo en que esto no es realmente lo que la pregunta pedía.


Realmente empujándolo

Podríamos tirar la mitad de los casos de prueba, siempre que el segundo punto final esté a la izquierda del primero (en lugar de intercambiarlos):

47 bytes

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

Tenga en cuenta que los valores de ty lson inconsecuentes a los resultados del experimento. Podríamos ignorarlos (suponiendo implícitamente que son iguales):

28 bytes

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

Obviamente no compite, pero hay que admitir que tiene cierta elegancia.

primo
fuente
4

Python 2, 141 bytes

descarado puerto de rtumbull, ya saltando yporque no es totalmente necesario.

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

El único problema es que pi ya se conoce en el programa.

Aquí está (golfable) con pi desconocido y sin funciones trigonométricas

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,yen ges solo para la dirección.

Karl Napf
fuente
Requiere from random import randint;from math import cos,pi. Falla t < l, por ejemplo 1000000,1000,70000.
primo