import util;
import game;
import driver;

/*
interface Solver
{
	this(const(Game) g);
	char single_step();
}
*/

class Solver_0
{
	this(const(Game) g) {}
	char single_step() { return 'W'; }
}

class Solver_1
{
	int g_wc = 0;

	Game g;
	this(const(Game) g)
	{
		this.g = g.clone();
	}

	char single_step()
	{
		char c = act(g, death_move(g));
		g.command(c);
		return c;
	}

	string death_move(const(Game) g)
	{
		string death;
		foreach(char c; "UDLRW") {
			Game gg = g.clone();
			gg.command(c);
			if( !gg.cleared && gg.dead )
				death ~= c;
		}
		return death;
	}

	char act(const(Game) g, string death)
	{
		const Pos   ro = g.map.robot;
		const Pos[] la = g.map.lambdas();
		const Pos   li = g.map.lift;

		Tuple!(char,int)[] cand;
		char c = 'W';
		if( la.empty ) {
			cand = search(g, ro, li, death);
		} else {
			foreach(lam; la)
				cand ~= search(g, ro, lam, death);
		}
		sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
			if(c1[1] != c2[1])
				return c1[1] < c2[1];
			return c1[0] < c2[0];
		})(cand);
		c = cand[0][0];

		if(c=='W') {
			g_wc++;
			if(g_wc > 10)
				c = 'A';
		}
		else
			g_wc = 0;
		return c;
	}

	Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death)
	{
		bool danger(int y, int x)
		{
			if(g.map[y+1,x] == '*')
				return true;
			if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
				return true;
			if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
				return true;
			if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
				return true;
			return false;
		}

		// avoid directly below '*'
		Tuple!(char,int)[] tryA() {
			const(Pos)[] q = [o];
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			if( !danger(o.y,o.x) ) {
				v[o.y][o.x]=true;
				for(int step=1; q.length; ++step) {
					Pos[] q2;
					foreach(p; q) {
						int[] dy=[-1,+1,0,0];
						int[] dx=[0,0,-1,+1];
						for(int i=0; i<4; ++i) {
							int y = p.y+dy[i];
							int x = p.x+dx[i];
							if(v[y][x]) continue;
							if(y==s.y && x==s.x) {
								char c = "UDRL"[i];
								if( death.count(c) == 0 )
									return [tuple(c,step)];
							} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
								if(danger(y,x))
									continue;
								q2 ~= new Pos(y,x);
								v[y][x]=true;
							}
						}
					}
					q = q2;
				}
			}
			return [];
		}

		// any empty space is my ground
		Tuple!(char,int)[] tryB() {
			const(Pos)[] q = [o];
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			v[o.y][o.x]=true;
			for(int step=15; q.length; ++step) {
				Pos[] q2;
				foreach(p; q) {
					int[] dy=[-1,+1,0,0];
					int[] dx=[0,0,-1,+1];
					for(int i=0; i<4; ++i) {
						int y = p.y+dy[i];
						int x = p.x+dx[i];
						if(v[y][x]) continue;
						if(y==s.y && x==s.x) {
							char c = "UDRL"[i];
							if( death.count(c) == 0 )
								return [tuple(c,step)];
						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}

		// push rocks!
		Tuple!(char,int)[] tryC() {
			const(Pos)[] q = [o];
			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
			v[o.y][o.x]=true;
			for(int step=30; q.length; ++step) {
				Pos[] q2;
				foreach(p; q) {
					int[] dy=[-1,+1,0,0];
					int[] dx=[0,0,-1,+1];
					for(int i=0; i<4; ++i) {
						int y = p.y+dy[i];
						int x = p.x+dx[i];
						if(v[y][x]) continue;
						if(y==s.y && x==s.x) {
							char c = "UDRL"[i];
							if( death.count(c) == 0 )
								return [tuple(c,step)];
						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						} else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) {
							q2 ~= new Pos(y,x);
							v[y][x]=true;
						}
					}
				}
				q = q2;
			}
			return [];
		}
		return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max);
	}
}
