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
6293256fec 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: */
6293256fec 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'; }
6293256fec 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: 
9d4aca73fa 2012-07-14        kinaba: 		char c = 'W';
9d4aca73fa 2012-07-14        kinaba: 		if( la.empty ) {
b4aceba693 2012-07-14        kinaba: 			auto r = search(g, ro, li, death);
9d4aca73fa 2012-07-14        kinaba: 			c = r[0];
9d4aca73fa 2012-07-14        kinaba: 		} else {
9d4aca73fa 2012-07-14        kinaba: 			Tuple!(char,int)[] cand;
9d4aca73fa 2012-07-14        kinaba: 			foreach(lam; la)
b4aceba693 2012-07-14        kinaba: 				cand ~= search(g, ro, lam, death);
9d4aca73fa 2012-07-14        kinaba: 			sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
9d4aca73fa 2012-07-14        kinaba: 				if(c1[1] != c2[1])
9d4aca73fa 2012-07-14        kinaba: 					return c1[1] < c2[1];
9d4aca73fa 2012-07-14        kinaba: 				return c1[0] < c2[0];
9d4aca73fa 2012-07-14        kinaba: 			})(cand);
9d4aca73fa 2012-07-14        kinaba: 			c = cand[0][0];
9d4aca73fa 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: 
b4aceba693 2012-07-14        kinaba: 	Tuple!(char,int) search(in Game g, in Pos s, in Pos o, string death)
9d4aca73fa 2012-07-14        kinaba: 	{
5fc8a9c49b 2012-07-14        kinaba: 		// avoid directly below '*'
9d4aca73fa 2012-07-14        kinaba: 		const(Pos)[] q = [o];
9d4aca73fa 2012-07-14        kinaba: 		bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
5fc8a9c49b 2012-07-14        kinaba: 		v[o.y][o.x]=true;
9d4aca73fa 2012-07-14        kinaba: 		for(int step=1; q.length; ++step) {
9d4aca73fa 2012-07-14        kinaba: 			Pos[] q2;
9d4aca73fa 2012-07-14        kinaba: 			foreach(p; q) {
9d4aca73fa 2012-07-14        kinaba: 				int[] dy=[-1,+1,0,0];
9d4aca73fa 2012-07-14        kinaba: 				int[] dx=[0,0,-1,+1];
9d4aca73fa 2012-07-14        kinaba: 				for(int i=0; i<4; ++i) {
9d4aca73fa 2012-07-14        kinaba: 					int y = p.y+dy[i];
9d4aca73fa 2012-07-14        kinaba: 					int x = p.x+dx[i];
9d4aca73fa 2012-07-14        kinaba: 					if(v[y][x]) continue;
9d4aca73fa 2012-07-14        kinaba: 					if(y==s.y && x==s.x) {
b4aceba693 2012-07-14        kinaba: 						char c = "UDRL"[i];
b4aceba693 2012-07-14        kinaba: 						if( death.count(c) == 0 )
b4aceba693 2012-07-14        kinaba: 							return tuple(c,step);
9d4aca73fa 2012-07-14        kinaba: 					} else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
9d4aca73fa 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
9d4aca73fa 2012-07-14        kinaba: 						v[y][x]=true;
9d4aca73fa 2012-07-14        kinaba: 					} else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') {
9d4aca73fa 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
9d4aca73fa 2012-07-14        kinaba: 						v[y][x]=true;
9d4aca73fa 2012-07-14        kinaba: 					}
9d4aca73fa 2012-07-14        kinaba: 				}
9d4aca73fa 2012-07-14        kinaba: 			}
9d4aca73fa 2012-07-14        kinaba: 			q = q2;
9d4aca73fa 2012-07-14        kinaba: 		}
5fc8a9c49b 2012-07-14        kinaba: 
5fc8a9c49b 2012-07-14        kinaba: 		// any empty space is my ground
9d4aca73fa 2012-07-14        kinaba: 		q = [o];
9d4aca73fa 2012-07-14        kinaba: 		v = new bool[][](g.map.H+2, g.map.W+2);
5fc8a9c49b 2012-07-14        kinaba: 		v[o.y][o.x]=true;
9d4aca73fa 2012-07-14        kinaba: 		for(int step=1000; q.length; ++step) {
9d4aca73fa 2012-07-14        kinaba: 			Pos[] q2;
9d4aca73fa 2012-07-14        kinaba: 			foreach(p; q) {
9d4aca73fa 2012-07-14        kinaba: 				int[] dy=[-1,+1,0,0];
9d4aca73fa 2012-07-14        kinaba: 				int[] dx=[0,0,-1,+1];
9d4aca73fa 2012-07-14        kinaba: 				for(int i=0; i<4; ++i) {
9d4aca73fa 2012-07-14        kinaba: 					int y = p.y+dy[i];
9d4aca73fa 2012-07-14        kinaba: 					int x = p.x+dx[i];
9d4aca73fa 2012-07-14        kinaba: 					if(v[y][x]) continue;
9d4aca73fa 2012-07-14        kinaba: 					if(y==s.y && x==s.x) {
b4aceba693 2012-07-14        kinaba: 						char c = "UDRL"[i];
b4aceba693 2012-07-14        kinaba: 						if( death.count(c) == 0 )
b4aceba693 2012-07-14        kinaba: 							return tuple(c,step);
b4aceba693 2012-07-14        kinaba: 					} else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
b4aceba693 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
b4aceba693 2012-07-14        kinaba: 						v[y][x]=true;
b4aceba693 2012-07-14        kinaba: 					} else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) {
5fc8a9c49b 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
5fc8a9c49b 2012-07-14        kinaba: 						v[y][x]=true;
5fc8a9c49b 2012-07-14        kinaba: 					}
5fc8a9c49b 2012-07-14        kinaba: 				}
5fc8a9c49b 2012-07-14        kinaba: 			}
5fc8a9c49b 2012-07-14        kinaba: 			q = q2;
5fc8a9c49b 2012-07-14        kinaba: 		}
5fc8a9c49b 2012-07-14        kinaba: 
5fc8a9c49b 2012-07-14        kinaba: 		// push rocks!
5fc8a9c49b 2012-07-14        kinaba: 		q = [o];
5fc8a9c49b 2012-07-14        kinaba: 		v = new bool[][](g.map.H+2, g.map.W+2);
5fc8a9c49b 2012-07-14        kinaba: 		v[o.y][o.x]=true;
5fc8a9c49b 2012-07-14        kinaba: 		for(int step=2000; q.length; ++step) {
5fc8a9c49b 2012-07-14        kinaba: 			Pos[] q2;
5fc8a9c49b 2012-07-14        kinaba: 			foreach(p; q) {
5fc8a9c49b 2012-07-14        kinaba: 				int[] dy=[-1,+1,0,0];
5fc8a9c49b 2012-07-14        kinaba: 				int[] dx=[0,0,-1,+1];
5fc8a9c49b 2012-07-14        kinaba: 				for(int i=0; i<4; ++i) {
5fc8a9c49b 2012-07-14        kinaba: 					int y = p.y+dy[i];
5fc8a9c49b 2012-07-14        kinaba: 					int x = p.x+dx[i];
5fc8a9c49b 2012-07-14        kinaba: 					if(v[y][x]) continue;
5fc8a9c49b 2012-07-14        kinaba: 					if(y==s.y && x==s.x) {
5fc8a9c49b 2012-07-14        kinaba: 						char c = "UDRL"[i];
5fc8a9c49b 2012-07-14        kinaba: 						if( death.count(c) == 0 )
5fc8a9c49b 2012-07-14        kinaba: 							return tuple(c,step);
5fc8a9c49b 2012-07-14        kinaba: 					} else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
5fc8a9c49b 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
5fc8a9c49b 2012-07-14        kinaba: 						v[y][x]=true;
5fc8a9c49b 2012-07-14        kinaba: 					} else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) {
5fc8a9c49b 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
5fc8a9c49b 2012-07-14        kinaba: 						v[y][x]=true;
5fc8a9c49b 2012-07-14        kinaba: 					} else if(dy[i]==0 && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) {
9d4aca73fa 2012-07-14        kinaba: 						q2 ~= new Pos(y,x);
9d4aca73fa 2012-07-14        kinaba: 						v[y][x]=true;
9d4aca73fa 2012-07-14        kinaba: 					}
9d4aca73fa 2012-07-14        kinaba: 				}
9d4aca73fa 2012-07-14        kinaba: 			}
9d4aca73fa 2012-07-14        kinaba: 			q = q2;
9d4aca73fa 2012-07-14        kinaba: 		}
9d4aca73fa 2012-07-14        kinaba: 		return tuple('W', int.max);
9d4aca73fa 2012-07-14        kinaba: 	}
6293256fec 2012-07-14        kinaba: }