Weigh Balls to Find Which One is Heavy or Light

Suppose you have 12 balls and a balance scale. You are informed that exactly one ball is either too light or too heavy. In as few weighings as possible, find which ball is the heavy (or light) one.

This focus of this program is on displaying the logic alternatives.

Let  A = {1..4}  B = {5..8}  C = {9..12}
  Case 1 : A < B   ==>   {1..4} light or {5..8} heavy.
  Let  D = {1, 2, 5}  E = {3, 4, 6}  F = {7, 8}
    Case 1.1 : D < E   ==>   {1, 2} light or {6} heavy.
      Case 1.1.1 : 1 < 2   ==>   1 light.
      Case 1.1.2 : 1 = 2   ==>   6 heavy.
      Case 1.1.3 : 1 > 2   ==>   2 light.

Weigh.c - source file

   1: #include <stdio.h>
   2: #include <stdlib.h>
   3: #include <string.h>
   4: 
   5: #define INDENT 4
   6: 
   7: static void stillsame (int nballs, int depth, char a,
   8: 		char *s, int lowequal);
   9: static void compare (int nballs, int depth, char a, char *s,
  10: 		int lowlight, int numlight, int lowheavy, int numheavy);
  11: 
  12: static FILE *out;
  13: 
  14: static void printset (int z, int nz)
  15: {
  16: 	if (nz == 1) fprintf (out, "{%d}", z);
  17: 	else if (nz == 2) fprintf (out, "{%d, %d}", z, z+1);
  18: 	else fprintf (out, "{%d..%d}", z, z+nz-1);
  19: } /* End of printset */
  20: 
  21: 
  22: static void printrange (int z, int nz)
  23: {
  24: 	if (nz == 1) fprintf (out, "%d", z);
  25: 	else if (nz == 2) fprintf (out, "%d, %d", z, z+1);
  26: 	else fprintf (out, "%d..%d", z, z+nz-1);
  27: } /* End of printrange */
  28: 
  29: 
  30: static void prtcase (int depth, char *s, char a, char sign,
  31: 			int l, int nl, int h, int nh)
  32: {
  33: 	fprintf (out, "\n%*cCase %s : %c %c %c   ==>   ",
  34: 			depth, ' ', s, a, sign, a+1);
  35: 	if (nh == 0)
  36: 	{
  37: 		if (nl == 1) fprintf (out, "%d", l);
  38: 		else printset (l, nl);
  39: 		fprintf (out, " light.\n");
  40: 	}
  41: 	else if (nl == 0)
  42: 	{
  43: 		if (nh == 1) fprintf (out, "%d", h);
  44: 		else printset (h, nh);
  45: 		fprintf (out, " heavy.\n");
  46: 	}
  47: 	else
  48: 	{
  49: 		printset (l, nl);
  50: 		fprintf (out, " light or ");
  51: 		printset (h, nh);
  52: 		fprintf (out, " heavy.\n");
  53: 	}
  54: } /* End of prtcase */
  55: 
  56: 
  57: static void let (char x, int depth, int a, int na,
  58: 			int b, int nb, int c, int nc)
  59: {
  60: 	fprintf (out, "\n%*cLet  %c = ", depth, ' ', x);
  61: 	printset (a, na);
  62: 	fprintf (out, "  %c = ", x+1);
  63: 	printset (b, nb);
  64: 	if (nc > 0)
  65: 	{
  66: 		fprintf (out, "  %c = ", x+2);
  67: 		printset (c, nc);
  68: 	}
  69: 	fprintf (out, "\n");
  70: } /* End of let */
  71: 
  72: 
  73: static void printsets (int x, int nx, int y, int ny)
  74: {
  75: 	if (nx == 0) printrange (y, ny);
  76: 	else if (ny == 0) printrange (x, nx);
  77: 	else
  78: 	{
  79: 		if (x < y)
  80: 		{
  81: 			printrange (x, nx);
  82: 			fprintf (out, ", ");
  83: 			printrange (y, ny);
  84: 		}
  85: 		else
  86: 		{
  87: 			printrange (y, ny);
  88: 			fprintf (out, ", ");
  89: 			printrange (x, nx);
  90: 		}
  91: 	}
  92: } /* End of printsets */
  93: 
  94: 
  95: /*recursive*/ static void stillsame (int nballs, int depth, char a,
  96: 							char *s, int lowequal)
  97: {
  98: 	int		size;
  99: 	int		len, n;
 100: 	
 101: 	if (lowequal == nballs)
 102: 	{
 103: 		fprintf (out, "\n%*cCase %s.1 : %d < 1   ==>   %d light.\n",
 104: 				depth, ' ', s, lowequal, lowequal);
 105: 		fprintf (out, "%*cCase %s.2 : %d = 1   ==>   All balls are equal.\n",
 106: 				depth, ' ', s, lowequal);
 107: 		fprintf (out, "%*cCase %s.3 : %d > 1   ==>   %d heavy.\n",
 108: 				depth, ' ', s, lowequal, lowequal);
 109: 		return;
 110: 	}
 111: 	
 112: 	n = (nballs - lowequal) / 3;
 113: 	size = nballs-lowequal+1 - n;
 114: 	
 115: 	let (a, depth, 1, size, lowequal, size, lowequal+size, n);
 116: 	
 117: 	len = strlen (s);
 118: 	strcat (s, ".1");
 119: 	
 120: 	prtcase (depth, s, a, '<', 1, 0, lowequal, size);
 121: 	compare (nballs, depth+INDENT, (char)(a+3), s, 1, 0, lowequal, size);
 122: 	
 123: 	s[len+1] = '2';
 124: 	fprintf (out, "\n%*cCase %s : %c = %c   ==>   ", depth, ' ', s, a, a+1);
 125: 	
 126: 	if (n > 0)
 127: 	{
 128: 		printset (lowequal+size, n);
 129: 		fprintf (out, " unknown.\n");
 130: 		stillsame (nballs, depth+INDENT, (char)(a+3), s, lowequal+size);	/* recurse */
 131: 	}
 132: 	else
 133: 	{
 134: 		fprintf (out, "All balls are equal.\n");
 135: 	}
 136: 	
 137: 	s[len+1] = '3';
 138: 	prtcase (depth, s, a, '>', lowequal, size, 1, 0);
 139: 	compare (nballs, depth+INDENT, (char)(a+3), s, lowequal, size, 1, 0);
 140: 	
 141: 	s[len] = '\0';
 142: } /* End of stillsame */
 143: 
 144: 
 145: /*recursive*/ static void compare (int nballs, int depth, char a, char *s,
 146: 		int lowlight, int numlight, int lowheavy, int numheavy)
 147: {
 148: 	int		tot;
 149: 	int		third;
 150: 	int		len;
 151: 	int		fromlight, fromheavy;
 152: 	int		x, y;
 153: 	
 154: 	tot = numlight + numheavy;
 155: 	if (tot <= 1) return;
 156: 	third = (tot+1) / 3;
 157: 	
 158: 	len = strlen (s);
 159: 	strcat (s, ".1");
 160: 	
 161: 	if (tot <= 3)
 162: 	{
 163: 		if (numheavy > 1)
 164: 		{
 165: 			x = lowheavy;
 166: 			y = lowheavy + 1;
 167: 		}
 168: 		else
 169: 		{
 170: 			x = lowlight;
 171: 			y = (numlight==1 ? nballs : lowlight+1);
 172: 		}
 173: 		
 174: 		fprintf (out, "\n%*cCase %s : %d < %d   ==>   ", depth, ' ', s, x, y);
 175: 		if (numlight >= numheavy)
 176: 		{
 177: 			fprintf (out, "%d light.\n", lowlight);
 178: 		}
 179: 		else
 180: 		{
 181: 			fprintf (out, "%d heavy,\n", lowheavy+1);
 182: 		}
 183: 		
 184: 		s[len+1] = '2';
 185: 		if (tot != 2 || (numheavy != 0 && numlight != 0))
 186: 		{
 187: 			fprintf (out, "%*cCase %s : %d = %d   ==>   ", depth, ' ', s, x, y);
 188: 			switch (numheavy)
 189: 			{
 190: 				case 0 : fprintf (out, "%d light.\n", lowlight+2);	break;
 191: 				case 1 : fprintf (out, "%d heavy.\n", lowheavy);	break;
 192: 				case 2 : fprintf (out, "%d light.\n", lowlight);	break;
 193: 				case 3 : fprintf (out, "%d heavy.\n", lowheavy+2);	break;
 194: 			}
 195: 			s[len+1] = '3';
 196: 		}
 197: 		
 198: 		if (numlight != 1 || numheavy != 1)
 199: 		{
 200: 			fprintf (out, "%*cCase %s : %d > %d   ==>   ", depth, ' ', s, x, y);
 201: 			if (numheavy > numlight)
 202: 			{
 203: 				fprintf (out, "%d heavy.\n", lowheavy);
 204: 			}
 205: 			else
 206: 			{
 207: 				fprintf (out, "%d light.\n", lowlight+1);
 208: 			}
 209: 		}
 210: 	}
 211: 	else	/* tot > 3 */
 212: 	{
 213: 		if (numlight >= numheavy)
 214: 		{
 215: 			if (numlight >= 2*third) fromlight = third;
 216: 			else fromlight = numlight / 2;
 217: 			fromheavy = third - fromlight;
 218: 		}
 219: 		else
 220: 		{
 221: 			if (numheavy >= 2*third) fromheavy = third;
 222: 			else fromheavy = numheavy / 2;
 223: 			fromlight = third - fromheavy;
 224: 		}
 225: 		
 226: 		fprintf (out, "\n%*cLet  %c = {", depth, ' ', a);
 227: 		printsets (lowlight, fromlight, lowheavy, fromheavy);
 228: 		fprintf (out, "}  %c = {", a+1);
 229: 		printsets (lowlight+fromlight, fromlight,
 230: 				lowheavy+fromheavy, fromheavy);
 231: 		fprintf (out, "}  %c = {", a+2);
 232: 		printsets (lowlight+2*fromlight, numlight-2*fromlight,
 233: 				lowheavy+2*fromheavy, numheavy-2*fromheavy);
 234: 		fprintf (out, "}\n");
 235: 		
 236: 		prtcase (depth, s, a, '<', lowlight, fromlight,
 237: 				lowheavy+fromheavy, fromheavy);
 238: 		compare (nballs, depth+INDENT, (char)(a+3), s, lowlight, fromlight,
 239: 				lowheavy+fromheavy, fromheavy);	/* recurse */
 240: 				
 241: 		s[len+1] = '2';
 242: 		prtcase (depth, s, a, '=', lowlight+2*fromlight,
 243: 				numlight-2*fromlight, lowheavy+2*fromheavy,
 244: 				numheavy-2*fromheavy);
 245: 		compare (nballs, depth+INDENT, (char)(a+3), s, lowlight+2*fromlight,
 246: 				numlight-2*fromlight, lowheavy+2*fromheavy,
 247: 				numheavy-2*fromheavy);	/* recurse */
 248: 		
 249: 		s[len+1] = '3';
 250: 		prtcase (depth, s, a, '>', lowlight+fromlight,
 251: 				fromlight, lowheavy, fromheavy);
 252: 		compare (nballs, depth+INDENT, (char)(a+3), s, lowlight+fromlight,
 253: 				fromlight, lowheavy, fromheavy);	/* recurse */
 254: 	}
 255: 	
 256: 	s[len] = '\0';
 257: } /* End of compare */
 258: 
 259: 
 260: int main()
 261: {
 262: 	int		n, nballs;
 263: 	char	s[1000];
 264: 	
 265: 	printf ("\nEnter number of balls (0 to quit) -->");
 266: 	scanf ("%d", &nballs);
 267: 	if (nballs < 1) exit(0);
 268: 
 269: 	out = fopen ("weigh.out", "w");
 270: 	if (!out)
 271: 	{
 272: 		fprintf (stderr, "\nUnable to write to weigh.out\n");
 273: 		exit (0);
 274: 	}
 275: 	
 276: 	fprintf (out, "\n======================================\n\n");
 277: 	fprintf (out, "Number of balls is %d.\n", nballs);
 278: 		
 279: 	if (nballs == 1)
 280: 	{
 281: 		fprintf (out, "\n%*cCannot weigh just one ball.\n", INDENT, ' ');
 282: 		exit(1);
 283: 	}
 284: 		
 285: 	if (nballs == 2)
 286: 	{
 287: 		fprintf (out, "\n%*cCase 1 : 1 < 2   ==>   1 light and 2 heavy.\n",
 288: 					INDENT, ' ');
 289: 		fprintf (out, "%*cCase 2 : 1 = 2   ==>   Both 1 and 2 are equal.\n",
 290: 					INDENT, ' ');
 291: 		fprintf (out, "%*cCase 3 : 1 > 2   ==>   2 light and 1 heavy.\n",
 292: 					INDENT, ' ');
 293: 		exit(0);
 294: 	}
 295: 		
 296: 	/* nballs > 2 */
 297: 	n = (nballs+2) / 3;
 298: 	let ('A', INDENT, 1, n, n+1, n, 2*n+1, nballs-2*n);
 299: 	
 300: 	strcpy (s, "1");
 301: 	prtcase (INDENT, s, 'A', '<', 1, n, n+1, n);
 302: 	compare (nballs, 2*INDENT, 'D', s, 1, n, n+1, n);
 303: 	
 304: 	fprintf (out, "\n");
 305: 	if (2*n < nballs)
 306: 	{
 307: 		strcpy (s, "2");
 308: 		fprintf (out, "%*cCase 2 : A = B   ==>   ", INDENT, ' ');
 309: 		printset (2*n+1, nballs-2*n);
 310: 		fprintf (out, " unknown.\n");
 311: 		stillsame (nballs, 2*INDENT, 'D', s, 2*n+1);
 312: 	}
 313: 	else
 314: 	{
 315: 		fprintf (out, "Case 2 : A = B   ==>   All balls are equal.\n");
 316: 	}
 317: 	
 318: 	strcpy (s, "3");
 319: 	prtcase (INDENT, s, 'A', '>', n+1, n, 1, n);
 320: 	compare (nballs, 2*INDENT, 'D', s, n+1, n, 1, n);
 321: 
 322: 	fclose (out);
 323: 	fprintf (stderr, "\nFinished writing to weigh.out\n");
 324: 
 325: 	return 0;
 326: } /* End of main */
 327: 

