#!/usr/bin/env dub
/+ dub.sdl:
	name "solitaire"
	dependency "ae" version="==0.0.2190"
	dependency "x11" version="==1.0.16"
+/

// ---------------------------------------------------------------------------------------------------------------------

import core.thread;

import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.sorting;
import std.bitmanip;
import std.conv;
import std.datetime;
import std.exception;
import std.file;
import std.math;
import std.net.curl;
import std.parallelism;
import std.process;
import std.random;
import std.range;
import std.stdio;
import std.string;

import ae.utils.array;
import ae.utils.graphics.color;
import ae.utils.graphics.im_convert;
import ae.utils.graphics.image;
import ae.utils.math;
import ae.utils.meta;
import ae.utils.regex;

// ---------------------------------------------------------------------------------------------------------------------

// Following coordinates are for a 4K (3840x2160) screen.

enum coordBaseW = 3840;
enum coordBaseH = 2160;

/// Distance, in pixels, from the top of a card to the top of the card it's stacked on
enum cardStackVDistance = 31;

/// Distance, in pixels, from the left edge of a stack of cards to the left edge of the stack of cards next to it.
enum cardStackHDistance = 152;

enum cardFreeCellHDistance = cardStackHDistance;

enum cardFoundationHDistance = cardStackHDistance;

enum cardStackX = 1364; // 163
enum cardStackY = 930;  // 299

enum cardFoundationX = 2124;
enum cardFoundationY = 666;

enum foundationMaxStackHeight = 8; // How many pixels are foundation cards allowed to creep up

enum cardFreeCellX = cardStackX; // Approx.
enum cardFreeCellY = cardFoundationY;  // Approx.

enum cardFlowerX = 1932; // Approx.
enum cardFlowerY = cardFoundationY; // Approx.

enum cardSigilDX = 4;
enum cardSigilDY = 4;
enum cardSigilW = 24;
enum cardSigilH = 20;

enum dragonButtonW = 57;
enum dragonButtonH = dragonButtonW;
enum dragonButtonLeftX = 1820;
enum dragonButton1TopY = 671;
enum dragonButtonVDistance = 83;

enum cardW = 121;
enum cardH = 232;

enum newGameBtnX = 2353;
enum newGameBtnY = 1453;
enum newGameBtnW = 244;
enum newGameBtnH = 45;

enum CardArea
{
	heap,
	freeCell,
	flower,
	foundation,
}

struct CardPos
{
	CardArea area;
	uint column;
	uint depth;
}

struct ScreenCoord { int x, y; }

int hOffset(int w)
{
	return w == 1366 ? -10 : 0;
}

int vOffset(int h)
{
	return h ==  768 ?  50 : 0;
}

ScreenCoord adjustByResolution(ScreenCoord coord, int w, int h)
{
	return ScreenCoord(
		coord.x - (coordBaseW - w) / 2 + hOffset(w),
		coord.y - (coordBaseH - h) / 2 + vOffset(h),
	);
}

ScreenCoord getScreenCoord(CardPos pos)
{
	final switch (pos.area)
	{
		case CardArea.heap:
			return ScreenCoord(
				cardStackX + pos.column * cardStackHDistance,
				cardStackY + pos.depth  * cardStackVDistance,
			);
		case CardArea.freeCell:
			return ScreenCoord(
				cardFreeCellX + pos.column * cardFreeCellHDistance,
				cardFreeCellY,
			);
		case CardArea.flower:
			return ScreenCoord(cardFlowerX, cardFlowerY);
		case CardArea.foundation:
			return ScreenCoord(
				cardFoundationX + pos.column * cardFoundationHDistance,
				cardFoundationY,
			);
	}
}

alias Screen = Image!BGR;

auto getCardImage(Screen screen, CardPos pos, int dy = 0)
{
	auto coord = getScreenCoord(pos).adjustByResolution(screen.w, screen.h);
	coord.x += cardSigilDX;
	coord.y += cardSigilDY;
	coord.y += dy;
	return screen.crop(
		coord.x,
		coord.y,
		coord.x + cardSigilW,
		coord.y + cardSigilH,
	);
}
alias CardImage = typeof(getCardImage(Screen.init, CardPos.init));

// ---------------------------------------------------------------------------------------------------------------------

enum freeCellCount = 3;
enum foundationCount = 3;
enum stackCount = 8;

enum CardSuit : ubyte
{
	empty,
	invalid,
	faceDown,
	flower,
	red,	// Colors are in dragon button order
	green,
	black,
	firstColor = red,
	lastColor = black,
}

enum CardRank : ubyte
{
	none,
	dragon,
	flower,
	rank1,
	rank2,
	rank3,
	rank4,
	rank5,
	rank6,
	rank7,
	rank8,
	rank9,
}

enum colorSuitCount = CardSuit.lastColor - CardSuit.firstColor + 1;
enum digitSuitCount = CardRank.rank9 - CardRank.rank1 + 1;
enum dragonPerSuitCount = 4;

enum initialCardCount = colorSuitCount * (digitSuitCount + dragonPerSuitCount) + 1 /* flower */;
static assert(initialCardCount == 40);

enum initialStackSize = initialCardCount / stackCount;
static assert(initialStackSize == 5);

struct Card
{
	mixin(bitfields!(
		CardSuit, "suit", 4,
		CardRank, "rank", 4,
	));

	static const char[enumLength!CardSuit] suitChars = "_X?FRGB";
	static const char[enumLength!CardRank] rankChars = "_DF123456789";

