Projects , Lessons , Ideas

Main Navigation Menu

Breadcrumbs

Example using random sticks to make a triangle

« Back

Problem

You have a sack of 100 sticks sized 1cm to 100cm long.
If you choose three sticks at random from the sack, what are the chances that the combination you choose will form a right triangle? For example, if you pull the 3cm, 4cm, and 5cm sticks from the bag, it will form a right triangle. If you pull the 1cm, the 10cm, and the 100cm sticks out, it won't even form a triangle. 


  |\
	  | \
	  |  \ 
	  ----

Object oriented programming as a simulator

The simpliest way to solve this problem is to create a collection of 100 numbers, take three out and see if they solve the Pythagoras theorem (a*a + b*b = c*c). Mathemations may scoff at this idea, however it will allow use to test later solutions.

An interval is created by sending #to: to a number. For example: 
	1 to: 30
will create an interval from one to thirty. In the problem, we have a bag which contains one stick of each size, since we can't choose the same item from the bag more than once, we shouldn't be able to select the same item from the collection more than once. Create an Interval and see what happens when you try to remove an item:
	| anInterval |
		anInterval := 1 to: 100.
		anInterval remove: 3
This should bring up a debugger with the message "Error: elements cannot be removed from an Interval."

The Interval can be converted into an OrderedCollection using #asOrderedCollection.
| aCollection |
aCollection := (1 to: 100) asOrderedCollection.
aCollection remove: 3
We actually want to remove a particular index, not a particular item, browse the OrderedCollection methods and look for the method #removeAt:.

To choose a random number we can use the #atRandom, contributed by David N. Smith. Since the method OrderedCollection>>removeAt: returns the item that it removes as the return value, we simply need to use that to set our stick variable.

	| bagOfSticks stickOne stickTwo stickThree |
		bagOfSticks := (1 to: 100) asOrderedCollection.
		stickOne := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickTwo := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickThree := bagOfSticks removeAt: (bagOfSticks size atRandom).

Now we just need to determine which stick is the longest, and which are the two shortest. We could write several if statements to determine which stick is longer and which is shorter, however we can use another collection - the SortedCollection - to do this for us. At this point, we have a pretty good chunk of code, so it is time to test it. The following will create a collection of number, choose three, and sort them, then print them in the Transcript. You can open a transcript with:
	Transcript open
Run the following code and see what appears in the transcript:

	| bagOfSticks stickOne stickTwo stickThree sortedSticks |
		bagOfSticks := (1 to: 100) asOrderedCollection.
		stickOne := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickTwo := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickThree := bagOfSticks removeAt: (bagOfSticks size atRandom).
		sortedSticks := SortedCollection with: stickOne with: stickTwo with: stickThree.
		"Test your list of sticks"
		Transcript show: 'The sorted sticks should each be unique and in order: '; 
			show: sortedSticks;
			cr.

If you run it over and over, you should get different results each time.

Next is to apply the mathematical theorem. If you browse the Number class (superclass of Integer), you'll notice the method #squared in the mathematical functions group.

	| bagOfSticks stickOne stickTwo stickThree sortedSticks |
		bagOfSticks := (1 to: 100) asOrderedCollection.
		stickOne := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickTwo := bagOfSticks removeAt: (bagOfSticks size atRandom).
		stickThree := bagOfSticks removeAt: (bagOfSticks size atRandom).
		sortedSticks := SortedCollection with: stickOne with: stickTwo with: stickThree.
		sortedSticks third squared = (sortedSticks second squared + sortedSticks first squared) 
				ifTrue: [Transcript show: sortedSticks; show: ' is a right triangle.'; cr] 
				ifFalse: [Transcript show: sortedSticks; show: ' is not a right triangle.'; cr].

We may have to run the code several times to see if it will find a right triangle.

Running the code manually can be time consuming. By using the #timesRepeat:, we can run the code over and over, and collect the results:

	| rightTriangleCount totalTries |
		totalTries := 10000.
		rightTriangleCount := 0.
		totalTries timesRepeat: [| bagOfSticks stickOne stickTwo stickThree sortedSticks |
			bagOfSticks := (1 to: 100) asOrderedCollection.
			stickOne := bagOfSticks removeAt: (bagOfSticks size atRandom).
			stickTwo := bagOfSticks removeAt: (bagOfSticks size atRandom).
			stickThree := bagOfSticks removeAt: (bagOfSticks size atRandom).
			sortedSticks := SortedCollection with: stickOne with: stickTwo with: stickThree.
			sortedSticks third squared = (sortedSticks second squared + sortedSticks first squared) 
					ifTrue: [rightTriangleCount := rightTriangleCount + 1]].
		Transcript show: 'Out of ',totalTries asStringWithCommas, ' attempts, a right triangle was created ',  (rightTriangleCount isOrAreStringWith: 'time').

This code may take a few seconds to run. If you change totalTries to 100 thousand, it will take a few minutes to run. If you change it to 1 million, you may as well go to lunch while it runs.

How many combinations

Looking at our problem again, what are the combinations that produce a right triangle?
Break this problem down into a smaller problem, what are the numbers that sum up to 25? The method #do: is used to loop over items in a collection, and takes a single argument block. The method #select: also takes a single argument block, but its argument should evaluate to true or false. The return value of #select: is a collection of all items that match. Try the following in your workspace:
	| interval sum |
		interval := (1 to: 100).
		sum := 5.
		interval do: [:e | Transcript show: (interval select: [:num | num squared + e squared = sum squared]) printString]
This should print something like the following in the transcript:
#()#()#(4)#(3)#()#()#()#()#()#()...
This is close to what we want, but not quite. If x squared + b squared = sum squared, then there isn't another number which can be added to b squared and will equal sum squared, so #select: isn't quite what what we want. The method #detect:ifNone: will return the first item in a collection that matches, and if none match, then it will execute the ifNone block. Try the following:
	#(1 2 3) detect: [:number | number = 3] ifNone: [Transcript show: 'I did not find anything']
		#(1 2 3) detect: [:number | number > 3] ifNone: []
If you inspect the results of the second example, note that the return value of [] is nil.
Trying again, we can use:
	| interval |
		interval := (1 to: 100).
		interval do: [:sum | 
			interval do: [:e || matchesE | 
				matchesE := interval detect: [:num | num squared + e squared = sum squared] ifNone: [].
				matchesE ifNotNil: 
					[Transcript show: e printString, ' squared + ', matchesE printString, ' squared = ', sum printString, ' squared'; cr]]].
Running this generates:
3 squared + 4 squared = 5 squared
	4 squared + 3 squared = 5 squared
	6 squared + 8 squared = 10 squared
	8 squared + 6 squared = 10 squared
	5 squared + 12 squared = 13 squared
	12 squared + 5 squared = 13 squared
	9 squared + 12 squared = 15 squared
	12 squared + 9 squared = 15 squared
	   ...
This is close to what we want, but has a lot of duplicates. One way to remove them is to set matchesE to values greater than e. Another way to simplify the code is to not even create an interval:
	1 to: 100 do: [:sum | 
			1 to: sum do: [:e || matchesE | 
				matchesE := (e to: sum) detect: [:num | num squared + e squared = sum squared] ifNone: [].
				matchesE ifNotNil: 
					[Transcript show: e printString, ' squared + ', matchesE printString, ' squared = ', sum printString, ' squared'; cr]]].

Next steps