Check-in [1110e2f932]
Not logged in
Overview
SHA1 Hash:1110e2f932810bea823cd7a783dbdbf1f5df331c
Date: 2012-07-16 13:17:22
User: kinaba
Comment:Migrated to no-clone deathmove
Timelines: family | ancestors | descendants | both | trunk
Diffs: redesign
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes

Modified src/solver.d from [3413d0e80fd69f87] to [7de11f2564488051].

1 import util; 1 import util; 2 import game; 2 import game; 3 3 > 4 bool is_spacy(char c) > 5 { > 6 return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; > 7 } > 8 4 bool rocky(char c){ return c=='*'||c=='@'; } | 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)==t > 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 > 61 if( is_spacy_t(g.map[yy+1,xx+2]) && is_s > 62 return false; > 63 return true; > 64 } > 65 if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map > 66 if(g.hige_until_rise == 1 && g.map[yy+1, > 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 > 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 > 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 interface Solver 99 interface Solver 7 { 100 { 8 // this(in Game g); 101 // this(in Game g); 9 char single_step(); 102 char single_step(); 10 void force(char c); 103 void force(char c); 11 } 104 } ................................................................................................................................................................................ 39 132 40 void force(char c) 133 void force(char c) 41 { 134 { 42 if(c != 'A') 135 if(c != 'A') 43 g.command(c); 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 Tuple!(Pos, int)[] log; 139 Tuple!(Pos, int)[] log; 64 bool[][] forbidden_cell; 140 bool[][] forbidden_cell; 65 141 66 char act(const(Game) g, string death, int breath) 142 char act(const(Game) g, string death, int breath) 67 { 143 { 68 const Pos ro = g.map.robot; 144 const Pos ro = g.map.robot; 69 const Pos li = g.map.lift; 145 const Pos li = g.map.lift; ................................................................................................................................................................................ 113 189 114 // 'dig' mode 190 // 'dig' mode 115 if(cand.empty) { 191 if(cand.empty) { 116 const(Pos)[] tgt; 192 const(Pos)[] tgt; 117 for(int y=1; y<=g.map.H; ++y) 193 for(int y=1; y<=g.map.H; ++y) 118 for(int x=1; x<=g.map.W; ++x) 194 for(int x=1; x<=g.map.W; ++x) 119 if(g.map[y,x]=='.') 195 if(g.map[y,x]=='.') 120 if(rocky(g.map[y+1,x])||rocky(g.map[y+1, | 196 if(is_rocky(g.map[y+1,x])||is_rocky(g.ma 121 ||rocky(g.map[y,x+1])||rocky(g.map[y,x- | 197 ||is_rocky(g.map[y,x+1])||is_rocky(g.ma 122 tgt ~= new Pos(y,x); 198 tgt ~= new Pos(y,x); 123 cand ~= search(g, ro, tgt, death, true); 199 cand ~= search(g, ro, tgt, death, true); 124 } 200 } 125 201 126 if(cand.empty) { 202 if(cand.empty) { 127 choke_count++; 203 choke_count++; 128 cand ~= tuple('W',int.max); 204 cand ~= tuple('W',int.max); ................................................................................................................................................................................ 170 246 171 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death 247 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death 172 { 248 { 173 bool danger(int y, int x) 249 bool danger(int y, int x) 174 { 250 { 175 if(g.map[y,x] == ' ' || g.map[y,x] == 'R') 251 if(g.map[y,x] == ' ' || g.map[y,x] == 'R') 176 return false; 252 return false; 177 if(rocky(g.map[y+1,x])) | 253 if(is_rocky(g.map[y+1,x])) 178 return true; 254 return true; 179 if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g | 255 if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_r 180 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 256 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R')) 181 return true; 257 return true; 182 if(rocky(g.map[y+1,x+1]) && rocky(g.map[y,x+1]) && (g.ma | 258 if(is_rocky(g.map[y+1,x+1]) && is_rocky(g.map[y,x+1]) && 183 return true; 259 return true; 184 if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||rocky(g | 260 if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_r 185 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) 261 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R')) 186 return true; 262 return true; 187 if(rocky(g.map[y,x+1]) && rocky(g.map[y-1,x+1]) && (g.ma | 263 if(is_rocky(g.map[y,x+1]) && is_rocky(g.map[y-1,x+1]) && 188 return true; 264 return true; 189 return false; 265 return false; 190 } 266 } 191 267 192 // avoid directly below '*' 268 // avoid directly below '*' 193 Tuple!(char,int)[] tryA() { 269 Tuple!(char,int)[] tryA() { 194 const(Pos)[] q; 270 const(Pos)[] q; ................................................................................................................................................................................ 279 Pos[] q2; 355 Pos[] q2; 280 foreach(p; q) { 356 foreach(p; q) { 281 int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 357 int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 282 int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 358 int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 283 for(int i=0; i<yyy.length; ++i) { 359 for(int i=0; i<yyy.length; ++i) { 284 int y = yyy[i]; 360 int y = yyy[i]; 285 int x = xxx[i]; 361 int x = xxx[i]; 286 if(rocky(g.map[p])) { | 362 if(is_rocky(g.map[p])) { 287 if(i>=4)continue; 363 if(i>=4)continue; 288 if(y!=p.y)continue; 364 if(y!=p.y)continue; 289 if(g.map[y,p.x+(p.x-x)]! 365 if(g.map[y,p.x+(p.x-x)]! 290 } 366 } 291 if('1'<=g.map[y,x]&&g.map[y,x]<= 367 if('1'<=g.map[y,x]&&g.map[y,x]<= 292 foreach(ppp; g.tr.source 368 foreach(ppp; g.tr.source 293 yyy ~= ppp.y; 369 yyy ~= ppp.y; ................................................................................................................................................................................ 297 } 373 } 298 if(v[y][x]) continue; 374 if(v[y][x]) continue; 299 if(y==s.y && x==s.x && i<4) { 375 if(y==s.y && x==s.x && i<4) { 300 char c = "UDRL"[i]; 376 char c = "UDRL"[i]; 301 if( death.count(c) == 0 377 if( death.count(c) == 0 302 return [tuple(c, 378 return [tuple(c, 303 } else if(forbidden_cell[y][x]){ 379 } else if(forbidden_cell[y][x]){ 304 } else if(g.map[y,x]==' '||g.map | 380 } else if(g.map[y,x]==' '||g.map 305 q2 ~= new Pos(y,x); 381 q2 ~= new Pos(y,x); 306 v[y][x]=true; 382 v[y][x]=true; 307 } 383 } 308 } 384 } 309 } 385 } 310 q = q2; 386 q = q2; 311 } 387 } ................................................................................................................................................................................ 536 if(c != 'A') 612 if(c != 'A') 537 g.command(c); 613 g.command(c); 538 return c; 614 return c; 539 } 615 } 540 616 541 void force(char c) 617 void force(char c) 542 { 618 { 543 stderr.writeln(death_move(g)); < 544 if(c != 'A') 619 if(c != 'A') 545 g.command(c); 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_ < 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_roc < 594 if( is_spacy_t(g.map[yy+1,xx+2]) < 595 return false; < 596 return true; < 597 } < 598 if( is_spacy_t(g.map[yy+1,xx]) && is_roc < 599 if(g.hige_until_rise == 1 && g.m < 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. < 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. < 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) 623 char think(in Game g) 629 { 624 { 630 string s = death_move(g); < 631 stderr.writeln(s); < 632 625 633 auto Q = new Queue!(Tuple!(Pos,Pos)); 626 auto Q = new Queue!(Tuple!(Pos,Pos)); 634 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0); 627 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); 628 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2); 636 while(!Q.empty) { 629 while(!Q.empty) { 637 auto tup = Q.pop(); 630 auto tup = Q.pop(); 638 Pos p = tup[0][0]; 631 Pos p = tup[0][0]; ................................................................................................................................................................................ 668 } 661 } 669 } 662 } 670 } 663 } 671 return 'A'; 664 return 'A'; 672 } 665 } 673 } 666 } 674 667 675 alias Solver_3 MainSolver; | 668 //alias Solver_3 MainSolver; 676 //alias Solver_2!(Solver_1) MainSolver; | 669 alias Solver_2!(Solver_1) MainSolver; 677 //alias Solver_1 MainSolver; 670 //alias Solver_1 MainSolver; 678 //alias Solver_0 MainSolver; 671 //alias Solver_0 MainSolver;