	string toString() const
	{
		return [suitChars[suit], rankChars[rank]].idup;
	}

	@property string longName() const
	{
		final switch (suit)
		{
			case CardSuit.empty:
				return "(empty)";
			case CardSuit.invalid:
				return "(invalid)";
			case CardSuit.faceDown:
				return "(face down)";
			case CardSuit.flower:
				return "flower card";
			case CardSuit.red:
			case CardSuit.green:
			case CardSuit.black:
				if (rank == CardRank.dragon)
					return "%s %s".format(suit, rank);
				else
					return "%s %s".format(suit, int(rank - CardRank.rank1 + 1));
		}
	}

	this(CardSuit suit, CardRank rank = CardRank.none)
	{
		this.suit = suit;
		this.rank = rank;
	}

	this(string s)
	{
		assert(s.length == 2);
		suit = cast(CardSuit)suitChars.indexOf(s[0]);
		rank = cast(CardRank)rankChars.indexOf(s[1]);
		assert(isValid, "Bad specification: " ~ s);
	}

	bool isValid() const
	{
		return cast(int)suit >= 0 && cast(int)rank >= 0;
	}
}

// ---------------------------------------------------------------------------------------------------------------------

// enum maxStackSize = 15;
enum maxStackSize = initialStackSize + (CardRank.rank9 - CardRank.rank1); // 5 (initial stack size) + 8 (max. cards stackable on top of the initial stack)
static assert(maxStackSize == 13);

struct Stack
{
	ubyte size;
	Card[maxStackSize] cards;
}

struct Game
{
	Stack[stackCount] stacks;
	Card[freeCellCount] freeCells;
	Card[foundationCount] foundations; // so we know what we can discard to there

	string toString() const
	{
		return format(
			"%-(%s %)   %s  %-(%s %)\n\n%-(%-(%s %)\n%)",
			freeCells,
			flowerDiscarded ? Card("FF") : Card.init,
			foundations,
			stacks[].map!((ref stack) => stack.cards[]).array.transposed,
		);
	}

	@property bool flowerDiscarded() const
	{
		foreach (ref stack; stacks)
			foreach (card; stack.cards)
				if (card.suit == CardSuit.flower)
					return false;
		return true;
	}

	@property uint cardsLeft() const
	{
		uint result;
		foreach (ref stack; stacks)
			result += stack.size;
		foreach (card; freeCells)
			result += card.suit >= CardSuit.firstColor ? 1 : 0;
		return result;
	}

	Card getCard(CardPos pos) const
	{
		final switch (pos.area)
		{
			case CardArea.heap:
				return stacks[pos.column].cards[pos.depth];
			case CardArea.freeCell:
				return freeCells[pos.column];
			case CardArea.foundation:
				return foundations[pos.column];
			case CardArea.flower:
				return flowerDiscarded ? Card.init : Card("FF");
		}
	}

	static Game randomGame()
	{
		Game game;
		game.stacks =
			chain(
				iota(CardSuit.firstColor, cast(CardSuit)(CardSuit.lastColor + 1)).map!(suit =>
					chain(
						iota(CardRank.rank1, cast(CardRank)(CardRank.rank9 + 1)),
						iota(dragonPerSuitCount).map!(n => CardRank.dragon),
					)
					.map!(rank => Card(suit, rank))
				)
				.joiner,
				Card("FF").only,
			)
			.array
			.randomCover
			.array
			.chunks(initialStackSize).map!(chunk =>
				Stack(initialStackSize, chain(
						chunk,
						Card.init.repeat(maxStackSize - initialStackSize),
					)
					.array[0..maxStackSize])
			)
			.array;
		return game;
	}
}

enum MoveKind : ubyte
{
	none, // start game
	moveCards,
	slayDragons,
}

/// Terse card position descriptor for moves.
/// 0..stackCount - that stack
/// stackCount..freeCellCount - that free cell
/// freeCellCount - foundation (target only)
alias Place = ubyte;

struct Move
{
	MoveKind kind;

	union
	{
		// MoveKind.moveCards:
		struct
		{
			Place from, to;
			ubyte count;
		}
		// MoveKind.slayDragons:
		struct
		{
			CardSuit suit;
		}
	}

	string toString(lazy string cardStr) const
	{
		final switch (kind)
		{
			case MoveKind.none:
				return "Start the game";
			case MoveKind.moveCards:
			{
				string placeStr(Place p)
				{
					return
						p < stackCount ? format("stack %d", p + 1) :
						p < stackCount + freeCellCount ? format("free cell %d", p - stackCount + 1) :
						format("the foundation");
				}
				return format("Move %s from %s to %s",
					cardStr,
					placeStr(from),
					placeStr(to),
				);
			}		
			case MoveKind.slayDragons:
				return "Slay the %s dragon".format(suit);
		}
	}

	string toString() const
	{
		return toString(count == 1 ? "a card" : format("%s cards", count));
	}

	string toString(const ref Game game) const
	{
		if (count == 1)
			return toString("the " ~ game.getCard(placeToCardPos(from, from, count, game)).longName);
		else
			return toString("%s cards (%s through %s)".format(count,
					game.getCard(placeToCardPos(from, from, count, game)).longName,
					game.getCard(placeToCardPos(from, from, 1, game)).longName));
	}
}

/// Is it allowed to stack the lower card on the upper card?
bool canStack(Card upper, Card lower)
{
	if (lower.rank < CardRank.rank1)
		return false;
	if (upper.suit == lower.suit)
		return false;
	if (upper.rank != lower.rank + 1)
		return false;
	return true;
}

