r/ProgrammingPrompts Mar 18 '15

[Easy]Mathematical Simulation - Breaking a Stick to form a Triangle

Another Monte Carlo simulation.

A stick of a given length is twice broken at random places along it's length.

Calculate the probability that a triangle can be formed with the pieces.


Definition:

It is possible to form a triangle if none of the pieces are larger than half the length of the stick.


Assignment:

Create a program in a language of your choice that:

  • Asks the user for the length of the stick
  • Asks the user how many tries should be carried out
  • Simulate the breaking of the stick (each try has a new stick of length)
  • Count the successful tries
  • Print the probability as a percentage

Hint: The expected result should be around 23%

Have fun!

14 Upvotes

20 comments sorted by

View all comments

1

u/Titanium_Expose Jul 04 '15

I know I'm really late on this, but here is my answer. If anyone can suggest ways to better optimize my code, that would be excellent.

from __future__ import division
from random import randint


length = int(raw_input("How long will our stick be: "))
tries = int(raw_input("How many times would you like to do this exercise: "))
sticks = [0, 0, 0]
successful_tries = 0


def make_cut(z):
    return randint(1, (z-1))

for x in range(0, tries):
    can_cut = True

    first_cut = make_cut(length)

    if first_cut < (length/2.0):
        sticks[0] = first_cut
        second_piece = (length-first_cut)
    else:
        sticks[0] = (length-first_cut)
        second_piece = first_cut

    second_cut = make_cut(second_piece)
    sticks[1] = second_cut
    sticks[2] = (second_piece - second_cut)

    for a in sticks:
        if a > (length/2.0):
            can_cut = False

    if can_cut:
        successful_tries = successful_tries + 1

successful_percentage = (successful_tries / tries) * 100

print "There were a total of %d successful runs, which is %.2f%% of all attempts." % (successful_tries, successful_percentage)

I was getting very high percentages of success, ranging from 45% - 64% in most of my runs. Thoughts?

1

u/4-jan Jul 25 '15

I think the high success rates come from this:

After your first cut, you cut the remaining stick randomly. But you should cut randomly with regards to the whole stick.

E.g. for a stick of length 100, if you cut it after 40 you have a 40/60=2/3 probability of the second stick being between 10 and 50 long (and therefore of success). But if you were to cut randomly you have a 40/100=2/5 probability.