Pi Natural # 1 - Areia

9

Objetivo

Gere ( N) segmentos de linhas aleatórias de comprimento uniforme ( l), verifique se eles cruzam as tlinhas paralelas equidistantes ( ).

Simulação

O que estamos simulando? Agulha de Buffon . Alise a areia na sua caixa de areia, desenhe um conjunto de linhas paralelas igualmente espaçadas (chame a distância entre elas t). Pegue um pedaço reto de comprimento le solte-o Nna caixa de areia. Seja o número de vezes que cruzou uma linha c. Então Pi = (2 * l * n) / (t * c)!

Como estamos simulando isso?

  • Aceitar entrada N,t,l
  • Com N, t, ltodos sendo inteiros positivos
  • Faça os seguintes Nhorários:
    • Gere uma coordenada inteira uniformemente aleatória x,y
    • Com 1 <= x, y <= 10^6
    • x,y é o centro de um segmento de linha de comprimento l
    • Gere um número inteiro uniformemente aleatório a
    • Com 1 <= a <= 180
    • Seja Po ponto em que o segmento de linha cruzaria o eixo x
    • Então aé o ângulo(x,y), P, (inf,0)
  • Conte o número c,, de segmentos de linha que cruzam a linha x = i*tpara qualquer número inteiroi
  • Retorna (2 * l * N) / (t * c)

insira a descrição da imagem aqui

insira a descrição da imagem aqui

Especificação

  • Entrada
    • Flexível, receba informações de qualquer uma das formas padrão (por exemplo, parâmetro de função, STDIN) e em qualquer formato padrão (por exemplo, String, Binário)
  • Resultado
    • Flexível, produza de qualquer forma padrão (por exemplo, devolução, impressão)
    • Espaço em branco, espaço em branco à direita e à esquerda é aceitável
    • Precisão, forneça pelo menos 4 casas decimais de precisão (ou seja 3.1416)
  • Pontuação
    • O menor código vence!

Casos de teste

Sua saída pode não estar alinhada com isso, por causa do acaso. Mas, em média, você deve obter tanta precisão para o valor especificado 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

Esses desafios são simulações de algoritmos que exigem apenas a natureza e seu cérebro (e talvez alguns recursos reutilizáveis) para aproximar o Pi. Se você realmente precisa de Pi durante o apocalipse zumbi, esses métodos não desperdiçam munição ! Existem nove desafios no total.

NonlinearFruit
fonte
Eu pensei que você já fez o número 1?
Conor O'Brien
11
@ ConorO'Brien I indexa -o com zero XD
NonlinearFruit
o problema é que, em idiomas sem números complexos, é necessário transformar o número 0..180 em 0..pi, o que anula o objetivo do experimento com agulhas do buffon.
Level River St
@NonlinearFruit a direção atambém pode ser criada por outro método, se for uniforme? (pensando em uma bolha 2D Gauss)
Karl Napf
11
Pode-se supor isso t > l? Duas soluções abaixo fazem essa suposição, o que simplifica bastante a verificação de interseção.
Primo

Respostas:

9

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

Como uma linguagem de programação estatística e funcional, não é surpreendente que R seja bastante adequado para esse tipo de tarefa. O fato de que a maioria das funções pode receber entrada vetorizada é realmente útil para esse problema, pois, em vez de repetir Niterações, passamos apenas vetores de tamanho N. Obrigado a @Billywob por algumas sugestões que levam ao corte de 4 bytes. Muito obrigado ao @Primo por me explicar pacientemente como meu código não estava funcionando nos casos em t > lque agora está corrigido.

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

Experimente online!

Saída de amostra:

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

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

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

Explicação

O problema se resume a determinar se os dois xvalores da agulha estão nos dois lados de uma linha paralela. Isso tem algumas consequências importantes:

  1. y-valores são irrelevantes
  2. A localização absoluta no xeixo-é irrelevante, apenas a posição relativa às linhas paralelas mais próximas.

Essencialmente, esta é uma tarefa em um espaço unidimensional, onde geramos uma linha com comprimento em [0, l] (o ângulo adetermina esse comprimento) e depois verificamos quantas vezes esse comprimento excede t. O algoritmo aproximado é então:

  1. x1Valores de amostra de [0, 1000000]. Como linhas paralelas ocorrem em todos os tpontos th ao longo do xeixo, a posição relativa xé xmódulo t.
  2. Amostra de um ângulo a.
  3. Calcule a x2posição com base em a.
  4. Verifique quantas vezes x1+x2se encaixa t, ou seja, pegue o chão (x1+x2)/t.

