How i used 18 lines of R code to crack the Triangle Challenge

I recently came across a question that required logic and coding skills to solve. It went a little something like this:

Let there be a stick of length 1. Pick 2 points uniformly at random along the stick, and break the stick at those points. What is the probability of the three resulting pieces being able to form a triangle?

Interesting i thought. I do enjoy these types of challenges, and had fun trying to solve this problem. It took me a while to understand that the longest side (or one of the longest sides in the case of an isosceles triangle)  had to be smaller than the sum of the 2 smaller sides. In pseudo code a triangle would be possible IF:

Length of longest side < sum of other 2 sides, which is true IF

Length of longest side < 0.5 (half the length of the stick)

When i saw (in my mind’s eye) me breaking a stick in half and folding it so that both pieces overlap, it became obvious that i needed one of the pieces to be longer and then break that piece into 2 pieces of any length to form a would-be triangle. As a side note, i have been hoping to create my first gif for a while and this might be a useful one to animate a stick being broken into half, folded over and then one half growing in length and then breaking into 2 and forming a triangle.

I turned to the statistical computing language R to solve my problem, knowing i could randomly draw values from a uniform distribution with the runif() function.

The function takes 3 arguments, namely;

  • n – for number of observations (mandatory)
  • min – for minimum value to be drawn from the distribution (optional, with default of 0)
  • max – for maximum value to be drawn from the distribution (optional, with default of 1)

With 18 lines of uncommented code, i was able to generate 1 million random observations for each of the 2 random points on the stick between 0 and 1 and test the condition for forming a triangle. In other words test that the longest side is < 0.5. This took just over 1min, with most of the delay coming from line 15 where i sort each of the n number of rows. I ran the simulation 10, 100, 1k, 10k, 100k and 1m times (ie. the value for n) and noticed the higher n was the more the formula in line 31, which is the probability of forming a triangle, would converge to 25%.

My R code is below:

t1 = Sys.time()
# define lower and upper bounds for the stick
lb = 0
ub = 1
# randomly generate sides from a uniform distribution
n = 1000000
# randomly generate n points from a uniform distribution
# ran1 will be a vector of n random values for point 1 on the stick
ran1 = runif(n, lb, ub)
# ran2 will be a vector of n random values for point 2 on the stick
ran2 = runif(n, lb, ub)
# randpts will be our matrix of n point 1 and n point 2
randpts = cbind(ran1, ran2)
# now to sort each row so that point 1 is lower down the stick than point 2
randpts = t(apply(randpts, 1, sort))
# every triangle has 3 sides, so
# side 1 length = value of point 1
side1 = randpts[,1]
# side 2 length = distance between point 1 and point 2
side2 = randpts[,2] - randpts[,1]
# side 3 length = distance between point 2 and max size of stick of length 1
side3 = 1 - randpts[,2]
# add the 3 sides and make sure each observation of the sum of the sides equals 1
sumsides = side1 + side2 + side3
any(sumsides != 1)
# create a matrix of 1,000 rows and 3 columns for the 3 sides
tripts = t(rbind(side1, side2, side3))
# compute the max side of each observation
max = apply(tripts, 1, max)
# what proportion of observations meets the criteria for the formation of a triangle
length(which(max < 0.5) == TRUE) / length(max)

t2 = Sys.time()
difftime(t2,t1)

I tried sampling 1 billion observations, which worked for ran1 but i ran out of memory for ran2. Apparently my PC reached its total allocation of 8143Mb and i need to see help (memory size)…

Only way to learn is to hack.

Happy hacking!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s