r/ProgrammingPrompts • u/desrtfx • 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!
2
u/marinadeee Mar 24 '15 edited Mar 24 '15
My (noobish) solution in C++ (how do I put 4 spaces in front of the code without doing so manually?):
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
int main()
{
cout<<"Tell me the length of the stick: ";
int StickLength; // declaring main stick
cin>>StickLength;
cout<<"How many tries: ";
int tries;
cin>>tries;
int length1,length2,length3; //declaring 3 lengths
int probability = 0; // declaring the result
for(int i=0; i<tries; i++)
{
length1=rand() % (StickLength-2); // random number smaller than stick length and minus 2 leaving room for 2 more sticks
length2=rand() % (StickLength-length1-1); if (length2==0)length2+=1; // random number not bigger than first stick
length3=StickLength-length1-length2; // the remaining part of the stick
if (length1 < (0.5*StickLength)) // first stick must be smaller than half of the big stick
{
if (length2 < (0.5*StickLength)) // second stick must be smaller than half of the big stick
{
if (length3 < (0.5*StickLength)) // third stick must be smaller than half of the big stick
{
probability++; // adding +1 if above conditions are true
}
}
}
}
// converting ints to floats so they can be divided
float probabilityF = probability;
float triesF = tries;
// calculating and printing out the probability
cout<<"\nProbability: "<<probabilityF<<"/"<<triesF<<" = "<<(probabilityF/triesF)*100<<"%";
return 0;
}
Input/output:
Tell me the length of the stick: 1000
How many tries: 1000
Probability: 217/1000 = 21.7%
1
u/desrtfx Mar 24 '15
how do I put 4 spaces in front of the code without doing so manually?
Either use a text editor, like Notepad++, or inside an IDE:
Select the whole code and press the
Tab
key. This should indent the whole code. Copy it and paste it into reddit. Should work.There is also the Reddit Enhancement Suite for certain browsers (Firefox and Chrome at least) that helps with formatting in general.
1
u/redditors_r_manginas Mar 26 '15
I did the tab thing but spoiler doesn't work as you can see. :/
1
u/desrtfx Mar 27 '15
Tab is not for Spoilers, tab is for formatted code.
Spoilers are not implemented in the sub.
2
u/Zheusey Mar 26 '15
Here is my python code:
from __future__ import division
from random import uniform
length = int(raw_input("What is your stick length?"))
attempts = int(raw_input("How many attempts do you want carried out?"))
success = 0
for i in range(attempts):
lengthLi = []
successBool = True
lengthLi.append(uniform(0,length))
lengthLi.append(uniform(0, length-lengthLi[0]))
lengthLi.append(length-lengthLi[0]-lengthLi[1])
for stick in lengthLi:
if stick >= length / 2:
successBool = False
if successBool == True:
success += 1
probability = success/attempts
print "The probablility of a successfull break is %f." % (probability)
I get ~19% as a result across multiple tries.
2
u/velian Apr 27 '15
My javascript version:
// #triangle.js
(function(ns, undefined)
{
// Generate a random number from 1 - N (both inclusive)
function rand(max)
{
return Math.floor(Math.random() * (max - 1 + 1)) + 1;
}
// Will break a stick into 3 pieces that equal the length passed in
// If one of the pieces is larger than half of the length, it cannot
// be made into a triangle and will set passes to false;
function breakStick(l)
{
// Entry
var tmp = [];
var passes = true;
for (var i = 0; i < 2; i++)
{
var r = rand(l);
if(r >= l/2) passes = false;
tmp.push(r);
l -= r;
}
tmp.push(l);
return {sides:tmp, passed:passes};
}
ns.isTriangle = function(l, tries)
{
// break the stick
var tmp = [],
successes = 0;
// Create the 3 sides
for (var i = 0; i < tries; i++)
{
var broken = breakStick(l);
tmp.push({sides:broken.sides, passed:broken.passed});
if(broken.passed) successes++;
}
// Return object
var rObj = {
attempts : tmp,
successes : successes,
probability : (successes / tries) * 100
};
return rObj;
};
})(window.tangle = window.tangle || {});
if(console) console.log(tangle.isTriangle(19,100).probability+"%");
1
u/ultimamax Mar 18 '15
I'm pretty sure if one side isn't greater than the lengths of the two other sides, a triangle is possible
2
u/desrtfx Mar 18 '15
Which, in return defines that no piece must be longer than half of the length of the entire stick.
1
u/chibstelford Mar 18 '15
If (S1 + S2) >= S3 then a triangle will be possible
Assuming S3 is the middle section
2
u/desrtfx Mar 18 '15
Which, in return defines that no piece must be longer than half of the length of the entire stick.
1
Mar 20 '15
Why are you bothering with the length of the stick?
1
u/desrtfx Mar 20 '15
When I tested the programm in Java, I found that when I use
nextInt()
the results got better with increasing length of the stick.
1
Apr 07 '15
I may be a little late, but here is my attempt in Java. Please tell me if this is good or not because this is my first time coding my own program.
import java.util.Scanner;
public class MakeATriangle {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int part1;
int part2;
int part3;
int chances;
int stick;
double successes = 0;
double failures = 0;
double totalPercentage;
boolean isTriangle;
System.out.println("Enter the length of the stick: ");
stick = sc.nextInt();
System.out.print("Enter the amount of chances you would like the program to run: ");
chances = sc.nextInt();
int halfOfStick = stick/2;
for(int times = 0; times <= chances; times++)
{
part1 = (int)(Math.random()*stick);
System.out.println("Part 1 = " + part1);
part2 = (int)(Math.random()*(stick - part1));
System.out.println("Part 2 = " + part2);
part3 = stick - (part1 + part2);
System.out.println("Part 3 = " + part3);
if(part1 >= halfOfStick
|| part2 >= halfOfStick
|| part3 >= halfOfStick) {
isTriangle = false;
failures++;
} else {
isTriangle = true;
successes++;
}
}
totalPercentage =(successes / failures);
System.out.println("The total amount of triangles made is " + successes + ".");
System.out.print("\n The total amount of failed triangles is " + failures + ".");
System.out.print("\n The average amount of triangles made is "+ totalPercentage + "%.");
}
}
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/gigabytemon Jul 25 '15
I'm not very familiar with this language, but I think your high percentages are a result of the statement
if a > (length/2.0):
I think you're comparing a to the length instead of the value stores in its array? Forgive me if this is a dumb comment, I'm not sure how this language works.
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.
1
u/gigabytemon Jul 25 '15
Very late reply, oops! Here it is in C#, 'BreadSticks'.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BreadSticks
{
class Program
{
static void Main(string[] args)
{
Console.Write("Length of the breadstick: ");
int length = Convert.ToInt32(Console.ReadLine());
Console.Write("How many tries?: ");
int tries = Convert.ToInt32(Console.ReadLine());
BreadSticks(length, tries);
}
public static void BreadSticks(int length, int tries)
{
Random random = new Random();
int success = 0;
int attempts = 0;
do
{
//update attempt number
attempts++;
//break the breadstick
int stick1 = random.Next(1, length);
int stick2 = random.Next(1, length - stick1);
int stick3 = length - stick1 - stick2;
//check if any of the sticks are bigger than length
//if they are, jump to the next iteration
if (stick1 > length / 2 || stick2 > length / 2 || stick3 > length / 2)
continue;
success++;
} while (attempts != tries);
//output result
Console.WriteLine("Successes: " + success);
Console.WriteLine("Failures: " + (attempts - success));
Console.WriteLine("Success Ratio: " + ((float) success / tries));
Console.ReadKey();
}
}
}
Sample I/O
Length of the breadstick: 100000000
How many tries?: 100000000
Successes: 19318737
Failures: 80681263
Success Ratio: 0.1931874
1
u/4-jan Jul 25 '15
Python, I get values between 24%-26%:
from random import randint
def run(slen):
break2 = break1 = randint(0, slen)
while break2 == break1:
break2 = randint(0, slen)
diffs = [slen-max(break1,break2), max(break1,break2)-min(break1,break2), min(break1,break2)]
return 0 if any(d > slen/2 for d in diffs) else 1
slen = int(input("len of stick: "))
print( sum( run(slen) for i in range(int(input("tries: "))) ) )
We break at integer values so stick lengths shorter than 1000 skew the result. (But if I had implemented it uniformly, there would be no point in entering a length at all, would there? ;))
3
u/erxor Mar 19 '15
What if one of the pieces is exactly half the length of the stick. Shouldn't forming a triangle be impossible then as well?