6293256fec 2012-07-14 kinaba: import util; 6293256fec 2012-07-14 kinaba: import game; 6293256fec 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: class Solver_0 9d4aca73fa 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: this(const(Game) g) {} 9d4aca73fa 2012-07-14 kinaba: char single_step() { return 'W'; } 9d4aca73fa 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: class Solver_1 6293256fec 2012-07-14 kinaba: { c743b817b7 2012-07-14 kinaba: int wait_count = 0; 9d4aca73fa 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: Game g; 9d4aca73fa 2012-07-14 kinaba: this(const(Game) g) 9d4aca73fa 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: this.g = g.clone(); c4d04122d8 2012-07-14 kinaba: forbidden_cell = new bool[][](g.map.H+2, g.map.W+2); 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: char single_step() 9d4aca73fa 2012-07-14 kinaba: { c4d04122d8 2012-07-14 kinaba: Tuple!(string,int) de = death_move(g); c4d04122d8 2012-07-14 kinaba: char c = act(g, de[0], de[1]); 9d4aca73fa 2012-07-14 kinaba: g.command(c); 9d4aca73fa 2012-07-14 kinaba: return c; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: c4d04122d8 2012-07-14 kinaba: Tuple!(string,int) death_move(const(Game) g) b4aceba693 2012-07-14 kinaba: { b4aceba693 2012-07-14 kinaba: string death; c4d04122d8 2012-07-14 kinaba: int choice = 0; b4aceba693 2012-07-14 kinaba: foreach(char c; "UDLRW") { b4aceba693 2012-07-14 kinaba: Game gg = g.clone(); b4aceba693 2012-07-14 kinaba: gg.command(c); b4aceba693 2012-07-14 kinaba: if( !gg.cleared && gg.dead ) b4aceba693 2012-07-14 kinaba: death ~= c; c4d04122d8 2012-07-14 kinaba: else if( gg.map.robot != g.map.robot ) c4d04122d8 2012-07-14 kinaba: choice++; b4aceba693 2012-07-14 kinaba: } c4d04122d8 2012-07-14 kinaba: return tuple(death, choice); b4aceba693 2012-07-14 kinaba: } b4aceba693 2012-07-14 kinaba: c4d04122d8 2012-07-14 kinaba: Tuple!(Pos, int)[] log; c4d04122d8 2012-07-14 kinaba: bool[][] forbidden_cell; c4d04122d8 2012-07-14 kinaba: c4d04122d8 2012-07-14 kinaba: char act(const(Game) g, string death, int breath) 9d4aca73fa 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: const Pos ro = g.map.robot; 9d4aca73fa 2012-07-14 kinaba: const Pos[] la = g.map.lambdas(); 9d4aca73fa 2012-07-14 kinaba: const Pos li = g.map.lift; 9d4aca73fa 2012-07-14 kinaba: 62a5c6c47f 2012-07-14 kinaba: Tuple!(char,int)[] cand; 9d4aca73fa 2012-07-14 kinaba: char c = 'W'; 9d4aca73fa 2012-07-14 kinaba: if( la.empty ) { 901abf2f53 2012-07-14 kinaba: cand = search(g, ro, [li], death); 9d4aca73fa 2012-07-14 kinaba: } else { 901abf2f53 2012-07-14 kinaba: cand ~= search(g, ro, la, death); 901abf2f53 2012-07-14 kinaba: } 68c41bdbe0 2012-07-14 kinaba: if(cand.empty) { 68c41bdbe0 2012-07-14 kinaba: const(Pos)[] tgt; 68c41bdbe0 2012-07-14 kinaba: for(int y=1; y<=g.map.H; ++y) 68c41bdbe0 2012-07-14 kinaba: for(int x=1; x<=g.map.W; ++x) 68c41bdbe0 2012-07-14 kinaba: if(g.map[y,x]=='.') 68c41bdbe0 2012-07-14 kinaba: if(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='*'||g.map[y+1,x+1]=='*' 68c41bdbe0 2012-07-14 kinaba: ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*') 68c41bdbe0 2012-07-14 kinaba: tgt ~= new Pos(y,x); 68c41bdbe0 2012-07-14 kinaba: cand ~= search(g, ro, tgt, death); 68c41bdbe0 2012-07-14 kinaba: } 68c41bdbe0 2012-07-14 kinaba: 68c41bdbe0 2012-07-14 kinaba: if(cand.empty) 68c41bdbe0 2012-07-14 kinaba: cand ~= tuple('W',int.max); 62a5c6c47f 2012-07-14 kinaba: sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ 62a5c6c47f 2012-07-14 kinaba: if(c1[1] != c2[1]) 62a5c6c47f 2012-07-14 kinaba: return c1[1] < c2[1]; 62a5c6c47f 2012-07-14 kinaba: return c1[0] < c2[0]; 62a5c6c47f 2012-07-14 kinaba: })(cand); 62a5c6c47f 2012-07-14 kinaba: c = cand[0][0]; 62a5c6c47f 2012-07-14 kinaba: c743b817b7 2012-07-14 kinaba: if(death.count(c)) { c743b817b7 2012-07-14 kinaba: foreach(char live; "UDLRWA") c743b817b7 2012-07-14 kinaba: if(death.count(live)==0) { c743b817b7 2012-07-14 kinaba: c=live; c743b817b7 2012-07-14 kinaba: break; c743b817b7 2012-07-14 kinaba: } c743b817b7 2012-07-14 kinaba: } c743b817b7 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: if(c=='W') { c743b817b7 2012-07-14 kinaba: wait_count++; c743b817b7 2012-07-14 kinaba: if(wait_count > g.map.H) 9d4aca73fa 2012-07-14 kinaba: c = 'A'; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: else c743b817b7 2012-07-14 kinaba: wait_count = 0; c743b817b7 2012-07-14 kinaba: c4d04122d8 2012-07-14 kinaba: bool[char] choice; c4d04122d8 2012-07-14 kinaba: foreach(t; cand) c4d04122d8 2012-07-14 kinaba: choice[t[0]] = true; c4d04122d8 2012-07-14 kinaba: log ~= tuple(ro.clone(), cast(int)choice.length); c4d04122d8 2012-07-14 kinaba: if(log.length > 5) c4d04122d8 2012-07-14 kinaba: log = log[$-5..$]; c4d04122d8 2012-07-14 kinaba: int cnt = 0; c4d04122d8 2012-07-14 kinaba: foreach(l; log) c4d04122d8 2012-07-14 kinaba: if(l[0] == log[$-1][0]) c4d04122d8 2012-07-14 kinaba: ++cnt; c4d04122d8 2012-07-14 kinaba: if( cnt >= 3 && breath==1 ) { c4d04122d8 2012-07-14 kinaba: forbidden_cell[ro.y][ro.x] = true; c4d04122d8 2012-07-14 kinaba: } c4d04122d8 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: return c; 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: 901abf2f53 2012-07-14 kinaba: Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death) 9d4aca73fa 2012-07-14 kinaba: { 62a5c6c47f 2012-07-14 kinaba: bool danger(int y, int x) 62a5c6c47f 2012-07-14 kinaba: { 62a5c6c47f 2012-07-14 kinaba: if(g.map[y+1,x] == '*') 62a5c6c47f 2012-07-14 kinaba: return true; 62a5c6c47f 2012-07-14 kinaba: if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; 62a5c6c47f 2012-07-14 kinaba: if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; 62a5c6c47f 2012-07-14 kinaba: if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; 62a5c6c47f 2012-07-14 kinaba: if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) 62a5c6c47f 2012-07-14 kinaba: return true; 62a5c6c47f 2012-07-14 kinaba: return false; 62a5c6c47f 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: 5fc8a9c49b 2012-07-14 kinaba: // avoid directly below '*' 62a5c6c47f 2012-07-14 kinaba: Tuple!(char,int)[] tryA() { 901abf2f53 2012-07-14 kinaba: const(Pos)[] q; 901abf2f53 2012-07-14 kinaba: foreach(p; gs) 901abf2f53 2012-07-14 kinaba: if(!danger(p.y,p.x)) 901abf2f53 2012-07-14 kinaba: q ~= p; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 901abf2f53 2012-07-14 kinaba: foreach(p; q) v[p.y][p.x]=true; 901abf2f53 2012-07-14 kinaba: for(int step=1; q.length; ++step) { 901abf2f53 2012-07-14 kinaba: Pos[] q2; 901abf2f53 2012-07-14 kinaba: foreach(p; q) { 901abf2f53 2012-07-14 kinaba: int[] dy=[-1,+1,0,0]; 901abf2f53 2012-07-14 kinaba: int[] dx=[0,0,-1,+1]; 901abf2f53 2012-07-14 kinaba: for(int i=0; i<4; ++i) { 901abf2f53 2012-07-14 kinaba: int y = p.y+dy[i]; 901abf2f53 2012-07-14 kinaba: int x = p.x+dx[i]; 901abf2f53 2012-07-14 kinaba: if(v[y][x]) continue; 901abf2f53 2012-07-14 kinaba: if(y==s.y && x==s.x) { 901abf2f53 2012-07-14 kinaba: char c = "UDRL"[i]; 901abf2f53 2012-07-14 kinaba: if( death.count(c) == 0 ) 901abf2f53 2012-07-14 kinaba: return [tuple(c,step)]; 901abf2f53 2012-07-14 kinaba: } else if(forbidden_cell[y][x]){ 901abf2f53 2012-07-14 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { 901abf2f53 2012-07-14 kinaba: if(danger(y,x)) 901abf2f53 2012-07-14 kinaba: continue; 901abf2f53 2012-07-14 kinaba: q2 ~= new Pos(y,x); 901abf2f53 2012-07-14 kinaba: v[y][x]=true; 62a5c6c47f 2012-07-14 kinaba: } 5fc8a9c49b 2012-07-14 kinaba: } 5fc8a9c49b 2012-07-14 kinaba: } 901abf2f53 2012-07-14 kinaba: q = q2; 5fc8a9c49b 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: return []; 5fc8a9c49b 2012-07-14 kinaba: } 5fc8a9c49b 2012-07-14 kinaba: 5fc8a9c49b 2012-07-14 kinaba: // any empty space is my ground 62a5c6c47f 2012-07-14 kinaba: Tuple!(char,int)[] tryB() { 901abf2f53 2012-07-14 kinaba: const(Pos)[] q; 901abf2f53 2012-07-14 kinaba: foreach(p; gs) q ~= p; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 901abf2f53 2012-07-14 kinaba: foreach(p; q) v[p.y][p.x]=true; c4d04122d8 2012-07-14 kinaba: for(int step=10; q.length; ++step) { 62a5c6c47f 2012-07-14 kinaba: Pos[] q2; 62a5c6c47f 2012-07-14 kinaba: foreach(p; q) { 62a5c6c47f 2012-07-14 kinaba: int[] dy=[-1,+1,0,0]; 62a5c6c47f 2012-07-14 kinaba: int[] dx=[0,0,-1,+1]; 62a5c6c47f 2012-07-14 kinaba: for(int i=0; i<4; ++i) { 62a5c6c47f 2012-07-14 kinaba: int y = p.y+dy[i]; 62a5c6c47f 2012-07-14 kinaba: int x = p.x+dx[i]; 62a5c6c47f 2012-07-14 kinaba: if(v[y][x]) continue; 62a5c6c47f 2012-07-14 kinaba: if(y==s.y && x==s.x) { 62a5c6c47f 2012-07-14 kinaba: char c = "UDRL"[i]; 62a5c6c47f 2012-07-14 kinaba: if( death.count(c) == 0 ) 62a5c6c47f 2012-07-14 kinaba: return [tuple(c,step)]; c4d04122d8 2012-07-14 kinaba: } else if(forbidden_cell[y][x]){ 62a5c6c47f 2012-07-14 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { 62a5c6c47f 2012-07-14 kinaba: q2 ~= new Pos(y,x); 62a5c6c47f 2012-07-14 kinaba: v[y][x]=true; 62a5c6c47f 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: q = q2; 9d4aca73fa 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: return []; 9d4aca73fa 2012-07-14 kinaba: } 5fc8a9c49b 2012-07-14 kinaba: 5fc8a9c49b 2012-07-14 kinaba: // push rocks! 62a5c6c47f 2012-07-14 kinaba: Tuple!(char,int)[] tryC() { 901abf2f53 2012-07-14 kinaba: const(Pos)[] q; 901abf2f53 2012-07-14 kinaba: foreach(p; gs) q ~= p; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 901abf2f53 2012-07-14 kinaba: foreach(p; q) v[p.y][p.x]=true; c4d04122d8 2012-07-14 kinaba: for(int step=20; q.length; ++step) { 62a5c6c47f 2012-07-14 kinaba: Pos[] q2; 62a5c6c47f 2012-07-14 kinaba: foreach(p; q) { 62a5c6c47f 2012-07-14 kinaba: int[] dy=[-1,+1,0,0]; 62a5c6c47f 2012-07-14 kinaba: int[] dx=[0,0,-1,+1]; 62a5c6c47f 2012-07-14 kinaba: for(int i=0; i<4; ++i) { 62a5c6c47f 2012-07-14 kinaba: int y = p.y+dy[i]; 62a5c6c47f 2012-07-14 kinaba: int x = p.x+dx[i]; 62a5c6c47f 2012-07-14 kinaba: if(v[y][x]) continue; 62a5c6c47f 2012-07-14 kinaba: if(y==s.y && x==s.x) { 62a5c6c47f 2012-07-14 kinaba: char c = "UDRL"[i]; 62a5c6c47f 2012-07-14 kinaba: if( death.count(c) == 0 ) 62a5c6c47f 2012-07-14 kinaba: return [tuple(c,step)]; c4d04122d8 2012-07-14 kinaba: } else if(forbidden_cell[y][x]){ 62a5c6c47f 2012-07-14 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') { 62a5c6c47f 2012-07-14 kinaba: q2 ~= new Pos(y,x); 62a5c6c47f 2012-07-14 kinaba: v[y][x]=true; 62a5c6c47f 2012-07-14 kinaba: } else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) { 62a5c6c47f 2012-07-14 kinaba: q2 ~= new Pos(y,x); 62a5c6c47f 2012-07-14 kinaba: v[y][x]=true; 62a5c6c47f 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: q = q2; 9d4aca73fa 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: return []; 9d4aca73fa 2012-07-14 kinaba: } c4d04122d8 2012-07-14 kinaba: return tryA() ~ tryB() ~ tryC(); 9d4aca73fa 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: }