Paint Pictures from Counting Clues

Start with an empty picture with say 15 rows and 10 columns. It has 150 cells, each of which is either on or off. Now you are given clues for each row and for each column that shows how many cells are on, but it does not tell you where. You must deduce them from the clues.

Considerable effort was spent on explaining the reasoning. Take at look at the end of the output (paint.out) and see if you recognize the picture!

In column 5, cell 13 is 'off'.
In column 7, no more unknowns, so 1 is 'on'.
A small portion of column 8 is on (from 1 to 6).
In column 9, no more unknowns, so 1 is 'off'.
A small portion of column 10 is on (from 8 to 15).
A small portion of row 1 is on (from 6 to 8).
In row 1, no more unknowns, so 5 is 'on'.

Paint.c - source file

   1: #include <stdio.h>
   2: #include <stdlib.h>
   3: #include <ctype.h>
   4: #include <time.h>
   5: 
   6: 
   7: #define MAXSIZE 30
   8: 
   9: enum {UNKNOWN, OFF, ON};
  10: 
  11: static char *RC[2] = {"row", "column"};
  12: static char *Cr[2] = {"Column", "Row"};
  13: 
  14: static int getnums (FILE *inp, short *dat, int *siz)
  15: {
  16: 	char	ch;
  17: 	int		items;
  18: 	char	lin[1000];
  19: 	int		num;
  20: 	char	*pos;
  21: 	
  22: 	items = 0;
  23: 	if (fgets (lin, 999, inp) == NULL) return 0;
  24: 	pos = lin;
  25: 	while ((ch = *pos++) != '\0' && ch != '\n')
  26: 	{
  27: 		if (isspace (ch)) continue;
  28: 		if (!isdigit (ch))
  29: 		{
  30: 			fprintf (stderr, "\nInvalid counts: %s\n", pos);
  31: 			return 0;
  32: 		}
  33: 		if (isdigit (pos[0]))
  34: 		{
  35: 			num = 10*(ch-'0') + *pos-'0';
  36: 			pos++;
  37: 			if (isdigit (pos[0]))
  38: 			{
  39: 				fprintf (stderr, "\nNumbers must be 1 or 2 digits: %s\n", pos);
  40: 				return 0;
  41: 			}
  42: 		}
  43: 		else num = ch - '0';
  44: 		
  45: 		if (items >= MAXSIZE/2)
  46: 		{
  47: 			fprintf (stderr, "\nNumber of items must <= %d\n", MAXSIZE/2);
  48: 			return 0;
  49: 		}
  50: 		dat[items] = num;
  51: 		items++;
  52: 	}
  53: 	
  54: 	if (items < 1)
  55: 	{
  56: 		fprintf (stderr, "\nNumber of items must be at least one\n");
  57: 		return 0;
  58: 	}
  59: 	
  60: 	*siz = items;
  61: 	return 1;
  62: } /* End of getnums */
  63: 
  64: 
  65: static short getCell (short cells[MAXSIZE][MAXSIZE], int iscol, int row, int col)
  66: {
  67: 	if (iscol) return cells[col][row];
  68: 	else return cells[row][col];
  69: } /* End of getCell */
  70: 
  71: 
  72: static short *getCellPtr (short cells[MAXSIZE][MAXSIZE], int iscol, int row, int col)
  73: {
  74: 	if (iscol) return &(cells[col][row]);
  75: 	else return &(cells[row][col]);
  76: } /* End of getCell */
  77: 
  78: 
  79: static int changed (short cells[MAXSIZE][MAXSIZE], int row,
  80: 		int iscol, int scol, int ecol, int state)
  81: {
  82: 	short	*cellp;
  83: 	int		chg;
  84: 	int		column;
  85: 	
  86: 	chg = 0;
  87: 	for (column=scol; column<=ecol; column++)
  88: 	{
  89: 		cellp = getCellPtr (cells, iscol, row, column);
  90: 		if (*cellp == UNKNOWN)
  91: 		{
  92: 			*cellp = state;
  93: 			chg = 1;
  94: 		}
  95: 		else if (*cellp != state)
  96: 		{
  97: 			fprintf (stderr, "\nInvalid state change at %s %d, cell %d\n",
  98: 					RC[iscol], column+1, row+1);
  99: 			return 0;
 100: 		}
 101: 	}
 102: 	
 103: 	return chg;
 104: } /* End of changed */
 105: 
 106: 
 107: #define AFTER(i,j) ((j) < 0 || (i) > lateEnd[j])
 108: #define BEFORE(i,j) ((j) >= nblocks || (i) < earlyStart[j])
 109: 
 110: 
 111: /* Note : row and column will be reversed if 'iscol' */
 112: static void try (FILE *out, int row, short cells[MAXSIZE][MAXSIZE],
 113: 		int width, short blocks[MAXSIZE], short nblocks,
 114: 		short earlyStart[MAXSIZE], short lateEnd[MAXSIZE],
 115: 		int iscol, int *didanything)
 116: {
 117: 	short	cell, prevcell;
 118: 	short	early, late;
 119: 	int		i, j;
 120: 	int		length, longest;
 121: 	int		ons, ongroups, unknowns;
 122: 	int		scol, ecol;
 123: 
 124: 	/* Anything unknown in the row/column? */
 125: 	ons = 0;
 126: 	ongroups = 0;
 127: 	unknowns = 0;
 128: 	prevcell = UNKNOWN;
 129: 	for (i=0; i<width; i++)
 130: 	{
 131: 		cell = getCell (cells, iscol, row, i);
 132: 
 133: 		if (cell == UNKNOWN)
 134: 		{
 135: 			unknowns++;
 136: 		}
 137: 		else if (cell == ON)
 138: 		{
 139: 			ons++;
 140: 			if (prevcell != ON) ongroups++;
 141: 		}
 142: 		prevcell = cell;
 143: 	}
 144: 	if (unknowns == 0) return;	/* Nope */
 145: 
 146: 	length = 0;
 147: 	longest = 0;
 148: 	for (j=0; j<nblocks; j++)
 149: 	{
 150: 		length += blocks[j];
 151: 		if (blocks[j] > longest)
 152: 		{
 153: 			longest = blocks[j];
 154: 		}
 155: 	}
 156: 
 157: 	/* Too many on? */
 158: 	if (ons > length) return;
 159: 	
 160: 	/* Make sure early's are all in order, and late's too */
 161: 	for (j=1; j<nblocks; j++)
 162: 	{
 163: 		if (earlyStart[j] < earlyStart[j-1] + 2)
 164: 		{
 165: 			earlyStart[j] = earlyStart[j-1] + 2;
 166: 			*didanything = 1;
 167: 		}
 168: 		if (lateEnd[j-1] > lateEnd[j] - 2)
 169: 		{
 170: 			lateEnd[j-1] = lateEnd[j] - 2;
 171: 			*didanything = 1;
 172: 		}
 173: 	}
 174: 	
 175: 	/* Trivial case -- whole row/column */
 176: 	if (nblocks == 1 && blocks[0] == width)
 177: 	{
 178: 		if (changed (cells, row, iscol, 0, width-1, ON))
 179: 		{
 180: 			fprintf (out, "Entire %s %d is on (given).\n", RC[iscol], row+1);
 181: 			*didanything = 1;
 182: 		}
 183: 	}
 184: 	
 185: 	/* Most of the row/column is on */
 186: 	if (nblocks == 1 && blocks[0] > width/2)
 187: 	{
 188: 		if (changed (cells, row, iscol, width-blocks[0], blocks[0]-1, ON))
 189: 		{
 190: 			fprintf (out, "A large portion of %s %d is on (from %d to %d).\n",
 191: 					RC[iscol], row+1, width-blocks[0]+1, blocks[0]);
 192: 			*didanything = 1;
 193: 		}
 194: 	}
 195: 	
 196: 	/* Any long stretches in the row/column on? */
 197: 	for (j=0; j<nblocks; j++)
 198: 	{
 199: 		scol = lateEnd[j] - blocks[j] + 1;
 200: 		ecol = earlyStart[j] + blocks[j] - 1;
 201: 		if (ecol >= scol)
 202: 		{
 203: 			if (changed (cells, row, iscol, scol, ecol, ON))
 204: 			{
 205: 				fprintf (out, "A small portion of %s %d is on (from %d to %d).\n",
 206: 						RC[iscol], row+1, scol+1, ecol+1);
 207: 				*didanything = 1;
 208: 			}
 209: 		}
 210: 	}
 211: 	
 212: 	/* If the number of unknowns + ons = total length, turn 'em all on! */
 213: 	if (unknowns + ons == length)
 214: 	{
 215: 		for (i=0; i<width; i++)
 216: 		{
 217: 			if (getCell (cells, iscol, row, i) == UNKNOWN)
 218: 			{
 219: 				if (changed (cells, row, iscol, i, i, ON))
 220: 				{
 221: 					fprintf (out, "In %s %d, no more unknowns, so %d is 'on'.\n",
 222: 							RC[iscol], row+1, i+1);
 223: 					*didanything = 1;
 224: 				}
 225: 			}
 226: 		}
 227: 	}
 228: 	
 229: 	/* If the number of ons = total length, turn all unknowns off! */
 230: 	if (ons == length)
 231: 	{
 232: 		for (i=0; i<width; i++)
 233: 		{
 234: 			if (getCell (cells, iscol, row, i) == UNKNOWN)
 235: 			{
 236: 				if (changed (cells, row, iscol, i, i, OFF))
 237: 				{
 238: 					fprintf (out, "In %s %d, no more unknowns, so %d is 'off'.\n",
 239: 							RC[iscol], row+1, i+1);
 240: 					*didanything = 1;
 241: 				}
 242: 			}
 243: 		}
 244: 	}
 245: 	
 246: 	/* If all one's, put blanks next to each on cell */
 247: 	if (longest == 1)
 248: 	{
 249: 		for (i=0; i<width; i++)
 250: 		{
 251: 			if (getCell (cells, iscol, row, i) == ON)
 252: 			{
 253: 				if (i > 0 && changed (cells, row, iscol, i-1, i-1, OFF))
 254: 				{
 255: 					fprintf (out, "In %s %d, longest 'on' is 1, so %d is 'off'.\n",
 256: 							RC[iscol], row+1, i);
 257: 					*didanything = 1;
 258: 				}
 259: 				if (i+1 < width && changed (cells, row, iscol, i+1, i+1, OFF))
 260: 				{
 261: 					fprintf (out, "In %s %d, longest 'on' is 1, so %d is 'off'.\n",
 262: 							RC[iscol], row+1, i+1+1);
 263: 					*didanything = 1;
 264: 				}
 265: 			}
 266: 		}
 267: 	}
 268: 
 269: 	for (j=0; j<nblocks; j++)
 270: 	{
 271: 		early = earlyStart[j];
 272: 		late = lateEnd[j];
 273: 		
 274: 		/* If a region size perfect, set it all 'on' */
 275: 		if (late - early + 1 < blocks[j])
 276: 		{
 277: 			fprintf (stderr, "\nBig problem -- late minus early is too small\n");
 278: 			fprintf (stderr, "    %s %d, block %d, early=%d late=%d\n",
 279: 					RC[iscol], row+1, j+1, early, late);
 280: 			return;
 281: 		}
 282: 		else if (late - early + 1 == blocks[j])
 283: 		{
 284: 			if (changed (cells, row, iscol, early, late, ON))
 285: 			{
 286: 				fprintf (out, "In %s %d, block %d extends from %d to %d.\n",
 287: 						RC[iscol], row+1, j+1, early+1, late+1);
 288: 				*didanything = 1;
 289: 			}
 290: 			if (early > 0 && changed (cells, row, iscol, early-1, early-1, OFF))
 291: 			{
 292: 				fprintf (out, "In %s %d, left of block %d (%s %d) is 'off'.\n",
 293: 						RC[iscol], row+1, j+1, RC[1-iscol], early);
 294: 				*didanything = 1;
 295: 			}
 296: 			if (late < width-1 && changed (cells, row, iscol, late+1, late+1, OFF))
 297: 			{
 298: 				fprintf (out, "In %s %d, right of block %d (%s %d) is 'off'.\n",
 299: 						RC[iscol], row+1, j+1, RC[1-iscol], late+2);
 300: 				*didanything = 1;
 301: 			}
 302: 			
 303: 			/* Reduce any neightbor's sizes a little */
 304: 			if (j > 0)
 305: 			{
 306: 				if (lateEnd[j-1] > early-2)
 307: 				{
 308: 					lateEnd[j-1] = early - 2;
 309: 					*didanything = 1;
 310: 				}
 311: 			}
 312: 			if (j < nblocks-1)
 313: 			{
 314: 				if (earlyStart[j+1] < late+2)
 315: 				{
 316: 					earlyStart[j+1] = late+2;
 317: 					*didanything = 1;
 318: 				}
 319: 			}
 320: 		}
 321: 		
 322: 		/* If any 'off's inside a possible region, reduce that region */
 323: 		for (i=early; i<=late; i++)
 324: 		{
 325: 			if (getCell (cells, iscol, row, i) == OFF)
 326: 			{
 327: 				if (i - early < blocks[j])
 328: 				{
 329: 					earlyStart[j] = i + 1;
 330: 					*didanything = 1;
 331: 				}
 332: 				if (late - i < blocks[j])
 333: 				{
 334: 					lateEnd[j] = i - 1;
 335: 					*didanything = 1;
 336: 				}
 337: 			}
 338: 		}
 339: 	}
 340: 
 341: 	/* If anything is 'on' inside just one region, shorten that region */
 342: 	for (i=0; i<width; i++)
 343: 	{
 344: 		cell = getCell (cells, iscol, row, i);
 345: 		
 346: 		if (cell == ON)
 347: 		{
 348: 			ons = 1;	/* Measure size of 'on' group */
 349: 			for (j=i+1; j<width; j++)
 350: 			{
 351: 				if (getCell (cells, iscol, row, j) != ON) break;
 352: 				ons++;
 353: 			}
 354: 			for (j=0; j<nblocks; j++)
 355: 			{
 356: 				if (i >= earlyStart[j] && i <= lateEnd[j])
 357: 				{
 358: 					if ((AFTER(i,j-1) ||
 359: 							(ons > blocks[j-1] && AFTER(i,j-2))) &&
 360: 						(BEFORE(i,j+1) ||
 361: 							(ons > blocks[j+1] && BEFORE(i,j+2))))
 362: 					{
 363: 						if (earlyStart[j] < i - blocks[j] + ons)
 364: 						{
 365: 							earlyStart[j] = i - blocks[j] + ons;
 366: 							*didanything = 1;
 367: 						}
 368: 						if (lateEnd[j] > i + blocks[j] - 1)
 369: 						{
 370: 							lateEnd[j] = i + blocks[j] - 1;
 371: 							*didanything = 1;
 372: 						}
 373: 					}
 374: 				}
 375: 			}
 376: 		}
 377: 		else if (cell == UNKNOWN)
 378: 		{
 379: 			for (j=0; j<nblocks; j++)
 380: 			{
 381: 				/* In some block, maybe? */
 382: 				if (i >= earlyStart[j] && i <= lateEnd[j]) break;		/* Yes */
 383: 			}
 384: 			if (j == nblocks && changed (cells, row, iscol, i, i, OFF))	/* No */
 385: 			{
 386: 				fprintf (out, "In %s %d, cell %d is 'off'.\n",
 387: 						RC[iscol], row+1, i+1);
 388: 				*didanything = 1;
 389: 			}
 390: 		}
 391: 	}
 392: 	
 393: 	/* If exactly the right number of ongroups, and they don't overlap */
 394: 	/* then we know where each group is, approximately */
 395: 	ongroups = 0;
 396: 	i = 0;
 397: 	while (i < width)
 398: 	{
 399: 		if (getCell (cells, iscol, row, i) == ON)
 400: 		{
 401: 			if (++ongroups > nblocks) break;	/* Error! */
 402: 			i += longest;			/* Skip past this group */
 403: 		}
 404: 		else i++;
 405: 	}
 406: 	if (ongroups == nblocks)		/* Exact right number of 'on' groups */
 407: 	{
 408: 		ongroups = 0;
 409: 		i = 0;
 410: 		while (i < width)
 411: 		{
 412: 			if (getCell (cells, iscol, row, i) == ON)
 413: 			{
 414: 				if (earlyStart[ongroups] < i - blocks[ongroups] + 1)
 415: 				{
 416: 					earlyStart[ongroups] = i - blocks[ongroups] + 1;
 417: 					*didanything = 1;
 418: 				}
 419: 				i += longest;
 420: 				ongroups++;
 421: 			}
 422: 			else i++;
 423: 		}
 424: 	}
 425: 
 426: 	/* If any strech of 'on's is the same length as 'longest', */
 427: 	/* Then both neighbors must be 'off' */
 428: 	length = 0;
 429: 	for (i=0; i<width; i++)
 430: 	{
 431: 		if (getCell (cells, iscol, row, i) == ON)
 432: 		{
 433: 			length++;
 434: 			if (length == longest)
 435: 			{
 436: 				if (i - length >= 0 &&
 437: 						changed (cells, row, iscol, i-length, i-length, OFF))
 438: 				{
 439: 					fprintf (out, "In %s %d, cell %d is 'off'.\n",
 440: 							RC[iscol], row+1, i-length+1);
 441: 					*didanything = 1;
 442: 				}
 443: 				if (i + 1 < width &&
 444: 						changed (cells, row, iscol, i+1, i+1, OFF))
 445: 				{
 446: 					fprintf (out, "In %s %d, cell %d is 'off'.\n",
 447: 							RC[iscol], row+1, i+1+1);
 448: 					*didanything = 1;
 449: 				}
 450: 			}
 451: 		}
 452: 		else length = 0;
 453: 	}
 454: } /* End of try */
 455: 
 456: 
 457: static int logic (FILE *out, short cells[MAXSIZE][MAXSIZE],
 458: 		int width, int height,
 459: 		short datah[MAXSIZE], short dataw[MAXSIZE],
 460: 		short widths[MAXSIZE][MAXSIZE/2],
 461: 		short heights[MAXSIZE][MAXSIZE/2])
 462: {
 463: 	int		didanything;
 464: 	short	earlyStarth[MAXSIZE][MAXSIZE], earlyStartv[MAXSIZE][MAXSIZE];
 465: 	short	lateEndh[MAXSIZE][MAXSIZE], lateEndv[MAXSIZE][MAXSIZE];
 466: 	int		iter, j, length;
 467: 	int		row, col;
 468: 	
 469: 	for (row=0; row<height; row++)
 470: 	{
 471: 		length = 0;
 472: 		for (j=0; j<dataw[row]; j++)
 473: 		{
 474: 			earlyStarth[row][j] = length;
 475: 			length += widths[row][j] + 1;
 476: 		}
 477: 
 478: 		length = width - 1;
 479: 		for (j=dataw[row]-1; j>=0; j--)
 480: 		{
 481: 			lateEndh[row][j] = length;
 482: 			length -= widths[row][j] + 1;
 483: 		}
 484: 	}
 485: 
 486: 	for (col=0; col<width; col++)
 487: 	{
 488: 		length = 0;
 489: 		for (j=0; j<datah[col]; j++)
 490: 		{
 491: 			earlyStartv[col][j] = length;
 492: 			length += heights[col][j] + 1;
 493: 		}
 494: 		
 495: 		length = height - 1;
 496: 		for (j=datah[col]-1; j>=0; j--)
 497: 		{
 498: 			lateEndv[col][j] = length;
 499: 			length -= heights[col][j] + 1;
 500: 		}
 501: 	}
 502: 
 503: 	iter = 0;
 504: 	while (1)
 505: 	{
 506: 		didanything = 0;
 507: 		printf ("Iteration %d\n", ++iter);
 508: 		
 509: 		/* Try row rules */
 510: 		for (row=0; row<height; row++)
 511: 		{
 512: 			/* printf ("Now try row %d\n", row+1); */
 513: 			try (out, row, cells, width, widths[row], dataw[row],
 514: 					earlyStarth[row], lateEndh[row], 0, &didanything);
 515: 		}
 516: 		
 517: 		/* Try column rules */
 518: 		for (col=0; col<width; col++)
 519: 		{
 520: 			/* printf ("Now try column %d\n", col+1); */
 521: 			try (out, col, cells, height, heights[col], datah[col],
 522: 					earlyStartv[col], lateEndv[col], 1, &didanything);
 523: 		}
 524: 		
 525: 		if (!didanything) break;
 526: 	}
 527: 	
 528: 	fprintf (out, "\n");
 529: 	for (row=0; row<height; row++)
 530: 	{
 531: 		for (j=0; j<dataw[row]; j++)
 532: 		{
 533: 			fprintf (out, "Row %d, block %d (size %d) = %d to %d\n",
 534: 				row+1, j+1, widths[row][j], earlyStarth[row][j], lateEndh[row][j]);
 535: 		}
 536: 	}
 537: 
 538: 	fprintf (out, "\n");
 539: 	for (col=0; col<width; col++)
 540: 	{
 541: 		for (j=0; j<datah[col]; j++)
 542: 		{
 543: 			fprintf (out, "Column %d, block %d (size %d) = %d to %d\n",
 544: 				col+1, j+1, heights[col][j], earlyStartv[col][j], lateEndv[col][j]);
 545: 		}
 546: 	}
 547: 	
 548: 	return iter;
 549: } /* End of logic */
 550: 
 551: 
 552: int main ()
 553: {
 554: 	char	ans[132];
 555: 	short	cells[MAXSIZE][MAXSIZE];
 556: 	short	datah[MAXSIZE];
 557: 	short	dataw[MAXSIZE];
 558: 	short	heights[MAXSIZE][MAXSIZE/2];
 559: 	short	widths[MAXSIZE][MAXSIZE/2];
 560: 	int		height, width;
 561: 	int		i, j, k;
 562: 	FILE	*inp;
 563: 	int		iter;
 564: 	int		known;
 565: 	int		longestRow, longestCol;
 566: 	long	minutes;
 567: 	FILE	*out;
 568: 	char	outfile[132];
 569: 	int		quiet;
 570: 	long	seconds;
 571: 	int		siz;
 572: 	clock_t	startime;
 573: 	
 574: 	/*********************** Overhead ***********************/
 575: 	printf ("Enter data file (blank if none) -->");
 576: 	gets (ans);
 577: 	if (ans[0] == '\0' || ans[0] == '\n')
 578: 	{
 579: 		quiet = 0;
 580: 		printf ("Enter name for data file -->");
 581: 		gets (outfile);
 582: 		out = fopen (outfile, "w");
 583: 		if (!out)
 584: 		{
 585: 			fprintf (stderr, "\nUnable to write to %s\n", outfile);
 586: 			exit (0);
 587: 		}
 588: 		inp = stdin;
 589: 	}
 590: 	else
 591: 	{
 592: 		quiet = 1;
 593: 		inp = fopen (ans, "r");
 594: 		if (!inp)
 595: 		{
 596: 			fprintf (stderr, "\nUnable to read %s\n", ans);
 597: 			exit (0);
 598: 		}
 599: 	}
 600: 	
 601: 	/*********************** Get input data ***********************/
 602: 	if (!quiet) printf ("\nEnter height -->");
 603: 	fgets (ans, 131, inp);
 604: 	if (sscanf (ans, "%d", &height) < 1) height = -1;
 605: 	if (height < 2 || height > MAXSIZE)
 606: 	{
 607: 		fprintf (stderr, "\nHeight must be from 2 to %d\n", MAXSIZE);
 608: 		exit (0);
 609: 	}
 610: 	
 611: 	if (!quiet) printf ("Enter width -->");
 612: 	fgets (ans, 131, inp);
 613: 	if (sscanf (ans, "%d", &width) < 1) width = -1;
 614: 	if (width < 2 || width > MAXSIZE)
 615: 	{
 616: 		fprintf (stderr, "\nWidth must be from 2 to %d\n", MAXSIZE);
 617: 		exit (0);
 618: 	}
 619: 	
 620: 	/* Get info for each row */
 621: 	if (!quiet) printf ("\n");
 622: 	longestRow = 0;
 623: 	for (i=0; i<height; i++)
 624: 	{
 625: 		do
 626: 		{
 627: 			if (!quiet) printf ("Values for row %d -->", i+1);
 628: 		}
 629: 		while (!getnums (inp, widths[i], &siz));
 630: 		dataw[i] = siz;
 631: 		if (siz > longestRow) longestRow = siz; 
 632: 	}
 633: 	
 634: 	/* Get info for each column */
 635: 	if (!quiet) printf ("\n");
 636: 	longestCol = 0;
 637: 	for (i=0; i<width; i++)
 638: 	{
 639: 		do
 640: 		{
 641: 			if (!quiet) printf ("Values for column %d -->", i+1);
 642: 		}
 643: 		while (!getnums (inp, heights[i], &siz));
 644: 		datah[i] = siz;
 645: 		if (siz > longestCol) longestCol = siz;
 646: 	}
 647: 	
 648: 	if (quiet) fclose (inp);
 649: 	else
 650: 	{
 651: 		fprintf (out, "%d\n", height);
 652: 		fprintf (out, "%d\n", width);
 653: 		for (i=0; i<height; i++)
 654: 		{
 655: 			for (j=0; j<dataw[i]; j++)
 656: 			{
 657: 				fprintf (out, "%d ", widths[i][j]);
 658: 			}
 659: 			fprintf (out, "\n");
 660: 		}
 661: 	
 662: 		for (i=0; i<width; i++)
 663: 		{
 664: 			for (j=0; j<datah[i]; j++)
 665: 			{
 666: 				fprintf (out, "%d ", heights[i][j]);
 667: 			}
 668: 			fprintf (out, "\n");
 669: 		}
 670: 		fclose (out);
 671: 		fprintf (stderr, "\nFinished writing to %s\n", outfile);
 672: 	}
 673: 	
 674: 	/****************** Compute data matrix ******************/
 675: 	for (i=0; i<height; i++)
 676: 	{
 677: 		for (j=0; j<width; j++)
 678: 		{
 679: 			cells[i][j] = UNKNOWN;
 680: 		}
 681: 	}
 682: 	out = fopen ("paint.out", "w");
 683: 	startime = clock ();
 684: 	iter = logic (out, cells, width, height, datah, dataw, widths, heights);
 685: 	seconds = (clock() - startime) / CLOCKS_PER_SEC;
 686: 	minutes = seconds / 60;
 687: 	fprintf (out, "\n\n");
 688: 	
 689: 	
 690: 	/*********************** Print result ***********************/
 691: 	fprintf (out, "%*c", 3*longestRow+7, ' ');
 692: 	for (i=0; i<width; i++) fprintf (out, "%2d ", i+1);
 693: 	fprintf (out, "\n");
 694: 
 695: 	fprintf (out, "   +");
 696: 	for (i=0; i<3*longestRow; i++) fprintf (out, "-");
 697: 	fprintf (out, "-+-");
 698: 	for (i=0; i<3*width; i++) fprintf (out, "-");
 699: 	fprintf (out, " +\n");
 700: 	
 701: 	for (i=0; i<longestCol; i++)
 702: 	{
 703: 		fprintf (out, "   |%*c |", 3*longestRow, ' ');
 704: 		for (j=0; j<width; j++)
 705: 		{
 706: 			if (datah[j] >= longestCol-i)
 707: 			{
 708: 				fprintf (out, " %2d", heights[j][i+datah[j]-longestCol]);
 709: 			}
 710: 			else
 711: 			{
 712: 				fprintf (out, "   ");
 713: 			}
 714: 		}
 715: 		fprintf (out, "  |\n");
 716: 	}
 717: 	
 718: 	fprintf (out, "   +");
 719: 	for (i=0; i<3*longestRow; i++) fprintf (out, "-");
 720: 	fprintf (out, "-+-");
 721: 	for (i=0; i<3*width; i++) fprintf (out, "-");
 722: 	fprintf (out, " +\n");
 723: 	
 724: 	known = width * height;
 725: 	for (i=0; i<height; i++)
 726: 	{
 727: 		for (k=0; k<2; k++)
 728: 		{
 729: 			if (k == 1) fprintf (out, "%2d |", i+1);
 730: 			else fprintf (out, "   |");
 731: 			for (j=0; j<longestRow; j++)
 732: 			{
 733: 				if (k == 1 && dataw[i] >= longestRow-j)
 734: 				{
 735: 					fprintf (out, " %2d", widths[i][j+dataw[i]-longestRow]);
 736: 				}
 737: 				else
 738: 				{
 739: 					fprintf (out, "   ");
 740: 				}
 741: 			}
 742: 			fprintf (out, " | ");
 743: 			
 744: 			for (j=0; j<width; j++)
 745: 			{
 746: 				switch (cells[i][j])
 747: 				{
 748: 					case UNKNOWN :
 749: 						if (k == 1) fprintf (out, " ? ");
 750: 						else fprintf (out, "   ");
 751: 						if (k == 1) known--;
 752: 						break;
 753: 						
 754: 					case OFF :
 755: 						if (k == 1) fprintf (out, " . ");
 756: 						else fprintf (out, "   ");
 757: 						break;
 758: 					
 759: 					case ON :
 760: 						fprintf (out, "XXX");
 761: 						break;
 762: 				}
 763: 			}
 764: 			fprintf (out, " |\n");
 765: 		}
 766: 	}
 767: 
 768: 	fprintf (out, "   +");
 769: 	for (i=0; i<3*longestRow; i++) fprintf (out, "-");
 770: 	fprintf (out, "-+-");
 771: 	for (i=0; i<3*width; i++) fprintf (out, "-");
 772: 	fprintf (out, " +\n");
 773: 	
 774: 	if (known < width * height)
 775: 	{
 776: 		fprintf (out, "\n\nCompleted %d of %d cells\n", known, width*height);
 777: 	}
 778: 	fprintf (out, "Elapsed time: %ld:%2.2ld:%2.2ld  (h:mm:ss);  "
 779: 			"took %d iteration%s.\n",
 780: 			minutes/60, minutes%60, seconds%60,
 781: 			iter, (iter==1 ? "" : "s"));
 782: 	fclose (out);
 783: 
 784: 	fprintf (stderr, "\nFinished writing to paint.out\n");
 785: 	fprintf (stderr, "Completed %d of %d cells\n", known, width*height);
 786: 
 787: 	return 0;
 788: } /* End of main */

