Index: src/solver.d ================================================================== --- src/solver.d +++ src/solver.d @@ -1,9 +1,102 @@ import util; import game; -bool rocky(char c){ return c=='*'||c=='@'; } +bool is_spacy(char c) +{ + return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; +} + +bool is_rocky(char c) +{ + return c=='*' || c=='@'; +} + +bool is_true_space(char c) +{ + return c==' '; +} + +bool is_trampoline_source(char c) +{ + return 'A'<=c && c<='I'; +} + +bool is_rocklambda(char c) +{ + return is_rocky(c) || c=='\\'; +} + +Tuple!(string,int) death_move(in Game g) +{ + // TODO: S + + string death; + int breath; + int y = g.map.robot.y; + int x = g.map.robot.x; + int[5] dy_=[+1,-1,0,0,0]; + int[5] dx_=[0,0,-1,+1,0]; + char[] ds=['U','D','L','R','W']; + for(int i=0; i<5; ++i) + { + bool after_move_death(int y, int x, char tr_tgt) + { + bool is_spacy_t(char c) { + if(is_true_space(c) || c=='R' || c==tr_tgt) + return true; + return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt); + } + + // check water + if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level ) + return true; + + // check falling rock. + int yy=y+1, xx=x; + if( is_spacy_t(g.map[yy, xx]) ) + { + if( is_rocky(g.map[yy+1,xx]) ) + return true; + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) { + if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) ) + return false; + return true; + } + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) { + if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W') + return false; + return true; + } + } + return false; + } + + int dy=dy_[i], dx=dx_[i]; + 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]) ) + { + if( after_move_death(y+dy, x+dx, char.init) ) + death ~= ds[i]; + else if(ds[i] != 'W') + breath ++; + } + else if( is_trampoline_source(g.map[y+dy,x+dx]) ) + { + Pos p = g.tr.target_pos(g.map[y+dy,x+dx]); + if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) ) + death ~= ds[i]; + else + breath ++; + } + else + { + death ~= ds[i]; + } + } + + return tuple(death, breath); +} interface Solver { // this(in Game g); char single_step(); @@ -41,27 +134,10 @@ { if(c != 'A') g.command(c); } - Tuple!(string,int) death_move(const(Game) g) - { - string death; - int choice = 0; - foreach(char c; "UDLRW") { - Game gg = g.clone(); - gg.command(c); - if( !gg.cleared && gg.dead ) - death ~= c; - else if( gg.map.robot != g.map.robot ) - choice++; - else if( c != 'W' ) // meaningless move - death ~= c; - } - return tuple(death, choice); - } - Tuple!(Pos, int)[] log; bool[][] forbidden_cell; char act(const(Game) g, string death, int breath) { @@ -115,12 +191,12 @@ if(cand.empty) { const(Pos)[] tgt; for(int y=1; y<=g.map.H; ++y) for(int x=1; x<=g.map.W; ++x) if(g.map[y,x]=='.') - if(rocky(g.map[y+1,x])||rocky(g.map[y+1,x-1])||rocky(g.map[y+1,x+1]) - ||rocky(g.map[y,x+1])||rocky(g.map[y,x-1])) + if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1]) + ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1])) tgt ~= new Pos(y,x); cand ~= search(g, ro, tgt, death, true); } if(cand.empty) { @@ -172,21 +248,21 @@ { bool danger(int y, int x) { if(g.map[y,x] == ' ' || g.map[y,x] == 'R') return false; - if(rocky(g.map[y+1,x])) + if(is_rocky(g.map[y+1,x])) return true; - if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g.map[y,x-1])) + if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1])) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) return true; - 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')) + 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')) return true; - if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||rocky(g.map[y-1,x-1])) + if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1])) && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) return true; - 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')) + 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')) return true; return false; } // avoid directly below '*' @@ -281,11 +357,11 @@ int[] yyy=[p.y-1,p.y+1,p.y,p.y]; int[] xxx=[p.x,p.x,p.x-1,p.x+1]; for(int i=0; i=4)continue; if(y!=p.y)continue; if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue; } if('1'<=g.map[y,x]&&g.map[y,x]<='9') { @@ -299,11 +375,11 @@ if(y==s.y && x==s.x && i<4) { char c = "UDRL"[i]; if( death.count(c) == 0 ) return [tuple(c,step)]; } else if(forbidden_cell[y][x]){ - } 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) { + } 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) { q2 ~= new Pos(y,x); v[y][x]=true; } } } @@ -538,99 +614,16 @@ return c; } void force(char c) { -stderr.writeln(death_move(g)); if(c != 'A') g.command(c); } - bool is_spacy(char c) { - return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; - } - bool is_rocky(char c) { - return c=='*' || c=='@'; - } - bool is_true_space(char c) { - return c==' '; - } - bool is_trampoline_source(char c) { - return 'A'<=c && c<='I'; - } - bool is_rocklambda(char c) { - return is_rocky(c) || c=='\\'; - } - - string death_move(in Game g) - { - // TODO: S - string death; - int y = g.map.robot.y; - int x = g.map.robot.x; - int[5] dy_=[-1,+1,0,0,0]; - int[5] dx_=[0,0,-1,+1,0]; - char[] ds=['D','U','L','R','W']; - for(int i=0; i<5; ++i) - { - bool after_move_death(int y, int x, char tr_tgt) - { - bool is_spacy_t(char c) { - if(is_spacy(c) || c==tr_tgt) - return true; - return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt); - } - - // check water - if( g.hp==0 && y<=g.water_level ) - return true; - - // check falling rock. - int yy=y+1, xx=x; - if( is_spacy_t(g.map[yy, xx]) ) - { - if( is_rocky(g.map[yy+1,xx]) ) - return true; - if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) { - if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) ) - return false; - return true; - } - if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) { - if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W') - return false; - return true; - } - } - return false; - } - - int dy=dy_[i], dx=dx_[i]; - 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]) ) - { - if( after_move_death(y+dy, x+dx, char.init) ) - death ~= ds[i]; - } - else if( is_trampoline_source(g.map[y+dy,x+dx]) ) - { - Pos p = g.tr.target_pos(g.map[y+dy,x+dx]); - if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) ) - death ~= ds[i]; - } - else - { - death ~= ds[i]; - } - } - return death; - } - char think(in Game g) { - string s = death_move(g); - stderr.writeln(s); auto Q = new Queue!(Tuple!(Pos,Pos)); Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0); Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2); while(!Q.empty) { @@ -670,9 +663,9 @@ } return 'A'; } } -alias Solver_3 MainSolver; -//alias Solver_2!(Solver_1) MainSolver; +//alias Solver_3 MainSolver; +alias Solver_2!(Solver_1) MainSolver; //alias Solver_1 MainSolver; //alias Solver_0 MainSolver;