ubyte getFoundationIndex(bool normalized)(CardSuit suit, const ref Game game)
{
	static if (normalized)
	{
		assert(suit >= CardSuit.firstColor && suit <= CardSuit.lastColor);
		return cast(ubyte)(suit - CardSuit.firstColor);
	}
	else
		foreach (ubyte foundationIndex, foundationCard; game.foundations)
			if (foundationCard.suit == suit || foundationCard.suit == CardSuit.empty)
				return foundationIndex;
	assert(false);
}

/// Attempt a move. Return true if successful.
/// If not, do not modify game.
bool tryMove(bool normalized)(Move move, ref Game game)
{
	final switch (move.kind)
	{
		case MoveKind.none:
			assert(false);
		case MoveKind.moveCards:
		{
			assert(move.from != move.to);
			assert(move.count > 0 && move.count <= maxStackSize);

			// Validate and collect source
			Card[] cards;
			if (move.from < stackCount)
			{
				assert(move.count <= game.stacks[move.from].size);
				auto stackSize = game.stacks[move.from].size;
				cards = game.stacks[move.from].cards[stackSize - move.count .. stackSize];
				foreach (i; 0..cards.length-1)
					if (!canStack(cards[i], cards[i+1]))
						return false; // TODO: Optimize? N^2
			}
			else
			{
				assert(move.from < stackCount + freeCellCount);
				auto freeCellIndex = move.from - stackCount;
				assert(move.count == 1);
				if (game.freeCells[freeCellIndex].suit <= CardSuit.faceDown)
					return false;
				cards = (&game.freeCells[freeCellIndex])[0..1];
			}

			// Validate and apply destination
			if (move.to < stackCount)
			{
				auto stackSize = game.stacks[move.to].size;
				if (stackSize)
				{
					if (!canStack(game.stacks[move.to].cards[stackSize-1], cards[0]))
						return false;
				}
				assert(stackSize + move.count <= maxStackSize);
				game.stacks[move.to].cards[stackSize..stackSize+move.count] = cards;
				game.stacks[move.to].size += move.count;
			}
			else
			if (move.to < stackCount + freeCellCount)
			{
				auto freeCellIndex = move.to - stackCount;
				assert(move.count == 1);
				if (game.freeCells[freeCellIndex].suit != CardSuit.empty)
					return false;
				game.freeCells[freeCellIndex] = cards[0];
			}
			else
			{
				assert(move.to == stackCount + freeCellCount);
				assert(move.count == 1);
				size_t foundationIndex = getFoundationIndex!normalized(cards[0].suit, game);
				if (game.foundations[foundationIndex].suit == CardSuit.empty)
				{
					if (cards[0].rank != CardRank.rank1)
						return false;
				}
				else
				{
					assert(game.foundations[foundationIndex].suit == cards[0].suit);
					if (cards[0].rank != game.foundations[foundationIndex].rank + 1)
						return false;
				}
				game.foundations[foundationIndex] = cards[0];
			}

			// Apply source
			if (move.from < stackCount)
			{
				auto stackSize = game.stacks[move.from].size -= move.count;
				game.stacks[move.from].cards[stackSize  .. stackSize + move.count] = Card.init;
			}
			else
			{
				auto freeCellIndex = move.from - stackCount;
				game.freeCells[freeCellIndex] = Card.init;
			}

			return true;
		}
		case MoveKind.slayDragons:
		{
			int haveFreeCellDragon = -1;
			uint exposedDragons;
			foreach (freeCellIndex; 0..freeCellCount)
			{
				auto card = game.freeCells[freeCellIndex];
				if (card.rank == CardRank.dragon && card.suit == move.suit)
				{
					if (haveFreeCellDragon < 0)
						haveFreeCellDragon = freeCellIndex;
					exposedDragons++;
				}
			}
			if (haveFreeCellDragon < 0)
			{
				foreach (freeCellIndex; 0..freeCellCount)
					if (game.freeCells[freeCellIndex].suit == CardSuit.empty)
					{
						haveFreeCellDragon = freeCellIndex;
						break;
					}
			}
			if (haveFreeCellDragon < 0)
				return false;

			foreach (stackIndex; 0..stackCount)
				if (game.stacks[stackIndex].size)
				{
					auto card = game.stacks[stackIndex].cards[game.stacks[stackIndex].size-1];
					if (card.rank == CardRank.dragon && card.suit == move.suit)
						exposedDragons++;
				}
			if (exposedDragons != dragonPerSuitCount)
				return false;

			foreach (freeCellIndex; 0..freeCellCount)
			{
				auto card = &game.freeCells[freeCellIndex];
				if (card.rank == CardRank.dragon && card.suit == move.suit)
					*card = Card.init;
			}
			foreach (stackIndex; 0..stackCount)
				if (game.stacks[stackIndex].size)
				{
					auto card = &game.stacks[stackIndex].cards[game.stacks[stackIndex].size-1];
					if (card.rank == CardRank.dragon && card.suit == move.suit)
					{
						*card = Card.init;
						game.stacks[stackIndex].size--;
					}
				}

			game.freeCells[haveFreeCellDragon].suit = CardSuit.faceDown;
			return true;
		}
	}
}

