6293256fec 2012-07-14 kinaba: import util; 6293256fec 2012-07-14 kinaba: import game; 9d4aca73fa 2012-07-14 kinaba: import driver; 6293256fec 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: /* 9d4aca73fa 2012-07-14 kinaba: interface Solver 6293256fec 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: this(const(Game) g); 9d4aca73fa 2012-07-14 kinaba: char single_step(); 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: */ 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'; } 6293256fec 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: class Solver_1 6293256fec 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: int g_wc = 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(); 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: char single_step() 9d4aca73fa 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: char c = act(g); 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: 9d4aca73fa 2012-07-14 kinaba: char act(const(Game) g) 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: 9d4aca73fa 2012-07-14 kinaba: char c = 'W'; 9d4aca73fa 2012-07-14 kinaba: if( la.empty ) { 9d4aca73fa 2012-07-14 kinaba: auto r = search(g, ro, li); 9d4aca73fa 2012-07-14 kinaba: c = r[0]; 9d4aca73fa 2012-07-14 kinaba: } else { 9d4aca73fa 2012-07-14 kinaba: Tuple!(char,int)[] cand; 9d4aca73fa 2012-07-14 kinaba: foreach(lam; la) 9d4aca73fa 2012-07-14 kinaba: cand ~= search(g, ro, lam); 9d4aca73fa 2012-07-14 kinaba: sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ 9d4aca73fa 2012-07-14 kinaba: if(c1[1] != c2[1]) 9d4aca73fa 2012-07-14 kinaba: return c1[1] < c2[1]; 9d4aca73fa 2012-07-14 kinaba: return c1[0] < c2[0]; 9d4aca73fa 2012-07-14 kinaba: })(cand); 9d4aca73fa 2012-07-14 kinaba: c = cand[0][0]; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: if(c=='W') { 9d4aca73fa 2012-07-14 kinaba: g_wc++; 9d4aca73fa 2012-07-14 kinaba: if(g_wc > 10) 9d4aca73fa 2012-07-14 kinaba: c = 'A'; 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: else 9d4aca73fa 2012-07-14 kinaba: g_wc = 0; 9d4aca73fa 2012-07-14 kinaba: return c; 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: 9d4aca73fa 2012-07-14 kinaba: Tuple!(char,int) search(in Game g, in Pos s, in Pos o) 9d4aca73fa 2012-07-14 kinaba: { 9d4aca73fa 2012-07-14 kinaba: const(Pos)[] q = [o]; 9d4aca73fa 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 9d4aca73fa 2012-07-14 kinaba: for(int step=1; q.length; ++step) { 9d4aca73fa 2012-07-14 kinaba: Pos[] q2; 9d4aca73fa 2012-07-14 kinaba: foreach(p; q) { 9d4aca73fa 2012-07-14 kinaba: int[] dy=[-1,+1,0,0]; 9d4aca73fa 2012-07-14 kinaba: int[] dx=[0,0,-1,+1]; 9d4aca73fa 2012-07-14 kinaba: for(int i=0; i<4; ++i) { 9d4aca73fa 2012-07-14 kinaba: int y = p.y+dy[i]; 9d4aca73fa 2012-07-14 kinaba: int x = p.x+dx[i]; 9d4aca73fa 2012-07-14 kinaba: if(v[y][x]) continue; 9d4aca73fa 2012-07-14 kinaba: if(y==s.y && x==s.x) { 9d4aca73fa 2012-07-14 kinaba: if(i==0) return tuple('U',step); 9d4aca73fa 2012-07-14 kinaba: if(i==1) return tuple('D',step); 9d4aca73fa 2012-07-14 kinaba: if(i==2) return tuple('R',step); 9d4aca73fa 2012-07-14 kinaba: if(i==3) return tuple('L',step); 9d4aca73fa 2012-07-14 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { 9d4aca73fa 2012-07-14 kinaba: q2 ~= new Pos(y,x); 9d4aca73fa 2012-07-14 kinaba: v[y][x]=true; 9d4aca73fa 2012-07-14 kinaba: } else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') { 9d4aca73fa 2012-07-14 kinaba: q2 ~= new Pos(y,x); 9d4aca73fa 2012-07-14 kinaba: v[y][x]=true; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: q = q2; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: q = [o]; 9d4aca73fa 2012-07-14 kinaba: v = new bool[][](g.map.H+2, g.map.W+2); 9d4aca73fa 2012-07-14 kinaba: for(int step=1000; q.length; ++step) { 9d4aca73fa 2012-07-14 kinaba: Pos[] q2; 9d4aca73fa 2012-07-14 kinaba: foreach(p; q) { 9d4aca73fa 2012-07-14 kinaba: int[] dy=[-1,+1,0,0]; 9d4aca73fa 2012-07-14 kinaba: int[] dx=[0,0,-1,+1]; 9d4aca73fa 2012-07-14 kinaba: for(int i=0; i<4; ++i) { 9d4aca73fa 2012-07-14 kinaba: int y = p.y+dy[i]; 9d4aca73fa 2012-07-14 kinaba: int x = p.x+dx[i]; 9d4aca73fa 2012-07-14 kinaba: if(v[y][x]) continue; 9d4aca73fa 2012-07-14 kinaba: if(y==s.y && x==s.x) { 9d4aca73fa 2012-07-14 kinaba: if(i==0) return tuple('U',step); 9d4aca73fa 2012-07-14 kinaba: if(i==1) return tuple('D',step); 9d4aca73fa 2012-07-14 kinaba: if(i==2) return tuple('R',step); 9d4aca73fa 2012-07-14 kinaba: if(i==3) return tuple('L',step); 9d4aca73fa 2012-07-14 kinaba: } else if(g.map[y,x]==' '||g.map[y,x]=='\\') { 9d4aca73fa 2012-07-14 kinaba: q2 ~= new Pos(y,x); 9d4aca73fa 2012-07-14 kinaba: v[y][x]=true; 9d4aca73fa 2012-07-14 kinaba: } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) { 9d4aca73fa 2012-07-14 kinaba: q2 ~= new Pos(y,x); 9d4aca73fa 2012-07-14 kinaba: v[y][x]=true; 9d4aca73fa 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: q = q2; 6293256fec 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: return tuple('W', int.max); 6293256fec 2012-07-14 kinaba: } 6293256fec 2012-07-14 kinaba: }