1 import util;
2 import game;
3
4 bool rocky(char c){ return c=='*'||c=='@'; }
5
6 interface Solver
7 {
8 // this(in Game g);
9 char single_step();
10 void force(char c);
11 }
12
13 class Solver_0 : Solver
14 {
15 this(in Game g) {}
16 char single_step() { return 'W'; }
17 void force(char c) {}
18 }
19
20 class Solver_1 : Solver
21 {
22 int wait_count = 0;
23 int choke_count = 0;
24
25 Game g;
26 this(in Game g)
27 {
28 this.g = g.clone();
29 forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
30 }
31
32 char single_step()
33 {
34 Tuple!(string,int) de = death_move(g);
35 char c = act(g, de[0], de[1]);
36 force(c);
37 return c;
38 }
39
40 void force(char c)
41 {
42 if(c != 'A')
43 g.command(c);
44 }
45
46 Tuple!(string,int) death_move(const(Game) g)
47 {
48 string death;
49 int choice = 0;
50 foreach(char c; "UDLRW") {
51 Game gg = g.clone();
52 gg.command(c);
53 if( !gg.cleared && gg.dead )
54 death ~= c;
55 else if( gg.map.robot != g.map.robot )
56 choice++;
57 else if( c != 'W' ) // meaningless move
58 death ~= c;
59 }
60 return tuple(death, choice);
61 }
62
63 Tuple!(Pos, int)[] log;
64 bool[][] forbidden_cell;
65
66 char act(const(Game) g, string death, int breath)
67 {
68 const Pos ro = g.map.robot;
69 const Pos li = g.map.lift;
70 Pos[] la = g.map.lambdas();
71 sort!((Pos a,Pos b){
72 int ad=abs(a.y-li.y)+abs(a.x-li.x);
73 int bd=abs(b.y-li.y)+abs(b.x-li.x);
74 return ad>bd;;
75 })(la);
76 Pos[] ra = g.map.razors();
77 const(Pos)[] hi = g.map.objects('W');
78
79 Tuple!(char,int)[] cand;
80 char c = 'W';
81 if( g.map.collected_lambda == g.map.total_lambda ) {
82 cand = search(g, ro, [li], death);
83 } else if( !la.empty ){
84 cand ~= search(g, ro, la~ra, death);
85 }
86
87 // 'higesori' mode
88 if( !hi.empty && g.map.razor>0 ) {
89 int his = 0;
90 for(int dy=-1; dy<=+1; ++dy)
91 for(int dx=-1; dx<=+1; ++dx)
92 if(g.map[ro.y+dy,ro.x+dx] == 'W')
93 his++;
94
95 if(his>=2 || his==hi.length)
96 cand = [tuple('S',int.max)];
97 if(cand.empty) {
98 const(Pos)[] tgt;
99 for(int y=1; y<=g.map.H; ++y)
100 for(int x=1; x<=g.map.W; ++x)
101 if(g.map[y,x]=='.'||g.map[y,x]==' ') {
102 his = 0;
103 for(int dy=-1; dy<=+1; ++dy)
104 for(int dx=-1; dx<=+1; ++dx)
105 if(g.map[y+dy,x+dx] == 'W')
106 his++;
107 if(his>=2)
108 tgt ~= new Pos(y,x);
109 }
110 cand ~= search(g, ro, tgt, death, true);
111 }
112 }
113
114 // 'dig' mode
115 if(cand.empty) {
116 const(Pos)[] tgt;
117 for(int y=1; y<=g.map.H; ++y)
118 for(int x=1; x<=g.map.W; ++x)
119 if(g.map[y,x]=='.')
120 if(rocky(g.map[y+1,x])||rocky(g.map[y+1,x-1])||rocky(g.map[y+1,x+1])
121 ||rocky(g.map[y,x+1])||rocky(g.map[y,x-1]))
122 tgt ~= new Pos(y,x);
123 cand ~= search(g, ro, tgt, death, true);
124 }
125
126 if(cand.empty) {
127 choke_count++;
128 cand ~= tuple('W',int.max);
129 }
130 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
131 if(c1[1] != c2[1])
132 return c1[1] < c2[1];
133 return c1[0] < c2[0];
134 })(cand);
135 c = cand[0][0];
136
137 if(death.count(c) || wait_count>=2) {
138 foreach(char live; "UDLRW")
139 if(death.count(live)==0) {
140 c=live;
141 break;
142 }
143 }
144
145 if(c == 'W')
146 wait_count++;
147 else
148 wait_count = 0;
149 if(wait_count==2)
150 c = 'A';
151 if(choke_count >= g.map.H)
152 c = 'A';
153
154 bool[char] choice;
155 foreach(t; cand)
156 choice[t[0]] = true;
157 log ~= tuple(ro.clone(), cast(int)choice.length);
158 if(log.length > 5)
159 log = log[$-5..$];
160 int cnt = 0;
161 foreach(l; log)
162 if(l[0] == log[$-1][0])
163 ++cnt;
164 if( cnt >= 3 && breath==1 ) {
165 forbidden_cell[ro.y][ro.x] = true;
166 }
167
168 return c;
169 }
170
171 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death, bool danger_ok=false)
172 {
173 bool danger(int y, int x)
174 {
175 if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
176 return false;
177 if(rocky(g.map[y+1,x]))
178 return true;
179 if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g.map[y,x-1]))
180 && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
181 return true;
182 if(rocky(g.map[y+1,x+1]) && rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
183 return true;
184 if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||rocky(g.map[y-1,x-1]))
185 && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
186 return true;
187 if(rocky(g.map[y,x+1]) && rocky(g.map[y-1,x+1]) && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
188 return true;
189 return false;
190 }
191
192 // avoid directly below '*'
193 Tuple!(char,int)[] tryA() {
194 const(Pos)[] q;
195 foreach(p; gs)
196 if(!danger(p.y,p.x))
197 q ~= p;
198 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
199 foreach(p; q) v[p.y][p.x]=true;
200 for(int step=1; q.length; ++step) {
201 Pos[] q2;
202 foreach(p; q) {
203 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
204 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
205 for(int i=0; i<yyy.length; ++i) {
206 int y = yyy[i];
207 int x = xxx[i];
208 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
209 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
210 yyy ~= ppp.y;
211 xxx ~= ppp.x;
212 }
213 continue;
214 }
215 if(v[y][x]) continue;
216 if(y==s.y && x==s.x && i<4) {
217 char c = "UDRL"[i];
218 if( death.count(c) == 0 )
219 return [tuple(c,step)];
220 } else if(forbidden_cell[y][x]){
221 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
222 if(danger(y,x))
223 continue;
224 q2 ~= new Pos(y,x);
225 v[y][x]=true;
226 }
227 }
228 }
229 q = q2;
230 }
231 return [];
232 }
233
234 // any empty space is my ground
235 Tuple!(char,int)[] tryB() {
236 const(Pos)[] q;
237 foreach(p; gs) q ~= p;
238 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
239 foreach(p; q) v[p.y][p.x]=true;
240 for(int step=10; q.length; ++step) {
241 Pos[] q2;
242 foreach(p; q) {
243 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
244 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
245 for(int i=0; i<yyy.length; ++i) {
246 int y = yyy[i];
247 int x = xxx[i];
248 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
249 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
250 yyy ~= ppp.y;
251 xxx ~= ppp.x;
252 }
253 continue;
254 }
255 if(v[y][x]) continue;
256 if(y==s.y && x==s.x && i<4) {
257 char c = "UDRL"[i];
258 if( death.count(c) == 0 )
259 return [tuple(c,step)];
260 } else if(forbidden_cell[y][x]){
261 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='!'||i>=4) {
262 q2 ~= new Pos(y,x);
263 v[y][x]=true;
264 }
265 }
266 }
267 q = q2;
268 }
269 return [];
270 }
271
272 // push rocks!
273 Tuple!(char,int)[] tryC() {
274 const(Pos)[] q;
275 foreach(p; gs) q ~= p;
276 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
277 foreach(p; q) v[p.y][p.x]=true;
278 for(int step=20; q.length; ++step) {
279 Pos[] q2;
280 foreach(p; q) {
281 int[] yyy=[p.y-1,p.y+1,p.y,p.y];
282 int[] xxx=[p.x,p.x,p.x-1,p.x+1];
283 for(int i=0; i<yyy.length; ++i) {
284 int y = yyy[i];
285 int x = xxx[i];
286 if(rocky(g.map[p])) {
287 if(i>=4)continue;
288 if(y!=p.y)continue;
289 if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
290 }
291 if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
292 foreach(ppp; g.tr.source_pos(g.map[y,x])) {
293 yyy ~= ppp.y;
294 xxx ~= ppp.x;
295 }
296 continue;
297 }
298 if(v[y][x]) continue;
299 if(y==s.y && x==s.x && i<4) {
300 char c = "UDRL"[i];
301 if( death.count(c) == 0 )
302 return [tuple(c,step)];
303 } else if(forbidden_cell[y][x]){
304 } else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
305 q2 ~= new Pos(y,x);
306 v[y][x]=true;
307 }
308 }
309 }
310 q = q2;
311 }
312 return [];
313 }
314 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
315 }
316 }
317
318 class Solver_2(SubSolver) : Solver
319 {
320 // Parameters.
321 int PredictFuture = 10;
322 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
323 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step)
324
325 Game current_game;
326 SubSolver sub_solver;
327
328 enum {Tentative, Tentative_Stuck, Fixed};
329 string plan;
330 int plan_state;
331 int replan_limit;
332 bool lambda_getter;
333 int clear_improvement = 3;
334
335 this(in Game g)
336 {
337 current_game = g.clone();
338 plan = "";
339 plan_state = Tentative;
340 if(g.map.W*g.map.H <= 400) {
341 RandomChoicePattern = ["UU","UD","UL","UR",
342 "DU","DD","DL","DR",
343 "LU","LD","LL","LR",
344 "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
345 PredictFuture = 20;
346 clear_improvement = 1;
347 }
348 else if(g.map.W*g.map.H <= 4096) {
349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
350 PredictFuture = 10;
351 clear_improvement = 0;
352 }
353 else {
354 RandomChoicePattern = ["U","D","L","R"];
355 PredictFuture = 10;
356 clear_improvement = 0;
357 }
358
359 replan_limit = PredictFuture;
360 }
361
362 char single_step()
363 {
364 if(current_game.dead || current_game.cleared)
365 return 'A';
366
367 // Make enough prediction.
368 while( plan_state==Tentative && plan.length<replan_limit )
369 single_step_predict();
370
371 // If the future is bad, correct.
372 if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
373 replan();
374
375 // Follow the predicted plan.
376 if( plan.empty )
377 return 'A';
378 char c = plan[0];
379 plan = plan[1..$];
380 int b_lambda = current_game.map.collected_lambda;
381 current_game.command(c);
382 int a_lambda = current_game.map.collected_lambda;
383 if(b_lambda < a_lambda) lambda_getter = false;
384 return c;
385 }
386
387 void force(char c)
388 {
389 if(plan.length>0 && plan[0]==c)
390 {
391 // If matching the plan, just go forward.
392 plan = plan[1..$];
393 }
394 else
395 {
396 // Discard the plan, otherwise.
397 plan_state = Tentative;
398 plan = "";
399 sub_solver = null;
400 }
401 current_game.command(c);
402 }
403
404 void single_step_predict()
405 {
406 if(sub_solver is null) {
407 sub_solver = new SubSolver(current_game);
408 plan = "";
409 }
410
411 char c = sub_solver.single_step();
412 if(c == 'A')
413 plan_state = Tentative_Stuck;
414 else {
415 plan ~= c;
416 if(sub_solver.g.cleared) {
417 if(clear_improvement-->0) {
418 plan_state = Tentative_Stuck;
419 replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
420 } else {
421 plan_state = Fixed;
422 }
423 } else {
424 plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
425 }
426 }
427 }
428
429 void replan()
430 {
431 // Try to replace every step of the plan by another move.
432 Game g = current_game.clone();
433 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
434 int insertion_point = plan.length;
435 bool tiebreak_by_turn = false;
436 int consider_length = min(ReplanLength, g.map.W*g.map.H);
437 if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
438
439 for(int i=0; i<plan.length; ++i) {
440 foreach(string prefix; RandomChoicePattern)
441 if(prefix[0] != plan[i]) {
442 Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
443 r[1] = plan[0..i] ~ prefix ~ r[1];
444 bool better = false, tbt=false;
445 if(!cand[0].g.cleared && r[0].g.cleared)
446 better = true;
447 else if(cand[0].g.cleared && r[0].g.cleared) {
448 better = cand[0].g.score < r[0].g.score;
449 }
450 else if(!cand[0].g.cleared && !r[0].g.cleared) {
451 if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
452 better = true;
453 else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
454 if(cand[0].g.dead && !r[0].g.dead)
455 better = true;
456 else if(cand[0].g.dead == r[0].g.dead) {
457 better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
458 tbt = true;
459 }
460 }
461 }
462 if(better) {
463 cand = r;
464 tiebreak_by_turn = true;
465 insertion_point = i+prefix.length;
466 if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
467 }
468 }
469 g.command(plan[i]);
470 }
471
472 if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
473 sub_solver = cand[0];
474 plan = cand[1];
475 plan_state = Tentative_Stuck;
476 replan_limit = min(plan.length - insertion_point, PredictFuture);
477 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
478 } else {
479 sub_solver = cand[0];
480 plan = cand[1];
481 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]);
482 replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
483 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
484 }
485 }
486
487 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
488 {
489 if(consider_length<=0) consider_length = 2;
490
491 SubSolver s = new SubSolver(g);
492 foreach(char c; prefix)
493 s.force(c);
494 string log;
495 int state = Tentative;
496 while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
497 char c = s.single_step();
498 if( c == 'A' ) {
499 state = Tentative_Stuck;
500 break;
501 }
502 log ~= c;
503 }
504 if(s.g.cleared) state = Fixed;
505 else if(s.g.dead) state = Tentative_Stuck;
506 return tuple(s, log, state);
507 }
508 }
509
510 class Queue(T)
511 {
512 alias Tuple!(T,int) t;
513
514 t[] cur, next;
515
516 void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
517 bool empty() { return cur.empty; }
518 t pop() {
519 t v = cur[0]; cur = cur[1..$];
520 if(cur.empty) { cur = next; next = null; }
521 return v;
522 }
523 }
524
525 class Solver_3 : Solver
526 {
527 Game g;
528 this(in Game g)
529 {
530 this.g = g.clone();
531 }
532
533 char single_step()
534 {
535 char c = think(g);
536 if(c != 'A')
537 g.command(c);
538 return c;
539 }
540
541 void force(char c)
542 {
543 stderr.writeln(death_move(g));
544 if(c != 'A')
545 g.command(c);
546 }
547
548 bool is_spacy(char c) {
549 return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O';
550 }
551 bool is_rocky(char c) {
552 return c=='*' || c=='@';
553 }
554 bool is_true_space(char c) {
555 return c==' ';
556 }
557 bool is_trampoline_source(char c) {
558 return 'A'<=c && c<='I';
559 }
560 bool is_rocklambda(char c) {
561 return is_rocky(c) || c=='\\';
562 }
563
564 string death_move(in Game g)
565 {
566 // TODO: S
567 string death;
568 int y = g.map.robot.y;
569 int x = g.map.robot.x;
570 int[5] dy_=[-1,+1,0,0,0];
571 int[5] dx_=[0,0,-1,+1,0];
572 char[] ds=['D','U','L','R','W'];
573 for(int i=0; i<5; ++i)
574 {
575 bool after_move_death(int y, int x, char tr_tgt)
576 {
577 bool is_spacy_t(char c) {
578 if(is_spacy(c) || c==tr_tgt)
579 return true;
580 return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
581 }
582
583 // check water
584 if( g.hp==0 && y<=g.water_level )
585 return true;
586
587 // check falling rock.
588 int yy=y+1, xx=x;
589 if( is_spacy_t(g.map[yy, xx]) )
590 {
591 if( is_rocky(g.map[yy+1,xx]) )
592 return true;
593 if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
594 if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
595 return false;
596 return true;
597 }
598 if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
599 if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
600 return false;
601 return true;
602 }
603 }
604 return false;
605 }
606
607 int dy=dy_[i], dx=dx_[i];
608 if( is_spacy(g.map[y+dy,x+dx])
609 || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
610 {
611 if( after_move_death(y+dy, x+dx, char.init) )
612 death ~= ds[i];
613 }
614 else if( is_trampoline_source(g.map[y+dy,x+dx]) )
615 {
616 Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
617 if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
618 death ~= ds[i];
619 }
620 else
621 {
622 death ~= ds[i];
623 }
624 }
625 return death;
626 }
627
628 char think(in Game g)
629 {
630 string s = death_move(g);
631 stderr.writeln(s);
632
633 auto Q = new Queue!(Tuple!(Pos,Pos));
634 Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
635 Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
636 while(!Q.empty) {
637 auto tup = Q.pop();
638 Pos p = tup[0][0];
639 Pos prev = tup[0][1];
640 int dist = tup[1];
641 if(V[p.y][p.x])
642 continue;
643 V[p.y][p.x] = prev;
644 if(g.map[p]=='\\' || g.map[p]=='O')
645 {
646 Pos goback(Pos p) {
647 return V[p.y][p.x];
648 }
649 for(;;) {
650 Pos q = goback(p);
651 if(q == g.map.robot)
652 if(q.y==p.y)
653 return q.x<p.x ? 'R' : 'L';
654 else
655 return q.y<p.y ? 'U' : 'D';
656 p=q;
657 }
658 }
659
660 int[4] dy=[-1,+1,0,0];
661 int[4] dx=[0,0,-1,+1];
662 char[] ds=['D','U','L','R'];
663 for(int i=0; i<4; ++i)
664 {
665 int y=p.y+dy[i], x=p.x+dx[i];
666 if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O')&&!V[y][x]) {
667 Q.push(tuple(new Pos(y,x),p), dist+1);
668 }
669 }
670 }
671 return 'A';
672 }
673 }
674
675 alias Solver_3 MainSolver;
676 //alias Solver_2!(Solver_1) MainSolver;
677 //alias Solver_1 MainSolver;
678 //alias Solver_0 MainSolver;