void findMoves(ref const Game game, void delegate(Move move, ref Game newGame) handler)
{
	Game newGame = game;
	Move move;
	move.kind = MoveKind.moveCards;
	foreach (Place from; 0..stackCount+freeCellCount)
	{
		if (from < stackCount && !game.stacks[from].size)
			continue;

		move.from = from;
		foreach (Place to; 0..stackCount+freeCellCount+1)
			if (from != to)
			{
				move.to = to;
				foreach (ubyte count; 1 .. ((from < stackCount && to < stackCount) ? game.stacks[from].size : 1) + 1)
				{
					move.count = count;
					if (tryMove!true(move, newGame))
					{
						handler(move, newGame);
						newGame = game;
					}
				}
			}
	}

	move.kind = MoveKind.slayDragons;
	foreach (CardSuit suit; CardSuit.firstColor .. cast(CardSuit)(CardSuit.lastColor+1))
	{
		move.suit = suit;
		if (tryMove!true(move, newGame))
		{
			handler(move, newGame);
			newGame = game;
		}
	}
}

// ---------------------------------------------------------------------------------------------------------------------

int imageDiff(CardImage a, CardImage b)
{
	assert(a.w == b.w);
	assert(a.h == b.h);

	ubyte norm(ubyte a, ubyte b)
	{
		auto d = cast(ubyte)abs(int(a) - int(b));
		return d < 50 ? 0 : cast(ubyte)(d - 50);
	}

	int diff;
	foreach (y; 0..a.h)
		foreach (x; 0..a.w)
		{
			diff += norm(a[x, y].r, b[x, y].r);
			diff += norm(a[x, y].g, b[x, y].g);
			diff += norm(a[x, y].b, b[x, y].b);
		}
	return diff;
}

CardImage[Card] cardImages;
CardImage[CardPos] blankImages;

Screen loadScreen(string fileName)
{
	return fileName.read.parseViaIMConvert!BGR;
}

Screen getReference(string fileName, string md5sum)
{
	if (!fileName.exists)
	{
		auto url = "https://dump.thecybershadow.net/" ~ md5sum ~ "/" ~ fileName;
		stderr.writeln("Downloading reference image from " ~ url);
		download(url, fileName);
	}
	return loadScreen(fileName);
}

int windowX, windowY, windowW, windowH;

void focus()
{
	//warpMouse(ScreenCoord(windowW / 2, windowH / 2));
	stderr.writeln("Waiting for game window...");
	auto result = execute(["xdotool", "search", "--sync", "--name", "SHENZHEN I/O", "windowactivate", "getwindowgeometry"]);
	enforce(result.status == 0, "xdotool failed");
	result.output.matchInto(`Window .*
  Position: (\d+),(\d+) \(screen: \d+\)
  Geometry: (\d+)x(\d+)
`, windowX, windowY, windowW, windowH);
	assert(windowW, "Couldn't parse window info: " ~ result.output);
}

Screen captureScreen()
{
	static bool focused;
	if (!focused)
	{
		focus();
		focused = true;
	}
	enum fn = "screen.bmp";
	stderr.writeln("Invoking maim...");
	enforce(spawnProcess(["scrot", "--focused", fn]).wait() == 0, "scrot failed");
	//enforce(spawnProcess(["maim", "--geometry", "%dx%d+%d+%d".format(windowW, windowH, windowX, windowY), fn]).wait() == 0, "maim failed");
	stderr.writeln("Loading screen...");
	return loadScreen(fn);
}

