Differences From Artifact [3413d0e80fd69f87]:
- File
src/solver.d
- 2012-07-16 03:53:00 - part of checkin [971863e35a] on branch trunk - No-cloning death-move(). With several fixes to the simulator. (user: kinaba) [annotate]
To Artifact [7de11f2564488051]:
- File
src/solver.d
- 2012-07-16 04:17:22 - part of checkin [1110e2f932] on branch trunk - Migrated to no-clone deathmove (user: kinaba) [annotate]
1 1 import util;
2 2 import game;
3 3
4 -bool rocky(char c){ return c=='*'||c=='@'; }
4 +bool is_spacy(char c)
5 +{
6 + return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
7 +}
8 +
9 +bool is_rocky(char c)
10 +{
11 + return c=='*' || c=='@';
12 +}
13 +
14 +bool is_true_space(char c)
15 +{
16 + return c==' ';
17 +}
18 +
19 +bool is_trampoline_source(char c)
20 +{
21 + return 'A'<=c && c<='I';
22 +}
23 +
24 +bool is_rocklambda(char c)
25 +{
26 + return is_rocky(c) || c=='\\';
27 +}
28 +
29 +Tuple!(string,int) death_move(in Game g)
30 +{
31 + // TODO: S
32 +
33 + string death;
34 + int breath;
35 + int y = g.map.robot.y;
36 + int x = g.map.robot.x;
37 + int[5] dy_=[+1,-1,0,0,0];
38 + int[5] dx_=[0,0,-1,+1,0];
39 + char[] ds=['U','D','L','R','W'];
40 + for(int i=0; i<5; ++i)
41 + {
42 + bool after_move_death(int y, int x, char tr_tgt)
43 + {
44 + bool is_spacy_t(char c) {
45 + if(is_true_space(c) || c=='R' || c==tr_tgt)
46 + return true;
47 + return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
48 + }
49 +
50 + // check water
51 + if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level )
52 + return true;
53 +
54 + // check falling rock.
55 + int yy=y+1, xx=x;
56 + if( is_spacy_t(g.map[yy, xx]) )
57 + {
58 + if( is_rocky(g.map[yy+1,xx]) )
59 + return true;
60 + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
61 + if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
62 + return false;
63 + return true;
64 + }
65 + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
66 + if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
67 + return false;
68 + return true;
69 + }
70 + }
71 + return false;
72 + }
73 +
74 + int dy=dy_[i], dx=dx_[i];
75 + 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]) )
76 + {
77 + if( after_move_death(y+dy, x+dx, char.init) )
78 + death ~= ds[i];
79 + else if(ds[i] != 'W')
80 + breath ++;
81 + }
82 + else if( is_trampoline_source(g.map[y+dy,x+dx]) )
83 + {
84 + Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
85 + if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
86 + death ~= ds[i];
87 + else
88 + breath ++;
89 + }
90 + else
91 + {
92 + death ~= ds[i];
93 + }
94 + }
95 +
96 + return tuple(death, breath);
97 +}
5 98
6 99 interface Solver
7 100 {
8 101 // this(in Game g);
9 102 char single_step();
10 103 void force(char c);
11 104 }
................................................................................
39 132
40 133 void force(char c)
41 134 {
42 135 if(c != 'A')
43 136 g.command(c);
44 137 }
45 138
46 - Tuple!(string,int) death_move(const(Game) g)
47 - {
48 - string death;
49 - int choice = 0;
50 - foreach(char c; "UDLRW") {
51 - Game gg = g.clone();
52 - gg.command(c);
53 - if( !gg.cleared && gg.dead )
54 - death ~= c;
55 - else if( gg.map.robot != g.map.robot )
56 - choice++;
57 - else if( c != 'W' ) // meaningless move
58 - death ~= c;
59 - }
60 - return tuple(death, choice);
61 - }
62 -
63 139 Tuple!(Pos, int)[] log;
64 140 bool[][] forbidden_cell;
65 141
66 142 char act(const(Game) g, string death, int breath)
67 143 {
68 144 const Pos ro = g.map.robot;
69 145 const Pos li = g.map.lift;
................................................................................
113 189
114 190 // 'dig' mode
115 191 if(cand.empty) {
116 192 const(Pos)[] tgt;
117 193 for(int y=1; y<=g.map.H; ++y)
118 194 for(int x=1; x<=g.map.W; ++x)
119 195 if(g.map[y,x]=='.')
120 - if(rocky(g.map[y+1,x])||rocky(g.map[y+1,x-1])||rocky(g.map[y+1,x+1])
121 - ||rocky(g.map[y,x+1])||rocky(g.map[y,x-1]))
196 + if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
197 + ||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
122 198 tgt ~= new Pos(y,x);
123 199 cand ~= search(g, ro, tgt, death, true);
124 200 }
125 201
126 202 if(cand.empty) {
127 203 choke_count++;
128 204 cand ~= tuple('W',int.max);
................................................................................
170 246
171 247 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
172 248 {
173 249 bool danger(int y, int x)
174 250 {
175 251 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
176 252 return false;
177 - if(rocky(g.map[y+1,x]))
253 + if(is_rocky(g.map[y+1,x]))
178 254 return true;
179 - if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g.map[y,x-1]))
255 + if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
180 256 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
181 257 return true;
182 - 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'))
258 + 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'))
183 259 return true;
184 - if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||rocky(g.map[y-1,x-1]))
260 + if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
185 261 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
186 262 return true;
187 - 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'))
263 + 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'))
188 264 return true;
189 265 return false;
190 266 }
191 267
192 268 // avoid directly below '*'
193 269 Tuple!(char,int)[] tryA() {
194 270 const(Pos)[] q;
................................................................................
279 355 Pos[] q2;
280 356 foreach(p; q) {
281 357 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
282 358 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
283 359 for(int i=0; i<yyy.length; ++i) {
284 360 int y = yyy[i];
285 361 int x = xxx[i];
286 - if(rocky(g.map[p])) {
362 + if(is_rocky(g.map[p])) {
287 363 if(i>=4)continue;
288 364 if(y!=p.y)continue;
289 365 if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
290 366 }
291 367 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
292 368 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
293 369 yyy ~= ppp.y;
................................................................................
297 373 }
298 374 if(v[y][x]) continue;
299 375 if(y==s.y && x==s.x && i<4) {
300 376 char c = "UDRL"[i];
301 377 if( death.count(c) == 0 )
302 378 return [tuple(c,step)];
303 379 } else if(forbidden_cell[y][x]){
304 - } 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) {
380 + } 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) {
305 381 q2 ~= new Pos(y,x);
306 382 v[y][x]=true;
307 383 }
308 384 }
309 385 }
310 386 q = q2;
311 387 }
................................................................................
536 612 if(c != 'A')
537 613 g.command(c);
538 614 return c;
539 615 }
540 616
541 617 void force(char c)
542 618 {
543 -stderr.writeln(death_move(g));
544 619 if(c != 'A')
545 620 g.command(c);
546 621 }
547 622
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 623 char think(in Game g)
629 624 {
630 - string s = death_move(g);
631 - stderr.writeln(s);
632 625
633 626 auto Q = new Queue!(Tuple!(Pos,Pos));
634 627 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
635 628 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
636 629 while(!Q.empty) {
637 630 auto tup = Q.pop();
638 631 Pos p = tup[0][0];
................................................................................
668 661 }
669 662 }
670 663 }
671 664 return 'A';
672 665 }
673 666 }
674 667
675 -alias Solver_3 MainSolver;
676 -//alias Solver_2!(Solver_1) MainSolver;
668 +//alias Solver_3 MainSolver;
669 +alias Solver_2!(Solver_1) MainSolver;
677 670 //alias Solver_1 MainSolver;
678 671 //alias Solver_0 MainSolver;