See also: part 1, part 2 and part 3.
NOTE: I got the objective of the marble puzzle wrong, but I’d already written this version. I’ll post a follow-up with the actual puzzle later.
Recently in the Color Computer Facebook group, Steve Ostrom wrote a BASIC program to solve a probability puzzle. He wrote:
You have 15 marbles in a bag. 5 are red, 4 are blue, 3 are white and 3 are black. You pull out one marble at a time, without putting it back, until you have 3 marbles of the same color. What are the odds of getting 3 red marbles, of getting 3 blue marbles, of getting 3 white marbles or of getting 3 black marbles.Steve Ostrom (March 21, 2020 on the CoCo Facebook Group)
I mentioned this in my article about the BASIC RND command recently, but did not address the actual puzzle Steve presented. Today, I will try.
If my understanding of the question is correct, you have a bag with 15 marbles:
- 5 red marbles
- 4 blue marbles
- 3 white marbles
- 3 black marbles
You pull three marbles out of the bag. What are the odds that all three are red, blue, white or black? Since there are more red marbles than any other, grabbing three red marbles must be more likely than any other color. Since there are more blue marbles than white or black marbles, grabbing three blue ones must be more likely than white or black. And, with white and black marbles having the same count, they should have the same probability.
There’s probably a very simple math formula to solve this, but it’s more more fun to write a program to actually try it!
Simulating a Bag of Marbles
I remember making some card programs in BASIC as a teenage. You could create an array representing all the cards, and then shuffle them using the RND random function. For example:
10 REM shuffle.bas 20 REM CREATE ALPHABET ARRAY 30 DIM A$(25) 40 FOR A=0 TO 24 50 A$(A)=CHR$(65+A) 60 NEXT 70 REM DISPLAY ARRAY 80 GOSUB 190 90 REM SWAP EACH ONE RANDOMLY 100 FOR A=0 TO 25 110 S=RND(26)-1 120 SV$=A$(S) 130 A$(S)=A$(A) 140 A$(A)=SV$ 150 NEXT 160 REM DISPLAY ARRAY 170 GOSUB 200 180 END 190 REM DISPLAY ARRAY 200 FOR A=0 TO 25 210 PRINT A$(A); 220 NEXT 230 PRINT 240 RETURN
Starting at line 30, this program creates a string array of 26 items, each containing a letter of the alphabet:
In line 80, it calls a subroutine that will PRINT out the array.
Starting at line 100, it shuffles the array by going through each entry and swapping it with a randomly selected entry.
In line 170, it calls the subroutine to display the array again.
My first thought was to create an array of marbles and then shuffle them. The program would then randomly pull one out of the virtual bag (array) to see what it got.
But then I realized that would be silly and wasteful since we are dealing with randomly selecting an item.
For cards, you need to shuffle them because you get the “next out” card (the one on the top of the deck, unless you are cheating and bottom dealing). But, if you fan open a deck and say “pick a card, any card” the deck doesn’t have to be shuffled since you are randomly picking one. For a magic trick, though, we want the deck to be shuffled because if they were all in order, one could easily look at the remaining cards and determine which one was missing.
But I digress…
If we used a non-sorted array of alphabetical letters:
…and we are going to randomly select one, the order of the items in the array should not matter. We might randomly select 16, 4 and 22. Or 1, 9 and 14. Or 26, 2 and 7.
I don’t need to randomize the marbles in a marble bag at all.
With that out of the way, I next thought about a way to visualize the process of pulling random marbles out of a bag. Since we are dealing with colors, and I am doing this on a Color Computer, I thought maybe I’d use the screen and have color characters represent each of the marble colors.
10 CLS 20 REM DISPLAY MARBLES 30 REM 5 RED=191, 4 BLUE=175, 3 WHITE=207, 3 BLACK=128 40 PRINT@0,STRING$(5,191);STRING$(4,175);STRING$(3,207);STRING$(3,128)
I could then use PEEK to randomly select one of the colors on the screen. Since I need to pick three, and can’t pick the same one twice, I could use POKE to reset the one I Just picked to some value representing “already picked.”
And, to track which ones I picked, I would also POKE the value to another spot on the screen. I could then visually see the process run as a marble was “picked” from the top row (changed to a different character) and “moved” to somewhere else (the color block appearing in a new location).
Then, after picking three marbles, I could look at what I picked and see if they all matched. If they did, I could increment a counter for each color. If all three were red, I would increment a Red Count variable. If all three were black, I’d increment a Black Count variable.
Along with four individual counters (for red, blue, white and black), I’d also have a Total Count. I could get statistics by dividing the individual counts into that total. For example, if there were 100 total counts, and the Blue Count was 15, then picking three blue ones happened 15 out of 100 times – 15%.
I could then reset the marbles and do it again, and let this program run as long as it took for a pattern to emerge.
According to Steve, here is what I should expect:
I ran 100,000 iterations (took most of the night) and here are the rounded percentages I found. Red = 42.5%, blue = 27.5%, white and black are both 15.0%.Steve Ostrom
Keeping my Optimizing Color BASIC series in mind, I am going to present to you an “easy to read but slower to run” version of what I came up with. It is heavily comment, and thus heavily slowed down.
10 ' marble.bas 20 ' 30 ' INITIALIZE STATS 40 ' 50 RC=0:BC=0:WC=0:KC=0:TC=0 60 CLS 70 ' 80 ' DISPLAY MARBLES 90 ' 5 RED=191, 4 BLUE=175, 3 WHITE=207, 3 BLACK=128 100 ' 110 PRINT@0,STRING$(5,191);STRING$(4,175);STRING$(3,207);STRING$(3,128) 120 ' 130 ' GRAB THREE MARBLES 140 ' 150 FOR MD=1088 TO 1090 160 ' 170 ' RANDOM MARBLE LOCATION 180 ' 190 ML=1024+RND(15)-1 200 ' 210 ' GRAB MARBLE 220 ' 230 V=PEEK(ML) 240 ' 250 ' IF MARBLE USED, TRY AGAIN 260 ' 270 IF V=0 THEN 190 280 ' 290 ' MARK MARBLE REMOVED 300 ' 310 POKE ML,0 320 ' 330 ' PUT MARBLE IN HAND 340 ' 350 POKE MD,V 360 NEXT 370 ' 380 ' CHECK FIRST GRAB 390 ' 400 V=PEEK(1088) 410 ' 420 ' DOES IT MATCH NEXT TWO? 430 ' 440 IF V=PEEK(1089) AND V=PEEK(1090) THEN 500 450 ' 460 ' NO, START OVER 470 ' 480 GOTO 110 490 ' 500 ' ALL THREE THE SAME! 510 ' 520 ' IF RED, INC RED COUNT 530 ' 540 IF V=191 THEN RC=RC+1 550 ' 560 ' IF BLUE, INC BLUE COUNT 570 ' 580 IF V=175 THEN BC=BC+1 590 ' 600 ' IF WHITE, INC WHITE COUNT 610 ' 620 IF V=207 THEN WC=WC+1 630 ' 640 ' IF BLACK, INC BLACK COUNT 650 ' 660 IF V=128 THEN KC=KC+1 670 ' 680 ' INC TOTAL COUNT 690 ' 700 TC=TC+1 710 ' 720 ' PRINT COUNT AND PERCENTAGE 730 ' 740 PRINT @128,"RED :";RC,RC/TC 750 PRINT "BLUE :";BC,BC/TC 760 PRINT "WHITE:";WC,WC/TC 770 PRINT "BLACK:";KC,KC/TC 780 GOTO 110
When it runs, it looks like this:
The top line represents the avialable marbles in the bag. As one is chosen, I POKE it to 0, which appears as an inverted @ character.
Below are the three picked marbles. It looks like I forgot to erase the “chosen” line between cycles, so it’s showing three marbles when above only two have actually been selected. This does not impact the outcome, since I choose three, which overwrites the previous three, before looking to see if they match.
As you can see, I am quite a bit off from Steve’s 42% / 22% / 15% / 15% results. I need to let it run much longer.
Or, perhaps I just need to optimize this program and dramatically speed it up.
This sounds like a follow-up article.
Until next time…
Actually, comments slow down Basic programs very little, as they are immediately disregarded after the first character (the comment token) is recognized.
The length of the line of comments doesn’t matter, but in benchmarks, the more lines, the slower.
Did you know that a comment at the end of the line is significantly slower?
10 MN=3:REM NUMBER OF MEN
Actually, to get a random shuffle with all permutations equally likely, you have to do something like this:
FOR i:= 1 to n-1
i.e. at each step you swap a(i) with a(j) where j is a randomly chosen number between i and n inclusive.
Re-typing my original reply as I look at your code. So my way was always doing a 1-in-26 swap, all the way through, and yours only swaps with the items after it. Doesn’t that mean that, if using alphabet A-Z as an example, the first swap has a 1-in-26 chance to be Z, and if it’s not, the second has a 1-in-25 chance, and so on? With the last swap being a 50/50 chance of swapping at last two?
Pingback: The marbles in a bag puzzle in Color BASIC – part 2 | Sub-Etha Software
Pingback: The marbles in a bag puzzle in Color BASIC – part 3 | Sub-Etha Software
Pingback: Random BASIC shuffling revisited. | Sub-Etha Software