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 9d4aca73fa 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'; } 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 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(); 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 ) { 62a5c6c47f 2012-07-14 kinaba: cand = search(g, ro, li, death); 9d4aca73fa 2012-07-14 kinaba: } else { 9d4aca73fa 2012-07-14 kinaba: foreach(lam; la) b4aceba693 2012-07-14 kinaba: cand ~= search(g, ro, lam, death); 9d4aca73fa 2012-07-14 kinaba: } c4d04122d8 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: 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'; 9d4aca73fa 2012-07-14 kinaba: } 9d4aca73fa 2012-07-14 kinaba: else 9d4aca73fa 2012-07-14 kinaba: g_wc = 0; 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: 62a5c6c47f 2012-07-14 kinaba: Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, 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() { 62a5c6c47f 2012-07-14 kinaba: const(Pos)[] q = [o]; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 62a5c6c47f 2012-07-14 kinaba: if( !danger(o.y,o.x) ) { 62a5c6c47f 2012-07-14 kinaba: v[o.y][o.x]=true; 62a5c6c47f 2012-07-14 kinaba: for(int step=1; 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: if(danger(y,x)) 62a5c6c47f 2012-07-14 kinaba: continue; 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: } 5fc8a9c49b 2012-07-14 kinaba: } 62a5c6c47f 2012-07-14 kinaba: q = q2; 5fc8a9c49b 2012-07-14 kinaba: } 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() { 62a5c6c47f 2012-07-14 kinaba: const(Pos)[] q = [o]; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 62a5c6c47f 2012-07-14 kinaba: v[o.y][o.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() { 62a5c6c47f 2012-07-14 kinaba: const(Pos)[] q = [o]; 62a5c6c47f 2012-07-14 kinaba: bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 62a5c6c47f 2012-07-14 kinaba: v[o.y][o.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: }