Differences From Artifact [8a530414bd295205]:
- File
src/solver.d
- 2012-07-16 04:40:41 - part of checkin [2e02a085bf] on branch trunk - Further solver names. (user: kinaba) [annotate]
To Artifact [77a8a9a8973002b1]:
- File
src/solver.d
- 2012-07-16 04:52:13 - part of checkin [8bc4298777] on branch trunk - BFS result reusing of solver "wind". (user: kinaba) [annotate]
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;