File Annotation
Not logged in
e784787a7c 2012-07-16        kinaba: //
e784787a7c 2012-07-16        kinaba: // http://en.wikipedia.org/wiki/F%C5%ABrinkazan
e784787a7c 2012-07-16        kinaba: //
6293256fec 2012-07-14        kinaba: import util;
6293256fec 2012-07-14        kinaba: import game;
e784787a7c 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: interface Solver
8bc4298777 2012-07-16        kinaba: {
8bc4298777 2012-07-16        kinaba: 	// this(in Game g);
8bc4298777 2012-07-16        kinaba: 	char single_step();
8bc4298777 2012-07-16        kinaba: 	void force(char c);
8bc4298777 2012-07-16        kinaba: }
8bc4298777 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: bool is_spacy(char c)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: bool is_rocky(char c)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	return c=='*' || c=='@';
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: bool is_true_space(char c)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	return c==' ';
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: bool is_trampoline_source(char c)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	return 'A'<=c && c<='I';
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: bool is_rocklambda(char c)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	return is_rocky(c) || c=='\\';
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: Tuple!(string,int) death_move(in Game g)
1110e2f932 2012-07-16        kinaba: {
1110e2f932 2012-07-16        kinaba: 	// TODO: S
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: 	string death;
1110e2f932 2012-07-16        kinaba: 	int breath;
1110e2f932 2012-07-16        kinaba: 	int y = g.map.robot.y;
1110e2f932 2012-07-16        kinaba: 	int x = g.map.robot.x;
1110e2f932 2012-07-16        kinaba: 	int[5] dy_=[+1,-1,0,0,0];
1110e2f932 2012-07-16        kinaba: 	int[5] dx_=[0,0,-1,+1,0];
1110e2f932 2012-07-16        kinaba: 	char[] ds=['U','D','L','R','W'];
1110e2f932 2012-07-16        kinaba: 	for(int i=0; i<5; ++i)
1110e2f932 2012-07-16        kinaba: 	{
1110e2f932 2012-07-16        kinaba: 		bool after_move_death(int y, int x, char tr_tgt)
1110e2f932 2012-07-16        kinaba: 		{
1110e2f932 2012-07-16        kinaba: 			bool is_spacy_t(char c) {
1110e2f932 2012-07-16        kinaba: 				if(is_true_space(c) || c=='R' || c==tr_tgt)
1110e2f932 2012-07-16        kinaba: 					return true;
1110e2f932 2012-07-16        kinaba: 				return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
1110e2f932 2012-07-16        kinaba: 			}
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: 			// check water
1110e2f932 2012-07-16        kinaba: 			if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level )
1110e2f932 2012-07-16        kinaba: 				return true;
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: 			// check falling rock.
1110e2f932 2012-07-16        kinaba: 			int yy=y+1, xx=x;
1110e2f932 2012-07-16        kinaba: 			if( is_spacy_t(g.map[yy, xx]) )
1110e2f932 2012-07-16        kinaba: 			{
1110e2f932 2012-07-16        kinaba: 				if( is_rocky(g.map[yy+1,xx]) )
1110e2f932 2012-07-16        kinaba: 					return true;
1110e2f932 2012-07-16        kinaba: 				if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
1110e2f932 2012-07-16        kinaba: 					if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
1110e2f932 2012-07-16        kinaba: 						return false;
1110e2f932 2012-07-16        kinaba: 					return true;
1110e2f932 2012-07-16        kinaba: 				}
1110e2f932 2012-07-16        kinaba: 				if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
1110e2f932 2012-07-16        kinaba: 					if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
1110e2f932 2012-07-16        kinaba: 						return false;
1110e2f932 2012-07-16        kinaba: 					return true;
1110e2f932 2012-07-16        kinaba: 				}
1110e2f932 2012-07-16        kinaba: 			}
1110e2f932 2012-07-16        kinaba: 			return false;
1110e2f932 2012-07-16        kinaba: 		}
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: 		int dy=dy_[i], dx=dx_[i];
1110e2f932 2012-07-16        kinaba: 		if( is_spacy(g.map[y+dy,x+dx]) || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
1110e2f932 2012-07-16        kinaba: 		{
1110e2f932 2012-07-16        kinaba: 			if( after_move_death(y+dy, x+dx, char.init) )
1110e2f932 2012-07-16        kinaba: 				death ~= ds[i];
1110e2f932 2012-07-16        kinaba: 			else if(ds[i] != 'W')
1110e2f932 2012-07-16        kinaba: 				breath ++;
1110e2f932 2012-07-16        kinaba: 		}
1110e2f932 2012-07-16        kinaba: 		else if( is_trampoline_source(g.map[y+dy,x+dx]) )
1110e2f932 2012-07-16        kinaba: 		{
1110e2f932 2012-07-16        kinaba: 			Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
1110e2f932 2012-07-16        kinaba: 			if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
1110e2f932 2012-07-16        kinaba: 				death ~= ds[i];
1110e2f932 2012-07-16        kinaba: 			else
1110e2f932 2012-07-16        kinaba: 				breath ++;
1110e2f932 2012-07-16        kinaba: 		}
1110e2f932 2012-07-16        kinaba: 		else
1110e2f932 2012-07-16        kinaba: 		{
1110e2f932 2012-07-16        kinaba: 			death ~= ds[i];
1110e2f932 2012-07-16        kinaba: 		}
1110e2f932 2012-07-16        kinaba: 	}
1110e2f932 2012-07-16        kinaba: 
1110e2f932 2012-07-16        kinaba: 	return tuple(death, breath);
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: class Queue(T)
1110e2f932 2012-07-16        kinaba: {
8bc4298777 2012-07-16        kinaba: 	alias Tuple!(T,int) t;
8bc4298777 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 	t[] cur, next;
8bc4298777 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 	void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
8bc4298777 2012-07-16        kinaba: 	bool empty() { return cur.empty; }
8bc4298777 2012-07-16        kinaba: 	t pop() {
8bc4298777 2012-07-16        kinaba: 		t v = cur[0]; cur = cur[1..$];
8bc4298777 2012-07-16        kinaba: 		if(cur.empty) { cur = next; next = null; }
8bc4298777 2012-07-16        kinaba: 		return v;
8bc4298777 2012-07-16        kinaba: 	}
1110e2f932 2012-07-16        kinaba: }
1110e2f932 2012-07-16        kinaba: 
2e02a085bf 2012-07-16        kinaba: ///
2e02a085bf 2012-07-16        kinaba: /// Solver "Mountain":  be immovable like a mountain.
2e02a085bf 2012-07-16        kinaba: ///
e784787a7c 2012-07-16        kinaba: class 不動如山 : Solver
9d4aca73fa 2012-07-14        kinaba: {
879099f815 2012-07-15        kinaba: 	this(in Game g) {}
9d4aca73fa 2012-07-14        kinaba: 	char single_step() { return 'W'; }
c2c105fda0 2012-07-15        kinaba: 	void force(char c) {}
9d4aca73fa 2012-07-14        kinaba: }
a03584f1c6 2012-07-15        kinaba: 
2e02a085bf 2012-07-16        kinaba: ///
2e02a085bf 2012-07-16        kinaba: /// Solver "Forest": shows contemplation.
2e02a085bf 2012-07-16        kinaba: ///
e784787a7c 2012-07-16        kinaba: class 徐如林 : Solver
6293256fec 2012-07-14        kinaba: {
c743b817b7 2012-07-14        kinaba: 	int wait_count = 0;
ea96f24715 2012-07-14        kinaba: 	int choke_count = 0;
6293256fec 2012-07-14        kinaba: 
9d4aca73fa 2012-07-14        kinaba: 	Game g;
879099f815 2012-07-15        kinaba: 	this(in Game g)
9d4aca73fa 2012-07-14        kinaba: 	{
9d4aca73fa 2012-07-14        kinaba: 		this.g = g.clone();
e02668367d 2012-07-15        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]);
879099f815 2012-07-15        kinaba: 		force(c);
9d4aca73fa 2012-07-14        kinaba: 		return c;
9d4aca73fa 2012-07-14        kinaba: 	}
9d4aca73fa 2012-07-14        kinaba: 
c2c105fda0 2012-07-15        kinaba: 	void force(char c)
62a5c6c47f 2012-07-14        kinaba: 	{
879099f815 2012-07-15        kinaba: 		if(c != 'A')
879099f815 2012-07-15        kinaba: 			g.command(c);
62a5c6c47f 2012-07-14        kinaba: 	}
62a5c6c47f 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)
62a5c6c47f 2012-07-14        kinaba: 	{
e02668367d 2012-07-15        kinaba: 		const Pos    ro = g.map.robot;
e02668367d 2012-07-15        kinaba: 		const Pos    li = g.map.lift;
e02668367d 2012-07-15        kinaba: 		Pos[] la = g.map.lambdas();
8acc8e6c78 2012-07-15        kinaba: 		sort!((Pos a,Pos b){
8acc8e6c78 2012-07-15        kinaba: 			int ad=abs(a.y-li.y)+abs(a.x-li.x);
8acc8e6c78 2012-07-15        kinaba: 			int bd=abs(b.y-li.y)+abs(b.x-li.x);
8acc8e6c78 2012-07-15        kinaba: 			return ad>bd;;
8acc8e6c78 2012-07-15        kinaba: 		})(la);
e02668367d 2012-07-15        kinaba: 		Pos[] ra = g.map.razors();
e02668367d 2012-07-15        kinaba: 		const(Pos)[] hi = g.map.objects('W');
62a5c6c47f 2012-07-14        kinaba: 
62a5c6c47f 2012-07-14        kinaba: 		Tuple!(char,int)[] cand;
9d4aca73fa 2012-07-14        kinaba: 		char c = 'W';
f8d6e266eb 2012-07-15        kinaba: 		if( g.map.collected_lambda == g.map.total_lambda ) {
901abf2f53 2012-07-14        kinaba: 			cand = search(g, ro, [li], death);
f8d6e266eb 2012-07-15        kinaba: 		} else if( !la.empty ){
34bbd14c1a 2012-07-15        kinaba: 			cand ~= search(g, ro, la~ra, death);
9f1a8c70cd 2012-07-15        kinaba: 		}
9f1a8c70cd 2012-07-15        kinaba: 
9f1a8c70cd 2012-07-15        kinaba: 		// 'higesori' mode
e02668367d 2012-07-15        kinaba: 		if( !hi.empty && g.map.razor>0 ) {
9f1a8c70cd 2012-07-15        kinaba: 			int his = 0;
9f1a8c70cd 2012-07-15        kinaba: 			for(int dy=-1; dy<=+1; ++dy)
9f1a8c70cd 2012-07-15        kinaba: 			for(int dx=-1; dx<=+1; ++dx)
e02668367d 2012-07-15        kinaba: 				if(g.map[ro.y+dy,ro.x+dx] == 'W')
9f1a8c70cd 2012-07-15        kinaba: 					his++;
9f1a8c70cd 2012-07-15        kinaba: 
9f1a8c70cd 2012-07-15        kinaba: 			if(his>=2 || his==hi.length)
9f1a8c70cd 2012-07-15        kinaba: 				cand = [tuple('S',int.max)];
9f1a8c70cd 2012-07-15        kinaba: 			if(cand.empty) {
9f1a8c70cd 2012-07-15        kinaba: 				const(Pos)[] tgt;
e02668367d 2012-07-15        kinaba: 				for(int y=1; y<=g.map.H; ++y)
e02668367d 2012-07-15        kinaba: 				for(int x=1; x<=g.map.W; ++x)
e02668367d 2012-07-15        kinaba: 					if(g.map[y,x]=='.'||g.map[y,x]==' ') {
9f1a8c70cd 2012-07-15        kinaba: 						his = 0;
9f1a8c70cd 2012-07-15        kinaba: 						for(int dy=-1; dy<=+1; ++dy)
9f1a8c70cd 2012-07-15        kinaba: 						for(int dx=-1; dx<=+1; ++dx)
e02668367d 2012-07-15        kinaba: 							if(g.map[y+dy,x+dx] == 'W')
9f1a8c70cd 2012-07-15        kinaba: 								his++;
9f1a8c70cd 2012-07-15        kinaba: 						if(his>=2)
9f1a8c70cd 2012-07-15        kinaba: 							tgt ~= new Pos(y,x);
9f1a8c70cd 2012-07-15        kinaba: 					}
9f1a8c70cd 2012-07-15        kinaba: 				cand ~= search(g, ro, tgt, death, true);
9f1a8c70cd 2012-07-15        kinaba: 			}
2f2eff2f03 2012-07-14        kinaba: 		}
2f2eff2f03 2012-07-14        kinaba: 
2f2eff2f03 2012-07-14        kinaba: 		// 'dig' mode
68c41bdbe0 2012-07-14        kinaba: 		if(cand.empty) {
68c41bdbe0 2012-07-14        kinaba: 			const(Pos)[] tgt;
e02668367d 2012-07-15        kinaba: 			for(int y=1; y<=g.map.H; ++y)
e02668367d 2012-07-15        kinaba: 			for(int x=1; x<=g.map.W; ++x)
e02668367d 2012-07-15        kinaba: 				if(g.map[y,x]=='.')
1110e2f932 2012-07-16        kinaba: 					if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
1110e2f932 2012-07-16        kinaba: 					 ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
68c41bdbe0 2012-07-14        kinaba: 						tgt ~= new Pos(y,x);
0c10424b3c 2012-07-14        kinaba: 			cand ~= search(g, ro, tgt, death, true);
1110e2f932 2012-07-16        kinaba: 		}
1110e2f932 2012-07-16        kinaba: 
70423f9ad9 2012-07-16        kinaba: 		// 'horo-push' mode
70423f9ad9 2012-07-16        kinaba: 		if(cand.empty) {
70423f9ad9 2012-07-16        kinaba: 			Pos[] horo = g.map.objects('@');
70423f9ad9 2012-07-16        kinaba: 			if(!horo.empty) {
70423f9ad9 2012-07-16        kinaba: 				cand ~= search(g, ro, horo, death, true);
70423f9ad9 2012-07-16        kinaba: 			}
70423f9ad9 2012-07-16        kinaba: 		}
70423f9ad9 2012-07-16        kinaba: 
ea96f24715 2012-07-14        kinaba: 		if(cand.empty) {
ea96f24715 2012-07-14        kinaba: 			choke_count++;
68c41bdbe0 2012-07-14        kinaba: 			cand ~= tuple('W',int.max);
ea96f24715 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: 
2f2eff2f03 2012-07-14        kinaba: 		if(death.count(c) || wait_count>=2) {
2f2eff2f03 2012-07-14        kinaba: 			foreach(char live; "UDLRW")
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: 				}
62a5c6c47f 2012-07-14        kinaba: 		}
c743b817b7 2012-07-14        kinaba: 
ea96f24715 2012-07-14        kinaba: 		if(c == 'W')
c743b817b7 2012-07-14        kinaba: 			wait_count++;
5fc8a9c49b 2012-07-14        kinaba: 		else
c743b817b7 2012-07-14        kinaba: 			wait_count = 0;
9a93aeb664 2012-07-15        kinaba: 		if(wait_count==2)
9a93aeb664 2012-07-15        kinaba: 			c = 'A';
e02668367d 2012-07-15        kinaba: 		if(choke_count >= g.map.H)
ea96f24715 2012-07-14        kinaba: 			c = 'A';
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: 
5fc8a9c49b 2012-07-14        kinaba: 		return c;
5fc8a9c49b 2012-07-14        kinaba: 	}
5fc8a9c49b 2012-07-14        kinaba: 
0c10424b3c 2012-07-14        kinaba: 	Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
5fc8a9c49b 2012-07-14        kinaba: 	{
62a5c6c47f 2012-07-14        kinaba: 		bool danger(int y, int x)
62a5c6c47f 2012-07-14        kinaba: 		{
e02668367d 2012-07-15        kinaba: 			if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
0c10424b3c 2012-07-14        kinaba: 				return false;
1110e2f932 2012-07-16        kinaba: 			if(is_rocky(g.map[y+1,x]))
913d120d42 2012-07-15        kinaba: 				return true;
1110e2f932 2012-07-16        kinaba: 			if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
913d120d42 2012-07-15        kinaba: 			  && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
1110e2f932 2012-07-16        kinaba: 			if(is_rocky(g.map[y+1,x+1]) && is_rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
1110e2f932 2012-07-16        kinaba: 			if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
913d120d42 2012-07-15        kinaba: 			  && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
62a5c6c47f 2012-07-14        kinaba: 				return true;
1110e2f932 2012-07-16        kinaba: 			if(is_rocky(g.map[y,x+1]) && is_rocky(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;
e02668367d 2012-07-15        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;
70423f9ad9 2012-07-16        kinaba: 			bool first_step = 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) {
6c02dd0cf0 2012-07-16        kinaba: 					int[] yyy=[p.y-1,p.y,p.y,p.y+1];
6c02dd0cf0 2012-07-16        kinaba: 					int[] xxx=[p.x,p.x-1,p.x+1,p.x];
6c02dd0cf0 2012-07-16        kinaba: 					string sss="URLD";
70423f9ad9 2012-07-16        kinaba: 					for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
6e4c06b018 2012-07-14        kinaba: 						int y = yyy[i];
6e4c06b018 2012-07-14        kinaba: 						int x = xxx[i];
e02668367d 2012-07-15        kinaba: 						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
d40deaae5a 2012-07-15        kinaba: 							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
6e4c06b018 2012-07-14        kinaba: 								yyy ~= ppp.y;
6e4c06b018 2012-07-14        kinaba: 								xxx ~= ppp.x;
6e4c06b018 2012-07-14        kinaba: 							}
6e4c06b018 2012-07-14        kinaba: 							continue;
6e4c06b018 2012-07-14        kinaba: 						}
901abf2f53 2012-07-14        kinaba: 						if(v[y][x]) continue;
6e4c06b018 2012-07-14        kinaba: 						if(y==s.y && x==s.x && i<4) {
6c02dd0cf0 2012-07-16        kinaba: 							char c = sss[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]){
e02668367d 2012-07-15        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
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: 				}
70423f9ad9 2012-07-16        kinaba: 				first_step = false;
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;
e02668367d 2012-07-15        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;
70423f9ad9 2012-07-16        kinaba: 			bool first_step = true;
84fb0102a2 2012-07-16        kinaba: 			for(int step=8; q.length; ++step) {
62a5c6c47f 2012-07-14        kinaba: 				Pos[] q2;
62a5c6c47f 2012-07-14        kinaba: 				foreach(p; q) {
6c02dd0cf0 2012-07-16        kinaba: 					int[] yyy=[p.y-1,p.y,p.y,p.y+1];
6c02dd0cf0 2012-07-16        kinaba: 					int[] xxx=[p.x,p.x-1,p.x+1,p.x];
6c02dd0cf0 2012-07-16        kinaba: 					string sss="URLD";
70423f9ad9 2012-07-16        kinaba: 					for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
6e4c06b018 2012-07-14        kinaba: 						int y = yyy[i];
6e4c06b018 2012-07-14        kinaba: 						int x = xxx[i];
e02668367d 2012-07-15        kinaba: 						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
d40deaae5a 2012-07-15        kinaba: 							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
6e4c06b018 2012-07-14        kinaba: 								yyy ~= ppp.y;
6e4c06b018 2012-07-14        kinaba: 								xxx ~= ppp.x;
6e4c06b018 2012-07-14        kinaba: 							}
6e4c06b018 2012-07-14        kinaba: 							continue;
6e4c06b018 2012-07-14        kinaba: 						}
62a5c6c47f 2012-07-14        kinaba: 						if(v[y][x]) continue;
6e4c06b018 2012-07-14        kinaba: 						if(y==s.y && x==s.x && i<4) {
6c02dd0cf0 2012-07-16        kinaba: 							char c = sss[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]){
e02668367d 2012-07-15        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
62a5c6c47f 2012-07-14        kinaba: 							q2 ~= new Pos(y,x);
62a5c6c47f 2012-07-14        kinaba: 							v[y][x]=true;
62a5c6c47f 2012-07-14        kinaba: 						}
5fc8a9c49b 2012-07-14        kinaba: 					}
5fc8a9c49b 2012-07-14        kinaba: 				}
70423f9ad9 2012-07-16        kinaba: 				first_step = false;
62a5c6c47f 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: 		// 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;
e02668367d 2012-07-15        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;
70423f9ad9 2012-07-16        kinaba: 			bool first_step = 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) {
6c02dd0cf0 2012-07-16        kinaba: 					int[] yyy=[p.y-1,p.y,p.y,p.y+1];
6c02dd0cf0 2012-07-16        kinaba: 					int[] xxx=[p.x,p.x-1,p.x+1,p.x];
6c02dd0cf0 2012-07-16        kinaba: 					string sss="URLD";
70423f9ad9 2012-07-16        kinaba: 					for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
6e4c06b018 2012-07-14        kinaba: 						int y = yyy[i];
6e4c06b018 2012-07-14        kinaba: 						int x = xxx[i];
1110e2f932 2012-07-16        kinaba: 						if(is_rocky(g.map[p])) {
faa7422a78 2012-07-14        kinaba: 							if(i>=4)continue;
faa7422a78 2012-07-14        kinaba: 							if(y!=p.y)continue;
e02668367d 2012-07-15        kinaba: 							if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
faa7422a78 2012-07-14        kinaba: 						}
e02668367d 2012-07-15        kinaba: 						if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
d40deaae5a 2012-07-15        kinaba: 							foreach(ppp; g.tr.source_pos(g.map[y,x])) {
6e4c06b018 2012-07-14        kinaba: 								yyy ~= ppp.y;
6e4c06b018 2012-07-14        kinaba: 								xxx ~= ppp.x;
6e4c06b018 2012-07-14        kinaba: 							}
6e4c06b018 2012-07-14        kinaba: 							continue;
6e4c06b018 2012-07-14        kinaba: 						}
62a5c6c47f 2012-07-14        kinaba: 						if(v[y][x]) continue;
6e4c06b018 2012-07-14        kinaba: 						if(y==s.y && x==s.x && i<4) {
6c02dd0cf0 2012-07-16        kinaba: 							char c = sss[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]){
1110e2f932 2012-07-16        kinaba: 						} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||is_rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
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: 					}
62a5c6c47f 2012-07-14        kinaba: 				}
70423f9ad9 2012-07-16        kinaba: 				first_step = false;
62a5c6c47f 2012-07-14        kinaba: 				q = q2;
62a5c6c47f 2012-07-14        kinaba: 			}
62a5c6c47f 2012-07-14        kinaba: 			return [];
62a5c6c47f 2012-07-14        kinaba: 		}
0c10424b3c 2012-07-14        kinaba: 		return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
0c10424b3c 2012-07-14        kinaba: 	}
0c10424b3c 2012-07-14        kinaba: }
fec7ddc502 2012-07-14        kinaba: 
2e02a085bf 2012-07-16        kinaba: ///
2e02a085bf 2012-07-16        kinaba: /// Solver "Fire": in raiding and plundering other solvers, be like fire.
2e02a085bf 2012-07-16        kinaba: ///
e784787a7c 2012-07-16        kinaba: class 侵掠如火(SubSolver) : Solver
45b72fc54e 2012-07-15        kinaba: {
c5c6ef71be 2012-07-16        kinaba: 	// Parameters.
1c7a01b7f4 2012-07-16        kinaba: 	int            PredictFuture = 10;
c5c6ef71be 2012-07-16        kinaba: 	const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
c5c6ef71be 2012-07-16        kinaba: 	const          ReplanLength  = 400; // O(PF*RCP*RL*SubSolver.single_step)
9a93aeb664 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	Game      current_game;
9a93aeb664 2012-07-15        kinaba: 	SubSolver sub_solver;
9a93aeb664 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	enum {Tentative, Tentative_Stuck, Fixed};
45b72fc54e 2012-07-15        kinaba: 	string plan;
9a93aeb664 2012-07-15        kinaba: 	int    plan_state;
c5c6ef71be 2012-07-16        kinaba: 	int    replan_limit;
ffac82fc99 2012-07-16        kinaba: 	bool   lambda_getter;
1c7a01b7f4 2012-07-16        kinaba: 	int    clear_improvement = 3;
45b72fc54e 2012-07-15        kinaba: 
45b72fc54e 2012-07-15        kinaba: 	this(in Game g)
45b72fc54e 2012-07-15        kinaba: 	{
9a93aeb664 2012-07-15        kinaba: 		current_game = g.clone();
9a93aeb664 2012-07-15        kinaba: 		plan         = "";
9a93aeb664 2012-07-15        kinaba: 		plan_state   = Tentative;
ff8066db42 2012-07-16        kinaba: 		if(g.map.W*g.map.H <= 400) {
c5c6ef71be 2012-07-16        kinaba: 			RandomChoicePattern = ["UU","UD","UL","UR",
c5c6ef71be 2012-07-16        kinaba: 			                       "DU","DD","DL","DR",
c5c6ef71be 2012-07-16        kinaba: 			                       "LU","LD","LL","LR",
c5c6ef71be 2012-07-16        kinaba: 			                       "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
ff8066db42 2012-07-16        kinaba: 			PredictFuture = 20;
971863e35a 2012-07-16        kinaba: 			clear_improvement = 1;
ff8066db42 2012-07-16        kinaba: 		}
ff8066db42 2012-07-16        kinaba: 		else if(g.map.W*g.map.H <= 4096) {
c5c6ef71be 2012-07-16        kinaba: 			RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
ff8066db42 2012-07-16        kinaba: 			PredictFuture = 10;
ff8066db42 2012-07-16        kinaba: 			clear_improvement = 0;
ff8066db42 2012-07-16        kinaba: 		}
ff8066db42 2012-07-16        kinaba: 		else {
c5c6ef71be 2012-07-16        kinaba: 			RandomChoicePattern = ["U","D","L","R"];
1c7a01b7f4 2012-07-16        kinaba: 			PredictFuture = 10;
ff8066db42 2012-07-16        kinaba: 			clear_improvement = 0;
ff8066db42 2012-07-16        kinaba: 		}
ff8066db42 2012-07-16        kinaba: 
ff8066db42 2012-07-16        kinaba: 		replan_limit = PredictFuture;
45b72fc54e 2012-07-15        kinaba: 	}
45b72fc54e 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	char single_step()
45b72fc54e 2012-07-15        kinaba: 	{
9a93aeb664 2012-07-15        kinaba: 		if(current_game.dead || current_game.cleared)
9a93aeb664 2012-07-15        kinaba: 			return 'A';
45b72fc54e 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		// Make enough prediction.
c5c6ef71be 2012-07-16        kinaba: 		while( plan_state==Tentative && plan.length<replan_limit )
9a93aeb664 2012-07-15        kinaba: 			single_step_predict();
45b72fc54e 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		// If the future is bad, correct.
ffac82fc99 2012-07-16        kinaba: 		if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
9a93aeb664 2012-07-15        kinaba: 			replan();
45b72fc54e 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		// Follow the predicted plan.
9a93aeb664 2012-07-15        kinaba: 		if( plan.empty )
45b72fc54e 2012-07-15        kinaba: 			return 'A';
45b72fc54e 2012-07-15        kinaba: 		char c = plan[0];
45b72fc54e 2012-07-15        kinaba: 		plan = plan[1..$];
ffac82fc99 2012-07-16        kinaba: 		int b_lambda = current_game.map.collected_lambda;
9a93aeb664 2012-07-15        kinaba: 		current_game.command(c);
ffac82fc99 2012-07-16        kinaba: 		int a_lambda = current_game.map.collected_lambda;
ffac82fc99 2012-07-16        kinaba: 		if(b_lambda < a_lambda) lambda_getter = false;
e8aa141dbe 2012-07-15        kinaba: 		return c;
e8aa141dbe 2012-07-15        kinaba: 	}
e8aa141dbe 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	void force(char c)
9a93aeb664 2012-07-15        kinaba: 	{
9a93aeb664 2012-07-15        kinaba: 		if(plan.length>0 && plan[0]==c)
9a93aeb664 2012-07-15        kinaba: 		{
9a93aeb664 2012-07-15        kinaba: 			// If matching the plan, just go forward.
e8aa141dbe 2012-07-15        kinaba: 			plan = plan[1..$];
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 		else
9a93aeb664 2012-07-15        kinaba: 		{
9a93aeb664 2012-07-15        kinaba: 			// Discard the plan, otherwise.
9a93aeb664 2012-07-15        kinaba: 			plan_state = Tentative;
9a93aeb664 2012-07-15        kinaba: 			plan       = "";
9a93aeb664 2012-07-15        kinaba: 			sub_solver = null;
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 		current_game.command(c);
9a93aeb664 2012-07-15        kinaba: 	}
9a93aeb664 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	void single_step_predict()
9a93aeb664 2012-07-15        kinaba: 	{
9a93aeb664 2012-07-15        kinaba: 		if(sub_solver is null) {
9a93aeb664 2012-07-15        kinaba: 			sub_solver = new SubSolver(current_game);
9a93aeb664 2012-07-15        kinaba: 			plan       = "";
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		char c = sub_solver.single_step();
9a93aeb664 2012-07-15        kinaba: 		if(c == 'A')
9a93aeb664 2012-07-15        kinaba: 			plan_state = Tentative_Stuck;
9a93aeb664 2012-07-15        kinaba: 		else {
9a93aeb664 2012-07-15        kinaba: 			plan ~= c;
ff8066db42 2012-07-16        kinaba: 			if(sub_solver.g.cleared) {
ff8066db42 2012-07-16        kinaba: 				if(clear_improvement-->0) {
ff8066db42 2012-07-16        kinaba: 					plan_state = Tentative_Stuck;
ff8066db42 2012-07-16        kinaba: 					replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
ff8066db42 2012-07-16        kinaba: 				} else {
ff8066db42 2012-07-16        kinaba: 					plan_state = Fixed;
ff8066db42 2012-07-16        kinaba: 				}
ff8066db42 2012-07-16        kinaba: 			} else {
ff8066db42 2012-07-16        kinaba: 				plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
ff8066db42 2012-07-16        kinaba: 			}
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 	}
9a93aeb664 2012-07-15        kinaba: 
9a93aeb664 2012-07-15        kinaba: 	void replan()
9a93aeb664 2012-07-15        kinaba: 	{
9a93aeb664 2012-07-15        kinaba: 		// Try to replace every step of the plan by another move.
9a93aeb664 2012-07-15        kinaba: 		Game g = current_game.clone();
c5c6ef71be 2012-07-16        kinaba: 		Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
1c7a01b7f4 2012-07-16        kinaba: 		int insertion_point = plan.length;
c5c6ef71be 2012-07-16        kinaba: 		bool tiebreak_by_turn = false;
ff8066db42 2012-07-16        kinaba: 		int consider_length = min(ReplanLength, g.map.W*g.map.H);
ff8066db42 2012-07-16        kinaba: 		if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
ff8066db42 2012-07-16        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		for(int i=0; i<plan.length; ++i) {
c5c6ef71be 2012-07-16        kinaba: 			foreach(string prefix; RandomChoicePattern)
9a93aeb664 2012-07-15        kinaba: 				if(prefix[0] != plan[i]) {
ff8066db42 2012-07-16        kinaba: 					Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
c5c6ef71be 2012-07-16        kinaba: 					r[1] = plan[0..i] ~ prefix ~ r[1];
c5c6ef71be 2012-07-16        kinaba: 					bool better = false, tbt=false;
c5c6ef71be 2012-07-16        kinaba: 					if(!cand[0].g.cleared && r[0].g.cleared)
c5c6ef71be 2012-07-16        kinaba: 						better = true;
c5c6ef71be 2012-07-16        kinaba: 					else if(cand[0].g.cleared && r[0].g.cleared) {
c5c6ef71be 2012-07-16        kinaba: 						better = cand[0].g.score < r[0].g.score;
c5c6ef71be 2012-07-16        kinaba: 					}
c5c6ef71be 2012-07-16        kinaba: 					else if(!cand[0].g.cleared && !r[0].g.cleared) {
c5c6ef71be 2012-07-16        kinaba: 						if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
c5c6ef71be 2012-07-16        kinaba: 							better = true;
c5c6ef71be 2012-07-16        kinaba: 						else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
c5c6ef71be 2012-07-16        kinaba: 							if(cand[0].g.dead && !r[0].g.dead)
c5c6ef71be 2012-07-16        kinaba: 								better = true;
c5c6ef71be 2012-07-16        kinaba: 							else if(cand[0].g.dead == r[0].g.dead) {
ffac82fc99 2012-07-16        kinaba: 								better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
c5c6ef71be 2012-07-16        kinaba: 								tbt = true;
c5c6ef71be 2012-07-16        kinaba: 							}
c5c6ef71be 2012-07-16        kinaba: 						}
c5c6ef71be 2012-07-16        kinaba: 					}
c5c6ef71be 2012-07-16        kinaba: 					if(better) {
9a93aeb664 2012-07-15        kinaba: 						cand = r;
c5c6ef71be 2012-07-16        kinaba: 						tiebreak_by_turn = true;
1c7a01b7f4 2012-07-16        kinaba: 						insertion_point = i+prefix.length;
ff8066db42 2012-07-16        kinaba: 						if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
1c7a01b7f4 2012-07-16        kinaba: 					}
9a93aeb664 2012-07-15        kinaba: 				}
9a93aeb664 2012-07-15        kinaba: 			g.command(plan[i]);
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 
1c7a01b7f4 2012-07-16        kinaba: 		if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
1c7a01b7f4 2012-07-16        kinaba: 			sub_solver   = cand[0];
1c7a01b7f4 2012-07-16        kinaba: 			plan         = cand[1];
1c7a01b7f4 2012-07-16        kinaba: 			plan_state   = Tentative_Stuck;
ff8066db42 2012-07-16        kinaba: 			replan_limit = min(plan.length - insertion_point, PredictFuture);
1c7a01b7f4 2012-07-16        kinaba: 			lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
1c7a01b7f4 2012-07-16        kinaba: 		} else {
1c7a01b7f4 2012-07-16        kinaba: 			sub_solver   = cand[0];
1c7a01b7f4 2012-07-16        kinaba: 			plan         = cand[1];
1c7a01b7f4 2012-07-16        kinaba: 			plan_state   = (plan.length < PredictFuture ? Fixed : cand[2]);
ff8066db42 2012-07-16        kinaba: 			replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
1c7a01b7f4 2012-07-16        kinaba: 			lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
1c7a01b7f4 2012-07-16        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 	}
9a93aeb664 2012-07-15        kinaba: 
ff8066db42 2012-07-16        kinaba: 	Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
9a93aeb664 2012-07-15        kinaba: 	{
ff8066db42 2012-07-16        kinaba: 		if(consider_length<=0) consider_length = 2;
ff8066db42 2012-07-16        kinaba: 
9a93aeb664 2012-07-15        kinaba: 		SubSolver s = new SubSolver(g);
9a93aeb664 2012-07-15        kinaba: 		foreach(char c; prefix)
9a93aeb664 2012-07-15        kinaba: 			s.force(c);
9a93aeb664 2012-07-15        kinaba: 		string log;
9a93aeb664 2012-07-15        kinaba: 		int state = Tentative;
ff8066db42 2012-07-16        kinaba: 		while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
9a93aeb664 2012-07-15        kinaba: 			char c = s.single_step();
9a93aeb664 2012-07-15        kinaba: 			if( c == 'A' ) {
9a93aeb664 2012-07-15        kinaba: 				state = Tentative_Stuck;
9a93aeb664 2012-07-15        kinaba: 				break;
9a93aeb664 2012-07-15        kinaba: 			}
9a93aeb664 2012-07-15        kinaba: 			log ~= c;
9a93aeb664 2012-07-15        kinaba: 		}
9a93aeb664 2012-07-15        kinaba: 		if(s.g.cleared) state = Fixed;
9a93aeb664 2012-07-15        kinaba: 		else if(s.g.dead) state = Tentative_Stuck;
c5c6ef71be 2012-07-16        kinaba: 		return tuple(s, log, state);
c5c6ef71be 2012-07-16        kinaba: 	}
c5c6ef71be 2012-07-16        kinaba: }
c5c6ef71be 2012-07-16        kinaba: 
2e02a085bf 2012-07-16        kinaba: ///
2e02a085bf 2012-07-16        kinaba: /// Solver "Wind": let your rapidity be that of the wind.
2e02a085bf 2012-07-16        kinaba: ///
50fc08d883 2012-07-16        kinaba: class 疾如風(bool UP) : Solver
971863e35a 2012-07-16        kinaba: {
971863e35a 2012-07-16        kinaba: 	Game g;
971863e35a 2012-07-16        kinaba: 	this(in Game g)
971863e35a 2012-07-16        kinaba: 	{
971863e35a 2012-07-16        kinaba: 		this.g = g.clone();
971863e35a 2012-07-16        kinaba: 	}
971863e35a 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 	string plan;
8bc4298777 2012-07-16        kinaba: 
971863e35a 2012-07-16        kinaba: 	char single_step()
971863e35a 2012-07-16        kinaba: 	{
b4c948b5ca 2012-07-16        kinaba: 		auto dm = death_move(g);
8bc4298777 2012-07-16        kinaba: 		if( plan.empty || dm[0].count(plan[0]) ) {
8bc4298777 2012-07-16        kinaba: 			plan = think(g, dm[0]);
8bc4298777 2012-07-16        kinaba: 			if( plan.empty )
8bc4298777 2012-07-16        kinaba: 				plan = "W";
8bc4298777 2012-07-16        kinaba: 		}
b4c948b5ca 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 		char c = plan[0];
8bc4298777 2012-07-16        kinaba: 		plan = plan[1..$];
8bc4298777 2012-07-16        kinaba: 
b4c948b5ca 2012-07-16        kinaba: 		if(c == 'W') {
b4c948b5ca 2012-07-16        kinaba: 			wait_counter++;
b4c948b5ca 2012-07-16        kinaba: 			if(dm[0].count(c) || wait_counter>=3) {
b4c948b5ca 2012-07-16        kinaba: 				c = 'A';
b4c948b5ca 2012-07-16        kinaba: 				foreach(char cc; "DLRU")
b4c948b5ca 2012-07-16        kinaba: 					if(dm[0].count(cc) == 0)
b4c948b5ca 2012-07-16        kinaba: 						c = cc;
b4c948b5ca 2012-07-16        kinaba: 			}
b4c948b5ca 2012-07-16        kinaba: 			if(wait_counter > 20)
b4c948b5ca 2012-07-16        kinaba: 				c = 'A';
b4c948b5ca 2012-07-16        kinaba: 		} else {
b4c948b5ca 2012-07-16        kinaba: 			wait_counter = 0;
b4c948b5ca 2012-07-16        kinaba: 		}
971863e35a 2012-07-16        kinaba: 		if(c != 'A')
971863e35a 2012-07-16        kinaba: 			g.command(c);
971863e35a 2012-07-16        kinaba: 		return c;
971863e35a 2012-07-16        kinaba: 	}
971863e35a 2012-07-16        kinaba: 
971863e35a 2012-07-16        kinaba: 	void force(char c)
971863e35a 2012-07-16        kinaba: 	{
971863e35a 2012-07-16        kinaba: 		if(c != 'A')
971863e35a 2012-07-16        kinaba: 			g.command(c);
971863e35a 2012-07-16        kinaba: 	}
971863e35a 2012-07-16        kinaba: 
b4c948b5ca 2012-07-16        kinaba: 	int wait_counter = 0;
971863e35a 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 	string think(in Game g, string death)
b4c948b5ca 2012-07-16        kinaba: 	{
971863e35a 2012-07-16        kinaba: 		auto Q = new Queue!(Tuple!(Pos,Pos));
971863e35a 2012-07-16        kinaba: 		Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
971863e35a 2012-07-16        kinaba: 		Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
971863e35a 2012-07-16        kinaba: 		while(!Q.empty) {
971863e35a 2012-07-16        kinaba: 			auto tup = Q.pop();
971863e35a 2012-07-16        kinaba: 			Pos  p    = tup[0][0];
971863e35a 2012-07-16        kinaba: 			Pos  prev = tup[0][1];
971863e35a 2012-07-16        kinaba: 			int  dist = tup[1];
971863e35a 2012-07-16        kinaba: 			if(V[p.y][p.x])
971863e35a 2012-07-16        kinaba: 				continue;
971863e35a 2012-07-16        kinaba: 			V[p.y][p.x] = prev;
971863e35a 2012-07-16        kinaba: 			if(g.map[p]=='\\' || g.map[p]=='O')
971863e35a 2012-07-16        kinaba: 			{
8bc4298777 2012-07-16        kinaba: 				char[] trace;
971863e35a 2012-07-16        kinaba: 				for(;;) {
8bc4298777 2012-07-16        kinaba: 					Pos q = V[p.y][p.x];
8bc4298777 2012-07-16        kinaba: 					trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L') :
8bc4298777 2012-07-16        kinaba: 					                     (q.y<p.y ? 'U' : 'D'));
8bc4298777 2012-07-16        kinaba: 					if(q == g.map.robot) {
8bc4298777 2012-07-16        kinaba: 						reverse(trace);
8bc4298777 2012-07-16        kinaba: 						return trace.idup;
8bc4298777 2012-07-16        kinaba: 					}
971863e35a 2012-07-16        kinaba: 					p=q;
971863e35a 2012-07-16        kinaba: 				}
971863e35a 2012-07-16        kinaba: 			}
971863e35a 2012-07-16        kinaba: 
50fc08d883 2012-07-16        kinaba: 			int[4] dy=UP ? [+1,0,0,-1]       : [-1,+1,0,0];
50fc08d883 2012-07-16        kinaba: 			int[4] dx=UP ? [0,-1,+1,0]       : [0,0,-1,+1];
50fc08d883 2012-07-16        kinaba: 			char[] ds=UP ? ['U','L','R','D'] : ['D','U','L','R'];
b4c948b5ca 2012-07-16        kinaba: 			for(int i=0; i<4; ++i) {
b4c948b5ca 2012-07-16        kinaba: 				if(g.map.robot==p && death.count(ds[i]))
b4c948b5ca 2012-07-16        kinaba: 					continue;
971863e35a 2012-07-16        kinaba: 				int y=p.y+dy[i], x=p.x+dx[i];
84fb0102a2 2012-07-16        kinaba: 				if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O'||g.map[y,x]=='!')&&!V[y][x]) {
971863e35a 2012-07-16        kinaba: 					Q.push(tuple(new Pos(y,x),p), dist+1);
971863e35a 2012-07-16        kinaba: 				}
971863e35a 2012-07-16        kinaba: 			}
971863e35a 2012-07-16        kinaba: 		}
b4c948b5ca 2012-07-16        kinaba: 
8bc4298777 2012-07-16        kinaba: 		return "";
8bc4298777 2012-07-16        kinaba: 	}
8bc4298777 2012-07-16        kinaba: }
8bc4298777 2012-07-16        kinaba: 
b2ea244589 2012-07-16        kinaba: class Switcher
b2ea244589 2012-07-16        kinaba: {
b2ea244589 2012-07-16        kinaba: 	this(in Game g)
b2ea244589 2012-07-16        kinaba: 	{
b2ea244589 2012-07-16        kinaba: 		if(g.map.W*g.map.H <= 1600)
b2ea244589 2012-07-16        kinaba: 			sub_solver = new 侵掠如火!(徐如林)(g);
b2ea244589 2012-07-16        kinaba: 		else
50fc08d883 2012-07-16        kinaba: 			sub_solver = new 侵掠如火!(疾如風!(true))(g);
b2ea244589 2012-07-16        kinaba: 	}
b2ea244589 2012-07-16        kinaba: 	char single_step() { return sub_solver.single_step(); }
b2ea244589 2012-07-16        kinaba: 	void force(char c) { return sub_solver.force(c); }
b2ea244589 2012-07-16        kinaba: 
b2ea244589 2012-07-16        kinaba: 	private Solver sub_solver;
b2ea244589 2012-07-16        kinaba: }
b2ea244589 2012-07-16        kinaba: 
50fc08d883 2012-07-16        kinaba: alias 侵掠如火!(疾如風!(false)) FastSolver;
1b261bd13b 2012-07-16        kinaba: 
50fc08d883 2012-07-16        kinaba: alias Switcher MainSolver;
50fc08d883 2012-07-16        kinaba: //alias 侵掠如火!(徐如林) MainSolver;