See also: part 1, part 2 and part 3.
Today I will present Art Flexser‘s solution to this marble puzzle, as well as a corrected version of mine.
First I will correct my version of the “pulling marbles out of a bag” puzzle recently presented by Steve Ostrom. I now understand the rules to be:
- You have a bag full of the following marbles: 5 red, 4 blue, 3 white, and 3 black.
- You have four marble trays, one for each color.
- You begin by pulling a marble out of the bag and placing it in the appropriate tray.
- Repeat until one of the trays has three of the marbles for that color.
- Track which color made it to three first.
- Do this 100,000 times (for our statistics).
- At the end, there should be some number of times each color of marbles was completed before any other color, in that turn.
Losing my marbles
I rewrote my visual simulator to represent the bag of marbles (the top line of groups of four color blocks) and each tray (four more lines, one for each color).
As my simulation runs, marbles will be taken from the top row (the bag) and placed in the appropriate tray.
When a tray is full (it has three of the same color marble), the round stops, and the total “completed” count for that color is incremented.
Repeat for 100,000 iterations. The current iteration count is displayed in the top right corner of the screen.
During this process, the statistics for each tray are displayed. It looks like this:
Here is my commented and non-optimized Color BASIC program:
10 ' marble2.bas 20 ' 30 ' INITIALIZE STATS 40 ' 50 RT=0:BT=0:WT=0:KT=0 60 CLS 70 PRINT "MARBLE BAG:" 80 ' 90 ' DO THIS 100,000 TIMES 100 ' 110 FOR TC=1 TO 10000 120 PRINT@25,TC 130 ' 140 ' DISPLAY MARBLES 150 ' 5 RED=191, 4 BLUE=175, 3 WHITE=207, 3 BLACK=128 160 ' 170 PRINT@32,STRING$(5,191);STRING$(4,175);STRING$(3,207);STRING$(3,128) 180 ' 190 ' RESET MARBLE TRAYS 200 ' 210 RL=1132:BL=RL+32:WL=RL+64:KL=RL+96 220 PRINT @96, "RED TRAY :" 230 PRINT "BLUE TRAY :" 240 PRINT "WHITE TRAY:" 250 PRINT "BLACK TRAY:" 260 ' 270 ' RESET MARBLE COUNTS 280 ' 290 RC=0:BC=0:WC=0:KC=0 300 ' 310 ' GRAB MARBLES 320 ' 330 MC=0 340 ' 350 ' RANDOM MARBLE LOCATTION 360 ' 370 ML=1024+32+RND(15)-1 380 ' 390 ' GRAB MARBLE 400 ' 410 V=PEEK(ML) 420 ' 430 ' IF MARBLE USED, TRY AGAIN 440 ' 450 IF V=0 THEN 370 460 ' 470 ' MARK MARBLE REMOVED 480 ' 490 POKE ML,0 500 ' 510 ' PUT MARBLE IN TRAY 520 ' 530 IF V=191 THEN POKE RL+RC,V:RC=RC+1:GOTO 600 540 IF V=175 THEN POKE BL+BC,V:BC=BC+1:GOTO 600 550 IF V=207 THEN POKE WL+WC,V:WC=WC+1:GOTO 600 560 IF V=128 THEN POKE KL+KC,V:KC=KC+1:GOTO 600 570 ' 580 ' CHECK FOR 3 IN A TRAY 590 ' 600 IF RC=3 THEN RT=RT+1:GOTO 680 610 IF BC=3 THEN BT=BT+1:GOTO 680 620 IF WC=3 THEN WT=WT+1:GOTO 680 630 IF KC=3 THEN KT=KT+1:GOTO 680 640 ' 650 ' NOT FULL YET, CONTINUE GRABBING MARBLES 660 ' 670 MC=MC+1:IF MC<15 THEN 370 680 ' 690 ' PRINT COUNT AND PERCENTAGE 700 ' 710 PRINT@256,"RED :";RT,RT/TC 720 PRINT "BLUE :";BT,BT/TC 730 PRINT "WHITE:";WT,WT/TC 740 PRINT "BLACK:";KT,KT/TC 750 ' 760 ' REPEAT 770 ' 780 NEXT 790 ' 800 ' REPORT RESULTS 810 ' 820 PRINT "TIME:";TIMER/60 830 END 840 ' 850 ' VARIABLES 860 ' 870 ' TC = TOTAL COUNT (RUNS) 880 ' 890 ' RL/BL/WL/KL = DEST. TRAY LOCATIONS 900 ' 910 ' TOTAL TIMES EACH TRAY FILLED: 920 ' RT = RED TOTAL 930 ' BT = BLUE TOTAL 940 ' WT = WHITE TOTAL 950 ' KT = BLACK TOTAL 960 ' 970 ' RC/BC/WC/KC = CURRENT TRAY COUNT 980 ' 990 ' MC = MARBLES PULLED FROM BAG 1000 ' 1010 ' ML = MARBLE LOCATION (PEEK) 1020 ' 1030 ' V = VALUE OF MARBLE PEEKED
It’s going to take a long time for the CoCo to do 100,000 iterations, but luckily I heard from a guy who did it a faster way…
Art Flexser
ADOS creator Art Flexser wrote in with his take on this puzzle. (And I tried really hard not to fan-boy over getting an e-mail from him. His RS-DOS replacement is legendary.)
Hi, Al. I found Steve Ostrom’s marbles problem of interest, and thought it would make an interesting programming exercise for myself. (I haven’t written a program in ages.)
I have described my understanding of the problem in the program’s initial comments. I hope it corresponds to Steve’s intent and to your (revised) interpretation.
I wrote the program under QBASIC-64 so that numerical results would be obtainable much faster. (Downloadable for free from www.qb64.net). I had to change two lines (lines 92 and 140) for CoCo compatibility since the RND function is defined differently on the two platforms. See the comments for the necessary changes. The listing I’ve attached is the QBASIC version. The output is most readable in 80-column mode.
I did not obtain the same probabilities as Steve did. I got .514, .281, .102, and .102 (based on a million trials) for red, blue, white, and black. I have no idea why there is a discrepancy. Perhaps you or Steve (whose email address I don’t have) could send me a copy of his program so I could investigate. Or, maybe your own revised program will be ready soon, so we can see if your results agree with me, with Steve, or with neither.
The speed difference between the two platforms is pretty amazing. The program runs about 200,000 times faster under QBASIC-64 on my 3.4 GHz Windows 10 (64-bit) PC than under CoCo Basic. So, I set NP, (in line 95) the number of trials between results printouts, for a million under QBASIC and five for the CoCo (simulated by the Mocha java emulator) and got results about every 2 seconds either way.
Best,
Art
Fantastic! Let’s take a look at what he submitted:
10 'A BAG CONTAINS 15 MARBLES, CONSISTING OF 5 RED, 4 BLUE, 3 WHITE AND 3 BLACK
20 'A TRIAL IS DEFINED AS DRAWING ONE MARBLE AT A TIME OUT OF THE BAG, UNTIL
30 'THREE MARBLES OF THE SAME COLOR HAVE BEEN DRAWN, NOT NECESSARILY IN A ROW.
40 'DRAWING IS DONE WITHOUT REPLACEMENT.
50 'THE PROGRAM REPRESENTS THE 4 COLORS BY THE DIGITS 1-4.
60 'WE WISH TO FIND THE PROBABILITIES THAT EACH OF THE 4 COLORS "WINS" A TRIAL BY
70 'SIMULATION OF A LARGE NUMBER OF TRIALS.
75 'THE MARBLES REMAINING IN THE BAG ARE REPRESENTED BY A STRING VARIABLE
80 M0$ = "111112222333444" 'INITIAL STATE OF THE BAG, WITH 15 MARBLES
90 CT(1) = 0: CT(2) = 0: CT(3) = 0: CT(4) = 0 'INITIALIZE WIN COUNTS FOR THE 4 COLORS
92 RANDOMIZE TIMER 'SEED RANDOM NUMBER GENERATOR USING TIMER VALUE
93 'FOR COCO, CHANGE ABOVE LINE TO X=RND(-TIMER) *
95 NP = 1000000
100 FOR I = 1 TO NP 'PRINT RESULTS AFTER A NUMBER NP OF TRIALS HAS OCCURRED
110 'INITIALIZE COUNTS OF HOW MANY MARBLES OF EACH COLOR HAVE BEEN DRAWN THIS TRIAL
120 R(1) = 0: R(2) = 0: R(3) = 0: R(4) = 0
130 MB$ = M0$: NM = LEN(MB$) 'NM = NUMBER OF MARBLES REMAINING IN BAG
135 'GRAB A RANDOM MARBLE FROM THE BAG
140 P = INT(RND * NM) + 1
145 'FOR COCO, CHANGE ABOVE LINE TO P=RND(NM) *
150 'P IS THE RANDOM POSITION NUMBER SELECTED WITHIN THE BAG CONTENTS STRING
160 CL$ = MID$(MB$, P, 1) 'CL$, THE COLOR OF THE SELECTED MARBLE, IS "1", "2", "3", OR "4"
170 C = VAL(CL$) 'CONVERT TO AN INTEGER FROM 1-4
180 R(C) = R(C) + 1 'R(C) IS HOW MANY MARBLES OF THIS COLOR HAVE BEEN DRAWN SO FAR
190 'IF WE HAVE 3 MARBLES DRAWN OF THIS COLOR, INCREMENT WINS COUNTER FOR THIS COLOR
200 'AND BEGIN A NEW TRIAL
210 IF R(C) = 3 THEN CT(C) = CT(C) + 1: GOTO 260
220 'ADJUST BAG'S CONTENT TO REFLECT THE CHOSEN MARBLE'S REMOVAL
230 MB$ = LEFT$(MB$, P - 1) + RIGHT$(MB$, NM - P)
240 NM = NM - 1
250 GOTO 140 'CONTINUE TRIAL, DRAW ANOTHER MARBLE RANDOMLY
260 NEXT I
270 'CALCULATE PROBABILITIES AND PRINT RESULTS SO FAR
280 TT = CT(1) + CT(2) + CT(3) + CT(4) 'TOTAL NUMBER OF TRIALS SO FAR
290 PR(1) = CT(1) / TT: PR(2) = CT(2) / TT: PR(3) = CT(3) / TT: PR(4) = CT(4) / TT
295 PRINT " RED BLUE WHITE BLACK TOTAL TRIALS"
300 PRINT CT(1); CT(2); CT(3); CT(4); " "; TT; " FREQUENCIES"
310 PRINT PR(1); PR(2); PR(3); PR(4); " PROBABILITIES": PRINT
320 GOTO 100
His approach uses a string containing characters representing each of the four marble types. I copied it in QB64 to try it out. I was immediately impressed that, even though it looks like an old-school DOS text program, it allowed me to resize the window so I could see the entire program at once:
With a press of F5, the program is compiled into an executable, and then ran:
It was blasting through a million iterations every few seconds, and was instantly showing results: Red at 51%, blue at 28%, white at 10% and black at 10%.
While this was running, I decided to see if it would run in PC-BASIC as well:
I let it run for awhile, but it didn’t print anything. It seems PC-BASIC is much slower than QB64, which is likely because QB64 is some kind of compiler that turns the BASIC into an executable. When I worked for Radio Shack (1988-1991 or so), I remember benchmarking a CoCo 3 BASIC against some Tandy 1000 BASICs and the CoCo was faster than everything but the 286 in turbo mode. Maybe that is the type of machine PC-BASIC is trying to simulate ;-)
And, of course, since his code supports it, I wanted to see it running on a (virtual) CoCo. I made the three changes his comments suggest (for how RND works, and reducing the number of iterations to 5 per cycle instead of a million):
Per his note, the CoCo version is updated every 5 times through, while the QB64 version is doing a million.
After a bit, we see the pattern develop:
Red is at 51%, blue at 26%, white at 11% and black at 10%. Even with far fewer iterations (5 versus a million each time through), it is already very close to the QB64 version that reported red at 51%, blue 28%, white 10% and black 10%.
Meanwhile, an hour later, my CoCo version completed 100,000 iterations:
My final results were red at 50%, blue at 29%, white at 10% and black 10%. This is very close to Art’s 51%/28%/10%/10% results, but it does not match the results from Steve’s simulation:
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
Is this just a difference in the patterns of the psuedo random number generator? I’ll share my results on Facebook and see what Steve says.
NOTE: The time value displayed at the end is meaningless. I forgot to take into consideration that the TIMER value rolls over at 65535 (16-bits). At a tick every 60th of a second (on an American NTSC CoCo using the 60Hz screen interrupt), that’s about 18 minutes. This took well longer than that, so it rolled over several times. I’ll have to add a bit more code so it can properly estimate the total time taken.
Until next time…