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