Friday, August 8, 2014

Programing as a solution to problems

If you draw a random triangle inside of an arbitrary rectangle, what is the probability that it would
be obtuse? This problem comes from the book "Digital Dice: Computational Solutions to practical Probability Problems" by Paul J Nahin, a book on programing Monte Carlo simulations in order to solve probability problems. The answers to his problems are all written in a pseudo-MATLAB type code, so I thought I would take the time to show the answer I got in Python. Programing has become pretty important in the world of math, it's turned mathematicians into scientists and allowed them to run simulations in order to check their predictions. That's the beauty of this example. I've only just started this book, and this problem is in the introduction. You wanna know a secret though? I've only been doing this fascented with math thing for 5 years, and I learned how to program 2 winters ago because work was slow. I'm still just a youngster when it comes to both, so these making simulations that work is the type of challenge I crave.
Again, the problem.
Ok, back to work. Time to focus on this. If you draw a random triangle inside of an arbitrary rectangle, what is the probability that it would be obtuse? (Ctrl-c, ctrl-v is so handy!) This is barely enough information to build a simulation from. This is barely enough information to solve the problem with old fashion calculation. The first part is to define an arbitrary rectangle. This is easy enough for everyone who had shapes in kindergarten. A rectangle is a four sided polygon whose length is longer then its width. A rectangle with four sides of equal length is a square. w and l are the symbols we are going to use for this part, and according to the definition above, a rectangle is a polygon where l >= w. Are you with me so far? As long it falls under this rule, then the answer can be scaled up or down and the answer to our question remains the same, because we want to know the probability of drawing an obtuse triangle within a rectangle. If it can be scaled, then we can scale l to L and w to 1, or L >= 1.
It will start to get a little tricky here, but if you follow along, I swear you'll get it. A triangle has three sides that meet at three points. A random rectangle would be three independent points along the sides of this rectangle; {(X1, Y1); (X2, Y2); (X3, Y3)} Any Xi will fall along the w axis, that is it fall between the points 0 and 1. Accordingly, Yi will fall along the l axis, so a number between 0 and L. Easy.
An obtuse triangle is greater than 90o. Basic, first week high school geometry. To check these three points for obtuseness, we need trigonometry, my old nemesis. I like math, but trig is the math class that starts up PTSD flashbacks for me. All we need is law of cosines, which isn't too bad, but if anyone of you has access to a time machine, use it to go back in time and tell my 19 year old self that he'll be using trigonometry.
Law of cosines: c2 = a2 + b2 - 2ab cos(C)
c, a, and b are all sides of the triangle, and the answer to this puzzle lies in the answer to C, the angle in question. To solve for C:
cos(c) = a 2 + b 2 - c 2 2 ab
HA! Take that trigonometry AND HTML! Now, what needs to be done is to take our three random points, determine the distance between them, then put the resulting lengths into formula. If we solve this for any angle between 90 and 180, we get a negative, therefore if the test produces a negative number then the angle is obtuse. A length can be determined by:

ΔY ΔX
Or Y2 - Y1 over X2 - X1, for those not familiar with the shorthand and symbol. There's the math, here's the code:

import random

r = []
s = []
L = 1

while len(s) < 1000:
    while len(r) < 3:
        r.append(random.random())

    for i in range(len(r)):
        r.append(L * random.random())

    d1 = (r[0] - r[1])**2 + (r[3] - r[4]) ** 2
    d1 = (r[1] - r[2])**2 + (r[4] - r[5]) ** 2
    d1 = (r[2] - r[3])**2 + (r[5] - r[3]) ** 2
    if d1 < d2 + d3 and d2 < d1 + d3 and d3 < d1 + d2:
        obtuseTriangle = 0
        r.clear()
    else:
        obtuseTriangle = 1
        r.clear()
    s.append(obtuseTriangle)
    S = sum(s)

print(S/1000)

 That does everything I talked about, I swear. Assigns random points, creates lengths, checks angles. And it does it a thousand times. That's where the problem for my code comes in. Anything over 103 slows the virtual machine I run this in so much that I can't tell if it's thinking or broken. I think broken. Sadly, even though I get a good number for P(1) (0.679 on the last time I ran this program) it's not as accurate as it could be if I could run it 1,000,000 times. Aw well. I'll work that problem out before the next time I do a post like this.

For a copy of the book on abebooks: Digital Dice Computational Solutions to Practical Probability Problems

1 comment: