//
// http://en.wikipedia.org/wiki/F%C5%ABrinkazan
//
import util;
import game;
interface Solver
{
// this(in Game g);
char single_step();
void force(char c);
}
Tuple!(string,int) death_move(in Game g)
{
// TODO: S
string death;
int breath;
int y = g.map.robot.y;
int x = g.map.robot.x;
int[5] dy_=[+1,-1,0,0,0];
int[5] dx_=[0,0,-1,+1,0];
char[] ds=['U','D','L','R','W'];
for(int i=0; i<5; ++i)
{
bool after_move_death(int y, int x, char tr_tgt)
{
bool is_spacy_t(char c) {
if(is_true_space(c) || c=='R' || c==tr_tgt)
return true;
return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt);
}
// check water
if( g.map[y,x]!='O' && g.hp==0 && y<=g.water_level )
return true;
// check falling rock.
int yy=y+1, xx=x;
if( is_spacy_t(g.map[yy, xx]) )
{
if( is_rocky(g.map[yy+1,xx]) )
return true;
if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) {
if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) )
return false;
return true;
}
if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) {
if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W')
return false;
return true;
}
}
return false;
}
int dy=dy_[i], dx=dx_[i];
if( is_spacy(g.map[y+dy,x+dx]) || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) )
{
if( after_move_death(y+dy, x+dx, char.init) )
death ~= ds[i];
else if(ds[i] != 'W')
breath ++;
}
else if( is_trampoline_source(g.map[y+dy,x+dx]) )
{
Pos p = g.tr.target_pos(g.map[y+dy,x+dx]);
if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) )
death ~= ds[i];
else
breath ++;
}
else
{
death ~= ds[i];
}
}
return tuple(death, breath);
}
class Queue(T)
{
alias Tuple!(T,int) t;
t[] cur, next;
void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); }
bool empty() { return cur.empty; }
t pop() {
t v = cur[0]; cur = cur[1..$];
if(cur.empty) { cur = next; next = null; }
return v;
}
}
///
/// Solver "Mountain": be immovable like a mountain.
///
class 不動如山 : Solver
{
this(in Game g) {}
char single_step() { return 'W'; }
void force(char c) {}
}
///
/// Solver "Forest": shows contemplation.
///
class 徐如林 : Solver
{
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!(Pos, int)[] log;
bool[][] forbidden_cell;
char act(const(Game) g, string death, int breath)
{
foreach(char c; "UDLR")
if( death.count(c)==0 && is_one_way_load(g,c) )
return c;
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.num_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);
}
}
// 'horo-push' mode
if(cand.empty) {
Pos[] horo = g.map.objects('@');
Pos[] tgt;
foreach(p; horo)
if((g.map[p.y,p.x-1]==' '||g.map[p.y,p.x-1]=='R')&&
(g.map[p.y,p.x+1]==' '||g.map[p.y,p.x+1]=='R')
||(g.map[p.y-1,p.x]==' '||g.map[p.y-1,p.x]=='R'))
tgt ~= p;
for(int y=1; y<=g.map.H; ++y)
for(int x=1; x<=g.map.W; ++x)
if(g.map[y,x]=='.')
if(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
||is_rocky(g.map[y,x+1])||is_rocky(g.map[y,x-1]))
tgt ~= new Pos(y,x);
if(!tgt.empty)
cand ~= search(g, ro, tgt, death, true);
}
// 'dig' mode
if(cand.empty) {
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(is_rocky(g.map[y+1,x])||is_rocky(g.map[y+1,x-1])||is_rocky(g.map[y+1,x+1])
||is_rocky(g.map[y,x+1])||is_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(wait_count==2)
c = 'A';
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 very_danger(int y, int x)
{
if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
return false;
if(is_rocky(g.map[y+1,x]))
return true;
return false;
}
bool danger(int y, int x)
{
if(g.map[y,x] == ' ' || g.map[y,x] == 'R')
return false;
if(is_rocky(g.map[y+1,x]))
return true;
if(is_rocky(g.map[y+1,x-1]) && (g.map[y,x-1]=='\\'||is_rocky(g.map[y,x-1]))
&& (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
return true;
if(is_rocky(g.map[y+1,x+1]) && is_rocky(g.map[y,x+1]) && (g.map[y+1,x]==' '||g.map[y+1,x]=='R'))
return true;
if(is_rocky(g.map[y,x-1]) && (g.map[y-1,x-1]=='\\'||is_rocky(g.map[y-1,x-1]))
&& (g.map[y-1,x]==' '||g.map[y-1,x]=='R'))
return true;
if(is_rocky(g.map[y,x+1]) && is_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(!very_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;
bool first_step = true;
for(int step=1; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y,p.y,p.y+1];
int[] xxx=[p.x,p.x-1,p.x+1,p.x];
string sss="URLD";
for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
int y = yyy[i];
int x = xxx[i];
if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
foreach(ppp; g.tr.source_pos(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 = sss[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;
}
}
}
first_step = false;
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;
bool first_step = true;
for(int step=8; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y,p.y,p.y+1];
int[] xxx=[p.x,p.x-1,p.x+1,p.x];
string sss="URLD";
for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
int y = yyy[i];
int x = xxx[i];
if('1'<=g.map[y,x]&&g.map[y,x]<='9') {
foreach(ppp; g.tr.source_pos(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 = sss[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;
}
}
}
first_step = false;
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;
bool first_step = true;
for(int step=20; q.length; ++step) {
Pos[] q2;
foreach(p; q) {
int[] yyy=[p.y-1,p.y,p.y,p.y+1];
int[] xxx=[p.x,p.x-1,p.x+1,p.x];
string sss="URLD";
for(int i=0; i<yyy.length; ++i) if(!first_step || g.map[p]!='@' || sss[i]=='L' || sss[i]=='R') {
int y = yyy[i];
int x = xxx[i];
if(is_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.tr.source_pos(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 = sss[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]=='.'||is_rocky(g.map[y,x])||g.map[y,x]=='!'||i>=4) {
q2 ~= new Pos(y,x);
v[y][x]=true;
}
}
}
first_step = false;
q = q2;
}
return [];
}
return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
}
bool is_one_way_load(in Game g, char c)
{
Pos p = g.map.robot.clone();
Pos q;
if(c=='U') q=new Pos(p.y+1,p.x);
if(c=='D') q=new Pos(p.y-1,p.x);
if(c=='L') q=new Pos(p.y,p.x-1);
if(c=='R') q=new Pos(p.y,p.x+1);
char d = g.map[q];
if(!(d==' '||d=='.'||d=='!'))
return false;
bool found_lambda = false;
int[4] dy=[-1,+1,0,0];
int[4] dx=[0,0,+1,-1];
for(;;)
{
Pos r = null;
for(int i=0; i<4; ++i) {
int y=q.y+dy[i];
int x=q.x+dx[i];
if(x==p.x && y==p.y)
continue;
char e = g.map[y,x];
if(e=='#')
continue;
if(e==' '||e=='.'||e=='!'||e=='R'||e=='\\') {
if(r !is null)
return false;
r = new Pos(y,x);
if(e=='\\')
found_lambda = true;
continue;
}
return false;
}
if(r is null)
break;
p=q;
q=r;
}
return found_lambda;
}
}
///
/// Solver "Fire": in raiding and plundering other solvers, be like fire.
///
class 侵掠如火(SubSolver) : Solver
{
// Parameters.
int PredictFuture = 10;
const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step)
Game current_game;
SubSolver sub_solver;
enum {Tentative, Tentative_Stuck, Fixed};
string plan;
int plan_state;
int replan_limit;
bool lambda_getter;
int clear_improvement = 3;
this(in Game g)
{
current_game = g.clone();
plan = "";
plan_state = Tentative;
if(g.map.W*g.map.H <= 400) {
RandomChoicePattern = ["UU","UD","UL","UR",
"DU","DD","DL","DR",
"LU","LD","LL","LR",
"RU","RD","RL","RR","UUU","UUUU","UUUUU"];
PredictFuture = 20;
clear_improvement = 1;
}
else if(g.map.W*g.map.H <= 4096) {
RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
PredictFuture = 10;
clear_improvement = 0;
}
else {
RandomChoicePattern = ["U","D","L","R"];
PredictFuture = 10;
clear_improvement = 0;
}
replan_limit = PredictFuture;
}
char single_step()
{
if(current_game.dead || current_game.cleared)
return 'A';
// Make enough prediction.
while( plan_state==Tentative && plan.length<replan_limit )
single_step_predict();
// If the future is bad, correct.
if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter )
replan();
// Follow the predicted plan.
if( plan.empty )
return 'A';
char c = plan[0];
plan = plan[1..$];
int b_lambda = current_game.map.collected_lambda;
current_game.command(c);
int a_lambda = current_game.map.collected_lambda;
if(b_lambda < a_lambda) lambda_getter = false;
return c;
}
void force(char c)
{
if(plan.length>0 && plan[0]==c)
{
// If matching the plan, just go forward.
plan = plan[1..$];
}
else
{
// Discard the plan, otherwise.
plan_state = Tentative;
plan = "";
sub_solver = null;
}
current_game.command(c);
}
void single_step_predict()
{
if(sub_solver is null) {
sub_solver = new SubSolver(current_game);
plan = "";
}
char c = sub_solver.single_step();
if(c == 'A')
plan_state = Tentative_Stuck;
else {
plan ~= c;
if(sub_solver.g.cleared) {
if(clear_improvement-->0) {
plan_state = Tentative_Stuck;
replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture);
} else {
plan_state = Fixed;
}
} else {
plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative);
}
}
}
void replan()
{
// Try to replace every step of the plan by another move.
Game g = current_game.clone();
Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
int insertion_point = plan.length;
bool tiebreak_by_turn = false;
int consider_length = min(ReplanLength, g.map.W*g.map.H);
if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length);
for(int i=0; i<plan.length; ++i) {
foreach(string prefix; RandomChoicePattern)
if(prefix[0] != plan[i]) {
Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length);
r[1] = plan[0..i] ~ prefix ~ r[1];
bool better = false, tbt=false;
if(!cand[0].g.cleared && r[0].g.cleared)
better = true;
else if(cand[0].g.cleared && r[0].g.cleared) {
better = cand[0].g.score < r[0].g.score;
}
else if(!cand[0].g.cleared && !r[0].g.cleared) {
if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
better = true;
else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
if(cand[0].g.dead && !r[0].g.dead)
better = true;
else if(cand[0].g.dead == r[0].g.dead) {
better = (cand[1].length < r[1].length && r[2]!=Tentative_Stuck);
tbt = true;
}
}
}
if(better) {
cand = r;
tiebreak_by_turn = true;
insertion_point = i+prefix.length;
if(r[0].g.cleared) consider_length = min(consider_length, r[1].length);
}
}
g.command(plan[i]);
}
if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) {
sub_solver = cand[0];
plan = cand[1];
plan_state = Tentative_Stuck;
replan_limit = min(plan.length - insertion_point, PredictFuture);
lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
} else {
sub_solver = cand[0];
plan = cand[1];
plan_state = (plan.length < PredictFuture ? Fixed : cand[2]);
replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture;
lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda;
}
}
Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length)
{
if(consider_length<=0) consider_length = 2;
SubSolver s = new SubSolver(g);
foreach(char c; prefix)
s.force(c);
string log;
int state = Tentative;
while(!s.g.cleared && !s.g.dead && log.length<=consider_length) {
char c = s.single_step();
if( c == 'A' ) {
state = Tentative_Stuck;
break;
}
log ~= c;
}
if(s.g.cleared) state = Fixed;
else if(s.g.dead) state = Tentative_Stuck;
return tuple(s, log, state);
}
}
///
/// Solver "Wind": let your rapidity be that of the wind.
///
class 疾如風(bool UP) : Solver
{
Game g;
this(in Game g)
{
this.g = g.clone();
}
string plan;
char single_step()
{
auto dm = death_move(g);
if( plan.empty || dm[0].count(plan[0]) ) {
plan = think(g, dm[0]);
if( plan.empty )
plan = "W";
}
char c = plan[0];
plan = plan[1..$];
if(c == 'W') {
wait_counter++;
if(dm[0].count(c) || wait_counter>=3) {
c = 'A';
foreach(char cc; "DLRU")
if(dm[0].count(cc) == 0)
c = cc;
}
if(wait_counter > 20)
c = 'A';
} else {
wait_counter = 0;
}
if(c != 'A')
g.command(c);
return c;
}
void force(char c)
{
if(c != 'A')
g.command(c);
}
int wait_counter = 0;
string think(in Game g, string death)
{
auto Q = new Queue!(Tuple!(Pos,Pos));
Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0);
Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2);
while(!Q.empty) {
auto tup = Q.pop();
Pos p = tup[0][0];
Pos prev = tup[0][1];
int dist = tup[1];
if(V[p.y][p.x])
continue;
V[p.y][p.x] = prev;
if(g.map[p]=='\\' || g.map[p]=='O')
{
char[] trace;
for(;;) {
Pos q = V[p.y][p.x];
trace ~= (q.y==p.y ? (q.x<p.x ? 'R' : 'L') :
(q.y<p.y ? 'U' : 'D'));
if(q == g.map.robot) {
reverse(trace);
return trace.idup;
}
p=q;
}
}
int[4] dy=UP ? [+1,0,0,-1] : [-1,+1,0,0];
int[4] dx=UP ? [0,-1,+1,0] : [0,0,-1,+1];
char[] ds=UP ? ['U','L','R','D'] : ['D','U','L','R'];
for(int i=0; i<4; ++i) {
if(g.map.robot==p && death.count(ds[i]))
continue;
int y=p.y+dy[i], x=p.x+dx[i];
if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O'||g.map[y,x]=='!')&&!V[y][x]) {
Q.push(tuple(new Pos(y,x),p), dist+1);
}
}
}
return "";
}
}
class Switcher
{
this(in Game g)
{
if(g.map.W*g.map.H <= 1600)
sub_solver = new 侵掠如火!(徐如林)(g);
else
sub_solver = new 侵掠如火!(疾如風!(true))(g);
}
char single_step() { return sub_solver.single_step(); }
void force(char c) { return sub_solver.force(c); }
private Solver sub_solver;
}
alias 侵掠如火!(疾如風!(false)) FastSolver;
alias Switcher MainSolver;
//alias FastSolver MainSolver;
//alias 徐如林 MainSolver;