A amostragem de Nnúmeros no módulo [0, 1e6] té equivalente a simplesmente amostragem de Nnúmeros em [0, t]. Como (x1+x2)/té equivalente a x1/t + x2/t, o primeiro passo passa a ser a amostragem de [0, t] / t, ou seja, [0, 1]. Para nossa sorte, esse é o intervalo padrão da runiffunção R , que retorna Nnúmeros reais de 0 a 1 de uma distribuição uniforme.

                          runif(N)

Repetimos esse passo para gerar ao ângulo da agulha.

                                         runif(N)

Esses números são interpretados como meia-volta (ou .5seja, 90 graus). (O OP solicita graus de 1 a 180, mas nos comentários é esclarecido que qualquer método é permitido se for tão ou mais preciso.) Para um ângulo θ, sin(θ)fornece-nos a distância do eixo x entre as extremidades da agulha. (Normalmente, você usaria o co-seno para algo como isso, mas no nosso caso, estamos considerando o ângulo θcomo sendo em relação ao eixo y, e não o eixo x (isto é, um valor de 0 graus vai -se , não à direita ) e, portanto, usamos o seno, que basicamente muda os números.) Multiplicado por lisso, nos dá a xlocalização do final da agulha.

                                   sinpi(runif(N))*l

Agora dividimos por te adicionamos o x1valor. Isso produz (x1+x2)/t, a que distância a agulha se sobressai x1, em termos de número de linhas paralelas. Para obter o número inteiro de quantas linhas foram cruzadas, usamos o floor.

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

Calculamos a soma, dando-nos a contagem cde quantas linhas são cruzadas por agulhas.

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

O restante do código está apenas implementando a fórmula para aproximar pi, ou seja (2*l*N)/(t*c),. Economizamos alguns bytes entre parênteses, aproveitando o fato 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))

E tudo está envolvido em uma função anônima:

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))
rturnbull
fonte
@rturnbull Nice one! Você não deveria pular os parênteses no começo? (2*l*N) => 2*l*N?
Billywob
@Billywob Bem-visto! Obrigado.
rturnbull
@rturnbull Ah, a propósito, (2*l*N)/(t*c) = 2*l*N/t/cpara que você possa salvar outros dois bytes, pule os parênteses na última parte também.
Billywob
@Billywob Novamente, bem manchado! Obrigado novamente.
rturnbull
11
@primo Obrigado novamente, ele deve ser corrigido agora.
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 o shebang como um, a entrada é obtida de stdin, com espaço separado. Se valores aleatórios não inteiros forem permitidos, isso poderá ser um pouco menor.

Tomei uma liberdade, aproximando π / 180 como 71/4068 , que é precisa dentro de 1,48 · 10 -9 .

Uso da amostra

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

Substituições matematicamente equivalentes mais ou menos

Assumindo que a coordenada x representa o ponto mais à esquerda da agulha, e não o meio, conforme especificado na descrição do problema:

89 bytes

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

O problema especifica que xdeve ser amostrado como um número inteiro aleatório. Se projetarmos o espaçamento entre linhas com um intervalo de um, isso nos deixará com valores da forma n/tcom 0 <= n < t, não necessariamente uniforme, se tnão dividir uniformemente 1e6. Supondo que uma distribuição uniforme seja aceitável:

76 bytes

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

Observe que, como randsempre será menor que um (e, portanto, truncado para zero), não é necessário no início do intervalo:

70 bytes

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

Supondo que o ângulo da agulha não precise ser um grau inteiro, mas apenas uniformemente aleatório:

59 bytes

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

Supondo que o ângulo possa ser qualquer distribuição uniforme:

52 bytes

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

A descrição acima é uma simulação matematicamente correta da agulha de Buffon. No entanto, neste ponto, acho que a maioria das pessoas concorda que isso não é realmente o que a pergunta fazia.


Realmente empurrando

Poderíamos simplesmente jogar fora metade dos casos de teste, sempre que o segundo ponto de extremidade estiver à esquerda do primeiro (em vez de trocá-los):

47 bytes

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

Observe que os valores te lsão irrelevantes para os resultados do experimento. Poderíamos simplesmente ignorá-los (assumindo implicitamente que sejam iguais):

28 bytes

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

Obviamente não-concorrente, mas você tem que admitir, ele tem uma certa elegância.

primo
fonte
4

Python 2, 141 bytes

porta descarada de rtumbull, já pulando yporque totalmente não é necessária.

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

O problema é apenas que pi já é conhecido no programa.

Aqui está (golfable) com pi desconhecido e sem funções 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,yin gé apenas para a direção.

Karl Napf
fonte
Requer from random import randint;from math import cos,pi. Falha t < l, por exemplo 1000000,1000,70000.
Primo