File Annotation
Not logged in
6293256fec 2012-07-14        kinaba: import util;
6293256fec 2012-07-14        kinaba: import game;
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'; }
9d4aca73fa 2012-07-14        kinaba: }
6293256fec 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: class Solver_1
6293256fec 2012-07-14        kinaba: {
c743b817b7 2012-07-14        kinaba: 	int wait_count = 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();
c4d04122d8 2012-07-14        kinaba: 		forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
9d4aca73fa 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 	char single_step()
9d4aca73fa 2012-07-14        kinaba: 	{
c4d04122d8 2012-07-14        kinaba: 		Tuple!(string,int) de = death_move(g);
c4d04122d8 2012-07-14        kinaba: 		char c = act(g, de[0], de[1]);
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: 
c4d04122d8 2012-07-14        kinaba: 	Tuple!(string,int) death_move(const(Game) g)
b4aceba693 2012-07-14        kinaba: 	{
b4aceba693 2012-07-14        kinaba: 		string death;
c4d04122d8 2012-07-14        kinaba: 		int choice = 0;
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;
c4d04122d8 2012-07-14        kinaba: 			else if( gg.map.robot != g.map.robot )
c4d04122d8 2012-07-14        kinaba: 				choice++;
b4aceba693 2012-07-14        kinaba: 		}
c4d04122d8 2012-07-14        kinaba: 		return tuple(death, choice);
b4aceba693 2012-07-14        kinaba: 	}
b4aceba693 2012-07-14        kinaba: 
c4d04122d8 2012-07-14        kinaba: 	Tuple!(Pos, int)[] log;
c4d04122d8 2012-07-14        kinaba: 	bool[][] forbidden_cell;
c4d04122d8 2012-07-14        kinaba: 
c4d04122d8 2012-07-14        kinaba: 	char act(const(Game) g, string death, int breath)
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 ) {
901abf2f53 2012-07-14        kinaba: 			cand = search(g, ro, [li], death);
9d4aca73fa 2012-07-14        kinaba: 		} else {
901abf2f53 2012-07-14        kinaba: 			cand ~= search(g, ro, la, death);
901abf2f53 2012-07-14        kinaba: 		}
68c41bdbe0 2012-07-14        kinaba: 		if(cand.empty) {
68c41bdbe0 2012-07-14        kinaba: 			const(Pos)[] tgt;
68c41bdbe0 2012-07-14        kinaba: 			for(int y=1; y<=g.map.H; ++y)
68c41bdbe0 2012-07-14        kinaba: 			for(int x=1; x<=g.map.W; ++x)
68c41bdbe0 2012-07-14        kinaba: 				if(g.map[y,x]=='.')
68c41bdbe0 2012-07-14        kinaba: 					if(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='*'||g.map[y+1,x+1]=='*'
68c41bdbe0 2012-07-14        kinaba: 					 ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*')
68c41bdbe0 2012-07-14        kinaba: 						tgt ~= new Pos(y,x);
68c41bdbe0 2012-07-14        kinaba: 			cand ~= search(g, ro, tgt, death);
68c41bdbe0 2012-07-14        kinaba: 		}
68c41bdbe0 2012-07-14        kinaba: 
68c41bdbe0 2012-07-14        kinaba: 		if(cand.empty)
68c41bdbe0 2012-07-14        kinaba: 			cand ~= tuple('W',int.max);
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: 
c743b817b7 2012-07-14        kinaba: 		if(death.count(c)) {
c743b817b7 2012-07-14        kinaba: 			foreach(char live; "UDLRWA")
c743b817b7 2012-07-14        kinaba: 				if(death.count(live)==0) {
c743b817b7 2012-07-14        kinaba: 					c=live;
c743b817b7 2012-07-14        kinaba: 					break;
c743b817b7 2012-07-14        kinaba: 				}
c743b817b7 2012-07-14        kinaba: 		}
c743b817b7 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 		if(c=='W') {
c743b817b7 2012-07-14        kinaba: 			wait_count++;
c743b817b7 2012-07-14        kinaba: 			if(wait_count > g.map.H)
9d4aca73fa 2012-07-14        kinaba: 				c = 'A';
9d4aca73fa 2012-07-14        kinaba: 		}
9d4aca73fa 2012-07-14        kinaba: 		else
c743b817b7 2012-07-14        kinaba: 			wait_count = 0;
c743b817b7 2012-07-14        kinaba: 
c4d04122d8 2012-07-14        kinaba: 		bool[char] choice;
c4d04122d8 2012-07-14        kinaba: 		foreach(t; cand)
c4d04122d8 2012-07-14        kinaba: 			choice[t[0]] = true;
c4d04122d8 2012-07-14        kinaba: 		log ~= tuple(ro.clone(), cast(int)choice.length);
c4d04122d8 2012-07-14        kinaba: 		if(log.length > 5)
c4d04122d8 2012-07-14        kinaba: 			log = log[$-5..$];
c4d04122d8 2012-07-14        kinaba: 		int cnt = 0;
c4d04122d8 2012-07-14        kinaba: 		foreach(l; log)
c4d04122d8 2012-07-14        kinaba: 			if(l[0] == log[$-1][0])
c4d04122d8 2012-07-14        kinaba: 				++cnt;
c4d04122d8 2012-07-14        kinaba: 		if( cnt >= 3 && breath==1 ) {
c4d04122d8 2012-07-14        kinaba: 			forbidden_cell[ro.y][ro.x] = true;
c4d04122d8 2012-07-14        kinaba: 		}
c4d04122d8 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 		return c;
6293256fec 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
901abf2f53 2012-07-14        kinaba: 	Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, 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() {
901abf2f53 2012-07-14        kinaba: 			const(Pos)[] q;
901abf2f53 2012-07-14        kinaba: 			foreach(p; gs)
901abf2f53 2012-07-14        kinaba: 				if(!danger(p.y,p.x))
901abf2f53 2012-07-14        kinaba: 					q ~= p;
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
901abf2f53 2012-07-14        kinaba: 			foreach(p; q) v[p.y][p.x]=true;
901abf2f53 2012-07-14        kinaba: 			for(int step=1; q.length; ++step) {
901abf2f53 2012-07-14        kinaba: 				Pos[] q2;
901abf2f53 2012-07-14        kinaba: 				foreach(p; q) {
901abf2f53 2012-07-14        kinaba: 					int[] dy=[-1,+1,0,0];
901abf2f53 2012-07-14        kinaba: 					int[] dx=[0,0,-1,+1];
901abf2f53 2012-07-14        kinaba: 					for(int i=0; i<4; ++i) {
901abf2f53 2012-07-14        kinaba: 						int y = p.y+dy[i];
901abf2f53 2012-07-14        kinaba: 						int x = p.x+dx[i];
901abf2f53 2012-07-14        kinaba: 						if(v[y][x]) continue;
901abf2f53 2012-07-14        kinaba: 						if(y==s.y && x==s.x) {
901abf2f53 2012-07-14        kinaba: 							char c = "UDRL"[i];
901abf2f53 2012-07-14        kinaba: 							if( death.count(c) == 0 )
901abf2f53 2012-07-14        kinaba: 								return [tuple(c,step)];
901abf2f53 2012-07-14        kinaba: 						} else if(forbidden_cell[y][x]){
901abf2f53 2012-07-14        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
901abf2f53 2012-07-14        kinaba: 							if(danger(y,x))
901abf2f53 2012-07-14        kinaba: 								continue;
901abf2f53 2012-07-14        kinaba: 							q2 ~= new Pos(y,x);
901abf2f53 2012-07-14        kinaba: 							v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 						}
5fc8a9c49b 2012-07-14        kinaba: 					}
5fc8a9c49b 2012-07-14        kinaba: 				}
901abf2f53 2012-07-14        kinaba: 				q = q2;
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() {
901abf2f53 2012-07-14        kinaba: 			const(Pos)[] q;
901abf2f53 2012-07-14        kinaba: 			foreach(p; gs) q ~= p;
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
901abf2f53 2012-07-14        kinaba: 			foreach(p; q) v[p.y][p.x]=true;
c4d04122d8 2012-07-14        kinaba: 			for(int step=10; 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)];
c4d04122d8 2012-07-14        kinaba: 						} else if(forbidden_cell[y][x]){
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() {
901abf2f53 2012-07-14        kinaba: 			const(Pos)[] q;
901abf2f53 2012-07-14        kinaba: 			foreach(p; gs) q ~= p;
62a5c6c47f 2012-07-14        kinaba: 			bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
901abf2f53 2012-07-14        kinaba: 			foreach(p; q) v[p.y][p.x]=true;
c4d04122d8 2012-07-14        kinaba: 			for(int step=20; 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)];
c4d04122d8 2012-07-14        kinaba: 						} else if(forbidden_cell[y][x]){
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: 		}
c4d04122d8 2012-07-14        kinaba: 		return tryA() ~ tryB() ~ tryC();
9d4aca73fa 2012-07-14        kinaba: 	}
6293256fec 2012-07-14        kinaba: }