import util;
import game;
class Solver_0
{
this(const(Game) g) {}
char single_step() { return 'W'; }
}
class Solver_1
{
int wait_count = 0;
Game g;
this(const(Game) g)
{
this.g = g.clone();
forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
}
char single_step()
{
Tuple!(string,int) de = death_move(g);
char c = act(g, de[0], de[1]);
g.command(c);
return c;
}
Tuple!(string,int) death_move(const(Game) g)
{
string death;
int choice = 0;
foreach(char c; "UDLRW") {
Game gg = g.clone();
gg.command(c);
if( !gg.cleared && gg.dead )
death ~= c;
else if( gg.map.robot != g.map.robot )
choice++;
}
return tuple(death, choice);
}
Tuple!(Pos, int)[] log;
bool[][] forbidden_cell;
char act(const(Game) g, string death, int breath)
{
const Pos ro = g.map.robot;
const Pos[] la = g.map.lambdas();
const Pos li = g.map.lift;
Tuple!(char,int)[] cand;
char c = 'W';
if( la.empty ) {
cand = search(g, ro, li, death);
} else {
foreach(lam; la)
cand ~= search(g, ro, lam, death);
}
cand ~= tuple('W',int.max);
sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
if(c1[1] != c2[1])
return c1[1] < c2[1];
return c1[0] < c2[0];
})(cand);
c = cand[0][0];
if(death.count(c)) {
foreach(char live; "UDLRWA")
if(death.count(live)==0) {
c=live;
break;
}
}
if(c=='W') {
wait_count++;
if(wait_count > g.map.H)
c = 'A';
}
else
wait_count = 0;
bool[char] choice;
foreach(t; cand)
choice[t[0]] = true;
log ~= tuple(ro.clone(), cast(int)choice.length);
if(log.length > 5)
log = log[$-5..$];
int cnt = 0;
foreach(l; log)
if(l[0] == log[$-1][0])
++cnt;
if( cnt >= 3 && breath==1 ) {
forbidden_cell[ro.y][ro.x] = true;
}
return c;
}
Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death)
{
bool danger(int y, int x)
{
if(g.map[y+1,x] == '*')
return true;
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'))
return true;
if(g.map[y+1,x+1]=='*' && (g.map[y,x+1]=='*') && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
return true;
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'))
return true;
if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
return true;
return false;
}
// avoid directly below '*'
Tuple!(char,int)[] tryA() {
const(Pos)[] q = [o];
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
if( !danger(o.y,o.x) ) {
v[o.y][o.x]=true;
for(int step=1; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] dy=[-1,+1,0,0];
int[] dx=[0,0,-1,+1];
for(int i=0; i<4; ++i) {
int y = p.y+dy[i];
int x = p.x+dx[i];
if(v[y][x]) continue;
if(y==s.y && x==s.x) {
char c = "UDRL"[i];
if( death.count(c) == 0 )
return [tuple(c,step)];
} else if(forbidden_cell[y][x]){
} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
if(danger(y,x))
continue;
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
q = q2;
}
}
return [];
}
// any empty space is my ground
Tuple!(char,int)[] tryB() {
const(Pos)[] q = [o];
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
v[o.y][o.x]=true;
for(int step=10; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] dy=[-1,+1,0,0];
int[] dx=[0,0,-1,+1];
for(int i=0; i<4; ++i) {
int y = p.y+dy[i];
int x = p.x+dx[i];
if(v[y][x]) continue;
if(y==s.y && x==s.x) {
char c = "UDRL"[i];
if( death.count(c) == 0 )
return [tuple(c,step)];
} else if(forbidden_cell[y][x]){
} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
q = q2;
}
return [];
}
// push rocks!
Tuple!(char,int)[] tryC() {
const(Pos)[] q = [o];
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
v[o.y][o.x]=true;
for(int step=20; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] dy=[-1,+1,0,0];
int[] dx=[0,0,-1,+1];
for(int i=0; i<4; ++i) {
int y = p.y+dy[i];
int x = p.x+dx[i];
if(v[y][x]) continue;
if(y==s.y && x==s.x) {
char c = "UDRL"[i];
if( death.count(c) == 0 )
return [tuple(c,step)];
} else if(forbidden_cell[y][x]){
} else if(g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.') {
q2 ~= new Pos(y,x);
v[y][x]=true;
} else if(dy[i]==0 && g.map[p]==' ' && g.map[y,x]=='*' && (g.map[y+dy[i],x+dx[i]]==' '||g.map[y+dy[i],x+dx[i]]=='R')) {
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
q = q2;
}
return [];
}
return tryA() ~ tryB() ~ tryC();
}
}