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; 9d4aca73fa 2012-07-14 kinaba: 8bc4298777 2012-07-16 kinaba: interface Solver 913d120d42 2012-07-15 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); 913d120d42 2012-07-15 kinaba: } c88611bab8 2012-07-15 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) c4d04122d8 2012-07-14 kinaba: { 879099f815 2012-07-15 kinaba: if(c != 'A') 879099f815 2012-07-15 kinaba: g.command(c); c4d04122d8 2012-07-14 kinaba: } c4d04122d8 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) c4d04122d8 2012-07-14 kinaba: { 9e34cad783 2012-07-16 kinaba: foreach(char c; "UDLR") 9e34cad783 2012-07-16 kinaba: if( death.count(c)==0 && is_one_way_load(g,c) ) 9e34cad783 2012-07-16 kinaba: return c; 9e34cad783 2012-07-16 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); 34bbd14c1a 2012-07-15 kinaba: } 34bbd14c1a 2012-07-15 kinaba: 9f1a8c70cd 2012-07-15 kinaba: // 'higesori' mode b96971b0b6 2012-07-16 kinaba: if( !hi.empty && g.map.num_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: } 9f1a8c70cd 2012-07-15 kinaba: } 9f1a8c70cd 2012-07-15 kinaba: 9fd05a2326 2012-07-16 kinaba: // 'horo-push' mode 9fd05a2326 2012-07-16 kinaba: if(cand.empty) { 9fd05a2326 2012-07-16 kinaba: Pos[] horo = g.map.objects('@'); 9fd05a2326 2012-07-16 kinaba: Pos[] tgt; 9fd05a2326 2012-07-16 kinaba: foreach(p; horo) 9fd05a2326 2012-07-16 kinaba: if((g.map[p.y,p.x-1]==' '||g.map[p.y,p.x-1]=='R')&& 9fd05a2326 2012-07-16 kinaba: (g.map[p.y,p.x+1]==' '||g.map[p.y,p.x+1]=='R') 9fd05a2326 2012-07-16 kinaba: ||(g.map[p.y-1,p.x]==' '||g.map[p.y-1,p.x]=='R')) 9fd05a2326 2012-07-16 kinaba: tgt ~= p; 9fd05a2326 2012-07-16 kinaba: 9fd05a2326 2012-07-16 kinaba: for(int y=1; y<=g.map.H; ++y) 9fd05a2326 2012-07-16 kinaba: for(int x=1; x<=g.map.W; ++x) 9fd05a2326 2012-07-16 kinaba: if(g.map[y,x]=='.') 9fd05a2326 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]) 9fd05a2326 2012-07-16 kinaba: ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1])) 9fd05a2326 2012-07-16 kinaba: tgt ~= new Pos(y,x); 9fd05a2326 2012-07-16 kinaba: 9fd05a2326 2012-07-16 kinaba: if(!tgt.empty) 9fd05a2326 2012-07-16 kinaba: cand ~= search(g, ro, tgt, death, true); 9fd05a2326 2012-07-16 kinaba: } 9fd05a2326 2012-07-16 kinaba: 2f2eff2f03 2012-07-14 kinaba: // 'dig' mode 68c41bdbe0 2012-07-14 kinaba: if(cand.empty) { 9fd05a2326 2012-07-16 kinaba: 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); 68c41bdbe0 2012-07-14 kinaba: } 68c41bdbe0 2012-07-14 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: { 3893826f55 2012-07-16 kinaba: bool very_danger(int y, int x) 3893826f55 2012-07-16 kinaba: { 3893826f55 2012-07-16 kinaba: if(g.map[y,x] == ' ' || g.map[y,x] == 'R') 3893826f55 2012-07-16 kinaba: return false; 3893826f55 2012-07-16 kinaba: if(is_rocky(g.map[y+1,x])) 3893826f55 2012-07-16 kinaba: return true; 3893826f55 2012-07-16 kinaba: return false; 3893826f55 2012-07-16 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) 3893826f55 2012-07-16 kinaba: if(!very_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(); 9e34cad783 2012-07-16 kinaba: } 9e34cad783 2012-07-16 kinaba: 9e34cad783 2012-07-16 kinaba: bool is_one_way_load(in Game g, char c) 9e34cad783 2012-07-16 kinaba: { 9e34cad783 2012-07-16 kinaba: Pos p = g.map.robot.clone(); 9e34cad783 2012-07-16 kinaba: Pos q; 9e34cad783 2012-07-16 kinaba: if(c=='U') q=new Pos(p.y+1,p.x); 9e34cad783 2012-07-16 kinaba: if(c=='D') q=new Pos(p.y-1,p.x); 9e34cad783 2012-07-16 kinaba: if(c=='L') q=new Pos(p.y,p.x-1); 9e34cad783 2012-07-16 kinaba: if(c=='R') q=new Pos(p.y,p.x+1); 9e34cad783 2012-07-16 kinaba: char d = g.map[q]; 9e34cad783 2012-07-16 kinaba: if(!(d==' '||d=='.'||d=='!')) 9e34cad783 2012-07-16 kinaba: return false; 9e34cad783 2012-07-16 kinaba: 9e34cad783 2012-07-16 kinaba: bool found_lambda = false; 9e34cad783 2012-07-16 kinaba: int[4] dy=[-1,+1,0,0]; 9e34cad783 2012-07-16 kinaba: int[4] dx=[0,0,+1,-1]; 9e34cad783 2012-07-16 kinaba: for(;;) 9e34cad783 2012-07-16 kinaba: { 9e34cad783 2012-07-16 kinaba: Pos r = null; 9e34cad783 2012-07-16 kinaba: for(int i=0; i<4; ++i) { 9e34cad783 2012-07-16 kinaba: int y=q.y+dy[i]; 9e34cad783 2012-07-16 kinaba: int x=q.x+dx[i]; 9e34cad783 2012-07-16 kinaba: if(x==p.x && y==p.y) 9e34cad783 2012-07-16 kinaba: continue; 9e34cad783 2012-07-16 kinaba: char e = g.map[y,x]; 9e34cad783 2012-07-16 kinaba: if(e=='#') 9e34cad783 2012-07-16 kinaba: continue; 9e34cad783 2012-07-16 kinaba: if(e==' '||e=='.'||e=='!'||e=='R'||e=='\\') { 9e34cad783 2012-07-16 kinaba: if(r !is null) 9e34cad783 2012-07-16 kinaba: return false; 9e34cad783 2012-07-16 kinaba: r = new Pos(y,x); 9e34cad783 2012-07-16 kinaba: if(e=='\\') 9e34cad783 2012-07-16 kinaba: found_lambda = true; 9e34cad783 2012-07-16 kinaba: continue; 9e34cad783 2012-07-16 kinaba: } 9e34cad783 2012-07-16 kinaba: return false; 9e34cad783 2012-07-16 kinaba: } 9e34cad783 2012-07-16 kinaba: if(r is null) 9e34cad783 2012-07-16 kinaba: break; 9e34cad783 2012-07-16 kinaba: p=q; 9e34cad783 2012-07-16 kinaba: q=r; 9e34cad783 2012-07-16 kinaba: } 9e34cad783 2012-07-16 kinaba: return found_lambda; 2e02a085bf 2012-07-16 kinaba: } 9a93aeb664 2012-07-15 kinaba: } 9a93aeb664 2012-07-15 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 9a93aeb664 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}; 9a93aeb664 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; 9a93aeb664 2012-07-15 kinaba: 9a93aeb664 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() 9a93aeb664 2012-07-15 kinaba: { 9a93aeb664 2012-07-15 kinaba: if(current_game.dead || current_game.cleared) 9a93aeb664 2012-07-15 kinaba: return 'A'; 9a93aeb664 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(); 9a93aeb664 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(); 9a93aeb664 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; 7bd1ed1180 2012-07-16 kinaba: //alias FastSolver MainSolver; 9e34cad783 2012-07-16 kinaba: //alias 徐如林 MainSolver;