#include <u.h>
#include <libc.h>
#include <draw.h>
#include <event.h>

enum{ZZZ = 100, SQ = 48, PAD = 2};

char goal[256], a[256];
int x = 3, y = 3, n = 9, e;
ulong moves;
Font *f;
Image *bg, *tile, *fg, *glenda, *bunny;
Point bo = {24, 14};

void
drawtile(int t)
{
	Rectangle r;
	char s[3];
	Point p;

	p = addpt(screen->r.min, mulpt(Pt(t % x, t / x), SQ));
	r = rectaddpt(Rect(0, 0, SQ, SQ), p);
	if(a[t] == '\0'){
		draw(screen, r, fg, nil, ZP);
		draw(screen, r, bg, glenda, ZP);
		return;
	}
	draw(screen, r, bg, nil, ZP);
	r = insetrect(r, PAD);
	if(bunny == nil){
		draw(screen, r, tile, nil, ZP);
		sprint(s, "%X", (uchar)a[t]);
		p = Pt(SQ - PAD - stringwidth(f, s), SQ - PAD - f->height);
		string(screen, addpt(r.min, divpt(p, 2)), fg, ZP, f, s);
	}
	else{
		p = mulpt(Pt((a[t] - 1) % x, (a[t] - 1) / x), SQ + PAD);
		draw(screen, r, fg, nil, ZP);
		draw(screen, r, bunny, nil, addpt(bo, p));
	}
}

void
eresized(int new)
{
	int fd, i;

	if(new && getwindow(display, Refnone) < 0)
		sysfatal("can't reattach to window");
	if((!new || Dx(screen->r) != x * SQ || Dy(screen->r) != y * SQ)
	&& (fd = open("/dev/wctl", OWRITE)) >= 0){
		fprint(fd, "resize -dx %d -dy %d",
			x * SQ + 2 * Borderwidth,
			y * SQ + 2 * Borderwidth);
		close(fd);
	}
	for(i = 0; i < n; i++)
		drawtile(i);
	flushimage(display, 1);
}

Image *
allocimg(ulong chan, ulong colour)
{
	Image *i;

	i = allocimage(display, Rect(0, 0, 1, 1), chan, 1, colour);
	if(i == nil)
		sysfatal("allocimage: %r");
	return i;
}

void
new(void)
{
	int i, r;

	for(i = 0; i < n - 1; i++)
		goal[i] = i + 1;
	goal[i] = '\0';
	strcpy(a, goal);
	srand(truerand());
	for(i = 0; i < n - 2; i++){
		r = nrand(n - i - 2) + i + 1;
		a[i] ^= a[r], a[r] ^= a[i], a[i] ^= a[r];
	}
	if(n & 1)
		a[0] ^= a[1], a[1] ^= a[0], a[0] ^= a[1];
	for(e = 0; a[e]; e++)
		;
	moves = 0;
}

void
mv(int Δ, int zzz)
{
	a[e] = a[e + Δ];
	drawtile(e);
	a[e += Δ] = '\0';
	drawtile(e);
	flushimage(display, 1);
	sleep(zzz);
	moves++;
}

void
diag(int dir)
{
	mv(dir, ZZZ);
	mv(-x, ZZZ);
	mv(-dir, ZZZ);
	mv(-x, ZZZ);
	mv(dir, ZZZ);
	mv(x, ZZZ);
}

void
horiz(int dir)
{
	mv(dir, ZZZ);
	mv(-x, ZZZ);
	mv(-dir, ZZZ);
	mv(x, ZZZ);
	mv(dir, ZZZ);
}

void
move(char targ, int row, int col)
{
	int t;

	for(t = 0; a[t] != targ; t++)
		;
	if(t == targ - 1)
		return;
	if(e / x == t / x)
		mv(e / x < y - 1 ? x : -x, ZZZ);
	while(e % x < t % x)
		mv(1, ZZZ);
	while(e % x > t % x)
		mv(-1, ZZZ);
	while(e / x < t / x)
		mv(x, ZZZ);
	while(a[e - x] != targ)
		mv(-x, ZZZ);
	while(e % x < col && e / x > row + 2)
		diag(1);
	while(e % x < col)
		horiz(1);
	while(e % x > col && e / x > row + 1)
		diag(-1);
	while(e % x > col)
		horiz(-1);
	while(e / x > row + 1){
		mv(1, ZZZ);
		mv(-x, ZZZ);
		mv(-x, ZZZ);
		mv(-1, ZZZ);
		mv(x, ZZZ);
	}
}

