• branch=trunk inherited from [16f0b5784f]
• sym-trunk inherited from [16f0b5784f]

Added maps/test2.map version [60334061c33d6104]

            1  +* L
            2  +  W
            3  +*
            4  +#R#
            5  +
            6  +Growth 2

Added maps/test3.map version [1e96116428423b73]

            1  +L *       CD
            2  +  *  \B    2
            3  + R   A1
            4  +
            5  +Trampoline A targets 1
            6  +Trampoline B targets 1
            7  +Trampoline C targets 1
            8  +Trampoline D targets 2

Modified src/game.d from [fe18e86f2be2ed95] to [d9bf3ea129c7cbc5].

   390    390         dead=true;
   391    391       }
   392    392      }
   393    393      else if(this[p]=='W') {
   394    394       if(hige_day) {
   395    395        for(int dy=-1; dy<=+1; ++dy)
   396    396        for(int dx=-1; dx<=+1; ++dx)
   397         -      if(this[p.y+dy,p.x+dx] == ' ')
          397  +      if(this[p.y+dy,p.x+dx] == ' ') {
   398    398          write(p.y+dy,p.x+dx,'W');
          399  +       if(robot.y==p.y+dy-1 && robot.x==p.x+dx)
          400  +        dead = false; // guarded by hige!
          401  +      }
   399    402       }
   400    403      }
   401    404     }
   402    405   
   403    406     return dead;
   404    407    }
   405    408   }

Modified src/solver.d from [15905b6766caaf1d] to [3413d0e80fd69f87].

   339    339     plan_state   = Tentative;
   340    340     if(g.map.W*g.map.H <= 400) {
   341    341      RandomChoicePattern = ["UU","UD","UL","UR",
   342    342                             "DU","DD","DL","DR",
   343    343                             "LU","LD","LL","LR",
   344    344                             "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
   345    345      PredictFuture = 20;
   346         -   clear_improvement = 3;
          346  +   clear_improvement = 1;
   347    347     }
   348    348     else if(g.map.W*g.map.H <= 4096) {
   349    349      RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
   350    350      PredictFuture = 10;
   351    351      clear_improvement = 0;
   352    352     }
   353    353     else {
................................................................................

   371    371     // If the future is bad, correct.
   372    372     if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
   373    373      replan();
   374    374   
   375    375     // Follow the predicted plan.
   376    376     if( plan.empty )
   377    377      return 'A';
   378         -stderr.writeln(plan, " ", plan_state);
   379    378     char c = plan[0];
   380    379     plan = plan[1..$];
   381    380     int b_lambda = current_game.map.collected_lambda;
   382    381     current_game.command(c);
   383    382     int a_lambda = current_game.map.collected_lambda;
   384    383     if(b_lambda < a_lambda) lambda_getter = false;
   385    384     return c;
................................................................................

   425    424       plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
   426    425      }
   427    426     }
   428    427    }
   429    428   
   430    429    void replan()
   431    430    {
   432         -stderr.writeln("replan!");
   433    431     // Try to replace every step of the plan by another move.
   434    432     Game g = current_game.clone();
   435    433     Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
   436    434     int insertion_point = plan.length;
   437         -writeln(cand, " ", cand[0].g.map.collected_lambda);
   438    435     bool tiebreak_by_turn = false;
   439    436     int consider_length = min(ReplanLength, g.map.W*g.map.H);
   440    437     if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
   441    438   
   442    439     for(int i=0; i<plan.length; ++i) {
   443    440      foreach(string prefix; RandomChoicePattern)
   444    441       if(prefix[0] != plan[i]) {
................................................................................

   463    460         }
   464    461        }
   465    462        if(better) {
   466    463         cand = r;
   467    464         tiebreak_by_turn = true;
   468    465         insertion_point = i+prefix.length;
   469    466         if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
   470         -writeln(cand, " ", cand[0].g.map.collected_lambda);
   471    467        }
   472    468       }
   473    469      g.command(plan[i]);
   474    470     }
   475    471   
   476    472     if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
   477    473      sub_solver   = cand[0];
