6293256fec 2012-07-14 kinaba: import util; 6293256fec 2012-07-14 kinaba: import game; 6293256fec 2012-07-14 kinaba: c88611bab8 2012-07-15 kinaba: bool rocky(char c){ return c=='*'||c=='@'; } c88611bab8 2012-07-15 kinaba: 9d4aca73fa 2012-07-14 kinaba: class Solver_0 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: 9d4aca73fa 2012-07-14 kinaba: class Solver_1 6293256fec 2012-07-14 kinaba: { c743b817b7 2012-07-14 kinaba: int wait_count = 0; ea96f24715 2012-07-14 kinaba: int choke_count = 0; 9d4aca73fa 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; c2c105fda0 2012-07-15 kinaba: } c2c105fda0 2012-07-15 kinaba: c2c105fda0 2012-07-15 kinaba: void force(char c) c2c105fda0 2012-07-15 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!(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; e02668367d 2012-07-15 kinaba: else if( gg.map.robot != g.map.robot ) c4d04122d8 2012-07-14 kinaba: choice++; 2f2eff2f03 2012-07-14 kinaba: else if( c != 'W' ) // meaningless move 2f2eff2f03 2012-07-14 kinaba: death ~= c; 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: { 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'); 9d4aca73fa 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: } 68c41bdbe0 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]=='.') c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y+1,x])||rocky(g.map[y+1,x-1])||rocky(g.map[y+1,x+1]) c88611bab8 2012-07-15 kinaba: ||rocky(g.map[y,x+1])||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); c4d04122d8 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: } 9d4aca73fa 2012-07-14 kinaba: } c743b817b7 2012-07-14 kinaba: ea96f24715 2012-07-14 kinaba: if(c == 'W') c743b817b7 2012-07-14 kinaba: wait_count++; 9d4aca73fa 2012-07-14 kinaba: else c743b817b7 2012-07-14 kinaba: wait_count = 0; 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: 9d4aca73fa 2012-07-14 kinaba: return c; 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 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) 9d4aca73fa 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; c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y+1,x])) c88611bab8 2012-07-15 kinaba: return true; c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g.map[y,x-1])) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y+1,x+1]) && rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||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; c88611bab8 2012-07-15 kinaba: if(rocky(g.map[y,x+1]) && 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; 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) { 6e4c06b018 2012-07-14 kinaba: int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 6e4c06b018 2012-07-14 kinaba: int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 6e4c06b018 2012-07-14 kinaba: for(int i=0; i<yyy.length; ++i) { 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') { e02668367d 2012-07-15 kinaba: foreach(ppp; g.map.tr_source[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) { 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]){ 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: } 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; 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) { 6e4c06b018 2012-07-14 kinaba: int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 6e4c06b018 2012-07-14 kinaba: int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 6e4c06b018 2012-07-14 kinaba: for(int i=0; i<yyy.length; ++i) { 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') { e02668367d 2012-07-15 kinaba: foreach(ppp; g.map.tr_source[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) { 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]){ 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: } b4aceba693 2012-07-14 kinaba: } b4aceba693 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: q = q2; b4aceba693 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: return []; b4aceba693 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; 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) { 6e4c06b018 2012-07-14 kinaba: int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 6e4c06b018 2012-07-14 kinaba: int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 6e4c06b018 2012-07-14 kinaba: for(int i=0; i<yyy.length; ++i) { 6e4c06b018 2012-07-14 kinaba: int y = yyy[i]; 6e4c06b018 2012-07-14 kinaba: int x = xxx[i]; c88611bab8 2012-07-15 kinaba: if(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') { e02668367d 2012-07-15 kinaba: foreach(ppp; g.map.tr_source[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) { 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]){ c88611bab8 2012-07-15 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||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: } 9d4aca73fa 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: q = q2; 6293256fec 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: 45b72fc54e 2012-07-15 kinaba: class Solver_2(Solver) 45b72fc54e 2012-07-15 kinaba: { 45b72fc54e 2012-07-15 kinaba: string plan; e8aa141dbe 2012-07-15 kinaba: bool plan_broken = true; 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: Game g; 45b72fc54e 2012-07-15 kinaba: this(in Game g) 45b72fc54e 2012-07-15 kinaba: { 45b72fc54e 2012-07-15 kinaba: this.g = g.clone(); 45b72fc54e 2012-07-15 kinaba: make_plan(g); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: Tuple!(Solver,string) run_sub_solver(in Game g) 45b72fc54e 2012-07-15 kinaba: { 45b72fc54e 2012-07-15 kinaba: string log; 45b72fc54e 2012-07-15 kinaba: auto s = new Solver(g); e02668367d 2012-07-15 kinaba: while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) { 45b72fc54e 2012-07-15 kinaba: char c = s.single_step(); 45b72fc54e 2012-07-15 kinaba: if( c == 'A' ) 45b72fc54e 2012-07-15 kinaba: break; 45b72fc54e 2012-07-15 kinaba: log ~= c; 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: while(log.length>0 && log[$-1]=='W') 45b72fc54e 2012-07-15 kinaba: log.length--; 45b72fc54e 2012-07-15 kinaba: return tuple(s, log); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: void make_plan(in Game g) { e8aa141dbe 2012-07-15 kinaba: plan_broken = false; 45b72fc54e 2012-07-15 kinaba: Tuple!(Solver,string) x = run_sub_solver(g); 45b72fc54e 2012-07-15 kinaba: plan = x[1]; 45b72fc54e 2012-07-15 kinaba: if(x[0].g.cleared) 45b72fc54e 2012-07-15 kinaba: return; 45b72fc54e 2012-07-15 kinaba: modify_plan(g, x[0].g.score); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: void modify_plan(in Game ini, long unmod) 45b72fc54e 2012-07-15 kinaba: { 45b72fc54e 2012-07-15 kinaba: int bp = max(0, (cast(int)plan.length)-10); 45b72fc54e 2012-07-15 kinaba: Game g = ini.clone(); 45b72fc54e 2012-07-15 kinaba: for(int i=0; i<bp; ++i) g.command(plan[i]); 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: Tuple!(string,long) cand = tuple(plan, unmod); 45b72fc54e 2012-07-15 kinaba: for(int i=bp; i<plan.length; ++i) { 0d078369c8 2012-07-15 kinaba: foreach(string c; ["U","D","L","R","UD","DU","LR","RL"]) 0d078369c8 2012-07-15 kinaba: if(c[0] != plan[i]) { 45b72fc54e 2012-07-15 kinaba: Tuple!(string,long) zz = try_plan(c, g); 45b72fc54e 2012-07-15 kinaba: if(cand[1]<zz[1]) 45b72fc54e 2012-07-15 kinaba: cand = tuple(plan[0..i]~c~zz[0], zz[1]); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: g.command(plan[i]); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: plan = cand[0]; 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 0d078369c8 2012-07-15 kinaba: Tuple!(string,long) try_plan(string c, in Game g) 45b72fc54e 2012-07-15 kinaba: { 45b72fc54e 2012-07-15 kinaba: Game gg = g.clone(); 0d078369c8 2012-07-15 kinaba: foreach(cc;c)gg.command(cc); 45b72fc54e 2012-07-15 kinaba: Tuple!(Solver, string) x = run_sub_solver(gg); 45b72fc54e 2012-07-15 kinaba: return tuple(x[1], x[0].g.score); 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: char single_step() { e8aa141dbe 2012-07-15 kinaba: if(plan_broken) e8aa141dbe 2012-07-15 kinaba: make_plan(g); 45b72fc54e 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..$]; 45b72fc54e 2012-07-15 kinaba: g.command(c); 45b72fc54e 2012-07-15 kinaba: return c; 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: 45b72fc54e 2012-07-15 kinaba: void force(char c) { 45b72fc54e 2012-07-15 kinaba: g.command(c); e8aa141dbe 2012-07-15 kinaba: if(plan.length==0 || plan[0]!=c) { e8aa141dbe 2012-07-15 kinaba: plan = ""; e8aa141dbe 2012-07-15 kinaba: plan_broken = true; e8aa141dbe 2012-07-15 kinaba: } e8aa141dbe 2012-07-15 kinaba: else e8aa141dbe 2012-07-15 kinaba: plan = plan[1..$]; 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: } 45b72fc54e 2012-07-15 kinaba: f8d6e266eb 2012-07-15 kinaba: //alias Solver_2!(Solver_1) MainSolver; f8d6e266eb 2012-07-15 kinaba: alias Solver_1 MainSolver;