1 import util;
2 import game;
3
4 class Solver_0
5 {
6 this(in Game g) {}
7 char single_step() { return 'W'; }
8 void force(char c) {}
9 }
10
11 class Solver_1
12 {
13 int wait_count = 0;
14 int choke_count = 0;
15
16 Game g;
17 this(in Game g)
18 {
19 this.g = g.clone();
20 forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
21 }
22
23 char single_step()
24 {
25 Tuple!(string,int) de = death_move(g);
26 char c = act(g, de[0], de[1]);
27 force(c);
28 return c;
29 }
30
31 void force(char c)
32 {
33 if(c != 'A')
34 g.command(c);
35 }
36
37 Tuple!(string,int) death_move(const(Game) g)
38 {
39 string death;
40 int choice = 0;
41 foreach(char c; "UDLRW") {
42 Game gg = g.clone();
43 gg.command(c);
44 if( !gg.cleared && gg.dead )
45 death ~= c;
46 else if( gg.map.robot != g.map.robot )
47 choice++;
48 else if( c != 'W' ) // meaningless move
49 death ~= c;
50 }
51 return tuple(death, choice);
52 }
53
54 Tuple!(Pos, int)[] log;
55 bool[][] forbidden_cell;
56
57 char act(const(Game) g, string death, int breath)
58 {
59 const Pos ro = g.map.robot;
60 const Pos li = g.map.lift;
61 Pos[] la = g.map.lambdas();
62 sort!((Pos a,Pos b){
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);
65 return ad>bd;;
66 })(la);
67 Pos[] ra = g.map.razors();
68 const(Pos)[] hi = g.map.objects('W');
69
70 Tuple!(char,int)[] cand;
71 char c = 'W';
72 if( la.empty ) {
73 cand = search(g, ro, [li], death);
74 } else {
75 cand ~= search(g, ro, la~ra, death);
76 }
77
78 // 'higesori' mode
79 if( !hi.empty && g.map.razor>0 ) {
80 int his = 0;
81 for(int dy=-1; dy<=+1; ++dy)
82 for(int dx=-1; dx<=+1; ++dx)
83 if(g.map[ro.y+dy,ro.x+dx] == 'W')
84 his++;
85
86 if(his>=2 || his==hi.length)
87 cand = [tuple('S',int.max)];
88 if(cand.empty) {
89 const(Pos)[] tgt;
90 for(int y=1; y<=g.map.H; ++y)
91 for(int x=1; x<=g.map.W; ++x)
92 if(g.map[y,x]=='.'||g.map[y,x]==' ') {
93 his = 0;
94 for(int dy=-1; dy<=+1; ++dy)
95 for(int dx=-1; dx<=+1; ++dx)
96 if(g.map[y+dy,x+dx] == 'W')
97 his++;
98 if(his>=2)
99 tgt ~= new Pos(y,x);
100 }
101 cand ~= search(g, ro, tgt, death, true);
102 }
103 }
104
105 // 'dig' mode
106 if(cand.empty) {
107 const(Pos)[] tgt;
108 for(int y=1; y<=g.map.H; ++y)
109 for(int x=1; x<=g.map.W; ++x)
110 if(g.map[y,x]=='.')
111 if(g.map[y+1,x]=='*'||g.map[y+1,x-1]=='*'||g.map[y+1,x+1]=='*'
112 ||g.map[y,x+1]=='*'||g.map[y,x-1]=='*')
113 tgt ~= new Pos(y,x);
114 cand ~= search(g, ro, tgt, death, true);
115 }
116
117 if(cand.empty) {
118 choke_count++;
119 cand ~= tuple('W',int.max);
120 }
121 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
122 if(c1[1] != c2[1])
123 return c1[1] < c2[1];
124 return c1[0] < c2[0];
125 })(cand);
126 c = cand[0][0];
127
128 if(death.count(c) || wait_count>=2) {
129 foreach(char live; "UDLRW")
130 if(death.count(live)==0) {
131 c=live;
132 break;
133 }
134 }
135
136 if(c == 'W')
137 wait_count++;
138 else
139 wait_count = 0;
140 if(choke_count >= g.map.H)
141 c = 'A';
142
143 bool[char] choice;
144 foreach(t; cand)
145 choice[t[0]] = true;
146 log ~= tuple(ro.clone(), cast(int)choice.length);
147 if(log.length > 5)
148 log = log[$-5..$];
149 int cnt = 0;
150 foreach(l; log)
151 if(l[0] == log[$-1][0])
152 ++cnt;
153 if( cnt >= 3 && breath==1 ) {
154 forbidden_cell[ro.y][ro.x] = true;
155 }
156
157 return c;
158 }
159
160 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
161 {
162 bool danger(int y, int x)
163 {
164 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
165 return false;
166 if(g.map[y+1,x] == '*')
167 return true;
168 if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x-1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
169 return true;
170 if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
171 return true;
172 if(g.map[y,x-1]=='*' && (g.map[y-1,x-1]=='\\'||g.map[y-1,x-1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
173 return true;
174 if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
175 return true;
176 return false;
177 }
178
179 // avoid directly below '*'
180 Tuple!(char,int)[] tryA() {
181 const(Pos)[] q;
182 foreach(p; gs)
183 if(!danger(p.y,p.x))
184 q ~= p;
185 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
186 foreach(p; q) v[p.y][p.x]=true;
187 for(int step=1; q.length; ++step) {
188 Pos[] q2;
189 foreach(p; q) {
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];
192 for(int i=0; i<yyy.length; ++i) {
193 int y = yyy[i];
194 int x = xxx[i];
195 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
196 foreach(ppp; g.map.tr_source[g.map[y,x]]) {
197 yyy ~= ppp.y;
198 xxx ~= ppp.x;
199 }
200 continue;
201 }
202 if(v[y][x]) continue;
203 if(y==s.y && x==s.x && i<4) {
204 char c = "UDRL"[i];
205 if( death.count(c) == 0 )
206 return [tuple(c,step)];
207 } else if(forbidden_cell[y][x]){
208 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
209 if(danger(y,x))
210 continue;
211 q2 ~= new Pos(y,x);
212 v[y][x]=true;
213 }
214 }
215 }
216 q = q2;
217 }
218 return [];
219 }
220
221 // any empty space is my ground
222 Tuple!(char,int)[] tryB() {
223 const(Pos)[] q;
224 foreach(p; gs) q ~= p;
225 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
226 foreach(p; q) v[p.y][p.x]=true;
227 for(int step=10; q.length; ++step) {
228 Pos[] q2;
229 foreach(p; q) {
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];
232 for(int i=0; i<yyy.length; ++i) {
233 int y = yyy[i];
234 int x = xxx[i];
235 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
236 foreach(ppp; g.map.tr_source[g.map[y,x]]) {
237 yyy ~= ppp.y;
238 xxx ~= ppp.x;
239 }
240 continue;
241 }
242 if(v[y][x]) continue;
243 if(y==s.y && x==s.x && i<4) {
244 char c = "UDRL"[i];
245 if( death.count(c) == 0 )
246 return [tuple(c,step)];
247 } else if(forbidden_cell[y][x]){
248 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
249 q2 ~= new Pos(y,x);
250 v[y][x]=true;
251 }
252 }
253 }
254 q = q2;
255 }
256 return [];
257 }
258
259 // push rocks!
260 Tuple!(char,int)[] tryC() {
261 const(Pos)[] q;
262 foreach(p; gs) q ~= p;
263 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
264 foreach(p; q) v[p.y][p.x]=true;
265 for(int step=20; q.length; ++step) {
266 Pos[] q2;
267 foreach(p; q) {
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];
270 for(int i=0; i<yyy.length; ++i) {
271 int y = yyy[i];
272 int x = xxx[i];
273 if(g.map[p] == '*') {
274 if(i>=4)continue;
275 if(y!=p.y)continue;
276 if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
277 }
278 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
279 foreach(ppp; g.map.tr_source[g.map[y,x]]) {
280 yyy ~= ppp.y;
281 xxx ~= ppp.x;
282 }
283 continue;
284 }
285 if(v[y][x]) continue;
286 if(y==s.y && x==s.x && i<4) {
287 char c = "UDRL"[i];
288 if( death.count(c) == 0 )
289 return [tuple(c,step)];
290 } else if(forbidden_cell[y][x]){
291 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='*'||g.map[y,x]=='!'||i>=4) {
292 q2 ~= new Pos(y,x);
293 v[y][x]=true;
294 }
295 }
296 }
297 q = q2;
298 }
299 return [];
300 }
301 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
302 }
303 }
304
305 class Solver_2(Solver)
306 {
307 string plan;
308
309 Game g;
310 this(in Game g)
311 {
312 this.g = g.clone();
313 make_plan(g);
314 }
315
316 Tuple!(Solver,string) run_sub_solver(in Game g)
317 {
318 string log;
319 auto s = new Solver(g);
320 while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) {
321 char c = s.single_step();
322 if( c == 'A' )
323 break;
324 log ~= c;
325 }
326 while(log.length>0 && log[$-1]=='W')
327 log.length--;
328 return tuple(s, log);
329 }
330
331 void make_plan(in Game g) {
332 Tuple!(Solver,string) x = run_sub_solver(g);
333 plan = x[1];
334 if(x[0].g.cleared)
335 return;
336 modify_plan(g, x[0].g.score);
337 }
338
339 void modify_plan(in Game ini, long unmod)
340 {
341 int bp = max(0, (cast(int)plan.length)-10);
342 Game g = ini.clone();
343 for(int i=0; i<bp; ++i) g.command(plan[i]);
344
345 Tuple!(string,long) cand = tuple(plan, unmod);
346 for(int i=bp; i<plan.length; ++i) {
347 foreach(string c; ["U","D","L","R","UD","DU","LR","RL"])
348 if(c[0] != plan[i]) {
349 Tuple!(string,long) zz = try_plan(c, g);
350 if(cand[1]<zz[1])
351 cand = tuple(plan[0..i]~c~zz[0], zz[1]);
352 }
353 g.command(plan[i]);
354 }
355 plan = cand[0];
356 }
357
358 Tuple!(string,long) try_plan(string c, in Game g)
359 {
360 Game gg = g.clone();
361 foreach(cc;c)gg.command(cc);
362 Tuple!(Solver, string) x = run_sub_solver(gg);
363 return tuple(x[1], x[0].g.score);
364 }
365
366 char single_step() {
367 if(plan.empty)
368 return 'A';
369 char c = plan[0];
370 plan = plan[1..$];
371 g.command(c);
372 return c;
373 }
374
375 void force(char c) {
376 g.command(c);
377 make_plan(g);
378 }
379 }
380
381 alias Solver_2!(Solver_1) MainSolver;
382 //alias Solver_1 MainSolver;