Objetivo
Genere ( N
) segmentos de línea aleatorios de longitud uniforme ( l
), verifique si cruzan las t
lí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 l
y colóquelo N
en 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, l
todos siendo enteros positivos - Haz los siguientes
N
horarios:- 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 longitudl
- Generar un entero uniformemente aleatorio
a
- Con
1 <= a <= 180
- Sea
P
el punto donde el segmento de línea cruzaría el eje x - Entonces
a
es el ángulo(x,y), P, (inf,0)
- Generar una coordenada entera uniformemente aleatoria
- Cuente el número
c
de segmentos de línea que cruzan la líneax = i*t
para cualquier número enteroi
- Regreso
(2 * l * N) / (t * c)
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.
a
también por otro método, si es uniforme? (pensando en una burbuja Gauss 2D)t > l
? Dos de las siguientes soluciones hacen esta suposición, lo que simplifica bastante la verificación de la intersección.Respuestas:
R,
1131007570686765596357 bytesComo 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
N
iteraciones, simplemente pasamos por vectores de tamañoN
. 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 ent > l
que ahora está solucionado.Pruébalo en línea!
Salida de muestra:
Explicación
El problema se reduce a determinar si los dos
x
valores de la aguja están a cada lado de una línea paralela. Esto tiene algunas consecuencias importantes:y
-los valores son irrelevantesx
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 ánguloa
determina esta longitud), y luego verificamos cuántas veces excede esta longitudt
. El algoritmo aproximado es entonces:x1
Valores de muestra de [0, 1000000]. Como las líneas paralelas ocurren en cadat
punto a lo largo delx
eje, la posición relativax
esx
módulot
.a
.x2
posición en función dea
.x1+x2
cabet
, es decir, tome el piso de(x1+x2)/t
.Los
N
números de muestreo en el módulo [0, 1e6]t
son equivalentes a simplemente losN
números de muestreo en [0,t
]. Como(x1+x2)/t
es equivalente ax1/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 larunif
función de R , que devuelveN
números reales de 0 a 1 de una distribución uniforme.Repetimos este paso para generar
a
, el ángulo de la aguja.Estos números se interpretan como media vuelta (
.5
es 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 porl
esto nos da lax
ubicación del extremo de la aguja.Ahora dividimos por
t
y sumamos elx1
valor. Esto produce(x1+x2)/t
, que es qué tan lejos sobresale la agujax1
, en términos de número de líneas paralelas. Para obtener el número entero de cuántas líneas se cruzaron, tomamos elfloor
.Calculamos la suma, dándonos el recuento
c
de cuántas líneas cruzan las agujas.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
:Y todo está envuelto en una función anónima:
fuente
(2*l*N) => 2*l*N
?(2*l*N)/(t*c) = 2*l*N/t/c
puede guardar otros dos bytes omitiendo los paréntesis en la última parte también.Perl, 97 bytes
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
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
El problema especifica que
x
se muestreará como un entero aleatorio. Si proyectamos el espacio entre líneas en un espacio de uno, esto nos dejará con valores de la forman/t
con0 <= n < t
, no necesariamente uniformes, sit
no se divide equitativamente1e6
. Asumiendo que una distribución uniforme es aceptable:76 bytes
Tenga en cuenta que dado
rand
que siempre será menor que uno (y, por lo tanto, truncado a cero), no es necesario al comienzo del rango:70 bytes
Suponiendo que el ángulo de la aguja no necesita ser un grado entero, sino solo un azar uniforme:
59 bytes
Suponiendo que el ángulo puede ser cualquier distribución uniforme:
52 bytes
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
Tenga en cuenta que los valores de
t
yl
son inconsecuentes a los resultados del experimento. Podríamos ignorarlos (suponiendo implícitamente que son iguales):28 bytes
Obviamente no compite, pero hay que admitir que tiene cierta elegancia.
fuente
Python 2, 141 bytes
descarado puerto de rtumbull, ya saltando
y
porque no es totalmente necesario.El único problema es que pi ya se conoce en el programa.
Aquí está (golfable) con pi desconocido y sin funciones trigonométricas
x,y
eng
es solo para la dirección.fuente
from random import randint;from math import cos,pi
. Fallat < l
, por ejemplo1000000,1000,70000
.