................................................................................

   507    503     }
   508    504     if(s.g.cleared) state = Fixed;
   509    505     else if(s.g.dead) state = Tentative_Stuck;
   510    506     return tuple(s, log, state);
   511    507    }
   512    508   }
   513    509   
   514         -alias Solver_2!(Solver_1) MainSolver;
          510  +class Queue(T)
          511  +{
          512  + alias Tuple!(T,int) t;
          513  +
          514  + t[] cur, next;
          515  +
          516  + void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
          517  + bool empty() { return cur.empty; }
          518  + t pop() {
          519  +  t v = cur[0]; cur = cur[1..$];
          520  +  if(cur.empty) { cur = next; next = null; }
          521  +  return v;
          522  + }
          523  +}
          524  +
          525  +class Solver_3 : Solver
          526  +{
          527  + Game g;
          528  + this(in Game g)
          529  + {
          530  +  this.g = g.clone();
          531  + }
          532  +
          533  + char single_step()
          534  + {
          535  +  char c = think(g);
          536  +  if(c != 'A')
          537  +   g.command(c);
          538  +  return c;
          539  + }
          540  +
          541  + void force(char c)
          542  + {
          543  +stderr.writeln(death_move(g));
          544  +  if(c != 'A')
          545  +   g.command(c);
          546  + }
          547  +
          548  + bool is_spacy(char c) {
          549  +  return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
          550  + }
          551  + bool is_rocky(char c) {
          552  +  return c=='*' || c=='@';
          553  + }
          554  + bool is_true_space(char c) {
          555  +  return c==' ';
          556  + }
          557  + bool is_trampoline_source(char c) {
          558  +  return 'A'<=c && c<='I';
          559  + }
          560  + bool is_rocklambda(char c) {
          561  +  return is_rocky(c) || c=='\\';
          562  + }
          563  +
          564  + string death_move(in Game g)
          565  + {
          566  +  // TODO: S
          567  +  string death;
          568  +  int y = g.map.robot.y;
          569  +  int x = g.map.robot.x;
          570  +  int[5] dy_=[-1,+1,0,0,0];
          571  +  int[5] dx_=[0,0,-1,+1,0];
          572  +  char[] ds=['D','U','L','R','W'];
          573  +  for(int i=0; i<5; ++i)
          574  +  {
          575  +   bool after_move_death(int y, int x, char tr_tgt)
          576  +   {
          577  +    bool is_spacy_t(char c) {
          578  +     if(is_spacy(c) || c==tr_tgt)
          579  +      return true;
          580  +     return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
          581  +    }
          582  +
          583  +    // check water
          584  +    if( g.hp==0 && y<=g.water_level )
          585  +     return true;
          586  +
          587  +    // check falling rock.
          588  +    int yy=y+1, xx=x;
          589  +    if( is_spacy_t(g.map[yy, xx]) )
          590  +    {
          591  +     if( is_rocky(g.map[yy+1,xx]) )
          592  +      return true;
          593  +     if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
          594  +      if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
          595  +       return false;
          596  +      return true;
          597  +     }
          598  +     if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
          599  +      if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
          600  +       return false;
          601  +      return true;
          602  +     }
          603  +    }
          604  +    return false;
          605  +   }
          606  +
          607  +   int dy=dy_[i], dx=dx_[i];
          608  +   if( is_spacy(g.map[y+dy,x+dx])
          609  +    || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
          610  +   {
          611  +    if( after_move_death(y+dy, x+dx, char.init) )
          612  +     death ~= ds[i];
          613  +   }
          614  +   else if( is_trampoline_source(g.map[y+dy,x+dx]) )
          615  +   {
          616  +    Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
          617  +    if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
          618  +     death ~= ds[i];
          619  +   }
          620  +   else
          621  +   {
          622  +    death ~= ds[i];
          623  +   }
          624  +  }
          625  +  return death;
          626  + }
          627  +
          628  + char think(in Game g)
          629  + {
          630  +  string s = death_move(g);
          631  +  stderr.writeln(s);
          632  +
          633  +  auto Q = new Queue!(Tuple!(Pos,Pos));
          634  +  Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
          635  +  Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
          636  +  while(!Q.empty) {
          637  +   auto tup = Q.pop();
          638  +   Pos  p    = tup[0][0];
          639  +   Pos  prev = tup[0][1];
          640  +   int  dist = tup[1];
          641  +   if(V[p.y][p.x])
          642  +    continue;
          643  +   V[p.y][p.x] = prev;
          644  +   if(g.map[p]=='\\' || g.map[p]=='O')
          645  +   {
          646  +    Pos goback(Pos p) {
          647  +     return V[p.y][p.x];
          648  +    }
          649  +    for(;;) {
          650  +     Pos q = goback(p);
          651  +     if(q == g.map.robot)
          652  +      if(q.y==p.y)
          653  +       return q.x<p.x ? 'R' : 'L';
          654  +      else
          655  +       return q.y<p.y ? 'U' : 'D';
          656  +     p=q;
          657  +    }
          658  +   }
          659  +
          660  +   int[4] dy=[-1,+1,0,0];
          661  +   int[4] dx=[0,0,-1,+1];
          662  +   char[] ds=['D','U','L','R'];
          663  +   for(int i=0; i<4; ++i)
          664  +   {
          665  +    int y=p.y+dy[i], x=p.x+dx[i];
          666  +    if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O')&&!V[y][x]) {
          667  +     Q.push(tuple(new Pos(y,x),p), dist+1);
          668  +    }
          669  +   }
          670  +  }
          671  +  return 'A';
          672  + }
          673  +}
          674  +
          675  +alias Solver_3 MainSolver;
          676  +//alias Solver_2!(Solver_1) MainSolver;
   515    677   //alias Solver_1 MainSolver;
   516    678   //alias Solver_0 MainSolver;