Differences From Artifact [42db89cb5c63a7bd]:
- File
src/solver.d
- 2012-07-14 09:16:47 - part of checkin [6293256fec] on branch trunk - Preparing for submission... (user: kinaba) [annotate]
To Artifact [0bb4050087a6fb3f]:
- File
src/solver.d
- 2012-07-14 12:29:17 - part of checkin [9d4aca73fa] on branch trunk - GUI+Solver revived. (user: kinaba) [annotate]
1 1 import util;
2 2 import game;
3 -import output;
3 +import driver;
4 4
5 -int g_wc = 0;
6 -
7 -void act(Game g)
5 +/*
6 +interface Solver
8 7 {
9 - Pos ro = g.map.robot;
10 - Pos[] la = g.map.lambdas();
11 - Pos li = g.map.lift;
8 + this(const(Game) g);
9 + char single_step();
10 +}
11 +*/
12 12
13 - char c = 'W';
14 - if( la.empty ) {
15 - auto r = search(g, ro, li);
16 - c = r[0];
17 - } else {
18 - Tuple!(char,int)[] cand;
19 - foreach(lam; la)
20 - cand ~= search(g, ro, lam);
21 - sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
22 - if(c1[1] != c2[1])
23 - return c1[1] < c2[1];
24 - return c1[0] < c2[0];
25 - })(cand);
26 - c = cand[0][0];
27 - }
28 - if(c=='W') {
29 - g_wc++;
30 - if(g_wc > 10)
31 - c = 'A';
32 - }
33 - else
34 - g_wc = 0;
35 - g.command(c);
13 +class Solver_0
14 +{
15 + this(const(Game) g) {}
16 + char single_step() { return 'W'; }
36 17 }
37 18
38 -Tuple!(char,int) search(Game g, Pos s, Pos o)
19 +class Solver_1
39 20 {
40 - Pos[] q = [o];
41 - bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
42 - for(int step=1; q.length; ++step) {
43 - Pos[] q2;
44 - foreach(p; q) {
45 - int[] dy=[-1,+1,0,0];
46 - int[] dx=[0,0,-1,+1];
47 - for(int i=0; i<4; ++i) {
48 - int y = p.y+dy[i];
49 - int x = p.x+dx[i];
50 - if(v[y][x]) continue;
51 - if(y==s.y && x==s.x) {
52 - if(i==0) return tuple('U',step);
53 - if(i==1) return tuple('D',step);
54 - if(i==2) return tuple('R',step);
55 - if(i==3) return tuple('L',step);
56 - } else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
57 - q2 ~= new Pos(y,x);
58 - v[y][x]=true;
59 - } else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') {
60 - q2 ~= new Pos(y,x);
61 - v[y][x]=true;
62 - }
63 - }
21 + int g_wc = 0;
22 +
23 + Game g;
24 + this(const(Game) g)
25 + {
26 + this.g = g.clone();
27 + }
28 +
29 + char single_step()
30 + {
31 + char c = act(g);
32 + g.command(c);
33 + return c;
34 + }
35 +
36 + char act(const(Game) g)
37 + {
38 + const Pos ro = g.map.robot;
39 + const Pos[] la = g.map.lambdas();
40 + const Pos li = g.map.lift;
41 +
42 + char c = 'W';
43 + if( la.empty ) {
44 + auto r = search(g, ro, li);
45 + c = r[0];
46 + } else {
47 + Tuple!(char,int)[] cand;
48 + foreach(lam; la)
49 + cand ~= search(g, ro, lam);
50 + sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
51 + if(c1[1] != c2[1])
52 + return c1[1] < c2[1];
53 + return c1[0] < c2[0];
54 + })(cand);
55 + c = cand[0][0];
56 + }
57 + if(c=='W') {
58 + g_wc++;
59 + if(g_wc > 10)
60 + c = 'A';
64 61 }
65 - q = q2;
62 + else
63 + g_wc = 0;
64 + return c;
66 65 }
67 - q = [o];
68 - v = new bool[][](g.map.H+2, g.map.W+2);
69 - for(int step=1000; q.length; ++step) {
70 - Pos[] q2;
71 - foreach(p; q) {
72 - int[] dy=[-1,+1,0,0];
73 - int[] dx=[0,0,-1,+1];
74 - for(int i=0; i<4; ++i) {
75 - int y = p.y+dy[i];
76 - int x = p.x+dx[i];
77 - if(v[y][x]) continue;
78 - if(y==s.y && x==s.x) {
79 - if(i==0) return tuple('U',step);
80 - if(i==1) return tuple('D',step);
81 - if(i==2) return tuple('R',step);
82 - if(i==3) return tuple('L',step);
83 - } else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
84 - q2 ~= new Pos(y,x);
85 - v[y][x]=true;
86 - } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) {
87 - q2 ~= new Pos(y,x);
88 - v[y][x]=true;
66 +
67 + Tuple!(char,int) search(in Game g, in Pos s, in Pos o)
68 + {
69 + const(Pos)[] q = [o];
70 + bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
71 + for(int step=1; q.length; ++step) {
72 + Pos[] q2;
73 + foreach(p; q) {
74 + int[] dy=[-1,+1,0,0];
75 + int[] dx=[0,0,-1,+1];
76 + for(int i=0; i<4; ++i) {
77 + int y = p.y+dy[i];
78 + int x = p.x+dx[i];
79 + if(v[y][x]) continue;
80 + if(y==s.y && x==s.x) {
81 + if(i==0) return tuple('U',step);
82 + if(i==1) return tuple('D',step);
83 + if(i==2) return tuple('R',step);
84 + if(i==3) return tuple('L',step);
85 + } else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
86 + q2 ~= new Pos(y,x);
87 + v[y][x]=true;
88 + } else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') {
89 + q2 ~= new Pos(y,x);
90 + v[y][x]=true;
91 + }
92 + }
93 + }
94 + q = q2;
95 + }
96 + q = [o];
97 + v = new bool[][](g.map.H+2, g.map.W+2);
98 + for(int step=1000; q.length; ++step) {
99 + Pos[] q2;
100 + foreach(p; q) {
101 + int[] dy=[-1,+1,0,0];
102 + int[] dx=[0,0,-1,+1];
103 + for(int i=0; i<4; ++i) {
104 + int y = p.y+dy[i];
105 + int x = p.x+dx[i];
106 + if(v[y][x]) continue;
107 + if(y==s.y && x==s.x) {
108 + if(i==0) return tuple('U',step);
109 + if(i==1) return tuple('D',step);
110 + if(i==2) return tuple('R',step);
111 + if(i==3) return tuple('L',step);
112 + } else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
113 + q2 ~= new Pos(y,x);
114 + v[y][x]=true;
115 + } else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) {
116 + q2 ~= new Pos(y,x);
117 + v[y][x]=true;
118 + }
89 119 }
90 120 }
121 + q = q2;
91 122 }
92 - q = q2;
123 + return tuple('W', int.max);
93 124 }
94 - return tuple('W', int.max);
95 -}
96 -
97 -void main(string[] args)
98 -{
99 - auto g = Game.load(stdin);
100 - g.set_output(new GuardedOutput(g));
101 -
102 - while(!g.dead && !g.cleared)
103 - act(g);
104 125 }