void learn()
{
	stderr.writeln("Learning...");
	auto screen = getReference("reference.png", "3f360f09fc625901366cb724715b8ef4");
	void study(CardPos pos, Card card)
	{
		auto image = getCardImage(screen, pos);
		if (card.suit == CardSuit.empty)
			blankImages[pos] = image;
		else
		if (card in cardImages)
		{
			// stderr.writefln("Duplicate card %s already exists; diff = %d", card, imageDiff(cardImages[card], image));
			// image.toBMP.toFile(card.toString() ~ format("%s", imageDiff(cardImages[card], image)) ~ ".bmp");
		}
		else
		{
			cardImages[card] = image;
			//image.toBMP.toFile(card.toString() ~ ".bmp");
		}
	}

	study(CardPos(CardArea.heap, 0, 0), Card("R3"));
	study(CardPos(CardArea.heap, 0, 1), Card("RD"));
	study(CardPos(CardArea.heap, 0, 2), Card("B5"));
	study(CardPos(CardArea.heap, 0, 3), Card("B6"));
	study(CardPos(CardArea.heap, 0, 4), Card("BD"));

	study(CardPos(CardArea.heap, 1, 0), Card("G2"));
	study(CardPos(CardArea.heap, 1, 1), Card("FF"));
	study(CardPos(CardArea.heap, 1, 2), Card("B7"));
	study(CardPos(CardArea.heap, 1, 3), Card("R6"));

	study(CardPos(CardArea.heap, 2, 0), Card("G9"));
	study(CardPos(CardArea.heap, 2, 1), Card("R8"));
	study(CardPos(CardArea.heap, 2, 2), Card("BD"));
	study(CardPos(CardArea.heap, 2, 3), Card("RD"));
	study(CardPos(CardArea.heap, 2, 4), Card("B8"));

	study(CardPos(CardArea.heap, 3, 0), Card("G5"));
	study(CardPos(CardArea.heap, 3, 1), Card("B9"));
	study(CardPos(CardArea.heap, 3, 2), Card("RD"));
	study(CardPos(CardArea.heap, 3, 3), Card("B2"));
	study(CardPos(CardArea.heap, 3, 4), Card("GD"));

	study(CardPos(CardArea.heap, 4, 0), Card("G6"));
	study(CardPos(CardArea.heap, 4, 1), Card("G3"));
	study(CardPos(CardArea.heap, 4, 2), Card("GD"));
	study(CardPos(CardArea.heap, 4, 3), Card("RD"));
	study(CardPos(CardArea.heap, 4, 4), Card("B4"));

	study(CardPos(CardArea.heap, 5, 0), Card("BD"));
	study(CardPos(CardArea.heap, 5, 1), Card("G4"));
	study(CardPos(CardArea.heap, 5, 2), Card("R1"));
	study(CardPos(CardArea.heap, 5, 3), Card("R7"));
	study(CardPos(CardArea.heap, 5, 4), Card("R9"));

	study(CardPos(CardArea.heap, 6, 0), Card("G1"));
	study(CardPos(CardArea.heap, 6, 1), Card("R2"));
	study(CardPos(CardArea.heap, 6, 2), Card("BD"));
	study(CardPos(CardArea.heap, 6, 3), Card("B3"));
	study(CardPos(CardArea.heap, 6, 4), Card("G7"));

	study(CardPos(CardArea.heap, 7, 0), Card("R5"));
	study(CardPos(CardArea.heap, 7, 1), Card("GD"));
	study(CardPos(CardArea.heap, 7, 2), Card("R4"));
	study(CardPos(CardArea.heap, 7, 3), Card("G8"));
	study(CardPos(CardArea.heap, 7, 4), Card("GD"));

	study(CardPos(CardArea.foundation, 0, 0), Card("B1"));
	// study(CardPos(CardArea.foundation, 1, 0), Card("__"));
	// study(CardPos(CardArea.foundation, 2, 0), Card("__"));

	screen = getReference("reference2.png", "a8cd22a35b5d12f6f06192978353f5eb");

	study(CardPos(CardArea.freeCell, 1, 0), Card("?_"));

	screen = getReference("reference3.png", "22f78ac55347ff4352e2b8ff0766cef4");

	study(CardPos(CardArea.heap, 0, 0), Card("__"));
	study(CardPos(CardArea.heap, 1, 0), Card("__"));
	study(CardPos(CardArea.heap, 2, 0), Card("__"));
	study(CardPos(CardArea.heap, 3, 0), Card("__"));
	study(CardPos(CardArea.heap, 4, 0), Card("__"));
	study(CardPos(CardArea.heap, 5, 0), Card("__"));
	study(CardPos(CardArea.heap, 6, 0), Card("__"));
	study(CardPos(CardArea.heap, 7, 0), Card("__"));

	study(CardPos(CardArea.freeCell, 0, 0), Card("__"));
	study(CardPos(CardArea.freeCell, 1, 0), Card("__"));
	study(CardPos(CardArea.freeCell, 2, 0), Card("__"));

	study(CardPos(CardArea.foundation, 0, 0), Card("__"));
	study(CardPos(CardArea.foundation, 1, 0), Card("__"));
	study(CardPos(CardArea.foundation, 2, 0), Card("__"));

	stderr.writeln("Done learning.");
}

Game recognize(Screen screen)
{
	Card read(CardPos pos)
	{
		foreach (dy; 0 .. (pos.area == CardArea.foundation ? foundationMaxStackHeight : 0) + 1)
		{
			auto image = getCardImage(screen, pos, -dy);
			if (dy == 0 && pos in blankImages && imageDiff(blankImages[pos], image)==0)
				return Card(CardSuit.empty);
			foreach (card, cardImage; cardImages) {
				auto diff = imageDiff(image, cardImage);
				if (diff == 0
				    || diff == 3 && card == Card("G2")
				    || diff == 19 && card == Card("B2")
				    || diff == 4733 && card == Card("R1")
				    || diff == 4722 && card == Card("G1")
				    || diff <= 10247 && card == Card("B1")
				    || diff == 4227 && card == Card("R4")
				    || diff == 3884 && card == Card("G4")
				    || diff == 9832 && card == Card("B4"))
					return card;
		}
		}
		return Card(pos.area == CardArea.heap ? CardSuit.empty : CardSuit.invalid);
	}

	Game game;
	foreach (stack; 0..stackCount)
		foreach (ubyte col; 0..maxStackSize)
		{
			game.stacks[stack].cards[col] = read(CardPos(CardArea.heap, stack, col));
			if (game.stacks[stack].cards[col].suit != CardSuit.empty)
				game.stacks[stack].size = cast(ubyte)(col+1);
		}
	foreach (stack; 0..freeCellCount)
		game.freeCells[stack] = read(CardPos(CardArea.freeCell, stack));
	foreach (stack; 0..foundationCount)
		game.foundations[stack] = read(CardPos(CardArea.foundation, stack));
	writeln(game);
	return game;
}

// ---------------------------------------------------------------------------------------------------------------------

void prepareGame(ref Game game)
{
	Card[enumLength!CardSuit] foundationSuits;
	foreach (card; game.foundations)
		foundationSuits[card.suit] = card;
	foreach (i, ref card; game.foundations)
		card = foundationSuits[CardSuit.firstColor + i];
}

