339 339 plan_state = Tentative; 340 340 if(g.map.W*g.map.H <= 400) { 341 341 RandomChoicePattern = ["UU","UD","UL","UR", 342 342 "DU","DD","DL","DR", 343 343 "LU","LD","LL","LR", 344 344 "RU","RD","RL","RR","UUU","UUUU","UUUUU"]; 345 345 PredictFuture = 20; 346 - clear_improvement = 3; 346 + clear_improvement = 1; 347 347 } 348 348 else if(g.map.W*g.map.H <= 4096) { 349 349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"]; 350 350 PredictFuture = 10; 351 351 clear_improvement = 0; 352 352 } 353 353 else { ................................................................................ 371 371 // If the future is bad, correct. 372 372 if( plan_state==Tentative_Stuck && plan.length<replan_limit && !lambda_getter ) 373 373 replan(); 374 374 375 375 // Follow the predicted plan. 376 376 if( plan.empty ) 377 377 return 'A'; 378 -stderr.writeln(plan, " ", plan_state); 379 378 char c = plan[0]; 380 379 plan = plan[1..$]; 381 380 int b_lambda = current_game.map.collected_lambda; 382 381 current_game.command(c); 383 382 int a_lambda = current_game.map.collected_lambda; 384 383 if(b_lambda < a_lambda) lambda_getter = false; 385 384 return c; ................................................................................ 425 424 plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative); 426 425 } 427 426 } 428 427 } 429 428 430 429 void replan() 431 430 { 432 -stderr.writeln("replan!"); 433 431 // Try to replace every step of the plan by another move. 434 432 Game g = current_game.clone(); 435 433 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck); 436 434 int insertion_point = plan.length; 437 -writeln(cand, " ", cand[0].g.map.collected_lambda); 438 435 bool tiebreak_by_turn = false; 439 436 int consider_length = min(ReplanLength, g.map.W*g.map.H); 440 437 if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length); 441 438 442 439 for(int i=0; i<plan.length; ++i) { 443 440 foreach(string prefix; RandomChoicePattern) 444 441 if(prefix[0] != plan[i]) { ................................................................................ 463 460 } 464 461 } 465 462 if(better) { 466 463 cand = r; 467 464 tiebreak_by_turn = true; 468 465 insertion_point = i+prefix.length; 469 466 if(r[0].g.cleared) consider_length = min(consider_length, r[1].length); 470 -writeln(cand, " ", cand[0].g.map.collected_lambda); 471 467 } 472 468 } 473 469 g.command(plan[i]); 474 470 } 475 471 476 472 if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) { 477 473 sub_solver = cand[0]; ................................................................................ 507 503 } 508 504 if(s.g.cleared) state = Fixed; 509 505 else if(s.g.dead) state = Tentative_Stuck; 510 506 return tuple(s, log, state); 511 507 } 512 508 } 513 509 514 -alias Solver_2!(Solver_1) MainSolver; 510 +class Queue(T) 511 +{ 512 + alias Tuple!(T,int) t; 513 + 514 + t[] cur, next; 515 + 516 + void push(T v, int p) { (cur.empty ? cur : next) ~= tuple(v,p); } 517 + bool empty() { return cur.empty; } 518 + t pop() { 519 + t v = cur[0]; cur = cur[1..$]; 520 + if(cur.empty) { cur = next; next = null; } 521 + return v; 522 + } 523 +} 524 + 525 +class Solver_3 : Solver 526 +{ 527 + Game g; 528 + this(in Game g) 529 + { 530 + this.g = g.clone(); 531 + } 532 + 533 + char single_step() 534 + { 535 + char c = think(g); 536 + if(c != 'A') 537 + g.command(c); 538 + return c; 539 + } 540 + 541 + void force(char c) 542 + { 543 +stderr.writeln(death_move(g)); 544 + if(c != 'A') 545 + g.command(c); 546 + } 547 + 548 + bool is_spacy(char c) { 549 + return c==' ' || c=='.' || c=='R' || c=='!' || c=='\\' || c=='O'; 550 + } 551 + bool is_rocky(char c) { 552 + return c=='*' || c=='@'; 553 + } 554 + bool is_true_space(char c) { 555 + return c==' '; 556 + } 557 + bool is_trampoline_source(char c) { 558 + return 'A'<=c && c<='I'; 559 + } 560 + bool is_rocklambda(char c) { 561 + return is_rocky(c) || c=='\\'; 562 + } 563 + 564 + string death_move(in Game g) 565 + { 566 + // TODO: S 567 + string death; 568 + int y = g.map.robot.y; 569 + int x = g.map.robot.x; 570 + int[5] dy_=[-1,+1,0,0,0]; 571 + int[5] dx_=[0,0,-1,+1,0]; 572 + char[] ds=['D','U','L','R','W']; 573 + for(int i=0; i<5; ++i) 574 + { 575 + bool after_move_death(int y, int x, char tr_tgt) 576 + { 577 + bool is_spacy_t(char c) { 578 + if(is_spacy(c) || c==tr_tgt) 579 + return true; 580 + return ('A'<=c && c<='I' && g.tr.target_of(c)==tr_tgt); 581 + } 582 + 583 + // check water 584 + if( g.hp==0 && y<=g.water_level ) 585 + return true; 586 + 587 + // check falling rock. 588 + int yy=y+1, xx=x; 589 + if( is_spacy_t(g.map[yy, xx]) ) 590 + { 591 + if( is_rocky(g.map[yy+1,xx]) ) 592 + return true; 593 + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx+1]) && is_rocky(g.map[yy,xx+1]) ) { 594 + if( is_spacy_t(g.map[yy+1,xx+2]) && is_spacy_t(g.map[yy,xx+2]) ) 595 + return false; 596 + return true; 597 + } 598 + if( is_spacy_t(g.map[yy+1,xx]) && is_rocky(g.map[yy+1,xx-1]) && is_rocklambda(g.map[yy,xx-1]) ) { 599 + if(g.hige_until_rise == 1 && g.map[yy+1,xx+1]=='W') 600 + return false; 601 + return true; 602 + } 603 + } 604 + return false; 605 + } 606 + 607 + int dy=dy_[i], dx=dx_[i]; 608 + if( is_spacy(g.map[y+dy,x+dx]) 609 + || dy==0 && is_rocky(g.map[y,x+dx]) && is_true_space(g.map[y,x+2*dx]) ) 610 + { 611 + if( after_move_death(y+dy, x+dx, char.init) ) 612 + death ~= ds[i]; 613 + } 614 + else if( is_trampoline_source(g.map[y+dy,x+dx]) ) 615 + { 616 + Pos p = g.tr.target_pos(g.map[y+dy,x+dx]); 617 + if( after_move_death(p.y, p.x, g.tr.target_of(g.map[y+dy,x+dx])) ) 618 + death ~= ds[i]; 619 + } 620 + else 621 + { 622 + death ~= ds[i]; 623 + } 624 + } 625 + return death; 626 + } 627 + 628 + char think(in Game g) 629 + { 630 + string s = death_move(g); 631 + stderr.writeln(s); 632 + 633 + auto Q = new Queue!(Tuple!(Pos,Pos)); 634 + Q.push(tuple(g.map.robot.clone(), g.map.robot.clone()), 0); 635 + Pos[][] V = new Pos[][](g.map.H+2, g.map.W+2); 636 + while(!Q.empty) { 637 + auto tup = Q.pop(); 638 + Pos p = tup[0][0]; 639 + Pos prev = tup[0][1]; 640 + int dist = tup[1]; 641 + if(V[p.y][p.x]) 642 + continue; 643 + V[p.y][p.x] = prev; 644 + if(g.map[p]=='\\' || g.map[p]=='O') 645 + { 646 + Pos goback(Pos p) { 647 + return V[p.y][p.x]; 648 + } 649 + for(;;) { 650 + Pos q = goback(p); 651 + if(q == g.map.robot) 652 + if(q.y==p.y) 653 + return q.x<p.x ? 'R' : 'L'; 654 + else 655 + return q.y<p.y ? 'U' : 'D'; 656 + p=q; 657 + } 658 + } 659 + 660 + int[4] dy=[-1,+1,0,0]; 661 + int[4] dx=[0,0,-1,+1]; 662 + char[] ds=['D','U','L','R']; 663 + for(int i=0; i<4; ++i) 664 + { 665 + int y=p.y+dy[i], x=p.x+dx[i]; 666 + if((g.map[y,x]==' '||g.map[y,x]=='\\'||g.map[y,x]=='.'||g.map[y,x]=='O')&&!V[y][x]) { 667 + Q.push(tuple(new Pos(y,x),p), dist+1); 668 + } 669 + } 670 + } 671 + return 'A'; 672 + } 673 +} 674 + 675 +alias Solver_3 MainSolver; 676 +//alias Solver_2!(Solver_1) MainSolver; 515 677 //alias Solver_1 MainSolver; 516 678 //alias Solver_0 MainSolver;