import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.*;
import java.util.*;

import javax.imageio.ImageIO;

public class Tests {
	Random rnd = new Random(239);
	int tests = 1;
	int[] dx = { 1, 0, -1, 0 };
	int[] dy = { 0, 1, 0, -1 };

	public void drawTest(int[][] map) {
		HashMap<Integer, Color> colors = new HashMap<Integer, Color>();

		int size = 20;

		new File("images").mkdir();
		BufferedImage image = new BufferedImage(map.length * size,
				map[0].length * size, BufferedImage.TYPE_INT_RGB);
		Graphics2D g = (Graphics2D) image.getGraphics();

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (!colors.containsKey(map[i][j])) {
					colors.put(
							map[i][j],
							new Color(rnd.nextInt(256), rnd.nextInt(256), rnd
									.nextInt(256)));
				}
				g.setColor(colors.get(map[i][j]));
				g.fillRect(i * size, j * size, size, size);
			}
		}

		try {
			ImageIO.write(image, "png",
					new File(String.format("images/%02d.png", tests - 1)));
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public void writeTest(int k, int w, int h, String[] m) {
		int[][] map = new int[m.length][m[0].length()];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = m[i].charAt(j);
			}
		}
		writeTest(k, w, h, map);
	}

	public void writeTest(int k, int w, int h, int[][] map) {
		writeTest(k, w, h, map, new ArrayList<Integer>());
	}

	public void writeTest(int k, int w, int h, int[][] map,
			ArrayList<Integer> cc) {
		System.out.println("Writing test " + tests
				+ ". Sizes of big rectangle: " + map.length / w + "x"
				+ map[0].length / h);
		try {
			int cw = map.length / w;
			int ch = map[0].length / h;

			if (!ready(cw, ch, map)) {
				System.err.println("Can't distinguish #" + tests);
				return;
			}

			if (!isConnected(cw, ch, map)) {
				System.err.println("Not connected #" + tests);
				return;
			}

			PrintWriter out = new PrintWriter(String.format("tests/%02d",
					tests++));

			out.println(k + " " + h + " " + w);

			if (cc.size() == 0) {
				cc = new ArrayList<Integer>();
				for (int i = 0; i < cw * ch; i++) {
					cc.add(i);
				}
				Collections.shuffle(cc, rnd);
			}

			char z = 'A';
			int cnt = 0;
			for (int color : cc) {
				int i = color / ch;
				int j = color % ch;

				int c = map[i * w][j * h];

				for (int x = i * w - w + 1; x < i * w + 2 * w - 1; x++) {
					for (int y = j * h - h + 1; y < j * h + 2 * h - 1; y++) {
						if (map.length > x && x >= 0 && map[0].length > y
								&& y >= 0 && map[x][y] == c) {
							out.print(z);
						} else {
							out.print(".");
						}
					}
					out.println();
				}
				cnt++;
				if (cnt < cw * ch)
					out.println();
				z++;
			}

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}

		drawTest(map);
	}

	public void isConnected(int x, int y, int[][] map, boolean[][] was) {
		if (was[x][y])
			return;

		was[x][y] = true;

		for (int i = 0; i < dx.length; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || xx > was.length - 1 || yy < 0
					|| yy > was[0].length - 1)
				continue;
			if (map[xx][yy] == map[x][y])
				isConnected(xx, yy, map, was);
		}
	}

	public boolean isConnected(int cw, int ch, int color, int[][] map) {
		int x = color / ch;
		int y = color % ch;

		int w = map.length / cw;
		int h = map[0].length / ch;

		boolean[][] was = new boolean[map.length][map[0].length];

		isConnected(x * w, y * h, map, was);

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (!was[i][j] && map[i][j] == map[x * w][y * h]) {
					return false;
				}
			}
		}
		return true;
	}

	public boolean isConnected(int cw, int ch, int[][] map) {
		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				if (!isConnected(cw, ch, i * ch + j, map)) {
					return false;
				}
			}
		}
		return true;
	}

	public boolean isInside(int xx, int yy, int w, int h, int x, int y) {
		if (1 - w + xx <= x && x <= 2 * w - 2 + xx && yy < y && y < yy + h - 1)
			return true;
		if (xx < x && x < xx + w - 1 && 1 - h + yy <= y && y <= 2 * h - 2 + yy)
			return true;
		if (xx <= x && x <= xx + w - 1 && yy <= y && y <= yy + h - 1)
			return true;
		return false;
	}

	public void randomTest(int w, int h, int cw, int ch) {
		randomTest(w, h, cw, ch, 1000);
	}

	public void randomTest(int w, int h, int cw, int ch, int it) {
		randomTest(w, h, cw, ch, it, 10000);
	}

	public void randomTest(int w, int h, int cw, int ch, int it, int max_in_each) {
		randomTest(w, h, cw, ch, it, max_in_each, 10000);
	}

	public boolean ready(int cw, int ch, int[][] map) {
		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				if (!ready(i, j, cw, ch, map)) {
					return false;
				}
			}
		}
		return true;
	}

	public boolean ready(int i, int j, int cw, int ch, int[][] map) {
		int w = map.length / cw;
		int h = map[0].length / ch;
		int color = map[i * w][j * h];
		int cnt = 0;
		int x = i * w;
		int y = j * h;

		for (int k = 0; k < dx.length; k++) {
			boolean good = false;
			int o = (k + 3) % 4;

			while (i * w <= x && x <= i * w + w - 1 && j * h <= y
					&& y <= j * h + h - 1) {
				if (map[x][y] != color)
					good = true;

				if (0 <= x + dx[o] && x + dx[o] < map.length && 0 <= y + dy[o]
						&& y + dy[o] < map[0].length) {
					if (map[x + dx[o]][y + dy[o]] == color)
						good = true;
				} else {
					good = true;
				}

				x += dx[k];
				y += dy[k];
			}

			// System.err.println(i + " " + j + " " + x + " " + y);

			x -= dx[k];
			y -= dy[k];

			if (good)
				cnt++;
		}
		if (cnt != 4)
			return false;

		return true;
	}

	public void init(int cw, int ch, int[][] map, boolean[][] fixed) {
		int w = map.length / cw;
		int h = map[0].length / ch;
		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				if (j != ch - 1) {
					int xx = rnd.nextInt(w - 2) + 1;

					int[] zz = new int[2];
					zz[0] = rnd.nextInt(2);
					zz[1] = 1 - zz[0];

					for (int k = 0; k < 2; k++) {
						map[i * w + xx][j * h + h - zz[k]] = i * ch
								+ (j + zz[k]);
						if (isConnected(cw, ch, i * ch + (j + 1 - zz[k]), map)) {
							fixed[i * w + xx][j * h + h - zz[k]] = true;
							break;
						} else {
							map[i * w + xx][j * h + h - zz[k]] = i * ch
									+ (j + 1 - zz[k]);
						}
					}
				}
				if (i != cw - 1) {
					int yy = rnd.nextInt(h - 2) + 1;

					int[] zz = new int[2];
					zz[0] = rnd.nextInt(2);
					zz[1] = 1 - zz[0];

					for (int k = 0; k < 2; k++) {
						map[i * w + w - zz[k]][j * h + yy] = (i + zz[k]) * ch
								+ j;
						if (isConnected(cw, ch, (i + 1 - zz[k]) * ch + j, map)) {
							fixed[i * w + w - zz[k]][j * h + yy] = true;
							break;
						} else {
							map[i * w + w - zz[k]][j * h + yy] = (i + 1 - zz[k])
									* ch + j;
						}
					}
				}
			}
		}
	}

	public void randomTest(int w, int h, int cw, int ch, int it,
			int max_in_each, int total_max) {
		int[][] map = new int[w * cw][h * ch];

		boolean[][] fixed = new boolean[w * cw][h * ch];

		int[] toColor = new int[cw * ch];
		Arrays.fill(toColor, max_in_each);

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				int cc = i / w;
				int hh = j / h;

				map[i][j] = cc * ch + hh;
			}
		}

		init(cw, ch, map, fixed);

		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				int x = w * i;
				int y = h * j;
				fixed[x][y] = true;
				fixed[x + w - 1][y] = true;
				fixed[x][y + h - 1] = true;
				fixed[x + w - 1][y + h - 1] = true;
			}
		}

		for (int t = 0; t < it && max_in_each > 0; t++) {
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[0].length; j++) {
					if (fixed[i][j])
						continue;

					HashSet<Integer> colors = new HashSet<Integer>();
					colors.add(map[i][j]);
					for (int k = 0; k < dx.length; k++) {
						int xx = i + dx[k];
						int yy = j + dy[k];
						if (xx < 0 || xx >= map.length || yy < 0
								|| yy >= map[0].length)
							continue;
						colors.add(map[xx][yy]);
					}

					Integer[] cc = colors.toArray(new Integer[colors.size()]);

					int color = cc[rnd.nextInt(cc.length)];

					if (color == map[i][j] || toColor[color] <= 0
							|| total_max <= 0)
						continue;

					int xx = color / ch;
					int yy = color % ch;
					if (!isInside(xx * w, yy * h, w, h, i, j)) {
						continue;
					}

					int before = map[i][j];
					map[i][j] = color;

					if (!isConnected(cw, ch, (i / w) * ch + (j / h), map)) {
						map[i][j] = before;
					} else {
						fixed[i][j] = true;
						toColor[color]--;
						total_max--;
					}
				}
			}
		}

		writeTest(cw * ch, w, h, map);
	}

	public void randomSimilar(int w, int h, int cw, int ch, int rrx, int rry) {
		randomSimilar(w, h, cw, ch, rrx, rry, -1, -1);
	}

	public void randomSimilar(int w, int h, int cw, int ch, int rrx, int rry,
			int ii, int jj) {
		int[][] map = new int[w * cw][h * ch];
		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				for (int x = 0; x < w; x++) {
					for (int y = 0; y < h; y++) {
						map[i * w + x][j * h + y] = i * ch + j;
					}
				}

				int rx = rrx;
				int ry = rry;
				if ((rx == -1) || (ii == i && jj == j)) {
					rx = rnd.nextInt(w - 2) + 1;
				}
				if ((ry == -1) || (ii == i && jj == j)) {
					ry = rnd.nextInt(h - 2) + 1;
				}

				if (i != 0) {
					map[i * w][j * h + ry] = (i - 1) * ch + j;
				}

				if (j != 0) {
					map[i * w + rx][j * h] = i * ch + (j - 1);
				}
			}
		}

		writeTest(cw * ch, w, h, map);
	}

	public void generateRandomField(int cw, int ch, int[][] map,
			boolean[][] fixed) {
		int w = map.length / cw;
		int h = map[0].length / ch;
		for (int it = 0; it < 1000; it++)
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[0].length; j++) {
					if (fixed[i][j])
						continue;

					HashSet<Integer> colors = new HashSet<Integer>();
					colors.add(map[i][j]);
					for (int k = 0; k < dx.length; k++) {
						int xx = i + dx[k];
						int yy = j + dy[k];
						if (xx < 0 || xx >= map.length || yy < 0
								|| yy >= map[0].length)
							continue;
						colors.add(map[xx][yy]);
					}

					Integer[] cc = colors.toArray(new Integer[colors.size()]);

					int color = cc[rnd.nextInt(cc.length)];

					if (color == map[i][j])
						continue;

					int xx = color / ch;
					int yy = color % ch;
					if (!isInside(xx * w, yy * h, w, h, i, j)) {
						continue;
					}

					int before = map[i][j];
					map[i][j] = color;

					if (!isConnected(cw, ch, (i / w) * ch + (j / h), map)) {
						map[i][j] = before;
					} else {
						fixed[i][j] = true;
					}
				}
			}
	}

	public int[][] trans(int cw, int ch, int[][] map, boolean t, boolean v) {
		int w = map.length / cw;
		int h = map[0].length / ch;
		if (v) {
			for (int i = 0; i < map.length / 2; i++) {
				for (int j = 0; j < h * ch; j++) {
					int q = map[i][j];
					map[i][j] = map[map.length - 1 - i][j];
					map[map.length - 1 - i][j] = q;
				}
			}
		}

		if (t) {
			int[][] tmap = new int[ch * h][cw * w];
			for (int i = 0; i < tmap.length; i++) {
				for (int j = 0; j < tmap[i].length; j++) {
					tmap[i][j] = map[j][i];
				}
			}
			map = tmap;
		}
		return map;
	}

	public void random1Long(boolean t, boolean v) {
		int cw = 1;
		int ch = 25;
		int w = 5;
		int h = 5;

		int[][] map = new int[w * cw][h * ch];

		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				for (int x = 0; x < w; x++) {
					for (int y = 0; y < h; y++) {
						map[i * w + x][j * h + y] = i * ch + j;
					}
				}
			}
		}

		for (int i = 1; i < ch; i++) {
			map[2][i * h] = i - 1;
		}

		map[2][h + 1] = 0;
		map[2][2 * h + 1] = 1;

		map = trans(cw, ch, map, t, v);

		writeTest(24, w, h, map);
	}

	public void random2Long(boolean random, boolean t) {
		random2Long(random, t, false, 12);
	}

	public void random2Long(boolean random, boolean t, boolean v, int max) {
		int cw = 2;
		int ch = 12;
		int w = 5;
		int h = 5;

		int[][] map = new int[w * cw][h * ch];

		boolean[][] fixed = new boolean[w * cw][h * ch];

		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				for (int x = 0; x < w; x++) {
					for (int y = 0; y < h; y++) {
						map[i * w + x][j * h + y] = i * ch + j;
						if (i == 0) {
							fixed[i * w + x][j * h + y] = true;
						}
					}
				}
			}
		}

		for (int i = 1; i < ch; i++) {
			map[2][i * h] = i - 1;
			fixed[2][i * h] = true;
		}

		List<Integer> ind = new ArrayList<Integer>();

		if (max != ch) {
			for (int i = 0; i < max; i++) {
				ind.add(i);
			}

			Collections.shuffle(ind, rnd);
			ind = ind.subList(0, max);
		}

		for (int i = 0; i < ch; i++) {
			int yy = i * h + 1;
			int xx = w;
			if ((rnd.nextBoolean() && random && ind.size() == 0)
					|| ind.contains(i)) {
				yy = i * h + 3;
			}

			for (int y = 0; y < h; y++) {
				fixed[xx][i * h + y] = true;
			}

			map[xx][yy] = i;
			fixed[xx + 1][yy] = true;
		}

		generateRandomField(cw, ch, map, fixed);

		map = trans(cw, ch, map, t, v);

		writeTest(24, w, h, map);
	}

	public void random2Long2(int pos, boolean t, boolean v) {
		int cw = 2;
		int ch = 12;
		int w = 5;
		int h = 5;

		int[][] map = new int[w * cw][h * ch];

		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				for (int x = 0; x < w; x++) {
					for (int y = 0; y < h; y++) {
						map[i * w + x][j * h + y] = i * ch + j;
					}
				}
			}
		}

		for (int i = 1; i < ch; i++) {
			map[2][i * h] = i - 1;
			map[2 + w][i * h] = ch + i - 1;
		}

		for (int i = 0; i < ch; i++) {
			if (i == pos)
				map[w][h * i + 1] = i;
			else
				map[w][h * i + 3] = i;
		}

		map = trans(cw, ch, map, t, v);

		writeTest(24, w, h, map);
	}

	public void random3Long(boolean t, boolean v) {
		int cw = 3;
		int ch = 8;
		int w = 5;
		int h = 5;

		int[][] map = new int[cw * w][ch * h];
		boolean[][] fixed = new boolean[cw * w][ch * h];

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				int ww = i / w;
				int hh = j / h;

				map[i][j] = ww * ch + hh;
				if (ww != 2) {
					fixed[i][j] = true;
				}
			}
		}

		for (int i = 1; i < ch; i++) {
			map[2][i * h] = i - 1;
			fixed[2][i * h] = true;
			map[2 + w][i * h] = ch + i - 1;
			fixed[2 + w][i * h] = true;
		}

		List<Integer> ind = new ArrayList<Integer>();
		for (int i = 0; i < ch; i++) {
			ind.add(i);
		}

		Collections.shuffle(ind);

		List<Integer> first = ind.subList(0, 4);
		List<Integer> first1 = ind.subList(4, 8);
		Collections.shuffle(first);
		Collections.shuffle(first1);

		List<Integer> second = new ArrayList<Integer>();
		second.addAll(first.subList(0, 2));
		second.addAll(first1.subList(0, 2));

		List<Integer>[] lists = new List[] { first, second };

		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < ch; j++) {
				int xx = (i + 1) * w;
				int yy = j * h + 1;

				if (lists[i].contains(j))
					yy = j * h + 3;

				for (int y = 0; y < h; y++) {
					fixed[xx][j * h + y] = true;
				}

				map[xx][yy] = i * ch + j;
				fixed[xx + 1][yy] = true;
			}
		}

		generateRandomField(cw, ch, map, fixed);
		map = trans(cw, ch, map, t, v);

		writeTest(24, w, h, map);
	}

	public void genAnalTest(int cw, int ch, boolean t, boolean v) {
		int w = 5;
		int h = 5;

		int[][] map = new int[cw * w][ch * h];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				int ww = i / w;
				int hh = j / h;

				map[i][j] = ww * ch + hh;
			}
		}

		for (int i = 0; i < cw; i++) {
			for (int j = 0; j < ch; j++) {
				if (i > 0) {
					map[i * w][j * h + 2] = (i - 1) * ch + j;
				}
				if (j > 0) {
					map[i * w + 2][j * h] = i * ch + (j - 1);
				}
			}
		}

		map[2][h + 1] = 0;
		map[2][2 * h + 1] = 1;

		int xx = 0;
		int yy = 2;

		if (t) {
			xx = 2;
			yy = 0;
		}

		if (v) {
			xx = cw - 1 - xx;
		}

		int color = xx * ch + yy;

		ArrayList<Integer> cc = new ArrayList<Integer>();
		for (int i = 0; i < cw * ch; i++) {
			if (i != color)
				cc.add(i);
		}

		Collections.shuffle(cc, rnd);

		ArrayList<Integer> colors = new ArrayList<Integer>();
		colors.add(color);
		for (int x : cc) {
			colors.add(x);
		}

		map = trans(cw, ch, map, t, v);

		writeTest(cw * ch, w, h, map, colors);
	}

	public ArrayList<Integer> prepareColors(int w, int h, int[][] map) {
		ArrayList<Integer> colors = new ArrayList<Integer>();
		int cw = map.length / w;
		int ch = map[0].length / h;
		for (int color = 0; color < cw * ch; color++) {
			for (int x = 0; x < cw; x++) {
				for (int y = 0; y < ch; y++) {
					if (map[x * w][y * h] == color)
						colors.add(x * ch + y);
				}
			}
		}
		return colors;
	}

	public void geneticsBig() {
		String[] test = new String[] { "PPPPPNNNNNOOOOOMMMMM",
				"PPPPNNNNNOOOOOMMMMMM", "PPPPNNNNNOOOOOMMMMMM",
				"PPPPPNFNNNOGOOOMEMMM", "PLPPPNFNNNOGOOOMEMMM",
				"LLLLLFFFFFGGGGGEEEEE", "LLLLFFFFFGGGGGEEEEEE",
				"LLLLFFFFFGGGGGEEEEEE", "LLLLLFJFFFGKGGGEIEEE",
				"LHLLLFJFFFGKGGGEIEEE", "HHHHHJJJJJKKKKKIIIII",
				"HHHHJJJJJKKKKKIIIIII", "HHHHJJJJJKKKKKIIIIII",
				"HDHHHJBJJJKCKKKIAIII", "HDHHHJBJJJKCKKKIAIII",
				"DDDDDBBBBBCCCCCAAAAA", "DDDDBBBBBCCCCCAAAAAA",
				"DDDDBBBBBCCCCCAAAAAA", "DDDDDBBBBBCCCCCAAAAA",
				"DDDDDBBBBBCCCCCAAAAA", };

		int[][] map = new int[test.length][test[0].length()];
		for (int i = 0; i < test.length; i++) {
			for (int j = 0; j < test.length; j++) {
				map[i][j] = test[i].charAt(j) - 'A';
			}
		}

		writeTest(16, 5, 5, map, prepareColors(5, 5, map));
		writeTest(16, 5, 5, trans(4, 4, map, true, false),
				prepareColors(5, 5, map));
		writeTest(16, 5, 5, trans(4, 4, map, true, false),
				prepareColors(5, 5, map));
		writeTest(16, 5, 5, trans(4, 4, map, true, true),
				prepareColors(5, 5, map));
	}

	public void gen() {
		if (!new File("tests").exists()) {
			new File("tests").mkdir();
		}

		writeTest(4, 3, 4, new String[] { "BBBBAAAA", "BBBBBBAA", "BDBBAAAA",
				"DDDDCAAC", "DDDCCCAC", "DDDDCCCC" });

		for (int w = 0; w < 3; w++) {
			for (int i = 1; i < 5; i++) {
				randomTest(w + 3, w + 3, i, i);
			}
		}

		randomTest(5, 5, 4, 4, 0);
		randomTest(5, 5, 4, 4, 1);
		randomTest(5, 5, 4, 4, 2);
		randomTest(5, 5, 4, 4, 1, 1);
		randomTest(5, 5, 4, 4, 2, 2);

		System.err.println("Gen random");

		for (int i = 0; i < 40; i++) {
			int w = rnd.nextInt(4) + 1;
			randomTest(rnd.nextInt(3) + 3, rnd.nextInt(3) + 3, w, w,
					rnd.nextInt(30), rnd.nextInt(30), rnd.nextInt(200));
		}

		System.err.println("Gen similar");

		// TODO: gen similar pieces
		randomSimilar(5, 5, 4, 4, -1, -1);
		randomSimilar(5, 5, 4, 4, 3, 1);
		for (int i = 0; i < 4; i++)
			randomSimilar(5, 5, 4, 4, 3, 1, rnd.nextInt(3) + 1,
					rnd.nextInt(3) + 1);

		// TODO: anal tests

		System.err.println("Gen anal");

		for (int i = 0; i < 4; i++) {
			for (int w = 3; w < 5; w++) {
				genAnalTest(w, w, false, false);
				genAnalTest(w, w, false, true);
				genAnalTest(w, w, true, false);
				genAnalTest(w, w, true, true);
			}
		}

		// TODO: Buzdalov's test
		System.err.println("Buzdalov's test");
		geneticsBig();
	}

	public static void main(String[] args) {
		new Tests().gen();
	}
}
