The marbles in a bag puzzle in Color BASIC – part 3

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:

Marble bag simulator, version 2.

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:

QB64 with Art Flexser’s marble puzzle code.

With a press of F5, the program is compiled into an executable, and then ran:

Art Flexser’s marble puzzle code in operation.

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:

Art Flexser’s marble program running under PC-BASIC.

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):

Art Flexser’s marble simulation code on a virtual CoCo.

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:

Art Flexser’s marble simulator has produced results.

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:

Marble bag simulator, version 2 after 100000 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…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.