/* This program is in the public domain */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define DX 12
#define DY 10

/* Make the matrix CPU-friendly aligned. */
#define MX 16
#define MY 16

static intmax_t count[MX][MY], tcount;

static int tr[MX][MY];

static time_t t0, t1, t2;

static void
show(int a[MX][MY])
{
	int x, y;
	double r1, r2;

	if (t0 == 0) {
		time(&t0);
		t1 = t0;
		return;
	}
	time(&t2);
	r1 =  tcount / (t2 - t0);
	r2 =  100000000.0 / (t2 - t1);
	fprintf(stderr, "...%jd %f %f\n", tcount, r1, r2);
	t1 = t2;
	for (y = 0; y < DY; y++) {
		for (x = 0; x < DX; x++) {
			if (a[x][y] < 0)
				fprintf(stderr, "*");
			else
				fprintf(stderr, "%d", a[x][y]);
		}
		fprintf(stderr, "\n");
	}
	fprintf(stderr, "---\n");
	fflush(stderr);
}

static int
acc(int a[MX][MY] __unused)
{
	static int n;

	tcount++;
	if (++n == 100000000) {
		show(a);
		n = 0;
	}
	return (1);
}

#define FX(fn, N, M, fx)					\
static int							\
fn(int a[MX][MY])						\
{								\
	int sx, sy, sl, n, m;					\
								\
	m = 0;							\
	for (sx = 0; sx < DX; sx++) {				\
		for (sy = 0; sy <= DY - N; sy++) {		\
			for (sl = 0; sl < N; sl++)		\
				if (a[sx][sy + sl])		\
					goto nope;		\
			for (sl = 0; sl < N; sl++)		\
				a[sx][sy + sl] = M;		\
			n = fx(a);				\
			m += n;					\
			for (sl = 0; sl < N; sl++) {		\
				count[sx][sy + sl] += n;	\
				a[sx][sy + sl] = 0;		\
			}					\
			nope:					\
				;				\
		}						\
	}							\
	for (sy = 0; sy < DY; sy++) {				\
		for (sx = 0; sx <= DX - N; sx++) {		\
			for (sl = 0; sl < N; sl++)		\
				if (a[sx + sl][sy])		\
					goto neither;		\
			for (sl = 0; sl < N; sl++)		\
				a[sx + sl][sy] = M;		\
			n = fx(a);				\
			m += n;					\
			for (sl = 0; sl < N; sl++) {		\
				count[sx + sl][sy] += n;	\
				a[sx + sl][sy] = 0;		\
			}					\
			neither:				\
				;				\
		}						\
	}							\
	return (m);						\
}		

FX(do2, 2, 5, acc)
FX(do3b, 3, 4, do2)
FX(do3a, 3, 3, do3b)
FX(do4, 4, 2, do3a)
FX(do5, 5, 1, do4)

int
main(int argc __unused, char **argv __unused)
{
	int a[MX][MY];
	int x, y, bx, by;
	double w, bw;

	show(a);
#if 0
	tr[4][4] = -1;
	tr[4][5] = -1;
	tr[7][4] = -1;
	tr[7][5] = -1;
#endif
	for(;;) {
		tcount = 0;
		memset(count, 0, sizeof count);
		memcpy(a, tr, sizeof a);

		do5(a);

		printf("\n\ntcount = %jd\n", tcount);
		if (tcount == 0)
			break;
		for (y = 0; y < DY; y++) {
			for (x = 0; x < DX; x++)
				printf(" %11jd", count[x][y]);
			printf("\n");
		}
		

		printf("\n\n");
		
		
		bx = by = bw = 0;
		for (y = 0; y < DY; y++) {
			for (x = 0; x < DX; x++) {
				w = (double)count[x][y] / tcount;
				printf(" %.4f", w);
				if (w > bw) {
					bx = x;
					by = y;
					bw = w;
				}
			}
			printf("\n");
		}
		printf("\n\nAttempt at: (%d,%d) = %c%d\n", bx, by, 'A' + bx, 1 + by);
		fflush(stdout);
		tr[bx][by] = -1;
#if 0
		tr[DX - 1 - bx][by] = -1;
		tr[bx][DY - 1 - by] = -1;
		tr[DX - 1 - bx][DY - 1 - by] = -1;
#endif
	}
	exit (0);
}