1 import util;
2
3 ////////////////////////////////////////////////////////////////////////////////
4
5 class Pos
6 {
7 public immutable int y, x;
8 mixin DeriveCreate;
9 mixin DeriveCompare;
10 mixin DeriveShow;
11 Pos clone() const { return cast(Pos) this; }
12
13 @property:
14 Pos wait() { return this.clone(); }
15 Pos up() { return new Pos(y+1, x); }
16 Pos down() { return new Pos(y-1, x); }
17 Pos left() { return new Pos(y, x-1); }
18 Pos right() { return new Pos(y, x+1); }
19 alias wait W,w;
20 alias up U,u;
21 alias down D,d;
22 alias left L,l;
23 alias right R,r;
24 }
25
26 unittest
27 {
28 assert( (new Pos(2,1)).U == new Pos(3,1) );
29 assert( (new Pos(0,1)).D == new Pos(-1,1) );
30 assert( (new Pos(2,1)).L == new Pos(2,0) );
31 assert( (new Pos(2,1)).R == new Pos(2,2) );
32 int[Pos] aa;
33 aa[new Pos(1,2)] = 1;
34 aa[new Pos(1,2)] = 2;
35 aa[new Pos(2,1)] = 3;
36 assert( aa.length==2 );
37 assert( aa[new Pos(1,2)]==2 );
38 }
39
40 ////////////////////////////////////////////////////////////////////////////////
41
42 class Water
43 {
44 public immutable int base, pace;
45 mixin DeriveCreate;
46 mixin DeriveCompare;
47 mixin DeriveShow;
48 Water clone() const { return cast(Water)this; }
49
50 static load(string[string] params)
51 {
52 return new Water(params.get("Water", "0").to!int(),
53 params.get("Flooding", "0").to!int());
54 }
55
56 int level(int number_of_update) const
57 {
58 return pace ? base+(number_of_update/pace) : base;
59 }
60
61 int until_rise(int number_of_update) const
62 {
63 return pace ? pace-number_of_update%pace : int.max;
64 }
65 }
66
67 unittest
68 {
69 Water w = new Water(1, 3);
70 assert( 1 == w.level(0) );
71 assert( 1 == w.level(1) );
72 assert( 1 == w.level(2) );
73 assert( 2 == w.level(3) );
74 assert( 2 == w.level(4) );
75 assert( 2 == w.level(5) );
76 assert( 3 == w.level(6) );
77
78 w = new Water(1, 0);
79 assert( 1 == w.level(0) );
80 assert( 1 == w.level(1) );
81 assert( 1 == w.level(2) );
82 assert( 1 == w.level(3) );
83 assert( 1 == w.level(4) );
84 assert( 1 == w.level(5) );
85 }
86
87 ////////////////////////////////////////////////////////////////////////////////
88
89 class Hige
90 {
91 public immutable int pace;
92 mixin DeriveCreate;
93 mixin DeriveCompare;
94 mixin DeriveShow;
95 Hige clone() const { return cast(Hige)this; }
96
97 static load(string[string] params)
98 {
99 return new Hige(params.get("Growth", "25").to!int());
100 }
101
102 bool is_growing_turn(int turn) const
103 {
104 return pace ? turn%pace == pace-1 : false;
105 }
106
107 int until_rise(int turn) const
108 {
109 return pace ? pace-turn%pace : int.max;
110 }
111 }
112
113 ////////////////////////////////////////////////////////////////////////////////
114
115 class Map
116 {
117 mixin DeriveShow;
118
119 static Map load(string[] raw_data, string[string] params, char[char] trampo)
120 {
121 // TODO: choose optimal representation.
122 return new Map(raw_data, params, trampo);
123 }
124
125 char[][] data;
126 Pos robot;
127 Pos lift;
128 int waterproof;
129 Pos[char] tr_target;
130 Pos[][char] tr_source;
131 const(Hige) hige;
132 int razor;
133
134 Map clone() const { return new Map(this); }
135 this(in Map m) {
136 foreach(s; m.data)
137 this.data ~= s.dup;
138 this.robot = m.robot.clone();
139 this.lift = m.lift.clone();
140 this.waterproof = m.waterproof;
141 this.tr_target = cast(Pos[char])m.tr_target;
142 this.tr_source = cast(Pos[][char])m.tr_source;
143 this.hige = m.hige.clone();
144 this.razor = m.razor;
145 }
146
147 this(string[] raw_data, string[string] params, char[char] trampo)
148 {
149 int width = 0;
150 foreach(r; raw_data)
151 width = max(width, r.length);
152 foreach(r; raw_data) {
153 this.data ~= r.dup;
154 this.data[$-1].length = width;
155 this.data[$-1][r.length..$] = ' ';
156 }
157
158 for(int y=1; y<=H; ++y)
159 for(int x=1; x<=W; ++x) {
160 if(this[y,x] == 'R')
161 this.robot = new Pos(y,x);
162 if(this[y,x] == 'L' || this[y,x] == 'O')
163 this.lift = new Pos(y,x);
164 }
165
166 Pos[char] tr_pos;
167 for(int y=1; y<=H; ++y)
168 for(int x=1; x<=W; ++x) {
169 char c = this[y,x];
170 if('1'<=c && c<='9' || 'A'<=c&&c<='I')
171 tr_pos[c] = new Pos(y,x);
172 }
173
174 this.waterproof = params.get("Waterproof", "5").to!int();
175 foreach(fr,to; trampo) {
176 tr_target[fr] = tr_pos[to];
177 if(to !in tr_source) tr_source[to] = [];
178 tr_source[to] ~= tr_pos[fr];
179 }
180
181 this.hige = Hige.load(params);
182 this.razor = params.get("Razors", "0").to!int();
183 }
184
185 const @property {
186 int H() { return data.length; }
187 int W() { return data[0].length; }
188 }
189
190 const {
191 char opIndex(int y, int x)
192 {
193 // Adjust coordinate to the spec. bottom-left is (1,1).
194 --y, --x;
195 if(y<0||H<=y||x<0||W<=x)
196 return '#';
197 return data[H-1-y][x];
198 }
199
200 char opIndex(in Pos p)
201 {
202 return this[p.y, p.x];
203 }
204 }
205
206 void opIndexAssign(char c, int y, int x)
207 {
208 // Adjust coordinate to the spec. bottom-left is (1,1).
209 --y, --x;
210 if(y<0||H<=y||x<0||W<=x)
211 return;
212 data[H-1-y][x] = c;
213 }
214
215 void opIndexAssign(char c, in Pos p)
216 {
217 this[p.y, p.x] = c;
218 }
219
220 Pos[] objects(char c) const {
221 Pos[] ans;
222 for(int y=1; y<=H; ++y)
223 for(int x=1; x<=W; ++x)
224 if(this[y,x] == c)
225 ans ~= new Pos(y,x);
226 return ans;
227 }
228
229 Pos[] razors() const { return objects('!'); }
230 Pos[] lambdas() const { return objects('\\'); }
231
232 bool cleared() const
233 {
234 for(int y=1; y<=H; ++y)
235 for(int x=1; x<=W; ++x)
236 if(this[y,x] == 'L' || this[y,x] == 'O')
237 return false;
238 return true;
239 }
240
241 Tuple!(int,bool) command(char c, int turn)
242 {
243 assert( this[robot] == 'R' );
244 if(c=='R') return move( 0, +1, turn);
245 if(c=='L') return move( 0, -1, turn);
246 if(c=='U') return move(+1, 0, turn);
247 if(c=='D') return move(-1, 0, turn);
248 if(c=='W') return move( 0, 0, turn);
249 if(c=='S') return use_razor(turn);
250 assert(false);
251 }
252
253 Tuple!(int, bool) use_razor(int turn)
254 {
255 if(razor) {
256 razor--;
257 for(int dy=-1; dy<=+1; ++dy)
258 for(int dx=-1; dx<=+1; ++dx)
259 if(this[robot.y+dy,robot.x+dx] == 'W')
260 this[robot.y+dy,robot.x+dx] = ' ';
261 }
262
263 bool dead = update(turn);
264 return tuple(0,dead);
265 }
266
267 Tuple!(int, bool) move(int dy, int dx, int turn)
268 {
269 int y = robot.y;
270 int x = robot.x;
271 int lambda = 0;
272 if( '\\' == this[y+dy,x+dx] )
273 lambda++;
274 if( '!' == this[y+dy,x+dx] )
275 razor++;
276 if( " \\!.O".count(this[y+dy,x+dx])==1 ) {
277 this[y,x]=' ';
278 this[y+dy,x+dx]='R';
279 robot = new Pos(y+dy,x+dx);
280 } else if(dy==0 && '*'==this[y+dy,x+dx] && ' '==this[y+dy*2,x+dx*2]) {
281 this[y,x]=' ';
282 this[y+dy,x+dx]='R';
283 this[y+dy*2,x+dx*2]='*';
284 robot = new Pos(y+dy,x+dx);
285 } else if('A'<=this[y+dy,x+dx] && this[y+dy,x+dx]<='I') {
286 this[y,x]=' ';
287 Pos tp = tr_target[this[y+dy,x+dx]];
288 foreach(p; tr_source[this[tp]])
289 this[p] = ' ';
290 this[tp] = 'R';
291 robot = tp;
292 }
293 bool dead = update(turn);
294 return tuple(lambda,dead);
295 }
296
297 bool update(int turn)
298 {
299 bool dead = false;
300
301 char[][] next;
302 foreach(y,s; data)
303 next ~= s.dup;
304
305 ref char access(Pos p) { return next[H-p.y][p.x-1]; }
306
307 bool lambda = false;
308 for(int y=1; y<=H; ++y)
309 for(int x=1; x<=W; ++x)
310 lambda |= (this[y,x] == '\\');
311
312 for(int y=1; y<=H; ++y)
313 for(int x=1; x<=W; ++x) {
314 Pos p = new Pos(y,x);
315 if(this[p]=='*') {
316 if(this[p.D]==' ') {
317 access(p) =' ';
318 access(p.D)='*';
319 if(robot == p.D.D)
320 dead=true;
321 }
322 else if((this[p.D]=='*' || this[p.D]=='\\') && this[p.R]==' ' && this[p.R.D]==' ') {
323 access(p)=' ';
324 access(p.R.D)='*';
325 if(robot == p.R.D.D)
326 dead=true;
327 }
328 else if(this[p.D]=='*' && this[p.L]==' ' && this[p.L.D]==' ') {
329 access(p)=' ';
330 access(p.L.D)='*';
331 if(robot == p.L.D.D)
332 dead=true;
333 }
334 }
335 else if(this[p]=='L') {
336 if(!lambda)
337 access(p) = 'O';
338 }
339 else if(this[p]=='W') {
340 if( hige.is_growing_turn(turn) )
341 for(int dy=-1; dy<=+1; ++dy)
342 for(int dx=-1; dx<=+1; ++dx)
343 if(this[p.y+dy,p.x+dx] == ' ')
344 access(new Pos(p.y+dy,p.x+dx)) = 'W';
345 }
346 }
347 data = next;
348 return dead;
349 }
350 }
351
352 ////////////////////////////////////////////////////////////////////////////////
353
354 class Game
355 {
356 public:
357 this(File input)
358 {
359 // Read map data
360 string[] map_data_lines;
361 for(string line; !(line=input.readln().chomp()).empty; )
362 map_data_lines ~= line;
363
364 // H*W
365 H_ = map_data_lines.length;
366 W_ = 0;
367 foreach(mdl; map_data_lines)
368 W_ = max(W_, mdl.length);
369
370 // Copy to modifiable buffer and adjust coordinates.
371 raw_data_ = new char[][H_+1];
372 foreach(i,mdl; map_data_lines) {
373 char[] buf = new char[mdl.length+1];
374 buf[0] = '#';
375 buf[1..$] = mdl[];
376 raw_data_[H_-i] = buf;
377 }
378
379 // Detect objects
380 for(int y=1; y<=H_; ++y)
381 for(int x=1; x<raw_data_[y].length; ++x)
382 {
383 char c = raw_data_[y][x];
384 switch(c)
385 {
386 case '#':
387 case '.':
388 case ' ':
389 break;
390 case 'L':
391 case 'O':
392 lift_pos_ = new Pos(y,x);
393 break;
394 case 'A': .. case 'I':
395 case '1': .. case '9':
396 trampoline_pos_[c] = new Pos(y,x);
397 break;
398 case '!':
399 razor_pos_ ~= new Pos(y,x);
400 break;
401 case '\\':
402 lambda_pos_ ~= new Pos(y,x);
403 break;
404
405 // Moving objects are erased from raw_data_
406 case 'R':
407 robot_pos_ = new Pos(y,x);
408 raw_data_[y][x] = ' ';
409 break;
410 case '*':
411 case 'W':
412 dynamic_objects_[new Pos(y,x)] = c;
413 raw_data_[y][x] = ' ';
414 if(c=='*')
415 may_update_[new Pos(y,x)] = true;
416 break;
417 default:
418 assert(false);
419 }
420 }
421
422 // Read other parameters
423 for(string line; !(line=input.readln()).empty; )
424 {
425 string[] ss = line.split();
426 if( ss.length == 2 )
427 switch(ss[0])
428 {
429 case "Water": water_base_ = ss[1].to!int(); break;
430 case "Flooding": water_pace_ = ss[1].to!int(); break;
431 case "Waterproof": max_air_ = ss[1].to!int(); break;
432 case "Growth": hige_pace_ = ss[1].to!int(); break;
433 case "Razors": num_razor_ = ss[1].to!int(); break;
434 default: assert(false);
435 }
436 if( ss.length == 4 && ss[0]=="Trampoline" && ss[2]=="targets" )
437 {
438 char fr=ss[1][0], to=ss[3][0];
439 trampoline_[fr] = to;
440 if(to !in trampoline_rev_) trampoline_rev_[to] = [];
441 trampoline_rev_[to] ~= fr;
442 }
443 }
444
445 air_left_ = max_air_;
446 }
447
448 @property const {
449 int H() { return H_; }
450 int W() { return W_; }
451 char trampoline(char c) { return (c in trampoline_ ? trampoline_[c] : 0); }
452 const(Pos)[] trampoline_rev(char c) {
453 const(Pos)[] pp;
454 if(c in trampoline_rev_) {
455 foreach(ch; trampoline_rev_[c])
456 pp ~= trampoline_pos_[ch];
457 }
458 return pp;
459 }
460 int water_level() {
461 return water_pace_ ? water_base_ + turn_/water_pace_ : water_base_;
462 }
463 int water_until_rise() {
464 return water_pace_ ? water_pace_ - turn_%water_pace_ : int.max;
465 }
466 int hige_until_rise() {
467 return hige_pace_ ? hige_pace_ - turn_%hige_pace_ : int.max;
468 }
469 bool is_hige_turn() {
470 return hige_pace_ ? turn_%hige_pace_ == hige_pace_-1 : false;
471 }
472 int hp() { return air_left_; }
473 int num_razor() { return num_razor_; }
474 bool cleared() { return cleared_; }
475 bool dead() { return dead_; }
476 long score() { return num_lambda_*(dead_ ? 25L : cleared_ ? 75L : 50L) - turn_; }
477 const(Pos) robot() { return robot_pos_; }
478 const(Pos) lift() { return lift_pos_; }
479 Pos[] lambdas() {
480 Pos[] pp;
481 foreach(p; lambda_pos_)
482 pp ~= p.clone();
483 return pp;
484 }
485 Pos[] razors() {
486 Pos[] pp;
487 foreach(p; razor_pos_)
488 pp ~= p.clone();
489 return pp;
490 }
491 const(Pos)[] higes() {
492 const(Pos)[] pp;
493 foreach(p,c; dynamic_objects_)
494 if(c=='W')
495 pp ~= p;
496 return pp;
497 }
498 }
499 const {
500 char opIndex(in Pos p) { return opIndex(p.y, p.x); }
501 char opIndex(int y, int x) { return map_get(y, x); }
502 }
503
504 public:
505 void command(char c)
506 {
507 if(dead || cleared)
508 return;
509
510 if(c == 'U') command_move(+1, 0);
511 if(c == 'D') command_move(-1, 0);
512 if(c == 'L') command_move(0, -1);
513 if(c == 'R') command_move(0, +1);
514 if(c == 'S') use_razor();
515 if(c == 'W') {}
516
517 if(!cleared)
518 {
519 map_update();
520 water_update();
521 }
522 turn_ ++;
523 }
524
525 void command_move(int dy, int dx)
526 {
527 int y = robot_pos_.y, x = robot_pos_.x;
528 char c = this[y+dy, x+dx];
529 Pos p = new Pos(y+dy, x+dx);
530
531 switch(c){
532 case 'O':
533 cleared_ = true;
534 move_robot_to(p);
535 break;
536 case '\\':
537 take_lambda_at(p);
538 move_robot_to(p);
539 break;
540 case '!':
541 take_razor_at(p);
542 move_robot_to(p);
543 break;
544 case 'A': .. case 'I':
545 enter_trampoline_at(p, c);
546 break;
547 case ' ':
548 case '.':
549 move_robot_to(p);
550 break;
551 case '*':
552 if(dy!=0 || this[y,x+dx*2]!=' ')
553 break;
554 move_robot_to(p);
555 push_rock(p, new Pos(y,x+dx*2));
556 break;
557 default:
558 break;
559 }
560 }
561
562 void use_razor()
563 {
564 if(num_razor_ == 0)
565 return;
566 num_razor_ --;
567
568 for(int dy=-1; dy<=+1; ++dy)
569 for(int dx=-1; dx<=+1; ++dx) if(dy||dx)
570 {
571 Pos p = new Pos(robot_pos_.y+dy, robot_pos_.x+dx);
572 if(auto it = p in dynamic_objects_)
573 if(*it == 'W') {
574 something_gone(p);
575 dynamic_objects_.remove(p);
576 }
577 }
578 }
579
580 void take_lambda_at(Pos p)
581 {
582 map_set_empty(p);
583 num_lambda_ ++;
584 lambda_pos_ = lambda_pos_.erase(p);
585 }
586
587 void take_razor_at(Pos p)
588 {
589 map_set_empty(p);
590 num_razor_ ++;
591 razor_pos_ = razor_pos_.erase(p);
592 }
593
594 void enter_trampoline_at(Pos p, char c)
595 {
596 char d = trampoline(c);
597 foreach(cc; trampoline_rev_[d]) {
598 Pos pp = trampoline_pos_[cc];
599 something_gone(pp);
600 map_set_empty(pp);
601 }
602 move_robot_to(trampoline_pos_[d]);
603 }
604
605 void move_robot_to(Pos p)
606 {
607 something_gone(robot_pos_);
608 map_set_empty(p.y, p.x);
609 robot_pos_ = p;
610 }
611
612 void push_rock(Pos fr, Pos to)
613 {
614 dynamic_objects_.remove(fr);
615 dynamic_objects_[to] = '*';
616 may_update_[to] = true;
617 }
618
619 void something_gone(Pos p)
620 {
621 for(int dy=0; dy<=+1; ++dy)
622 for(int dx=-1; dx<=+1; ++dx) if(dy||dx)
623 may_update_[new Pos(p.y+dy,p.x+dx)] = true;
624 }
625
626 void map_update()
627 {
628 Pos[] may_update_list;
629 foreach(p,_; may_update_)
630 if(this[p] == '*')
631 may_update_list ~= p;
632 may_update_ = null;
633
634 if( is_hige_turn() )
635 foreach(p,c; dynamic_objects_)
636 if(c == 'W')
637 may_update_list ~= p;
638
639 sort(may_update_list);
640 char[Pos] to_be_written;
641 foreach(p; may_update_list)
642 if(is_hige_turn() && this[p]=='W')
643 {
644 for(int dy=-1; dy<=+1; ++dy)
645 for(int dx=-1; dx<=+1; ++dx) {
646 Pos q = new Pos(p.y+dy,p.x+dx);
647 if( this[q] == ' ' )
648 to_be_written[q] = 'W';
649 }
650 }
651 else
652 {
653 int y = p.y;
654 int x = p.x;
655 char below = this[y-1,x];
656 // *
657 // _
658 if(below==' ') {
659 Pos q = new Pos(y-1,x);
660 to_be_written[p] = ' ';
661 to_be_written[q] = '*';
662 may_update_[q] = true;
663 }
664 // *_ *_
665 // *_ or \_
666 else if((below=='*'||below=='\\')&&this[y-1,x+1]==' '&&this[y,x+1]==' ') {
667 Pos q = new Pos(y-1,x+1);
668 to_be_written[p] = ' ';
669 to_be_written[q] = '*';
670 may_update_[q] = true;
671 }
672 // _*
673 // _*
674 else if(below=='*'&&this[y-1,x-1]==' '&&this[y,x-1]==' ') {
675 Pos q = new Pos(y-1,x-1);
676 to_be_written[p] = ' ';
677 to_be_written[q] = '*';
678 may_update_[q] = true;
679 }
680 }
681
682 foreach(p,c; to_be_written) {
683 dynamic_objects_[p] = c;
684 if(c=='*' && p.y==robot_pos_.y+1 && p.x==robot_pos_.x)
685 dead_ = true;
686 }
687
688 if(lambda_pos_.empty)
689 raw_data_[lift_pos_.y][lift_pos_.x] = 'O';
690 }
691
692 void water_update()
693 {
694 if( robot_pos_.y <= water_level() )
695 air_left_ --;
696 else
697 air_left_ = max_air_;
698 if( air_left_ < 0 )
699 dead_ = true;
700 }
701
702 private:
703 char map_get(int y, int x) const
704 {
705 if( y<1 || H<y || x<1 || W<x ) return '#';
706 Pos p = new Pos(y,x);
707 if(p == robot_pos_)
708 return 'R';
709 if(auto it = (p in dynamic_objects_))
710 return *it;
711 if( x<0 || raw_data_[y].length<=x ) return ' ';
712 return raw_data_[y][x];
713 }
714
715 void map_set_empty(in Pos p)
716 {
717 return map_set_empty(p.y, p.x);
718 }
719
720 void map_set_empty(int y, int x)
721 {
722 if( y<1 || H<y || x<1 || W<x ) return;
723 if( x<0 || raw_data_[y].length<=x ) return;
724 raw_data_[y][x] = ' ';
725 }
726
727 public:
728 Game clone() const { return new Game(this); }
729 this(in Game g) {
730 H_ = g.H_;
731 W_ = g.W_;
732 raw_data_ = new char[][g.raw_data_.length];
733 foreach(i,d; g.raw_data_) raw_data_[i] = d.dup;
734 trampoline_pos_ = cast(Pos[char]) g.trampoline_pos_;
735 razor_pos_ = (cast(Game)g).razor_pos_.dup;
736 lambda_pos_ = (cast(Game)g).lambda_pos_.dup;
737 lift_pos_ = g.lift_pos_.clone();
738 robot_pos_ = g.robot_pos_.clone();
739 dynamic_objects_ = dup(g.dynamic_objects_);
740 trampoline_ = (cast(Game)g).trampoline_;
741 trampoline_rev_ = (cast(Game)g).trampoline_rev_;
742 water_base_ = g.water_base_;
743 water_pace_ = g.water_pace_;
744 max_air_ = g.max_air_;
745 hige_pace_ = g.hige_pace_;
746 num_razor_ = g.num_razor_;
747 num_lambda_ = g.num_lambda_;
748 turn_ = g.turn_;
749 air_left_ = g.air_left_;
750 cleared_ = g.cleared_;
751 dead_ = g.dead_;
752 may_update_ = dup(g.may_update_);
753 }
754
755 V[K] dup(V,K)(in V[K] aa) {
756 V[K] aa2;
757 foreach(k,v; aa) aa2[k] = v;
758 return aa2;
759 }
760
761 private:
762 int H_;
763 int W_;
764 char[][] raw_data_;
765 Pos[char] trampoline_pos_;
766 Pos[] razor_pos_;
767 Pos[] lambda_pos_;
768 Pos lift_pos_;
769 Pos robot_pos_;
770 char[Pos] dynamic_objects_;
771 char[char] trampoline_;
772 char[][char] trampoline_rev_;
773 int water_base_ = 0;
774 int water_pace_ = 0;
775 int max_air_ = 10;
776 int hige_pace_ = 25;
777 int num_razor_ = 0;
778 int num_lambda_ = 0;
779
780 int turn_ = 0;
781 int air_left_ = 0;
782 bool cleared_ = false;
783 bool dead_ = false;
784 bool[Pos] may_update_;
785 }