import util;
import game;
bool rocky(char c){ return c=='*'||c=='@'; }
class Solver_0
{
this(in Game g) {}
char single_step() { return 'W'; }
void force(char c) {}
}
class Solver_1
{
int wait_count = 0;
int choke_count = 0;
Game g;
this(in 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]);
force(c);
return c;
}
void force(char c)
{
if(c != 'A')
g.command(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++;
else if( c != 'W' ) // meaningless move
death ~= c;
}
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 li = g.map.lift;
Pos[] la = g.map.lambdas();
sort!((Pos a,Pos b){
int ad=abs(a.y-li.y)+abs(a.x-li.x);
int bd=abs(b.y-li.y)+abs(b.x-li.x);
return ad>bd;;
})(la);
Pos[] ra = g.map.razors();
const(Pos)[] hi = g.map.objects('W');
Tuple!(char,int)[] cand;
char c = 'W';
if( g.map.collected_lambda == g.map.total_lambda ) {
cand = search(g, ro, [li], death);
} else if( !la.empty ){
cand ~= search(g, ro, la~ra, death);
}
// 'higesori' mode
if( !hi.empty && g.map.razor>0 ) {
int his = 0;
for(int dy=-1; dy<=+1; ++dy)
for(int dx=-1; dx<=+1; ++dx)
if(g.map[ro.y+dy,ro.x+dx] == 'W')
his++;
if(his>=2 || his==hi.length)
cand = [tuple('S',int.max)];
if(cand.empty) {
const(Pos)[] tgt;
for(int y=1; y<=g.map.H; ++y)
for(int x=1; x<=g.map.W; ++x)
if(g.map[y,x]=='.'||g.map[y,x]==' ') {
his = 0;
for(int dy=-1; dy<=+1; ++dy)
for(int dx=-1; dx<=+1; ++dx)
if(g.map[y+dy,x+dx] == 'W')
his++;
if(his>=2)
tgt ~= new Pos(y,x);
}
cand ~= search(g, ro, tgt, death, true);
}
}
// 'dig' mode
if(cand.empty) {
const(Pos)[] tgt;
for(int y=1; y<=g.map.H; ++y)
for(int x=1; x<=g.map.W; ++x)
if(g.map[y,x]=='.')
if(rocky(g.map[y+1,x])||rocky(g.map[y+1,x-1])||rocky(g.map[y+1,x+1])
||rocky(g.map[y,x+1])||rocky(g.map[y,x-1]))
tgt ~= new Pos(y,x);
cand ~= search(g, ro, tgt, death, true);
}
if(cand.empty) {
choke_count++;
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) || wait_count>=2) {
foreach(char live; "UDLRW")
if(death.count(live)==0) {
c=live;
break;
}
}
if(c == 'W')
wait_count++;
else
wait_count = 0;
if(choke_count >= g.map.H)
c = 'A';
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[] gs, string death, bool danger_ok=false)
{
bool danger(int y, int x)
{
if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
return false;
if(rocky(g.map[y+1,x]))
return true;
if(rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||rocky(g.map[y,x-1])) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
return true;
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'))
return true;
if(rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||rocky(g.map[y-1,x-1])) && (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
return true;
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'))
return true;
return false;
}
// avoid directly below '*'
Tuple!(char,int)[] tryA() {
const(Pos)[] q;
foreach(p; gs)
if(!danger(p.y,p.x))
q ~= p;
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
foreach(p; q) v[p.y][p.x]=true;
for(int step=1; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y+1,p.y,p.y];
int[] xxx=[p.x,p.x,p.x-1,p.x+1];
for(int i=0; i<yyy.length; ++i) {
int y = yyy[i];
int x = xxx[i];
if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
foreach(ppp; g.map.tr_source[g.map[y,x]]) {
yyy ~= ppp.y;
xxx ~= ppp.x;
}
continue;
}
if(v[y][x]) continue;
if(y==s.y && x==s.x && i<4) {
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]=='.'||g.map[y,x]=='!'||i>=4) {
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;
foreach(p; gs) q ~= p;
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
foreach(p; q) v[p.y][p.x]=true;
for(int step=10; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y+1,p.y,p.y];
int[] xxx=[p.x,p.x,p.x-1,p.x+1];
for(int i=0; i<yyy.length; ++i) {
int y = yyy[i];
int x = xxx[i];
if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
foreach(ppp; g.map.tr_source[g.map[y,x]]) {
yyy ~= ppp.y;
xxx ~= ppp.x;
}
continue;
}
if(v[y][x]) continue;
if(y==s.y && x==s.x && i<4) {
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]=='.'||g.map[y,x]=='!'||i>=4) {
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
q = q2;
}
return [];
}
// push rocks!
Tuple!(char,int)[] tryC() {
const(Pos)[] q;
foreach(p; gs) q ~= p;
bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
foreach(p; q) v[p.y][p.x]=true;
for(int step=20; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y+1,p.y,p.y];
int[] xxx=[p.x,p.x,p.x-1,p.x+1];
for(int i=0; i<yyy.length; ++i) {
int y = yyy[i];
int x = xxx[i];
if(rocky(g.map[p])) {
if(i>=4)continue;
if(y!=p.y)continue;
if(g.map[y,p.x+(p.x-x)]!=' '&&g.map[y,p.x+(p.x-x)]!='R')continue;
}
if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
foreach(ppp; g.map.tr_source[g.map[y,x]]) {
yyy ~= ppp.y;
xxx ~= ppp.x;
}
continue;
}
if(v[y][x]) continue;
if(y==s.y && x==s.x && i<4) {
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]=='.'||rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
q = q2;
}
return [];
}
return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
}
}
class Solver_2(Solver)
{
string plan;
bool plan_broken = true;
Game g;
this(in Game g)
{
this.g = g.clone();
make_plan(g);
}
Tuple!(Solver,string) run_sub_solver(in Game g)
{
string log;
auto s = new Solver(g);
while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) {
char c = s.single_step();
if( c == 'A' )
break;
log ~= c;
}
while(log.length>0 && log[$-1]=='W')
log.length--;
return tuple(s, log);
}
void make_plan(in Game g) {
plan_broken = false;
Tuple!(Solver,string) x = run_sub_solver(g);
plan = x[1];
if(x[0].g.cleared)
return;
modify_plan(g, x[0].g.score);
}
void modify_plan(in Game ini, long unmod)
{
int bp = max(0, (cast(int)plan.length)-10);
Game g = ini.clone();
for(int i=0; i<bp; ++i) g.command(plan[i]);
Tuple!(string,long) cand = tuple(plan, unmod);
for(int i=bp; i<plan.length; ++i) {
foreach(string c; ["U","D","L","R","UD","DU","LR","RL"])
if(c[0] != plan[i]) {
Tuple!(string,long) zz = try_plan(c, g);
if(cand[1]<zz[1])
cand = tuple(plan[0..i]~c~zz[0], zz[1]);
}
g.command(plan[i]);
}
plan = cand[0];
}
Tuple!(string,long) try_plan(string c, in Game g)
{
Game gg = g.clone();
foreach(cc;c)gg.command(cc);
Tuple!(Solver, string) x = run_sub_solver(gg);
return tuple(x[1], x[0].g.score);
}
char single_step() {
if(plan_broken)
make_plan(g);
if(plan.empty)
return 'A';
char c = plan[0];
plan = plan[1..$];
g.command(c);
return c;
}
void force(char c) {
g.command(c);
if(plan.length==0 || plan[0]!=c) {
plan = "";
plan_broken = true;
}
else
plan = plan[1..$];
}
}
//alias Solver_2!(Solver_1) MainSolver;
alias Solver_1 MainSolver;
//alias Solver_0 MainSolver;