/*
 * Copyright (c) 2015 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * COPYING, REDISTRIBUTION AND USE IN ANY FORM ARE PROHIBITED WITHOUT AN
 * EXPLICIT WRITTEN PERMISSION.
 */

#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <string>
#include <vector>

using namespace std;

static const char *host = "techchallenge.cimpress.com";
static const char *key = "c6530d33f5774750839239266ec3e5e7";
static const char *mode = "trial";

struct Square {
	Square(int x, int y, int size) : x(x), y(y), size(size) {}
	int x, y, size;
};

struct Grid {
	inline Square candidate(int c) {
		int x, y;

		x = mark[c][0]; y = mark[c][1];
		switch (c) {
		case 0:
			while (y < height) {
				if (m[x][y])
					goto found;
				if (++x == width) {
					y++;
					x = 0;
				}
			}
			break;
		case 1:
			while (x < width) {
				if (m[x][y])
					goto found;
				if (++y == height) {
					x++;
					y = 0;
				}
			}
			break;
		case 2:
			while (y < height) {
				if (m[x][y])
					goto found;
				if (--x == -1) {
					y++;
					x = width - 1;
				}
			}
			break;
		case 3:
			while (x >= 0) {
				if (m[x][y])
					goto found;
				if (++y == height) {
					x--;
					y = 0;
				}
			}
			break;
		case 4:
			while (y >= 0) {
				if (m[x][y])
					goto found;
				if (--x == -1) {
					y--;
					x = width - 1;
				}
			}
			break;
		case 5:
			while (x >= 0) {
				if (m[x][y])
					goto found;
				if (--y == -1) {
					x--;
					y = height - 1;
				}
			}
			break;
		case 6:
			while (y >= 0) {
				if (m[x][y])
					goto found;
				if (++x == width) {
					y--;
					x = 0;
				}
			}
			break;
		case 7:
			while (x < width) {
				if (m[x][y])
					goto found;
				if (--y == -1) {
					x++;
					y = height - 1;
				}
			}
			break;
		}
		return Square(0, 0, 0);
found:
		mark[c][0] = x; mark[c][1] = y;
		int dx = (c >= 2 && c <= 5) ? -1 : 1;
		int dy = (c >= 4 && c <= 7) ? -1 : 1;
		unsigned char i = 0, j = 0;
		do {
			i++;
			if (x + i * dx < 0 || x + i * dx >= width ||
			    y + i * dy < 0 || y + i * dy >= height)
				break;
			for (j = 0; j <= i; ++j)
				if (!m[x + dx * i][y + dy * j] ||
				    !m[x + dx * j][y + dy * i])
					break;
		} while (j > i);
		return Square(dx > 0 ? x : x - i + 1,
		    dy > 0 ? y : y - i + 1, i);
	}
	inline void add(const Square &square) {
		for (int y = 0; y < square.size; ++y)
			for (int x = 0; x < square.size; ++x)
				m[square.x + x][square.y + y] = 0;
		squares.push_back(square);
	}
	unsigned char m[100][100];
	vector<Square> squares;
	int width, height;
	int mark[8][2];
	inline void init() {
		mark[0][0] = 0; mark[0][1] = 0;
		mark[1][0] = 0; mark[1][1] = 0;
		mark[2][0] = width - 1; mark[2][1] = 0;
		mark[3][0] = width - 1; mark[3][1] = 0;
		mark[4][0] = width - 1; mark[4][1] = height - 1;
		mark[5][0] = width - 1; mark[5][1] = height - 1;
		mark[6][0] = 0; mark[6][1] = height - 1;
		mark[7][0] = 0; mark[7][1] = height - 1;
	}
};

static inline unsigned long
usec()
{
	static struct timeval tv;

	gettimeofday(&tv, NULL);
	return tv.tv_sec * 1000000 + tv.tv_usec;
}