/// Perform any automatic changes after a player move,
/// such as automatically discarding the flower card.
/// Returns the number of such actions done.
uint settleGame(bool gameIsNormalized)(ref Game game)
{
	uint actions;
recheck:
	// Discard flower
	foreach (stackIndex; 0..stackCount)
	{
		auto stackSize = game.stacks[stackIndex].size;
		if (stackSize && game.stacks[stackIndex].cards[stackSize-1].suit == CardSuit.flower)
		{
			game.stacks[stackIndex].cards[stackSize-1] = Card.init;
			game.stacks[stackIndex].size--;
			actions++;
		}
	}
	// Forcibly discard ranks into foundation (also to avoid search space explosion)
	{
		CardRank minRank = CardRank.rank9;
		foreach (card; game.foundations)
			if (minRank > card.rank)
				minRank = card.rank;
		if (minRank < CardRank.rank1)
			minRank = CardRank.rank1;
		minRank++; // at or one above minimal rank

		bool tryCard(Card card)
		{
			if (card.suit >= CardSuit.firstColor)
			{
				size_t foundationIndex = getFoundationIndex!gameIsNormalized(card.suit, game);
				auto foundationCard = &game.foundations[foundationIndex];
				if (card.rank >= CardRank.rank1 && card.rank <= minRank && ((foundationCard.rank == CardRank.none && card.rank == CardRank.rank1) || (card.rank == foundationCard.rank + 1)))
				{
					*foundationCard = card;
					return true;
				}
			}
			return false;
		}

		foreach (stackIndex; 0..stackCount)
		{
			auto stackSize = game.stacks[stackIndex].size;
			if (stackSize)
			{
				auto card = game.stacks[stackIndex].cards[stackSize-1];
				if (tryCard(card))
				{
					game.stacks[stackIndex].cards[stackSize-1] = Card.init;
					game.stacks[stackIndex].size--;
					actions++;
					goto recheck;
				}
			}
		}

		foreach (ref card; game.freeCells)
			if (tryCard(card))
			{
				card = Card.init;
				actions++;
				goto recheck;
			}
	}
	return actions;
}

/// Given a game state, its normalized version, and a move for the normalized version,
/// translate the move to have the same effect on the un-normalized game state.
Move denormalizeMove(ref Game normalizedGame, ref Game unnormalizedGame, Move normalizedMove)
{
	if (normalizedMove.kind != MoveKind.moveCards)
		return normalizedMove;

	ubyte[][Stack] stackOrder;
	ubyte[][Card] freeCellOrder;
	foreach (ubyte stackIndex; 0..stackCount)
		stackOrder[unnormalizedGame.stacks[stackIndex]] ~= stackIndex;
	foreach (ubyte freeCellIndex; 0..freeCellCount)
		freeCellOrder[unnormalizedGame.freeCells[freeCellIndex]] ~= freeCellIndex;

	Place translatePlace(Place place)
	{
		if (place < stackCount)
			return stackOrder[normalizedGame.stacks[place]].queuePop();
		// Free cells
		if (place < stackCount + freeCellCount)
		{
			auto freeCellIndex = place - stackCount;
			return cast(Place)(stackCount + freeCellOrder[normalizedGame.freeCells[freeCellIndex]].queuePop());
		}
		// Foundations
		return place;
	}

	Move denormalizedMove;
	denormalizedMove.kind = normalizedMove.kind;
	denormalizedMove.from = translatePlace(normalizedMove.from);
	denormalizedMove.to = translatePlace(normalizedMove.to);
	denormalizedMove.count = normalizedMove.count;
	return denormalizedMove;
}

/// Normalize functionally equivalent game states into a single canonical representation.
void normalizeGame(ref Game game)
{
	// Sort stuff
	sort(cast(ubyte[])(game.freeCells[]));
	sort(cast(ubyte[Stack.sizeof][])(game.stacks[]));
}

shared int initialCardsLeftThreshold = 3;

Move[] solve(Game origGame)
{
	stderr.writeln("Thinking...");
	auto initGame = origGame;
	prepareGame(initGame);
	normalizeGame(initGame);

	static struct Step
	{
		Game* game;
		Move move;
	}

	// Try to find a solution as quickly as possible.
	// As such, start out in rather greedy mode
	// (cull game states that have many more cards than
	// the best solution so far), and get less greedy
	// if we exhaust the search.
	int cardsLeftThreshold = initialCardsLeftThreshold;

	Step[Game] sawGame;
	Game* solution;

	do
	{
		writefln("Trying with cardsLeftThreshold=%d", cardsLeftThreshold);

		sawGame = null;
		sawGame[initGame] = Step.init;

		solution = null;
		Game[] queue = [initGame];

		int minCardsLeft = initGame.cardsLeft;

		while (queue.length && !solution)
		{
			auto game = queue.ptr;
			queue = queue[1..$];

			if (game.cardsLeft > minCardsLeft + cardsLeftThreshold)
				continue; // Cull!

			findMoves(*game,
				(Move move, ref Game newGame)
				{
					settleGame!true(newGame);
					normalizeGame(newGame);
					if (newGame !in sawGame)
					{
						sawGame[newGame] = Step(game, move);
						queue ~= newGame;
						// if (queue.length % 10000 == 0)
						// 	writeln(newGame.cardsLeft, " ", queue.length);
						// 	writeln(newGame);
						static bool[initialCardCount + 1] sawCardsLeft;
						auto cardsLeft = newGame.cardsLeft;
						if (!sawCardsLeft[cardsLeft])
						{
							writeln(cardsLeft, " ", queue.length);
							sawCardsLeft[cardsLeft] = true;
						}
						if (minCardsLeft > cardsLeft)
							minCardsLeft = cardsLeft;
						if (cardsLeft == 0)
							solution = &queue[$-1];
					}
				});
		}
		if (solution)
			break;
		cardsLeftThreshold += (cardsLeftThreshold/5) + 1;
	} while (cardsLeftThreshold < initialCardCount);

	if (solution)
	{
		writefln("Found solution with cardsLeftThreshold=%d", cardsLeftThreshold);

		Step[] path;
		for (Step step = sawGame[*solution]; step.game; step = sawGame[*step.game])
			path ~= step;
		path.reverse();

		auto denormalizedGame = origGame;

		Move[] denormalizedMoves;
		foreach (ref step; path)
		{
			auto move = denormalizeMove(*step.game, denormalizedGame, step.move);
			denormalizedMoves ~= move;
			auto result = tryMove!false(move, denormalizedGame);
			assert(result);
			settleGame!false(denormalizedGame);
		}
		return denormalizedMoves;
	}
	else
		return null;
}