paint.in - Sample input file

   1: 15
   2: 10
   3: 4 
   4: 1 2 
   5: 1 2 
   6: 1 2 
   7: 1 2 
   8: 2 2 
   9: 1 1 
  10: 2 2 
  11: 3 3 
  12: 9 
  13: 9 
  14: 10 
  15: 1 1 1 2 
  16: 2 4 
  17: 3 4 
  18: 4 
  19: 3 2 
  20: 6 1 
  21: 11 
  22: 1 1 4 
  23: 1 4 
  24: 1 3 2 
  25: 6 4 2 
  26: 14 
  27: 8 
  28: 

paint.out - Sample output

   1: A large portion of row 10 is on (from 2 to 9).
   2: A large portion of row 11 is on (from 2 to 9).
   3: Entire row 12 is on (given).
   4: A small portion of row 14 is on (from 7 to 7).
   5: A small portion of row 15 is on (from 3 to 3).
   6: A small portion of row 15 is on (from 7 to 8).
   7: In column 2, cell 9 is 'off'.
   8: In column 2, cell 13 is 'off'.
   9: A large portion of column 4 is on (from 5 to 11).
  10: In column 5, cell 14 is 'off'.
  11: In column 5, cell 15 is 'off'.
  12: In column 6, cell 14 is 'off'.
  13: In column 6, cell 15 is 'off'.
  14: In column 7, cell 9 is 'off'.
  15: In column 7, cell 13 is 'off'.
  16: A small portion of column 8 is on (from 2 to 6).
  17: A small portion of column 8 is on (from 9 to 11).
  18: A small portion of column 8 is on (from 14 to 14).
  19: A large portion of column 9 is on (from 2 to 14).
  20: A large portion of column 10 is on (from 8 to 8).
  21: In row 2, cell 10 is 'off'.
  22: In row 2, cell 7 is 'off'.
  23: In row 3, cell 10 is 'off'.
  24: In row 3, cell 7 is 'off'.
  25: In row 4, cell 10 is 'off'.
  26: In row 4, cell 7 is 'off'.
  27: In row 5, no more unknowns, so 1 is 'off'.
  28: In row 5, no more unknowns, so 2 is 'off'.
  29: In row 5, no more unknowns, so 3 is 'off'.
  30: In row 5, no more unknowns, so 5 is 'off'.
  31: In row 5, no more unknowns, so 6 is 'off'.
  32: In row 5, no more unknowns, so 7 is 'off'.
  33: In row 5, no more unknowns, so 10 is 'off'.
  34: In row 6, cell 10 is 'off'.
  35: In row 6, cell 7 is 'off'.
  36: In row 7, no more unknowns, so 1 is 'off'.
  37: In row 7, no more unknowns, so 2 is 'off'.
  38: In row 7, no more unknowns, so 3 is 'off'.
  39: In row 7, no more unknowns, so 5 is 'off'.
  40: In row 7, no more unknowns, so 6 is 'off'.
  41: In row 7, no more unknowns, so 7 is 'off'.
  42: In row 7, no more unknowns, so 8 is 'off'.
  43: In row 7, no more unknowns, so 10 is 'off'.
  44: In row 8, cell 8 is 'off'.
  45: In row 9, cell 1 is 'off'.
  46: In column 1, cell 1 is 'off'.
  47: In column 1, cell 2 is 'off'.
  48: In column 1, cell 3 is 'off'.
  49: In column 1, cell 4 is 'off'.
  50: In column 1, cell 6 is 'off'.
  51: In column 1, cell 8 is 'off'.
  52: In column 2, block 2 extends from 14 to 15.
  53: In column 2, cell 1 is 'off'.
  54: In column 2, cell 2 is 'off'.
  55: In column 2, cell 3 is 'off'.
  56: In column 2, cell 4 is 'off'.
  57: In column 2, cell 6 is 'off'.
  58: In column 2, cell 8 is 'off'.
  59: A small portion of column 3 is on (from 8 to 12).
  60: In column 3, left of block 2 (row 14) is 'off'.
  61: In column 3, cell 1 is 'off'.
  62: In column 3, cell 2 is 'off'.
  63: In column 3, cell 3 is 'off'.
  64: In column 3, cell 4 is 'off'.
  65: In column 3, cell 6 is 'off'.
  66: In column 4, cell 1 is 'off'.
  67: In column 8, right of block 2 (row 13) is 'off'.
  68: A small portion of column 10 is on (from 8 to 12).
  69: In column 10, cell 1 is 'off'.
  70: In row 6, cell 6 is 'off'.
  71: In row 8, no more unknowns, so 5 is 'off'.
  72: In row 8, no more unknowns, so 6 is 'off'.
  73: In row 8, no more unknowns, so 7 is 'off'.
  74: A small portion of row 9 is on (from 4 to 5).
  75: In row 9, cell 6 is 'off'.
  76: In row 10, no more unknowns, so 1 is 'off'.
  77: In row 11, no more unknowns, so 1 is 'off'.
  78: A small portion of row 14 is on (from 7 to 10).
  79: In row 14, cell 4 is 'off'.
  80: A small portion of row 15 is on (from 7 to 10).
  81: A small portion of column 1 is on (from 12 to 13).
  82: In column 1, no more unknowns, so 14 is 'on'.
  83: In column 1, no more unknowns, so 15 is 'on'.
  84: A small portion of column 3 is on (from 8 to 13).
  85: In column 4, cell 15 is 'off'.
  86: In column 5, cell 13 is 'off'.
  87: In column 7, no more unknowns, so 1 is 'on'.
  88: A small portion of column 8 is on (from 1 to 6).
  89: In column 9, no more unknowns, so 1 is 'off'.
  90: A small portion of column 10 is on (from 8 to 15).
  91: A small portion of row 1 is on (from 6 to 8).
  92: In row 1, no more unknowns, so 5 is 'on'.
  93: A small portion of row 6 is on (from 4 to 5).
  94: In row 13, cell 4 is 'off'.
  95: A small portion of column 4 is on (from 3 to 12).
  96: In column 4, no more unknowns, so 2 is 'on'.
  97: In column 5, no more unknowns, so 2 is 'off'.
  98: In column 5, no more unknowns, so 3 is 'off'.
  99: In column 5, no more unknowns, so 4 is 'off'.
 100: A small portion of column 6 is on (from 10 to 13).
 101: In column 6, cell 2 is 'off'.
 102: In column 6, cell 3 is 'off'.
 103: In column 6, cell 4 is 'off'.
 104: 
 105: Row 1, block 1 (size 4) = 4 to 7
 106: Row 2, block 1 (size 1) = 2 to 5
 107: Row 2, block 2 (size 2) = 7 to 8
 108: Row 3, block 1 (size 1) = 2 to 5
 109: Row 3, block 2 (size 2) = 7 to 8
 110: Row 4, block 1 (size 1) = 2 to 5
 111: Row 4, block 2 (size 2) = 7 to 8
 112: Row 5, block 1 (size 1) = 3 to 5
 113: Row 5, block 2 (size 2) = 7 to 8
 114: Row 6, block 1 (size 2) = 3 to 4
 115: Row 6, block 2 (size 2) = 7 to 8
 116: Row 7, block 1 (size 1) = 3 to 6
 117: Row 7, block 2 (size 1) = 8 to 8
 118: Row 8, block 1 (size 2) = 2 to 3
 119: Row 8, block 2 (size 2) = 8 to 9
 120: Row 9, block 1 (size 3) = 2 to 4
 121: Row 9, block 2 (size 3) = 7 to 9
 122: Row 10, block 1 (size 9) = 1 to 9
 123: Row 11, block 1 (size 9) = 1 to 9
 124: Row 12, block 1 (size 10) = 0 to 9
 125: Row 13, block 1 (size 1) = 0 to 0
 126: Row 13, block 2 (size 1) = 2 to 2
 127: Row 13, block 3 (size 1) = 5 to 5
 128: Row 13, block 4 (size 2) = 8 to 9
 129: Row 14, block 1 (size 2) = 0 to 1
 130: Row 14, block 2 (size 4) = 6 to 9
 131: Row 15, block 1 (size 3) = 0 to 3
 132: Row 15, block 2 (size 4) = 6 to 9
 133: 
 134: Column 1, block 1 (size 4) = 11 to 14
 135: Column 2, block 1 (size 3) = 9 to 11
 136: Column 2, block 2 (size 2) = 13 to 14
 137: Column 3, block 1 (size 6) = 7 to 12
 138: Column 3, block 2 (size 1) = 14 to 14
 139: Column 4, block 1 (size 11) = 1 to 11
 140: Column 5, block 1 (size 1) = 0 to 0
 141: Column 5, block 2 (size 1) = 5 to 5
 142: Column 5, block 3 (size 4) = 8 to 11
 143: Column 6, block 1 (size 1) = 0 to 0
 144: Column 6, block 2 (size 4) = 9 to 12
 145: Column 7, block 1 (size 1) = 0 to 0
 146: Column 7, block 2 (size 3) = 9 to 11
 147: Column 7, block 3 (size 2) = 13 to 14
 148: Column 8, block 1 (size 6) = 0 to 5
 149: Column 8, block 2 (size 4) = 8 to 11
 150: Column 8, block 3 (size 2) = 13 to 14
 151: Column 9, block 1 (size 14) = 1 to 14
 152: Column 10, block 1 (size 8) = 7 to 14
 153: 
 154: 
 155:                     1  2  3  4  5  6  7  8  9 10 
 156:    +-------------+------------------------------- +
 157:    |             |              1     1  6        |
 158:    |             |     3  6     1  1  3  4        |
 159:    |             |  4  2  1 11  4  4  2  2 14  8  |
 160:    +-------------+------------------------------- +
 161:    |             |             XXXXXXXXXXXX       |
 162:  1 |           4 |  .  .  .  . XXXXXXXXXXXX .  .  |
 163:    |             |          XXX         XXXXXX    |
 164:  2 |        1  2 |  .  .  . XXX .  .  . XXXXXX .  |
 165:    |             |          XXX         XXXXXX    |
 166:  3 |        1  2 |  .  .  . XXX .  .  . XXXXXX .  |
 167:    |             |          XXX         XXXXXX    |
 168:  4 |        1  2 |  .  .  . XXX .  .  . XXXXXX .  |
 169:    |             |          XXX         XXXXXX    |
 170:  5 |        1  2 |  .  .  . XXX .  .  . XXXXXX .  |
 171:    |             |          XXXXXX      XXXXXX    |
 172:  6 |        2  2 |  .  .  . XXXXXX .  . XXXXXX .  |
 173:    |             |          XXX            XXX    |
 174:  7 |        1  1 |  .  .  . XXX .  .  .  . XXX .  |
 175:    |             |       XXXXXX            XXXXXX |
 176:  8 |        2  2 |  .  . XXXXXX .  .  .  . XXXXXX |
 177:    |             |       XXXXXXXXX      XXXXXXXXX |
 178:  9 |        3  3 |  .  . XXXXXXXXX .  . XXXXXXXXX |
 179:    |             |    XXXXXXXXXXXXXXXXXXXXXXXXXXX |
 180: 10 |           9 |  . XXXXXXXXXXXXXXXXXXXXXXXXXXX |
 181:    |             |    XXXXXXXXXXXXXXXXXXXXXXXXXXX |
 182: 11 |           9 |  . XXXXXXXXXXXXXXXXXXXXXXXXXXX |
 183:    |             | XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX |
 184: 12 |          10 | XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX |
 185:    |             | XXX   XXX      XXX      XXXXXX |
 186: 13 |  1  1  1  2 | XXX . XXX .  . XXX .  . XXXXXX |
 187:    |             | XXXXXX            XXXXXXXXXXXX |
 188: 14 |        2  4 | XXXXXX .  .  .  . XXXXXXXXXXXX |
 189:    |             | XXXXXXXXX         XXXXXXXXXXXX |
 190: 15 |        3  4 | XXXXXXXXX .  .  . XXXXXXXXXXXX |
 191:    +-------------+------------------------------- +
 192: Elapsed time: 0:00:00  (h:mm:ss);  took 5 iterations.
 193: 
Email: steve@oharasteve.com