static string
solve(const string &puzzle)
{
	unsigned long beg = usec(), end = beg + 10000000;
	char *b = (char *)puzzle.c_str();
	char *p;
	char id[256], x[512];

	Grid initial, best;
	memset(&initial, 0, sizeof(initial));
	if ((p = strstr(b, "\"width\":")))
		initial.width = atoi(p + 8);
	if ((p = strstr(b, "\"height\":")))
		initial.height = atoi(p + 9);
	if ((p = strstr(b, "\"id\":")))
		sscanf(p + 6, "%[^\"]", id);
	p = strstr(b, "[[") + 2;
	for (int y = 0; p && y < initial.height; ++y) {
		for (int x = 0; p && x < initial.width; ++x) {
			int v = !strncmp(p, "true", 4);
			if (v)
				initial.m[x][y] = 1;
			p += v ? 5 : 6;
		}
		if (p)
			p = strchr(p, '[') + 1;
	}

	int min = 10000, pass = 0;
	for (pass = 0; ; ++pass) {
		if (pass % 10 == 0 && usec() >= end)
			break;
		Grid g = initial;
		g.init();
		while (true) {
			Square s = g.candidate(arc4random_uniform(8));
			if (!s.size) {
				if ((int)g.squares.size() < min) {
					min = g.squares.size();
					best = g;
				}
				break;
			}
			g.add(s);
		}
	}

	string r;
	snprintf(x, sizeof(x), "{\"id\":\"%s\",\"squares\":[", id);
	r += x;
	for (int i = 0; i < (int)best.squares.size(); ++i) {
		snprintf(x, sizeof(x), "%s{\"X\":%d,\"Y\":%d,\"Size\":%d}",
		    i ? "," : "", best.squares[i].x, best.squares[i].y,
		    best.squares[i].size);
		r += x;
	}
	r += "]}\n";
	return r;
}

static FILE *
tcp_connect(const string &host, unsigned port)
{
	FILE *f;
	struct hostent *e;
	struct sockaddr_in sa;
	int fd;

	if (!(e = gethostbyname(host.c_str())) || e->h_addrtype != AF_INET ||
	    e->h_length != sizeof(sa.sin_addr.s_addr) || !e->h_addr) {
		fprintf(stderr, "tcp_connect: gethostbyname: %s: %s\n",
		    host.c_str(), hstrerror(h_errno));
		return NULL;
	}
	memset(&sa, 0, sizeof(sa));
	sa.sin_family = AF_INET;
	memcpy(&sa.sin_addr.s_addr, e->h_addr, e->h_length);
	sa.sin_port = htons(port);
	if ((fd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
		fprintf(stderr, "tcp_connect: socket: %s\n", strerror(errno));
		return NULL;
	}
	if (connect(fd, (struct sockaddr *)&sa, sizeof(sa))) {
		fprintf(stderr, "tcp_connect: connect: %s:%u: %s\n",
		    inet_ntoa(sa.sin_addr), ntohs(sa.sin_port),
		    strerror(errno));
		close(fd);
		return NULL;
	}
	if (!(f = fdopen(fd, "r+"))) {
		fprintf(stderr, "tcp_connect: fdopen: %s\n", strerror(errno));
		close(fd);
	}
	return f;
}

static string
http_request(FILE *f, const string &body)
{
	char b[65536];
	ssize_t r;
	string s;

	if (body.empty())
		fprintf(f, "GET http://%s/%s/%s/puzzle HTTP/1.0\r\n\r\n",
		    host, key, mode);
	else
		fprintf(f, "POST http://%s/%s/%s/solution HTTP/1.0\r\n"
		    "Content-Length: %lu\r\n\r\n%s", host, key, mode,
		    body.size(), body.c_str());
	fflush(f);
	if (!fgets(b, sizeof(b), f) || strncmp(b, "HTTP/1.1 ", 9) ||
	    strncmp(b + 9, "200", 3)) {
		fprintf(stderr, "http_request: unexpected reply: %s", b);
		fclose(f);
		return "";
	}
	while (fgets(b, sizeof(b), f))
		if (!strcmp(b, "\r\n"))
			break;
	while (1) {
		r = fread(b, 1, sizeof(b) - 1, f);
		if (r < 0) {
			fprintf(stderr, "http_request: read\n");
			fclose(f);
			return "";
		}
		if (r == 0)
			break;
		b[r] = 0;
		s += b;
	}
	fclose(f);
	return s;
}

int main()
{
	FILE *fg, *fp;
	string s;

	if (!(fp = tcp_connect(host, 80)) || !(fg = tcp_connect(host, 80)))
		return 1;
	s = http_request(fg, "");
	if (s.empty())
		return 1;
	s = http_request(fp, solve(s));
	printf("%s\n", s.c_str());
}