142 142 } 143 143 } 144 144 145 145 if(c == 'W') 146 146 wait_count++; 147 147 else 148 148 wait_count = 0; 149 + if(wait_count==2) 150 + c = 'A'; 149 151 if(choke_count >= g.map.H) 150 152 c = 'A'; 151 153 152 154 bool[char] choice; 153 155 foreach(t; cand) 154 156 choice[t[0]] = true; 155 157 log ~= tuple(ro.clone(), cast(int)choice.length); ................................................................................ 311 313 } 312 314 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC(); 313 315 } 314 316 } 315 317 316 318 class Solver_2(SubSolver) : Solver 317 319 { 320 + static const PredictFuture = 10; 321 + 322 + Game current_game; 323 + SubSolver sub_solver; 324 + 325 + enum {Tentative, Tentative_Stuck, Fixed}; 318 326 string plan; 319 - bool plan_broken = true; 327 + int plan_state; 320 328 321 - Game g; 322 329 this(in Game g) 323 330 { 324 - this.g = g.clone(); 325 - make_plan(g); 331 + current_game = g.clone(); 332 + plan = ""; 333 + plan_state = Tentative; 334 + } 335 + 336 + char single_step() 337 + { 338 + if(current_game.dead || current_game.cleared) 339 + return 'A'; 340 + 341 + // Make enough prediction. 342 + while( plan_state==Tentative && plan.length<PredictFuture ) 343 + single_step_predict(); 344 + 345 + // If the future is bad, correct. 346 + if( plan_state==Tentative_Stuck && plan.length<PredictFuture ) 347 + replan(); 348 + 349 + // Follow the predicted plan. 350 + if( plan.empty ) 351 + return 'A'; 352 +writeln(plan, " ", plan_state); 353 + char c = plan[0]; 354 + plan = plan[1..$]; 355 + current_game.command(c); 356 + return c; 326 357 } 327 358 328 - Tuple!(SubSolver,string) run_sub_solver(in Game g) 359 + void force(char c) 329 360 { 330 - string log; 331 - auto s = new SubSolver(g); 332 - while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) { 333 - char c = s.single_step(); 334 - if( c == 'A' ) 335 - break; 336 - log ~= c; 361 + if(plan.length>0 && plan[0]==c) 362 + { 363 + // If matching the plan, just go forward. 364 + plan = plan[1..$]; 365 + } 366 + else 367 + { 368 + // Discard the plan, otherwise. 369 + plan_state = Tentative; 370 + plan = ""; 371 + sub_solver = null; 337 372 } 338 - while(log.length>0 && log[$-1]=='W') 339 - log.length--; 340 - return tuple(s, log); 373 + current_game.command(c); 341 374 } 342 375 343 - void make_plan(in Game g) { 344 - plan_broken = false; 345 - Tuple!(SubSolver,string) x = run_sub_solver(g); 346 - plan = x[1]; 347 - if(x[0].g.cleared) 348 - return; 349 - modify_plan(g, x[0].g.score); 376 + void single_step_predict() 377 + { 378 + if(sub_solver is null) { 379 + sub_solver = new SubSolver(current_game); 380 + plan = ""; 381 + } 382 + 383 + char c = sub_solver.single_step(); 384 + if(c == 'A') 385 + plan_state = Tentative_Stuck; 386 + else { 387 + plan ~= c; 388 + plan_state = (sub_solver.g.dead ? Tentative_Stuck : 389 + sub_solver.g.cleared ? Fixed : Tentative); 390 + } 350 391 } 351 392 352 - void modify_plan(in Game ini, long unmod) 393 + void replan() 353 394 { 354 - int bp = max(0, (cast(int)plan.length)-10); 355 - Game g = ini.clone(); 356 - for(int i=0; i<bp; ++i) g.command(plan[i]); 357 - 358 - Tuple!(string,long) cand = tuple(plan, unmod); 359 - for(int i=bp; i<plan.length; ++i) { 360 - foreach(string c; ["U","D","L","R","UD","DU","LR","RL"]) 361 - if(c[0] != plan[i]) { 362 - Tuple!(string,long) zz = try_plan(c, g); 363 - if(cand[1]<zz[1]) 364 - cand = tuple(plan[0..i]~c~zz[0], zz[1]); 395 +writeln("replan!"); 396 + // Try to replace every step of the plan by another move. 397 + Game g = current_game.clone(); 398 + Tuple!(long, SubSolver, string, int) cand = 399 + tuple(sub_solver.g.score, sub_solver, plan, Tentative_Stuck); 400 + for(int i=0; i<plan.length; ++i) { 401 + foreach(string prefix; ["U","D","L","R","UD","DU","LR","RL"]) 402 + if(prefix[0] != plan[i]) { 403 + Tuple!(long, SubSolver, string, int) r = try_plan(g, prefix); 404 + if(cand[0] < r[0]) { 405 + r[2] = plan[0..i] ~ prefix ~ r[2]; 406 + cand = r; 407 + } 365 408 } 366 409 g.command(plan[i]); 367 410 } 368 - plan = cand[0]; 369 - } 370 411 371 - Tuple!(string,long) try_plan(string c, in Game g) 372 - { 373 - Game gg = g.clone(); 374 - foreach(cc;c)gg.command(cc); 375 - Tuple!(SubSolver, string) x = run_sub_solver(gg); 376 - return tuple(x[1], x[0].g.score); 412 + sub_solver = cand[1]; 413 + plan = cand[2]; 414 + plan_state = (plan.length < PredictFuture ? Fixed : cand[3]); 377 415 } 378 416 379 - char single_step() { 380 - if(plan_broken) 381 - make_plan(g); 382 - if(plan.empty) 383 - return 'A'; 384 - char c = plan[0]; 385 - plan = plan[1..$]; 386 - g.command(c); 387 - return c; 388 - } 389 - 390 - void force(char c) { 391 - g.command(c); 392 - if(plan.length==0 || plan[0]!=c) { 393 - plan = ""; 394 - plan_broken = true; 417 + Tuple!(long, SubSolver, string, int) try_plan(in Game g, string prefix) 418 + { 419 + SubSolver s = new SubSolver(g); 420 + foreach(char c; prefix) 421 + s.force(c); 422 + string log; 423 + int state = Tentative; 424 + while(!s.g.cleared && !s.g.dead && log.length<=g.map.H*g.map.W) { 425 + char c = s.single_step(); 426 + if( c == 'A' ) { 427 + state = Tentative_Stuck; 428 + break; 429 + } 430 + log ~= c; 395 431 } 396 - else 397 - plan = plan[1..$]; 432 + if(s.g.cleared) state = Fixed; 433 + else if(s.g.dead) state = Tentative_Stuck; 434 + return tuple(s.g.score, s, log, state); 398 435 } 399 436 } 400 437 401 438 class MasterSolver : Solver 402 439 { 403 440 this(in Game g) 404 441 { ................................................................................ 412 449 } 413 450 414 451 private Solver sub; 415 452 char single_step() { return sub.single_step(); } 416 453 void force(char c) { sub.force(c); } 417 454 } 418 455 419 -alias MasterSolver MainSolver; 420 -//alias Solver_2!(Solver_1) MainSolver; 456 +//alias MasterSolver MainSolver; 457 +alias Solver_2!(Solver_1) MainSolver; 421 458 //alias Solver_1 MainSolver; 422 459 //alias Solver_0 MainSolver;