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.H+2, g.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.robot != g.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.robot;
60 const Pos li = g.lift;
61 Pos[] la = g.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.razors();
68 const(Pos)[] hi = g.higes();
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.num_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[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.H; ++y)
91 for(int x=1; x<=g.W; ++x)
92 if(g[y,x]=='.'||g[y,x]==' ') {
93 his = 0;
94 for(int dy=-1; dy<=+1; ++dy)
95 for(int dx=-1; dx<=+1; ++dx)
96 if(g[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.H; ++y)
109 for(int x=1; x<=g.W; ++x)
110 if(g[y,x]=='.')
111 if(g[y+1,x]=='*'||g[y+1,x-1]=='*'||g[y+1,x+1]=='*'
112 ||g[y,x+1]=='*'||g[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.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[y,x] == ' ' || g[y,x] == 'R')
165 return false;
166 if(g[y+1,x] == '*')
167 return true;
168 if(g[y+1,x-1]=='*' && (g[y,x-1]=='\\'||g[y,x-1]=='*') && (g[y+1,x]==' '||g[y+1,x]=='R'))
169 return true;
170 if(g[y+1,x+1]=='*' && (g[y,x+1]=='*') && (g[y+1,x]==' '||g[y+1,x]=='R'))
171 return true;
172 if(g[y,x-1]=='*' && (g[y-1,x-1]=='\\'||g[y-1,x-1]=='*') && (g[y-1,x]==' '||g[y-1,x]=='R'))
173 return true;
174 if(g[y,x+1]=='*' && (g[y-1,x+1]=='*') && (g[y-1,x]==' '||g[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.H+2, g.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[y,x]&&g[y,x]<='9') {
196 foreach(ppp; g.trampoline_rev(g[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[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[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.H+2, g.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[y,x]&&g[y,x]<='9') {
236 foreach(ppp; g.trampoline_rev(g[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[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[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.H+2, g.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[p] == '*') {
274 if(i>=4)continue;
275 if(y!=p.y)continue;
276 if(g[y,p.x+(p.x-x)]!=' '&&g[y,p.x+(p.x-x)]!='R')continue;
277 }
278 if('1'<=g[y,x]&&g[y,x]<='9') {
279 foreach(ppp; g.trampoline_rev(g[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[y,x]==' '||g[y,x]=='\\'||g[y,x]=='.'||g[y,x]=='*'||g[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 bool plan_broken = true;
309
310 Game g;
311 this(in Game g)
312 {
313 this.g = g.clone();
314 make_plan(g);
315 }
316
317 Tuple!(Solver,string) run_sub_solver(in Game g)
318 {
319 string log;
320 auto s = new Solver(g);
321 while(!g.cleared && !g.dead && plan.length<=g.H*g.W) {
322 char c = s.single_step();
323 if( c == 'A' )
324 break;
325 log ~= c;
326 }
327 while(log.length>0 && log[$-1]=='W')
328 log.length--;
329 return tuple(s, log);
330 }
331
332 void make_plan(in Game g) {
333 plan_broken = false;
334 Tuple!(Solver,string) x = run_sub_solver(g);
335 plan = x[1];
336 if(x[0].g.cleared)
337 return;
338 modify_plan(g, x[0].g.score);
339 }
340
341 void modify_plan(in Game ini, long unmod)
342 {
343 int bp = max(0, (cast(int)plan.length)-10);
344 Game g = ini.clone();
345 for(int i=0; i<bp; ++i) g.command(plan[i]);
346
347 Tuple!(string,long) cand = tuple(plan, unmod);
348 for(int i=bp; i<plan.length; ++i) {
349 foreach(string c; ["U","D","L","R","UD","DU","LR","RL"])
350 if(c[0] != plan[i]) {
351 Tuple!(string,long) zz = try_plan(c, g);
352 if(cand[1]<zz[1])
353 cand = tuple(plan[0..i]~c~zz[0], zz[1]);
354 }
355 g.command(plan[i]);
356 }
357 plan = cand[0];
358 }
359
360 Tuple!(string,long) try_plan(string c, in Game g)
361 {
362 Game gg = g.clone();
363 foreach(cc;c)gg.command(cc);
364 Tuple!(Solver, string) x = run_sub_solver(gg);
365 return tuple(x[1], x[0].g.score);
366 }
367
368 char single_step() {
369 if(plan_broken)
370 make_plan(g);
371 if(plan.empty)
372 return 'A';
373 char c = plan[0];
374 plan = plan[1..$];
375 g.command(c);
376 return c;
377 }
378
379 void force(char c) {
380 g.command(c);
381 if(plan.length==0 || plan[0]!=c) {
382 plan = "";
383 plan_broken = true;
384 }
385 else
386 plan = plan[1..$];
387 }
388 }
389
390 alias Solver_2!(Solver_1) MainSolver;
391 //alias Solver_1 MainSolver;