int
fillrow(int row)
{
	int i;

	for(i = 0; i < x - 1; i++){
		move(row * x + i + 1, row, i);
		if(ecankbd())
			return 0;
	}
	if(a[row * x + i] == a[row * x + i - 1] + 1)
		return 1;
	while(e % x < x - 1)
		mv(1, ZZZ);
	while(e / x > row + 1)
		mv(-x, ZZZ);
	if(a[e - 1] == a[e - x - 1] + 1){
		mv(x, ZZZ);
		mv(-1, ZZZ);
		mv(-x, ZZZ);
		mv(1, ZZZ);
	}
	if(ecankbd())
		return 0;
	move(row * x + i + 1, row + 1, x - 2);
	if(ecankbd())
		return 0;
	mv(1, ZZZ);
	mv(-x, ZZZ);
	mv(-1, ZZZ);
	mv(x, ZZZ);
	mv(1, ZZZ);
	mv(-x, ZZZ);
	mv(-x, ZZZ);
	mv(-1, ZZZ);
	mv(x, ZZZ);
	mv(1, ZZZ);
	mv(x, ZZZ);
	mv(-1, ZZZ);
	mv(-x, ZZZ);
	mv(-x, ZZZ);
	mv(1, ZZZ);
	mv(x, ZZZ);
	return 1;
}

void
solve(void)
{
	int i, j;

	for(i = 0; i < y - 2; i++)
		if(!fillrow(i))
			return;
	for(j = 0; j < x - 2; j++){
		move(i * x + j + 1, i, j);
		while(e / x < y - 1)
			mv(x, ZZZ);
		while(e % x > j)
			mv(-1, ZZZ);
		if(ecankbd())
			return;
		if(a[e - x + 1] == (i + 1) * x + j + 1){
			mv(1, ZZZ);
			mv(1, ZZZ);
			mv(-x, ZZZ);
			mv(-1, ZZZ);
			mv(x, ZZZ);
			mv(-1, ZZZ);
		}
		mv(-x, ZZZ);
		mv(1, ZZZ);
		if(ecankbd())
			return;
		move((i + 1) * x + j + 1, i, j + 1);
		mv(-x, ZZZ);
		mv(-1, ZZZ);
		mv(x, ZZZ);
		mv(1, ZZZ);
		if(ecankbd())
			return;
	}
	mv(1, ZZZ);
	while(strcmp(a, goal) != 0){
		if(ecankbd())
			return;
		mv(-x, ZZZ);
		mv(-1, ZZZ);
		mv(x, ZZZ);
		mv(1, ZZZ);
	}
}

void
main(int argc, char *argv[])
{
	int fd;
	Image *victory;

	if(argc > 1){
		if(!strchr(argv[1], 'x'))
			sysfatal("usage: %s [rowsxcols]", argv[0]);
		y = atoi(strtok(argv[1], "x"));
		x = atoi(strtok(nil, "x"));
		if(x < 3 || y < 3)
			sysfatal("dimensions %dx%d too small!", x, y);
		if((n = x * y) > 256)
			sysfatal("dimensions %dx%d too large!", x, y);
	}
	new();
	if(initdraw(nil, nil, argv[0]) < 0)
		sysfatal("initdraw: %r");
	bg = allocimg(screen->chan, DGreygreen);
	tile = allocimg(screen->chan, DPalegreygreen);
	fg = allocimg(screen->chan, DBlack);
	victory = allocimg(RGBA32, setalpha(DGreen, 0x7f));
	if((fd = open("/lib/face/48x48x4/g/glenda.1", OREAD)) >= 0){
		glenda = readimage(display, fd, 0);
		close(fd);
	}
	if(x == 3 && y == 3 && (fd = open("/lib/bunny.bit", OREAD)) >= 0){
		bunny = readimage(display, fd, 0);
		close(fd);
	}
	if((f = openfont(display, "/lib/font/bit/pelm/ascii.16.font")) == nil)
		sysfatal("can't open font: %r");
	einit(Emouse|Ekeyboard);
	eresized(0);
	for(;;){
		switch(ekbd()){
		case 0xF00E:	/* ↑ */
			if(e / x < y - 1)
				mv(x, 0);
			break;
		case 0xF800:	/* ↓ */
			if(e / x)
				mv(-x, 0);
			break;
		case 0xF011:	/* ← */
			if(e % x < x - 1)
				mv(1, 0);
			break;
		case 0xF012:	/* → */
			if(e % x)
				mv(-1, 0);
			break;
		case 's':
			solve();
			break;
		case 'q': case 0x7F:
			exits(nil);
		}
		if(strcmp(a, goal) == 0){
			draw(screen, screen->r, bunny == nil ? victory : bunny, nil, bo);
			if(ekbd() == 'n'){
				new();
				eresized(0);
			}
			else{
				print("solved in %uld moves\n", moves);
				exits(nil);
			}
		}
	}
}