void printSolution(Game game, Move[] moves)
{
	foreach (move; moves)
	{
		writeln(game);
		writeln(move.toString(game));
		auto result = tryMove!false(move, game);
		assert(result);
		settleGame!false(game);
	}
	writeln(game);
}

// ---------------------------------------------------------------------------------------------------------------------

/// Get the center-most coordinates from which we can start dragging a specific card.
ScreenCoord getCardCoord(CardPos pos, Screen screen, const ref Game game, bool topOnly)
{
	auto coords = getScreenCoord(pos).adjustByResolution(screen.w, screen.h);
	coords.x += cardW / 2;
	coords.y += (topOnly ? cardStackVDistance : cardH) / 2;
	if (pos.area == CardArea.foundation)
	{
		auto card = game.getCard(pos);
		if (card.suit != CardSuit.empty)
			coords.y -= card.rank - CardRank.rank1;
	}
	return coords;
}

CardPos placeToCardPos(Place place, Place from, ubyte depth, const ref Game game)
{
	if (place < stackCount)
		return CardPos(CardArea.heap, place, game.stacks[place].size - depth);
	else
	if (place < stackCount + freeCellCount)
		return CardPos(CardArea.freeCell, place - stackCount, 0);
	else
	if (place == stackCount + freeCellCount)
		return CardPos(CardArea.foundation, getFoundationIndex!false(game.getCard(placeToCardPos(from, from, 1, game)).suit, game), 0);
	else
		assert(false);
}

Duration scaleDuration(Duration d, float f) { return hnsecs(cast(long)(d.total!"hnsecs" * f)); }

enum instantMove = false;
float speed = float.nan;

@property moveDurationBase() { return 200.msecs.scaleDuration(speed); }
@property moveDurationPerPixel() { return 1.msecs.scaleDuration(speed); }
@property moveDelay() { return 0.msecs + 100.msecs.scaleDuration(speed); }
@property clickDelay() { return 20.msecs + 100.msecs.scaleDuration(speed); }

enum settleDelay = 265.msecs; // per action
enum dragonDelay = 400.msecs;
enum waterfallDelay = 2500.msecs;
enum dealDelay = 4500.msecs + 3*settleDelay;

pragma(lib, "X11");

static if (is(typeof({import deimos.X11.X;})))
{
	// Official Deimos bindings
	import deimos.X11.X;
	import deimos.X11.Xlib;
}
else
{
	// Gary Willoughby's bindings (dub build)
	import x11.X;
	import x11.Xlib;
}

void warpMouse(ScreenCoord coord)
{
	//enforce(spawnProcess(["xdotool", "mousemove", text(windowX + coord.x), text(windowY + coord.y)]).wait() == 0, "xdotool failed");

	static Display *dpy;
	if (!dpy)
		dpy = XOpenDisplay(null);
	enforce(dpy, "Can't open display!");

	auto rootWindow = XRootWindow(dpy, 0);
	XSelectInput(dpy, rootWindow, KeyReleaseMask);
	XWarpPointer(dpy, None, rootWindow, 0, 0, 0, 0, windowX + coord.x, windowY + coord.y);
	XFlush(dpy);
}

float ease(float t, float speed)
{
	speed = 0.3f + speed * 0.4f;
	t = t * 2 - 1;
	t = (1-pow(1-abs(t), 1/speed)) * sign(t);
	t = (t + 1) / 2;
	return t;
}

void mouseMove(ScreenCoord coord)
{
	if (!instantMove)
	{
		static int lastX = int.min;
		static int lastY = int.min;
		if (lastX == int.min) lastX = windowW / 2;
		if (lastY == int.min) lastY = windowH / 2;

		auto xSpeed = uniform01!float;
		auto ySpeed = uniform01!float;

		auto moveDuration = moveDurationBase + cast(int)sqrt(float(sqr(coord.x - lastX) + sqr(coord.y - lastY))) * moveDurationPerPixel;

		auto start = MonoTime.currTime();
		auto end = start + moveDuration;
		while (true)
		{
			auto now = MonoTime.currTime();
			if (now >= end)
				break;
			float t = 1f * (now - start).total!"hnsecs" / moveDuration.total!"hnsecs";
			warpMouse(ScreenCoord(
				lastX + cast(int)(ease(t, xSpeed) * (coord.x - lastX)),
				lastY + cast(int)(ease(t, ySpeed) * (coord.y - lastY)),
			));
			Thread.sleep(1.msecs);
		}
		lastX = coord.x;
		lastY = coord.y;
	}
	warpMouse(coord);
	Thread.sleep(moveDelay);
}

void mouseButton(bool down)
{
	// Clicking is hard, just use xdotool
	enforce(spawnProcess(["xdotool", down ? "mousedown" : "mouseup", "1"]).wait() == 0, "xdotool failed");
	Thread.sleep(clickDelay);
}

