'12BALL.BAS ... solves The 12 Ball Problem in QuickBASIC 'Copyright 1991 by Charles Graham, POB 58634, St. Louis, MO 63158 'All rights reserved ' '-----------------------The 12 Ball Problem-------------------------- 'You have a balance scale and 12 balls that look and feel identical. 'Eleven of the balls are the same weight. One of the balls is 'slightly heavier or lighter -- you don't know which -- than the 'other 11. Using only the balance scale and only for 3 weighings, you 'must determine which is the odd ball, and whether it is lighter or 'heavier. '-------------------------------------------------------------------- ' '-----------------------The logical solution------------------------- 'The 1st weighing is always 1 2 3 4 against 5 6 7 8. If they 'balance, you know that balls 1-8 are equal and the odd ball must be 'in 9-12. If they don't balance, you know that balls 9-12 are 'equal, and you know that either the light ball must be on the side 'that goes up, or the heavy ball must be on the side that goes down. ' 'The 2nd weighing depends upon the results of the 1st weighing. 'If the 1st weighing was equal, you'd now weigh 3 of the suspect 'balls (9-12) against 3 of the known equal balls (1-8); for example, 'weigh 9 10 11 on the left against 1 2 3 on the right. If the left 'side went down, we'd know that the odd ball was in 9 10 11 and that 'it was heavier. If the left side went up, we'd know that the odd 'ball was in 9 10 11 and that it was lighter. If both sides 'balanced, we'd know that the odd ball was ball 12, but we wouldn't 'know if it was lighter or heavier. ' 'If the 1st weighing wasn't equal, you'd now weigh (on the left) 3 'of the balls originally on the left side in the 1st weighing, plus '1 of the balls originally on the right side in the 1st weighing, 'against (on the right) 3 of the known equal balls, plus the lone 'ball that was originally on the left in the 1st weighing but wasn't 'included on the left in the 2nd weighing. For example, weigh 1 2 3 '8 against 9 10 11 4. ' 'If they balanced, you'd know that the odd ball was one of 5 6 7, 'and you'd know if it was lighter or heavier based on the outcome of 'the 1st weighing. ' 'If they didn't balance, there would be several possibilities. If 'the left side went in the same direction that it did on the 1st 'weighing, you'd know that the odd ball was in 1 2 3, and you'd know 'that it was lighter or heavier based on the results of the 1st 'weighing. If the left side went in the opposite direction from 'that which it went on the 1st weighing, you'd know that the odd 'ball was 8 or 4, and was lighter or heavier based on which 'direction it went in both the 1st and 2nd weighings. ' 'The 3rd weighing depends upon the results of the 1st 2 weighings. 'By the time you get here, one of three possible conditions will 'exist: (1) you will know which is the odd ball but will not know 'if it's lighter or heavier, (2) you will know that the odd ball is 'one of two balls and know that if it's one of them, it's lighter, 'but if it's the other one, it's heavier, or (3) you will know that 'the odd ball is one of three balls and also know whether it's 'lighter or heavier. ' 'In either of the 1st two cases, weigh the odd ball or (one of the 'two suspects) against a ball known to be equal. In the 3rd case, 'weigh two of the three suspect balls against each other. '-------------------------------------------------------------------- ' '---------------------The QuickBASIC solution------------------------ DIM ball(12), attribute$(12) 'Set up 12 balls and attributes RANDOMIZE TIMER 'Seed the RND function ' begin: ' FOR x = 1 TO 12 'Give each ball an initial ball(x) = 1 ' weight of 1 and an initial attribute$(x) = " equal" ' attribute of "equal" NEXT x ' oddball = INT(RND * 12) + 1 'Pick the odd ball randomly IF RND < .5 THEN 'Pick the odd ball's weight: oddweight = .9 ' a little less ELSE ' or oddweight = 1.1 ' a little more END IF ' than the others ball(oddball) = oddweight 'Give the odd ball its odd weight COLOR 7, 0 'White on black CLS 'Clear the screen COLOR 15, 1 'Bright white on blue PRINT "QuickBASIC solves the 12 ball problem"'Whadda we doin' here? PRINT 'Skip a line COLOR 15, 1 'Bright white on blue PRINT "Procedure: "'Title for displaying weighings COLOR 14, 0 'Bright yellow on black GOSUB firstweigh 'Weigh 'em once GOSUB secondweigh 'Weigh 'em twice GOSUB thirdweigh 'Weigh 'em thrice PRINT 'Skip a line COLOR 15, 1 'Bright white on blue PRINT "Results: "'Title for displaying weights ' and attributes COLOR 14, 0 'Bright green on black PRINT "Ball", "Weight", "Attribute" 'Print column headings FOR x = 1 TO 12 'Print the ball numbers, IF ball(x) = 1 THEN ' their weights and attributes. COLOR 11, 0 ' Use light cyan for all but ELSE ' the odd ball. COLOR 12, 0 ' Use light red for it. END IF ' PRINT USING "###"; x; ' PRINT , ' PRINT USING " #.#"; ball(x); ' LOCATE , 30 ' IF attribute$(x) = " equal" THEN ' COLOR 11, 0 ' ELSE ' COLOR 12, 0 ' END IF ' PRINT attribute$(x) ' NEXT x ' COLOR 15, 1 'Bright red on blue PRINT 'Skip a line PRINT "ESCape ends -- any other key repeats."; 'Whadda we do now? a$ = "" 'Initialize a$ to null WHILE a$ = "" 'While a$ is null a$ = INKEY$ ' Try to capture a key press WEND ' as long as a$ is null IF a$ = CHR$(27) THEN 'ESCape pressed? COLOR 7, 0 ' White on black CLS ' Clear the screen END ' T-T-That's all folks! ELSE 'Some other key? GOTO begin ' Crank 'er up again END IF ' ' firstweigh: ' lside$ = "1 2 3 4" 'Set display for left side rside$ = "5 6 7 8" 'Set display for right side 'Next line: do sides balance? IF ball(1) + ball(2) + ball(3) + ball(4) = ball(5) + ball(6) + ball(7) + ball(8) THEN FOR x = 9 TO 12 'Set attribute for balls attribute$(x) = "unequal" ' 9 through 12 to unequal NEXT x ' firstresult = 1 'Capture result operator$ = " = " 'Set display for operator ELSE 'Next line: left side heavier? IF ball(1) + ball(2) + ball(3) + ball(4) > ball(5) + ball(6) + ball(7) + ball(8) THEN FOR x = 1 TO 4 'Set attribute for balls attribute$(x) = "heavier" ' 1 through 4 to heavier NEXT x ' FOR x = 5 TO 8 'Set attribute for balls attribute$(x) = "lighter" ' 5 through 8 to lighter NEXT x ' operator$ = " > " 'Set display for operator ELSE 'OK. Right side is heavier. FOR x = 1 TO 4 'Set attribute for balls attribute$(x) = "lighter" ' 1 through 4 to lighter NEXT x ' FOR x = 5 TO 8 'Set attribute for balls attribute$(x) = "heavier" ' 5 through 8 to heavier NEXT x ' operator$ = " < " 'Set display for operator END IF ' firstresult = 2 'Capture result END IF ' 'Next line: display 1st weighing PRINT "1st weighing is " + lside$ + operator$ + rside$ RETURN ' ' secondweigh: ' IF firstresult = 1 THEN 'If odd ball is 9, 10, 11 or 12 lside$ = "9 10 11" ' Set display for left side rside$ = "1 2 3" ' Set display for right side ' Next line: are they equal? IF ball(9) + ball(10) + ball(11) = ball(1) + ball(2) + ball(3) THEN FOR x = 9 TO 11 ' Set attribute for balls 9 - 11 attribute$(x) = " equal" ' NEXT x ' secondresult = 1 ' Capture result operator$ = " = " ' Set display for operator ELSE ' If 9 - 11 <> 1 - 3 ' Next line: left side heavier? IF ball(9) + ball(10) + ball(11) > ball(1) + ball(2) + ball(3) THEN FOR x = 9 TO 11 ' Set attribute for balls 9 - 11 attribute$(x) = "heavier" ' NEXT x ' operator$ = " > " ' Set display for operator ELSE ' Right side heavier FOR x = 9 TO 11 ' Set attribute for balls 9 - 11 attribute$(x) = "lighter" ' NEXT x ' operator$ = " < " ' Set display for operator END IF ' secondresult = 3 ' Capture result attribute$(12) = " equal" ' Set attribute for ball 12 END IF ' ELSE 'If odd ball is in 1 - 8 lside$ = "1 2 3 8" ' Set display for left side rside$ = "9 10 11 4" ' Set display for right side ' Next line: 1 2 3 8 = 9 10 11 4? IF ball(1) + ball(2) + ball(3) + ball(8) = ball(9) + ball(10) + ball(11) + ball(4) THEN FOR x = 1 TO 4 ' Set attribute for balls 1 - 4 attribute$(x) = " equal" ' NEXT x ' attribute$(8) = " equal" ' Set attribute for ball 8 secondresult = 3 ' Capture result operator$ = " = " ' Set display for operator ELSE ' 1 2 3 8 <> 9 10 11 4 FOR x = 5 TO 7 ' Set attribute for balls 5 - 7 attribute$(x) = " equal" ' NEXT x ' ' Next line: 1 2 3 8 > 9 10 11 4? IF ball(1) + ball(2) + ball(3) + ball(8) > ball(9) + ball(10) + ball(11) + ball(4) THEN IF attribute$(8) = "heavier" THEN ' Do we know ball 8 is heavier? FOR x = 1 TO 3 ' Set attribute for balls 1 - 3 attribute$(x) = " equal"' NEXT x ' secondresult = 2 ' Capture result ELSE ' Ball 8 is not heavier attribute$(4) = " equal" ' Set attribute for ball 4 attribute$(8) = " equal" ' Set attribute for ball 8 secondresult = 3 ' Capture result END IF ' operator$ = " > " ' Set display for operator ELSE ' 1 2 3 8 < 9 10 11 4 IF attribute$(8) = "heavier" THEN ' Do we know ball 8 is heavier? attribute$(4) = " equal" ' Set attribute for ball 4 attribute$(8) = " equal" ' Set attribute for ball 8 secondresult = 3 ' Capture result ELSE ' Ball 8 is not heavier FOR x = 1 TO 3 ' Set attribute for balls 1 - 3 attribute$(x) = " equal"' NEXT x ' secondresult = 2 ' Capture result END IF ' operator$ = " < " ' Set display for operator END IF ' END IF ' END IF ' 'Next line: display 2nd weighing PRINT "2nd weighing is " + lside$ + operator$ + rside$ RETURN ' ' thirdweigh: ' IF secondresult = 1 THEN '9 10 11 = 1 2 3? FOR x = 1 TO 12 ' Find the odd ball and one IF attribute$(x) = "unequal" THEN ' that's not odd odd = x ' ELSE ' notodd = x ' END IF ' NEXT x ' lside$ = RIGHT$(STR$(odd), LEN(STR$(odd)) - 1)'Set display for left side rside$ = RIGHT$(STR$(notodd), LEN(STR$(notodd)) - 1)'Set display right " IF ball(odd) > ball(notodd) THEN ' Odd ball heavier? attribute$(odd) = "heavier" ' Set attribute for odd ball operator$ = " > " ' Set display for operator ELSE ' Odd ball lighter? attribute$(odd) = "lighter" ' Set attribute for odd ball operator$ = " < " ' Set display for operator END IF ' ELSE ' IF secondresult = 2 THEN ' 1 2 3 8 <> 9 10 11 4? odd1 = 0 ' Initialize 2 possibilities odd2 = 0 ' FOR x = 1 TO 12 ' Find the 2 possible odd balls, IF attribute$(x) <> " equal" THEN ' IF odd1 = 0 THEN ' odd1 = x ' ELSE ' odd2 = x ' END IF ' ELSE ' notodd = x ' and one that isn't END IF ' NEXT x ' rside$ = RIGHT$(STR$(notodd), LEN(STR$(notodd)) - 1)'Set Rside display IF ball(odd1) = ball(notodd) THEN ' If the 1st possible odd ball attribute$(odd1) = " equal" ' isn't odd, note it lside$ = RIGHT$(STR$(odd1), LEN(STR$(odd1)) - 1)'Set Lside display ELSE ' If the 2nd possible odd ball attribute$(odd2) = " equal" ' isn't odd, note it lside$ = RIGHT$(STR$(odd2), LEN(STR$(odd2)) - 1)'Set Lside display END IF ' operator$ = " = " ' Set display for operator ELSE ' You've narrowed it down to 3 ' possibilities and you know ' whether the odd ball is heavier ' or lighter odd1 = 0 ' Initialize 3 possibilities odd2 = 0 ' odd3 = 0 ' FOR x = 1 TO 12 ' Find the 3 possible odd balls, IF attribute$(x) <> " equal" THEN ' IF odd1 = 0 THEN ' odd1 = x ' ELSE ' IF odd2 = 0 THEN ' odd2 = x ' ELSE ' odd3 = x ' END IF ' END IF ' ELSE ' notodd = x ' and one that isn't END IF ' NEXT x ' lside$ = RIGHT$(STR$(odd1), LEN(STR$(odd1)) - 1)'Set display for Lside rside$ = RIGHT$(STR$(odd2), LEN(STR$(odd2)) - 1)'Set display for Rside IF ball(odd1) = ball(odd2) THEN ' If the 1st and 2nd possibili- attribute$(odd1) = " equal" ' ties aren't odd, note it attribute$(odd2) = " equal" ' operator$ = " = " ' Set display for operator ELSE ' IF ball(odd1) > ball(odd2) THEN ' If odd1 is heavier than odd2 IF attribute$(odd1) = "heavier" THEN 'and it's supposed to be, attribute$(odd2) = " equal"' mark odd2 as equal ELSE ' else attribute$(odd1) = " equal"' mark odd1 as equal END IF ' operator$ = " > " ' Set display for operator ELSE ' IF attribute$(odd1) = "lighter" THEN 'If odd 1 is lighter than attribute$(odd2) = " equal"' odd2 and it's supposed to be, ELSE ' mark odd2 as equal, else attribute$(odd1) = " equal"' mark odd1 as equal END IF ' operator$ = " < " ' Set display for operator END IF ' attribute$(odd3) = " equal" ' Set attribute of remaining ' not-odd possibility END IF ' END IF ' END IF ' IF lside$ = "12" THEN 'Adjust spacing for display spacer$ = "" ' ELSE ' spacer$ = " " ' END IF ' 'Next line: display 3rd weighing PRINT "3rd weighing is " + spacer$ + lside$ + operator$ + rside$ RETURN 'T-T-That's all folks