6293256fec 2012-07-14        kinaba: import util;
6293256fec 2012-07-14        kinaba: import game;
9d4aca73fa 2012-07-14        kinaba: import driver;
6293256fec 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: /*
9d4aca73fa 2012-07-14        kinaba: interface Solver
9d4aca73fa 2012-07-14        kinaba: {
9d4aca73fa 2012-07-14        kinaba: 	this(const(Game) g);
9d4aca73fa 2012-07-14        kinaba: 	char single_step();
9d4aca73fa 2012-07-14        kinaba: }
9d4aca73fa 2012-07-14        kinaba: */
9d4aca73fa 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: class Solver_0
9d4aca73fa 2012-07-14        kinaba: {
9d4aca73fa 2012-07-14        kinaba: 	this(const(Game) g) {}
9d4aca73fa 2012-07-14        kinaba: 	char single_step() { return 'W'; }
9d4aca73fa 2012-07-14        kinaba: }
6293256fec 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: class Solver_1
6293256fec 2012-07-14        kinaba: {
9d4aca73fa 2012-07-14        kinaba: 	int g_wc = 0;
9d4aca73fa 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 	Game g;
9d4aca73fa 2012-07-14        kinaba: 	this(const(Game) g)
9d4aca73fa 2012-07-14        kinaba: 	{
9d4aca73fa 2012-07-14        kinaba: 		this.g = g.clone();
9d4aca73fa 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 	char single_step()
9d4aca73fa 2012-07-14        kinaba: 	{
b4aceba693 2012-07-14        kinaba: 		char c = act(g, death_move(g));
9d4aca73fa 2012-07-14        kinaba: 		g.command(c);
9d4aca73fa 2012-07-14        kinaba: 		return c;
9d4aca73fa 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
b4aceba693 2012-07-14        kinaba: 	string death_move(const(Game) g)
b4aceba693 2012-07-14        kinaba: 	{
b4aceba693 2012-07-14        kinaba: 		string death;
b4aceba693 2012-07-14        kinaba: 		foreach(char c; "UDLRW") {
b4aceba693 2012-07-14        kinaba: 			Game gg = g.clone();
b4aceba693 2012-07-14        kinaba: 			gg.command(c);
b4aceba693 2012-07-14        kinaba: 			if( !gg.cleared && gg.dead )
b4aceba693 2012-07-14        kinaba: 				death ~= c;
b4aceba693 2012-07-14        kinaba: 		}
b4aceba693 2012-07-14        kinaba: 		return death;
b4aceba693 2012-07-14        kinaba: 	}
b4aceba693 2012-07-14        kinaba: 
b4aceba693 2012-07-14        kinaba: 	char act(const(Game) g, string death)
9d4aca73fa 2012-07-14        kinaba: 	{
9d4aca73fa 2012-07-14        kinaba: 		const Pos   ro = g.map.robot;
9d4aca73fa 2012-07-14        kinaba: 		const Pos[] la = g.map.lambdas();
9d4aca73fa 2012-07-14        kinaba: 		const Pos   li = g.map.lift;
9d4aca73fa 2012-07-14        kinaba: 
62a5c6c47f 2012-07-14        kinaba: 		Tuple!(char,int)[] cand;
9d4aca73fa 2012-07-14        kinaba: 		char c = 'W';
9d4aca73fa 2012-07-14        kinaba: 		if( la.empty ) {
62a5c6c47f 2012-07-14        kinaba: 			cand = search(g, ro, li, death);
9d4aca73fa 2012-07-14        kinaba: 		} else {
9d4aca73fa 2012-07-14        kinaba: 			foreach(lam; la)
b4aceba693 2012-07-14        kinaba: 				cand ~= search(g, ro, lam, death);
9d4aca73fa 2012-07-14        kinaba: 		}
62a5c6c47f 2012-07-14        kinaba: 		sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
62a5c6c47f 2012-07-14        kinaba: 			if(c1[1] != c2[1])
62a5c6c47f 2012-07-14        kinaba: 				return c1[1] < c2[1];
62a5c6c47f 2012-07-14        kinaba: 			return c1[0] < c2[0];
62a5c6c47f 2012-07-14        kinaba: 		})(cand);
62a5c6c47f 2012-07-14        kinaba: 		c = cand[0][0];
62a5c6c47f 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 		if(c=='W') {
9d4aca73fa 2012-07-14        kinaba: 			g_wc++;
9d4aca73fa 2012-07-14        kinaba: 			if(g_wc > 10)
9d4aca73fa 2012-07-14        kinaba: 				c = 'A';
6293256fec 2012-07-14        kinaba: 		}
9d4aca73fa 2012-07-14        kinaba: 		else
9d4aca73fa 2012-07-14        kinaba: 			g_wc = 0;
9d4aca73fa 2012-07-14        kinaba: 		return c;
6293256fec 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
62a5c6c47f 2012-07-14        kinaba: 	Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death)
9d4aca73fa 2012-07-14        kinaba: 	{
62a5c6c47f 2012-07-14        kinaba: 		bool danger(int y, int x)
62a5c6c47f 2012-07-14        kinaba: 		{
62a5c6c47f 2012-07-14        kinaba: 			if(g.map[y+1,x] == '*')
62a5c6c47f 2012-07-14        kinaba: 				return true;
62a5c6c47f 2012-07-14        kinaba: 			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'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
62a5c6c47f 2012-07-14        kinaba: 			if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
62a5c6c47f 2012-07-14        kinaba: 			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'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
62a5c6c47f 2012-07-14        kinaba: 			if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
62a5c6c47f 2012-07-14        kinaba: 			return false;
62a5c6c47f 2012-07-14        kinaba: 		}
62a5c6c47f 2012-07-14        kinaba: 
5fc8a9c49b 2012-07-14        kinaba: 		// avoid directly below '*'
62a5c6c47f 2012-07-14        kinaba: 		Tuple!(char,int)[] tryA() {
62a5c6c47f 2012-07-14        kinaba: 			const(Pos)[] q = [o];
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
62a5c6c47f 2012-07-14        kinaba: 			if( !danger(o.y,o.x) ) {
62a5c6c47f 2012-07-14        kinaba: 				v[o.y][o.x]=true;
62a5c6c47f 2012-07-14        kinaba: 				for(int step=1; q.length; ++step) {
62a5c6c47f 2012-07-14        kinaba: 					Pos[] q2;
62a5c6c47f 2012-07-14        kinaba: 					foreach(p; q) {
62a5c6c47f 2012-07-14        kinaba: 						int[] dy=[-1,+1,0,0];
62a5c6c47f 2012-07-14        kinaba: 						int[] dx=[0,0,-1,+1];
62a5c6c47f 2012-07-14        kinaba: 						for(int i=0; i<4; ++i) {
62a5c6c47f 2012-07-14        kinaba: 							int y = p.y+dy[i];
62a5c6c47f 2012-07-14        kinaba: 							int x = p.x+dx[i];
62a5c6c47f 2012-07-14        kinaba: 							if(v[y][x]) continue;
62a5c6c47f 2012-07-14        kinaba: 							if(y==s.y && x==s.x) {
62a5c6c47f 2012-07-14        kinaba: 								char c = "UDRL"[i];
62a5c6c47f 2012-07-14        kinaba: 								if( death.count(c) == 0 )
62a5c6c47f 2012-07-14        kinaba: 									return [tuple(c,step)];
62a5c6c47f 2012-07-14        kinaba: 							} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
62a5c6c47f 2012-07-14        kinaba: 								if(danger(y,x))
62a5c6c47f 2012-07-14        kinaba: 									continue;
62a5c6c47f 2012-07-14        kinaba: 								q2 ~= new Pos(y,x);
62a5c6c47f 2012-07-14        kinaba: 								v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 							}
62a5c6c47f 2012-07-14        kinaba: 						}
5fc8a9c49b 2012-07-14        kinaba: 					}
62a5c6c47f 2012-07-14        kinaba: 					q = q2;
5fc8a9c49b 2012-07-14        kinaba: 				}
5fc8a9c49b 2012-07-14        kinaba: 			}
62a5c6c47f 2012-07-14        kinaba: 			return [];
5fc8a9c49b 2012-07-14        kinaba: 		}
5fc8a9c49b 2012-07-14        kinaba: 
5fc8a9c49b 2012-07-14        kinaba: 		// any empty space is my ground
62a5c6c47f 2012-07-14        kinaba: 		Tuple!(char,int)[] tryB() {
62a5c6c47f 2012-07-14        kinaba: 			const(Pos)[] q = [o];
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
62a5c6c47f 2012-07-14        kinaba: 			v[o.y][o.x]=true;
62a5c6c47f 2012-07-14        kinaba: 			for(int step=15; q.length; ++step) {
62a5c6c47f 2012-07-14        kinaba: 				Pos[] q2;
62a5c6c47f 2012-07-14        kinaba: 				foreach(p; q) {
62a5c6c47f 2012-07-14        kinaba: 					int[] dy=[-1,+1,0,0];
62a5c6c47f 2012-07-14        kinaba: 					int[] dx=[0,0,-1,+1];
62a5c6c47f 2012-07-14        kinaba: 					for(int i=0; i<4; ++i) {
62a5c6c47f 2012-07-14        kinaba: 						int y = p.y+dy[i];
62a5c6c47f 2012-07-14        kinaba: 						int x = p.x+dx[i];
62a5c6c47f 2012-07-14        kinaba: 						if(v[y][x]) continue;
62a5c6c47f 2012-07-14        kinaba: 						if(y==s.y && x==s.x) {
62a5c6c47f 2012-07-14        kinaba: 							char c = "UDRL"[i];
62a5c6c47f 2012-07-14        kinaba: 							if( death.count(c) == 0 )
62a5c6c47f 2012-07-14        kinaba: 								return [tuple(c,step)];
62a5c6c47f 2012-07-14        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
62a5c6c47f 2012-07-14        kinaba: 							q2 ~= new Pos(y,x);
62a5c6c47f 2012-07-14        kinaba: 							v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 						}
9d4aca73fa 2012-07-14        kinaba: 					}
9d4aca73fa 2012-07-14        kinaba: 				}
62a5c6c47f 2012-07-14        kinaba: 				q = q2;
9d4aca73fa 2012-07-14        kinaba: 			}
62a5c6c47f 2012-07-14        kinaba: 			return [];
9d4aca73fa 2012-07-14        kinaba: 		}
5fc8a9c49b 2012-07-14        kinaba: 
5fc8a9c49b 2012-07-14        kinaba: 		// push rocks!
62a5c6c47f 2012-07-14        kinaba: 		Tuple!(char,int)[] tryC() {
62a5c6c47f 2012-07-14        kinaba: 			const(Pos)[] q = [o];
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
62a5c6c47f 2012-07-14        kinaba: 			v[o.y][o.x]=true;
62a5c6c47f 2012-07-14        kinaba: 			for(int step=30; q.length; ++step) {
62a5c6c47f 2012-07-14        kinaba: 				Pos[] q2;
62a5c6c47f 2012-07-14        kinaba: 				foreach(p; q) {
62a5c6c47f 2012-07-14        kinaba: 					int[] dy=[-1,+1,0,0];
62a5c6c47f 2012-07-14        kinaba: 					int[] dx=[0,0,-1,+1];
62a5c6c47f 2012-07-14        kinaba: 					for(int i=0; i<4; ++i) {
62a5c6c47f 2012-07-14        kinaba: 						int y = p.y+dy[i];
62a5c6c47f 2012-07-14        kinaba: 						int x = p.x+dx[i];
62a5c6c47f 2012-07-14        kinaba: 						if(v[y][x]) continue;
62a5c6c47f 2012-07-14        kinaba: 						if(y==s.y && x==s.x) {
62a5c6c47f 2012-07-14        kinaba: 							char c = "UDRL"[i];
62a5c6c47f 2012-07-14        kinaba: 							if( death.count(c) == 0 )
62a5c6c47f 2012-07-14        kinaba: 								return [tuple(c,step)];
62a5c6c47f 2012-07-14        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
62a5c6c47f 2012-07-14        kinaba: 							q2 ~= new Pos(y,x);
62a5c6c47f 2012-07-14        kinaba: 							v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 						} 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')) {
62a5c6c47f 2012-07-14        kinaba: 							q2 ~= new Pos(y,x);
62a5c6c47f 2012-07-14        kinaba: 							v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 						}
9d4aca73fa 2012-07-14        kinaba: 					}
9d4aca73fa 2012-07-14        kinaba: 				}
62a5c6c47f 2012-07-14        kinaba: 				q = q2;
9d4aca73fa 2012-07-14        kinaba: 			}
62a5c6c47f 2012-07-14        kinaba: 			return [];
9d4aca73fa 2012-07-14        kinaba: 		}
62a5c6c47f 2012-07-14        kinaba: 		return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max);
9d4aca73fa 2012-07-14        kinaba: 	}
6293256fec 2012-07-14        kinaba: }