void executeMove(Screen screen, Move move, const ref Game game)
{
	final switch (move.kind)
	{
		case MoveKind.none:
			assert(false);
		case MoveKind.moveCards:
			mouseMove(getCardCoord(placeToCardPos(move.from, move.from, move.count, game), screen, game, move.count > 1));
			mouseButton(true);
			mouseMove(getCardCoord(placeToCardPos(move.to, move.from, 0, game), screen, game, move.count > 1));
			mouseButton(false);
			break;
		case MoveKind.slayDragons:
			mouseMove(ScreenCoord(
				dragonButtonLeftX + dragonButtonW / 2,
				dragonButton1TopY + dragonButtonH / 2 + dragonButtonVDistance * (move.suit - CardSuit.firstColor),
			).adjustByResolution(screen.w, screen.h));
			mouseButton(true);
			mouseButton(false);
			Thread.sleep(dragonDelay);
			break;
	}
}

void newGame(Screen screen)
{
	auto coord = ScreenCoord(
		newGameBtnX + newGameBtnW / 2,
		newGameBtnY + newGameBtnH / 2,
	).adjustByResolution(screen.w, screen.h);
	if (screen.h == 768)
		coord.y = screen.h - 17 - newGameBtnH / 2;
	mouseMove(coord);
	mouseButton(true);
	mouseButton(false);
}

void runSolitaire(Screen screen)
{
	mouseMove(ScreenCoord(752, screen.h-187));
	mouseButton(true);
	mouseButton(false);
}

void home(Screen screen)
{
	mouseMove(ScreenCoord(20, screen.h/2-55));
	mouseButton(true);
	mouseButton(false);
}

void exitGame(Screen screen)
{
	mouseMove(ScreenCoord(screen.w-57, 56));
	mouseButton(true);
	mouseButton(false);
	warpMouse(ScreenCoord(screen.w + 10, screen.h - 10));
}

void executeSolution(Game game, Move[] moves, Screen screen)
{
	foreach (move; moves)
	{
		writeln(game);
		writeln(move.toString(game));
		executeMove(screen, move, game);
		auto result = tryMove!false(move, game);
		assert(result);
		auto actions = settleGame!false(game);
		Thread.sleep(actions * settleDelay);
	}
	writeln(game);
	Thread.sleep(waterfallDelay);
}

// ---------------------------------------------------------------------------------------------------------------------

void solitaire(string action, in float speed = 1f, int depth = 3)
{
	.speed = speed;
	.initialCardsLeftThreshold = depth;
	switch (action)
	{
		case "solve":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			printSolution(game, moves);
			break;
		}
		case "solve-last":
		{
			learn();
			auto screen = loadScreen("screen.bmp");
			auto game = recognize(screen);
			auto moves = solve(game);
			printSolution(game, moves);
			break;
		}
		case "play":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			executeSolution(game, moves, screen);
			newGame(screen);
			Thread.sleep(dealDelay);
			break;
		}
		case "step":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			if (moves.length)
				executeSolution(game, moves[0..1], screen);
			else
				writeln("No solution");
			break;
		}
		case "playloop":
			learn();
			while (true)
			{
				auto screen = captureScreen();
				auto game = recognize(screen);
				auto moves = solve(game);
				enforce(moves, "Failed to solve the game");
				executeSolution(game, moves, screen);

				newGame(screen);
				Thread.sleep(dealDelay);
			}
		case "demo":
		{
			learn();
			foreach_reverse (n; 0..5)
			{
				writefln("Starting demo in %d...", n);
				Thread.sleep(1.seconds);
			}
			auto shenzhenIO = spawnProcess(["/home/vladimir/.steam/root/steamapps/common/SHENZHEN IO/Shenzhen.bin.x86_64"]);
			Thread.sleep(10.seconds);

			.speed = 2f;
			auto screen = captureScreen();
			runSolitaire(screen);
			Thread.sleep(1.seconds);
			Thread.sleep(dealDelay);

			enum games = 5;
			foreach (n; 0..games)
			{
				.speed = 1f - (1f * n / (games-1));
				screen = captureScreen();
				auto game = recognize(screen);
				auto moves = solve(game);
				enforce(moves, "Failed to solve the game");
				executeSolution(game, moves, screen);

				.speed = 1f;
				if (n + 1 < games)
				{
					newGame(screen);
					Thread.sleep(dealDelay);
				}
			}

			.speed = 2f;
			home(screen);
			exitGame(screen);
			Thread.sleep(5.seconds);
			break;
		}
		case "new-game":
			newGame(captureScreen());
			break;
		case "bench":
		{
			initialCardsLeftThreshold = 0;
			enum games = 10;
			enum runs = 10;
			static void benchFun()
			{
				rndGen.seed(1);
				foreach (n; 0..games)
				{
					auto game = Game.randomGame();
					settleGame!false(game);
					solve(game);
				}
			}
			writeln(benchmark!benchFun(runs)[0].to!Duration);
			break;
		}
		case "solve-random-loop":
		{
			initialCardsLeftThreshold = 0;
			int solved, unsolved;
			foreach (n; long.max.iota.parallel)
			{
				auto game = Game.randomGame();
				settleGame!false(game);
				writeln(game);
				auto moves = solve(game);
				synchronized
				{
					(moves ? solved : unsolved)++;
					auto total = solved+unsolved;
					//printSolution(game, moves);
					writefln("Solved %d/%d (%d%%)", solved, total, 100*solved/total);
				}
			}
			assert(false);
		}
		default:
			throw new Exception("Unknown action: " ~ action);
	}
}

import ae.utils.funopt;
import ae.utils.main;
mixin main!(funopt!solitaire);