9
1
Goal
Generate (N
) random line segments of uniform length (l
), check if they cross the equidistant (t
) parallel lines.
Simulation
What are we simulating? Buffon's needle. Smooth out the sand in your sandbox, draw a set of equally spaced parallel lines (call the distance in between t
). Take a straight stick of length l
and drop it N
times into the sandbox. Let the number of times it crossed a line be c
. Then Pi = (2 * l * n) / (t * c)
!
How are we simulating this?
- Take input
N,t,l
- With
N, t, l
all being positive integers - Do the following
N
times:- Generate a uniformly random integer coordinate
x,y
- With
1 <= x, y <= 10^6
x,y
is the center of a line segment of lengthl
- Generate a uniformly random integer
a
- With
1 <= a <= 180
- Let
P
be the point where the line segment would cross the x-axis - Then
a
is the angle(x,y), P, (inf,0)
- Generate a uniformly random integer coordinate
- Count the number,
c
, of line segments that cross the linex = i*t
for any integeri
- Return
(2 * l * N) / (t * c)
Specification
- Input
- Flexible, take input in any of the standard ways (eg function parameter,STDIN) and in any standard format (eg String, Binary)
- Output
- Flexible, give output in any of the standard ways (eg return, print)
- White space, trailing and leading white space is acceptable
- Accuracy, please provide at least 4 decimal places of accuracy (ie
3.1416
)
- Scoring
- Shortest code wins!
Test Cases
Your output may not line up with these, because of random chance. But on average, you should get about this much accuracy for the given value of 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
These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are nine challenges total.
I thought you already did number 1? – Conor O'Brien – 2016-10-15T01:33:02.533
1
@ConorO'Brien I zero-index it XD
– NonlinearFruit – 2016-10-15T01:45:27.977the problem with this is, in languages without complex numbers, you need to turn the number 0..180 into 0..pi, which rather defeats the purpose of the buffon`s needle experiment. – Level River St – 2016-10-15T06:25:56.700
@NonlinearFruit can the direction
a
be also created by another method, if it is uniform? (thinking of a 2D Gauss Bubble) – Karl Napf – 2016-10-15T07:16:08.767@LevelRiverSt You could generate random values for sin ( [-1,1] then calculate cos ) and use that, if your language is unable to use the prescribed method. – NonlinearFruit – 2016-10-15T14:55:24.873
@KarlNapf The calculation for the direction of the segment is flexible. Anything that gives the segment uniform probability of facing any direction will work (as long as it is at least as granular as the given method). – NonlinearFruit – 2016-10-15T14:59:58.400
Can a fraction be output? – LegionMammal978 – 2016-10-15T16:06:50.467
@LegionMammal978 Fractions are acceptable – NonlinearFruit – 2016-10-15T20:06:44.697
1Can it be assumed that
t > l
? Two solutions below make this assumption, which simplifies the check for intersection quite a bit. – primo – 2016-10-18T10:38:42.007@primo Good catch.
t
could be equal to1
. "all being positive integers" – NonlinearFruit – 2016-10-19T02:59:51.577