Weigh.out - Sample output

   1: 
   2: ======================================
   3: 
   4: Number of balls is 12.
   5: 
   6:     Let  A = {1..4}  B = {5..8}  C = {9..12}
   7: 
   8:     Case 1 : A < B   ==>   {1..4} light or {5..8} heavy.
   9: 
  10:         Let  D = {1, 2, 5}  E = {3, 4, 6}  F = {7, 8}
  11: 
  12:         Case 1.1 : D < E   ==>   {1, 2} light or {6} heavy.
  13: 
  14:             Case 1.1.1 : 1 < 2   ==>   1 light.
  15:             Case 1.1.2 : 1 = 2   ==>   6 heavy.
  16:             Case 1.1.3 : 1 > 2   ==>   2 light.
  17: 
  18:         Case 1.2 : D = E   ==>   {7, 8} heavy.
  19: 
  20:             Case 1.2.1 : 7 < 8   ==>   8 heavy,
  21:             Case 1.2.2 : 7 > 8   ==>   7 heavy.
  22: 
  23:         Case 1.3 : D > E   ==>   {3, 4} light or {5} heavy.
  24: 
  25:             Case 1.3.1 : 3 < 4   ==>   3 light.
  26:             Case 1.3.2 : 3 = 4   ==>   5 heavy.
  27:             Case 1.3.3 : 3 > 4   ==>   4 light.
  28: 
  29:     Case 2 : A = B   ==>   {9..12} unknown.
  30: 
  31:         Let  D = {1..3}  E = {9..11}  F = {12}
  32: 
  33:         Case 2.1 : D < E   ==>   {9..11} heavy.
  34: 
  35:             Case 2.1.1 : 9 < 10   ==>   10 heavy,
  36:             Case 2.1.2 : 9 = 10   ==>   11 heavy.
  37:             Case 2.1.3 : 9 > 10   ==>   9 heavy.
  38: 
  39:         Case 2.2 : D = E   ==>   {12} unknown.
  40: 
  41:             Case 2.2.1 : 12 < 1   ==>   12 light.
  42:             Case 2.2.2 : 12 = 1   ==>   All balls are equal.
  43:             Case 2.2.3 : 12 > 1   ==>   12 heavy.
  44: 
  45:         Case 2.3 : D > E   ==>   {9..11} light.
  46: 
  47:             Case 2.3.1 : 9 < 10   ==>   9 light.
  48:             Case 2.3.2 : 9 = 10   ==>   11 light.
  49:             Case 2.3.3 : 9 > 10   ==>   10 light.
  50: 
  51:     Case 3 : A > B   ==>   {5..8} light or {1..4} heavy.
  52: 
  53:         Let  D = {1, 5, 6}  E = {2, 7, 8}  F = {3, 4}
  54: 
  55:         Case 3.1 : D < E   ==>   {5, 6} light or {2} heavy.
  56: 
  57:             Case 3.1.1 : 5 < 6   ==>   5 light.
  58:             Case 3.1.2 : 5 = 6   ==>   2 heavy.
  59:             Case 3.1.3 : 5 > 6   ==>   6 light.
  60: 
  61:         Case 3.2 : D = E   ==>   {3, 4} heavy.
  62: 
  63:             Case 3.2.1 : 3 < 4   ==>   4 heavy,
  64:             Case 3.2.2 : 3 > 4   ==>   3 heavy.
  65: 
  66:         Case 3.3 : D > E   ==>   {7, 8} light or {1} heavy.
  67: 
  68:             Case 3.3.1 : 7 < 8   ==>   7 light.
  69:             Case 3.3.2 : 7 = 8   ==>   1 heavy.
  70:             Case 3.3.3 : 7 > 8   ==>   8 light.
  71: 
Email: steve@oharasteve.com