Differences From Artifact [42b4ef037737dcd0]:
- File
src/solver.d
- 2012-07-15 11:17:59 - part of checkin [ff0ab77d3d] on branch trunk - new game class. (user: kinaba) [annotate]
To Artifact [22c356ff1975e92f]:
- File
src/solver.d
- 2012-07-15 12:01:04 - part of checkin [a03584f1c6] on branch trunk - Refactored. (user: kinaba) [annotate]
3 3
4 class Solver_0 4 class Solver_0
5 { 5 {
6 this(in Game g) {} 6 this(in Game g) {}
7 char single_step() { return 'W'; } 7 char single_step() { return 'W'; }
8 void force(char c) {} 8 void force(char c) {}
9 } 9 }
10 /* <
> 10
11 class Solver_1 11 class Solver_1
12 { 12 {
13 int wait_count = 0; 13 int wait_count = 0;
14 int choke_count = 0; 14 int choke_count = 0;
15 15
16 Game g; 16 Game g;
17 this(in Game g) 17 this(in Game g)
18 { 18 {
19 this.g = g.clone(); 19 this.g = g.clone();
20 forbidden_cell = new bool[][](g.map.H+2, g.map.W+2); | 20 forbidden_cell = new bool[][](g.H+2, g.W+2);
21 } 21 }
22 22
23 char single_step() 23 char single_step()
24 { 24 {
25 Tuple!(string,int) de = death_move(g); 25 Tuple!(string,int) de = death_move(g);
26 char c = act(g, de[0], de[1]); 26 char c = act(g, de[0], de[1]);
27 force(c); 27 force(c);
................................................................................................................................................................................
39 string death; 39 string death;
40 int choice = 0; 40 int choice = 0;
41 foreach(char c; "UDLRW") { 41 foreach(char c; "UDLRW") {
42 Game gg = g.clone(); 42 Game gg = g.clone();
43 gg.command(c); 43 gg.command(c);
44 if( !gg.cleared && gg.dead ) 44 if( !gg.cleared && gg.dead )
45 death ~= c; 45 death ~= c;
46 else if( gg.map.robot != g.map.robot ) | 46 else if( gg.robot != g.robot )
47 choice++; 47 choice++;
48 else if( c != 'W' ) // meaningless move 48 else if( c != 'W' ) // meaningless move
49 death ~= c; 49 death ~= c;
50 } 50 }
51 return tuple(death, choice); 51 return tuple(death, choice);
52 } 52 }
53 53
54 Tuple!(Pos, int)[] log; 54 Tuple!(Pos, int)[] log;
55 bool[][] forbidden_cell; 55 bool[][] forbidden_cell;
56 56
57 char act(const(Game) g, string death, int breath) 57 char act(const(Game) g, string death, int breath)
58 { 58 {
59 const Pos ro = g.map.robot; | 59 const Pos ro = g.robot;
60 const Pos li = g.map.lift; | 60 const Pos li = g.lift;
61 Pos[] la = g.map.lambdas(); | 61 Pos[] la = g.lambdas();
62 sort!((Pos a,Pos b){ 62 sort!((Pos a,Pos b){
63 int ad=abs(a.y-li.y)+abs(a.x-li.x); 63 int ad=abs(a.y-li.y)+abs(a.x-li.x);
64 int bd=abs(b.y-li.y)+abs(b.x-li.x); 64 int bd=abs(b.y-li.y)+abs(b.x-li.x);
65 return ad>bd;; 65 return ad>bd;;
66 })(la); 66 })(la);
67 Pos[] ra = g.map.razors(); | 67 Pos[] ra = g.razors();
68 const(Pos)[] hi = g.map.objects('W'); | 68 const(Pos)[] hi = g.higes();
69 69
70 Tuple!(char,int)[] cand; 70 Tuple!(char,int)[] cand;
71 char c = 'W'; 71 char c = 'W';
72 if( la.empty ) { 72 if( la.empty ) {
73 cand = search(g, ro, [li], death); 73 cand = search(g, ro, [li], death);
74 } else { 74 } else {
75 cand ~= search(g, ro, la~ra, death); 75 cand ~= search(g, ro, la~ra, death);
76 } 76 }
77 77
78 // 'higesori' mode 78 // 'higesori' mode
79 if( !hi.empty && g.map.razor>0 ) { | 79 if( !hi.empty && g.num_razor>0 ) {
80 int his = 0; 80 int his = 0;
81 for(int dy=-1; dy<=+1; ++dy) 81 for(int dy=-1; dy<=+1; ++dy)
82 for(int dx=-1; dx<=+1; ++dx) 82 for(int dx=-1; dx<=+1; ++dx)
83 if(g.map[ro.y+dy,ro.x+dx] == 'W') | 83 if(g[ro.y+dy,ro.x+dx] == 'W')
84 his++; 84 his++;
85 85
86 if(his>=2 || his==hi.length) 86 if(his>=2 || his==hi.length)
87 cand = [tuple('S',int.max)]; 87 cand = [tuple('S',int.max)];
88 if(cand.empty) { 88 if(cand.empty) {
89 const(Pos)[] tgt; 89 const(Pos)[] tgt;
90 for(int y=1; y<=g.map.H; ++y) | 90 for(int y=1; y<=g.H; ++y)
91 for(int x=1; x<=g.map.W; ++x) | 91 for(int x=1; x<=g.W; ++x)
92 if(g.map[y,x]=='.'||g.map[y,x]==' ') { | 92 if(g[y,x]=='.'||g[y,x]==' ') {
93 his = 0; 93 his = 0;
94 for(int dy=-1; dy<=+1; ++dy) 94 for(int dy=-1; dy<=+1; ++dy)
95 for(int dx=-1; dx<=+1; ++dx) 95 for(int dx=-1; dx<=+1; ++dx)
96 if(g.map[y+dy,x+dx] == ' | 96 if(g[y+dy,x+dx] == 'W')
97 his++; 97 his++;
98 if(his>=2) 98 if(his>=2)
99 tgt ~= new Pos(y,x); 99 tgt ~= new Pos(y,x);
100 } 100 }
101 cand ~= search(g, ro, tgt, death, true); 101 cand ~= search(g, ro, tgt, death, true);
102 } 102 }
103 } 103 }
104 104
105 // 'dig' mode 105 // 'dig' mode
106 if(cand.empty) { 106 if(cand.empty) {
107 const(Pos)[] tgt; 107 const(Pos)[] tgt;
108 for(int y=1; y<=g.map.H; ++y) | 108 for(int y=1; y<=g.H; ++y)
109 for(int x=1; x<=g.map.W; ++x) | 109 for(int x=1; x<=g.W; ++x)
110 if(g.map[y,x]=='.') | 110 if(g[y,x]=='.')
111 if(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='* | 111 if(g[y+1,x]=='*'||g[y+1,x-1]=='*'||g[y+1
112 ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*') | 112 ||g[y,x+1]=='*'||g[y,x-1]=='*')
113 tgt ~= new Pos(y,x); 113 tgt ~= new Pos(y,x);
114 cand ~= search(g, ro, tgt, death, true); 114 cand ~= search(g, ro, tgt, death, true);
115 } 115 }
116 116
117 if(cand.empty) { 117 if(cand.empty) {
118 choke_count++; 118 choke_count++;
119 cand ~= tuple('W',int.max); 119 cand ~= tuple('W',int.max);
................................................................................................................................................................................
133 } 133 }
134 } 134 }
135 135
136 if(c == 'W') 136 if(c == 'W')
137 wait_count++; 137 wait_count++;
138 else 138 else
139 wait_count = 0; 139 wait_count = 0;
140 if(choke_count >= g.map.H) | 140 if(choke_count >= g.H)
141 c = 'A'; 141 c = 'A';
142 142
143 bool[char] choice; 143 bool[char] choice;
144 foreach(t; cand) 144 foreach(t; cand)
145 choice[t[0]] = true; 145 choice[t[0]] = true;
146 log ~= tuple(ro.clone(), cast(int)choice.length); 146 log ~= tuple(ro.clone(), cast(int)choice.length);
147 if(log.length > 5) 147 if(log.length > 5)
................................................................................................................................................................................
157 return c; 157 return c;
158 } 158 }
159 159
160 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death 160 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death
161 { 161 {
162 bool danger(int y, int x) 162 bool danger(int y, int x)
163 { 163 {
164 if(g.map[y,x] == ' ' || g.map[y,x] == 'R') | 164 if(g[y,x] == ' ' || g[y,x] == 'R')
165 return false; 165 return false;
166 if(g.map[y+1,x] == '*') | 166 if(g[y+1,x] == '*')
> 167 return true;
> 168 if(g[y+1,x-1]=='*' && (g[y,x-1]=='\\'||g[y,x-1]=='*') &&
167 return true; 169 return true;
168 if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x | 170 if(g[y+1,x+1]=='*' && (g[y,x+1]=='*') && (g[y+1,x]==' '|
169 return true; 171 return true;
170 if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[ | 172 if(g[y,x-1]=='*' && (g[y-1,x-1]=='\\'||g[y-1,x-1]=='*')
171 return true; 173 return true;
172 if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1 | 174 if(g[y,x+1]=='*' && (g[y-1,x+1]=='*') && (g[y-1,x]==' '|
173 return true; <
174 if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[ <
175 return true; 175 return true;
176 return false; 176 return false;
177 } 177 }
178 178
179 // avoid directly below '*' 179 // avoid directly below '*'
180 Tuple!(char,int)[] tryA() { 180 Tuple!(char,int)[] tryA() {
181 const(Pos)[] q; 181 const(Pos)[] q;
182 foreach(p; gs) 182 foreach(p; gs)
183 if(!danger(p.y,p.x)) 183 if(!danger(p.y,p.x))
184 q ~= p; 184 q ~= p;
185 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); | 185 bool[][] v = new bool[][](g.H+2, g.W+2);
186 foreach(p; q) v[p.y][p.x]=true; 186 foreach(p; q) v[p.y][p.x]=true;
187 for(int step=1; q.length; ++step) { 187 for(int step=1; q.length; ++step) {
188 Pos[] q2; 188 Pos[] q2;
189 foreach(p; q) { 189 foreach(p; q) {
190 int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 190 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
191 int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 191 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
192 for(int i=0; i<yyy.length; ++i) { 192 for(int i=0; i<yyy.length; ++i) {
193 int y = yyy[i]; 193 int y = yyy[i];
194 int x = xxx[i]; 194 int x = xxx[i];
195 if('1'<=g.map[y,x]&&g.map[y,x]<= | 195 if('1'<=g[y,x]&&g[y,x]<='9') {
196 foreach(ppp; g.map.tr_so | 196 foreach(ppp; g.trampolin
197 yyy ~= ppp.y; 197 yyy ~= ppp.y;
198 xxx ~= ppp.x; 198 xxx ~= ppp.x;
199 } 199 }
200 continue; 200 continue;
201 } 201 }
202 if(v[y][x]) continue; 202 if(v[y][x]) continue;
203 if(y==s.y && x==s.x && i<4) { 203 if(y==s.y && x==s.x && i<4) {
204 char c = "UDRL"[i]; 204 char c = "UDRL"[i];
205 if( death.count(c) == 0 205 if( death.count(c) == 0
206 return [tuple(c, 206 return [tuple(c,
207 } else if(forbidden_cell[y][x]){ 207 } else if(forbidden_cell[y][x]){
208 } else if(g.map[y,x]==' '||g.map | 208 } else if(g[y,x]==' '||g[y,x]=='
209 if(danger(y,x)) 209 if(danger(y,x))
210 continue; 210 continue;
211 q2 ~= new Pos(y,x); 211 q2 ~= new Pos(y,x);
212 v[y][x]=true; 212 v[y][x]=true;
213 } 213 }
214 } 214 }
215 } 215 }
................................................................................................................................................................................
218 return []; 218 return [];
219 } 219 }
220 220
221 // any empty space is my ground 221 // any empty space is my ground
222 Tuple!(char,int)[] tryB() { 222 Tuple!(char,int)[] tryB() {
223 const(Pos)[] q; 223 const(Pos)[] q;
224 foreach(p; gs) q ~= p; 224 foreach(p; gs) q ~= p;
225 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); | 225 bool[][] v = new bool[][](g.H+2, g.W+2);
226 foreach(p; q) v[p.y][p.x]=true; 226 foreach(p; q) v[p.y][p.x]=true;
227 for(int step=10; q.length; ++step) { 227 for(int step=10; q.length; ++step) {
228 Pos[] q2; 228 Pos[] q2;
229 foreach(p; q) { 229 foreach(p; q) {
230 int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 230 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
231 int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 231 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
232 for(int i=0; i<yyy.length; ++i) { 232 for(int i=0; i<yyy.length; ++i) {
233 int y = yyy[i]; 233 int y = yyy[i];
234 int x = xxx[i]; 234 int x = xxx[i];
235 if('1'<=g.map[y,x]&&g.map[y,x]<= | 235 if('1'<=g[y,x]&&g[y,x]<='9') {
236 foreach(ppp; g.map.tr_so | 236 foreach(ppp; g.trampolin
237 yyy ~= ppp.y; 237 yyy ~= ppp.y;
238 xxx ~= ppp.x; 238 xxx ~= ppp.x;
239 } 239 }
240 continue; 240 continue;
241 } 241 }
242 if(v[y][x]) continue; 242 if(v[y][x]) continue;
243 if(y==s.y && x==s.x && i<4) { 243 if(y==s.y && x==s.x && i<4) {
244 char c = "UDRL"[i]; 244 char c = "UDRL"[i];
245 if( death.count(c) == 0 245 if( death.count(c) == 0
246 return [tuple(c, 246 return [tuple(c,
247 } else if(forbidden_cell[y][x]){ 247 } else if(forbidden_cell[y][x]){
248 } else if(g.map[y,x]==' '||g.map | 248 } else if(g[y,x]==' '||g[y,x]=='
249 q2 ~= new Pos(y,x); 249 q2 ~= new Pos(y,x);
250 v[y][x]=true; 250 v[y][x]=true;
251 } 251 }
252 } 252 }
253 } 253 }
254 q = q2; 254 q = q2;
255 } 255 }
................................................................................................................................................................................
256 return []; 256 return [];
257 } 257 }
258 258
259 // push rocks! 259 // push rocks!
260 Tuple!(char,int)[] tryC() { 260 Tuple!(char,int)[] tryC() {
261 const(Pos)[] q; 261 const(Pos)[] q;
262 foreach(p; gs) q ~= p; 262 foreach(p; gs) q ~= p;
263 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); | 263 bool[][] v = new bool[][](g.H+2, g.W+2);
264 foreach(p; q) v[p.y][p.x]=true; 264 foreach(p; q) v[p.y][p.x]=true;
265 for(int step=20; q.length; ++step) { 265 for(int step=20; q.length; ++step) {
266 Pos[] q2; 266 Pos[] q2;
267 foreach(p; q) { 267 foreach(p; q) {
268 int[] yyy=[p.y-1,p.y+1,p.y,p.y]; 268 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
269 int[] xxx=[p.x,p.x,p.x-1,p.x+1]; 269 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
270 for(int i=0; i<yyy.length; ++i) { 270 for(int i=0; i<yyy.length; ++i) {
271 int y = yyy[i]; 271 int y = yyy[i];
272 int x = xxx[i]; 272 int x = xxx[i];
273 if(g.map[p] == '*') { | 273 if(g[p] == '*') {
274 if(i>=4)continue; 274 if(i>=4)continue;
275 if(y!=p.y)continue; 275 if(y!=p.y)continue;
276 if(g.map[y,p.x+(p.x-x)]! | 276 if(g[y,p.x+(p.x-x)]!=' '
277 } 277 }
278 if('1'<=g.map[y,x]&&g.map[y,x]<= | 278 if('1'<=g[y,x]&&g[y,x]<='9') {
279 foreach(ppp; g.map.tr_so | 279 foreach(ppp; g.trampolin
280 yyy ~= ppp.y; 280 yyy ~= ppp.y;
281 xxx ~= ppp.x; 281 xxx ~= ppp.x;
282 } 282 }
283 continue; 283 continue;
284 } 284 }
285 if(v[y][x]) continue; 285 if(v[y][x]) continue;
286 if(y==s.y && x==s.x && i<4) { 286 if(y==s.y && x==s.x && i<4) {
287 char c = "UDRL"[i]; 287 char c = "UDRL"[i];
288 if( death.count(c) == 0 288 if( death.count(c) == 0
289 return [tuple(c, 289 return [tuple(c,
290 } else if(forbidden_cell[y][x]){ 290 } else if(forbidden_cell[y][x]){
291 } else if(g.map[y,x]==' '||g.map | 291 } else if(g[y,x]==' '||g[y,x]=='
292 q2 ~= new Pos(y,x); 292 q2 ~= new Pos(y,x);
293 v[y][x]=true; 293 v[y][x]=true;
294 } 294 }
295 } 295 }
296 } 296 }
297 q = q2; 297 q = q2;
298 } 298 }
................................................................................................................................................................................
314 make_plan(g); 314 make_plan(g);
315 } 315 }
316 316
317 Tuple!(Solver,string) run_sub_solver(in Game g) 317 Tuple!(Solver,string) run_sub_solver(in Game g)
318 { 318 {
319 string log; 319 string log;
320 auto s = new Solver(g); 320 auto s = new Solver(g);
321 while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) { | 321 while(!g.cleared && !g.dead && plan.length<=g.H*g.W) {
322 char c = s.single_step(); 322 char c = s.single_step();
323 if( c == 'A' ) 323 if( c == 'A' )
324 break; 324 break;
325 log ~= c; 325 log ~= c;
326 } 326 }
327 while(log.length>0 && log[$-1]=='W') 327 while(log.length>0 && log[$-1]=='W')
328 log.length--; 328 log.length--;
................................................................................................................................................................................
383 plan_broken = true; 383 plan_broken = true;
384 } 384 }
385 else 385 else
386 plan = plan[1..$]; 386 plan = plan[1..$];
387 } 387 }
388 } 388 }
389 389
390 //alias Solver_2!(Solver_1) MainSolver; | 390 alias Solver_2!(Solver_1) MainSolver;
391 alias Solver_1 MainSolver; | 391 //alias Solver_1 MainSolver;
392 */ <