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

Modified src/solver.d from [8a530414bd295205] to [77a8a9a8973002b1].

     1      1   //
     2      2   // http://en.wikipedia.org/wiki/F%C5%ABrinkazan
     3      3   //
     4      4   import util;
     5      5   import game;
            6  +
            7  +
            8  +interface Solver
            9  +{
           10  + // this(in Game g);
           11  + char single_step();
           12  + void force(char c);
           13  +}
           14  +
     6     15   
     7     16   bool is_spacy(char c)
     8     17   {
     9     18    return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
    10     19   }
    11     20   
    12     21   bool is_rocky(char c)
................................................................................

    95    104      death ~= ds[i];
    96    105     }
    97    106    }
    98    107   
    99    108    return tuple(death, breath);
   100    109   }
   101    110   
   102         -interface Solver
          111  +class Queue(T)
   103    112   {
   104         - // this(in Game g);
   105         - char single_step();
   106         - void force(char c);
          113  + alias Tuple!(T,int) t;
          114  +
          115  + t[] cur, next;
          116  +
          117  + void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
          118  + bool empty() { return cur.empty; }
          119  + t pop() {
          120  +  t v = cur[0]; cur = cur[1..$];
          121  +  if(cur.empty) { cur = next; next = null; }
          122  +  return v;
          123  + }
   107    124   }
   108    125   
   109    126   ///
   110    127   /// Solver "Mountain":  be immovable like a mountain.
   111    128   ///
   112    129   class 不動如山 : Solver
   113    130   {
................................................................................

   591    608     }
   592    609     if(s.g.cleared) state = Fixed;
   593    610     else if(s.g.dead) state = Tentative_Stuck;
   594    611     return tuple(s, log, state);
   595    612    }
   596    613   }
   597    614   
   598         -class Queue(T)
   599         -{
   600         - alias Tuple!(T,int) t;
   601         -
   602         - t[] cur, next;
   603         -
   604         - void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
   605         - bool empty() { return cur.empty; }
   606         - t pop() {
   607         -  t v = cur[0]; cur = cur[1..$];
   608         -  if(cur.empty) { cur = next; next = null; }
   609         -  return v;
   610         - }
   611         -}
   612         -
   613    615   ///
   614    616   /// Solver "Wind": let your rapidity be that of the wind.
   615    617   ///
   616    618   class 疾如風 : Solver
   617    619   {
   618    620    Game g;
   619    621    this(in Game g)
   620    622    {
   621    623     this.g = g.clone();
   622    624    }
          625  +
          626  + string plan;
   623    627   
   624    628    char single_step()
   625    629    {
   626    630     auto dm = death_move(g);
          631  +  if( plan.empty || dm[0].count(plan[0]) ) {
          632  +   plan = think(g, dm[0]);
          633  +   if( plan.empty )
          634  +    plan = "W";
          635  +  }
   627    636   
   628         -  char c = think(g, dm[0]);
          637  +  char c = plan[0];
          638  +  plan = plan[1..$];
          639  +
   629    640     if(c == 'W') {
   630    641      wait_counter++;
   631    642      if(dm[0].count(c) || wait_counter>=3) {
   632    643       c = 'A';
   633    644       foreach(char cc; "DLRU")
   634    645        if(dm[0].count(cc) == 0)
   635    646         c = cc;
................................................................................

   648    659    {
   649    660     if(c != 'A')
   650    661      g.command(c);
   651    662    }
   652    663   
   653    664    int wait_counter = 0;
   654    665   
   655         - char think(in Game g, string death)
          666  + string think(in Game g, string death)
   656    667    {
   657    668     auto Q = new Queue!(Tuple!(Pos,Pos));
   658    669     Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
   659    670     Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
   660    671     while(!Q.empty) {
   661    672      auto tup = Q.pop();
   662    673      Pos  p    = tup[0][0];
................................................................................

   663    674      Pos  prev = tup[0][1];
   664    675      int  dist = tup[1];
   665    676      if(V[p.y][p.x])
   666    677       continue;
   667    678      V[p.y][p.x] = prev;
   668    679      if(g.map[p]=='\\' || g.map[p]=='O')
   669    680      {
   670         -    Pos goback(Pos p) {
   671         -     return V[p.y][p.x];
   672         -    }
          681  +    char[] trace;
   673    682       for(;;) {
   674         -     Pos q = goback(p);
   675         -     if(q == g.map.robot)
   676         -      if(q.y==p.y)
   677         -       return q.x<p.x ? 'R' : 'L';
   678         -      else
   679         -       return q.y<p.y ? 'U' : 'D';
          683  +     Pos q = V[p.y][p.x];
          684  +     trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L') :
          685  +                          (q.y<p.y ? 'U' : 'D'));
          686  +     if(q == g.map.robot) {
          687  +      reverse(trace);
          688  +      return trace.idup;
          689  +     }
   680    690        p=q;
   681    691       }
   682    692      }
   683    693   
   684    694      int[4] dy=[-1,+1,0,0];
   685    695      int[4] dx=[0,0,-1,+1];
   686    696      char[] ds=['D','U','L','R'];
................................................................................

   690    700       int y=p.y+dy[i], x=p.x+dx[i];
   691    701       if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O')&&!V[y][x]) {
   692    702        Q.push(tuple(new Pos(y,x),p), dist+1);
   693    703       }
   694    704      }
   695    705     }
   696    706   
   697         -  return 'W';
          707  +  return "";
   698    708    }
   699    709   }
   700    710   
   701    711   //alias 侵掠如火!(疾如風) MainSolver;
   702    712   //alias 侵掠如火!(徐如林) MainSolver;
   703    713   alias 疾如風 MainSolver;
   704    714   //alias 徐如林 MainSolver;
   705    715   //alias 不動如山 MainSolver;