339 plan_state = Tentative; 339 plan_state = Tentative; 340 if(g.map.W*g.map.H <= 400) { 340 if(g.map.W*g.map.H <= 400) { 341 RandomChoicePattern = ["UU","UD","UL","UR", 341 RandomChoicePattern = ["UU","UD","UL","UR", 342 "DU","DD","DL","DR", 342 "DU","DD","DL","DR", 343 "LU","LD","LL","LR", 343 "LU","LD","LL","LR", 344 "RU","RD","RL","RR","UUU","UUUU", 344 "RU","RD","RL","RR","UUU","UUUU", 345 PredictFuture = 20; 345 PredictFuture = 20; 346 clear_improvement = 3; | 346 clear_improvement = 1; 347 } 347 } 348 else if(g.map.W*g.map.H <= 4096) { 348 else if(g.map.W*g.map.H <= 4096) { 349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," 349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," 350 PredictFuture = 10; 350 PredictFuture = 10; 351 clear_improvement = 0; 351 clear_improvement = 0; 352 } 352 } 353 else { 353 else { ................................................................................................................................................................................ 371 // If the future is bad, correct. 371 // If the future is bad, correct. 372 if( plan_state==Tentative_Stuck && plan.length<replan_limit && ! 372 if( plan_state==Tentative_Stuck && plan.length<replan_limit && ! 373 replan(); 373 replan(); 374 374 375 // Follow the predicted plan. 375 // Follow the predicted plan. 376 if( plan.empty ) 376 if( plan.empty ) 377 return 'A'; 377 return 'A'; 378 stderr.writeln(plan, " ", plan_state); < 379 char c = plan[0]; 378 char c = plan[0]; 380 plan = plan[1..$]; 379 plan = plan[1..$]; 381 int b_lambda = current_game.map.collected_lambda; 380 int b_lambda = current_game.map.collected_lambda; 382 current_game.command(c); 381 current_game.command(c); 383 int a_lambda = current_game.map.collected_lambda; 382 int a_lambda = current_game.map.collected_lambda; 384 if(b_lambda < a_lambda) lambda_getter = false; 383 if(b_lambda < a_lambda) lambda_getter = false; 385 return c; 384 return c; ................................................................................................................................................................................ 425 plan_state = (sub_solver.g.dead ? Tentative_Stuc 424 plan_state = (sub_solver.g.dead ? Tentative_Stuc 426 } 425 } 427 } 426 } 428 } 427 } 429 428 430 void replan() 429 void replan() 431 { 430 { 432 stderr.writeln("replan!"); < 433 // Try to replace every step of the plan by another move. 431 // Try to replace every step of the plan by another move. 434 Game g = current_game.clone(); 432 Game g = current_game.clone(); 435 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 433 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 436 int insertion_point = plan.length; 434 int insertion_point = plan.length; 437 writeln(cand, " ", cand[0].g.map.collected_lambda); < 438 bool tiebreak_by_turn = false; 435 bool tiebreak_by_turn = false; 439 int consider_length = min(ReplanLength, g.map.W*g.map.H); 436 int consider_length = min(ReplanLength, g.map.W*g.map.H); 440 if(cand[0].g.cleared) consider_length = min(consider_length, can 437 if(cand[0].g.cleared) consider_length = min(consider_length, can 441 438 442 for(int i=0; i<plan.length; ++i) { 439 for(int i=0; i<plan.length; ++i) { 443 foreach(string prefix; RandomChoicePattern) 440 foreach(string prefix; RandomChoicePattern) 444 if(prefix[0] != plan[i]) { 441 if(prefix[0] != plan[i]) { ................................................................................................................................................................................ 463 } 460 } 464 } 461 } 465 if(better) { 462 if(better) { 466 cand = r; 463 cand = r; 467 tiebreak_by_turn = true; 464 tiebreak_by_turn = true; 468 insertion_point = i+prefix.lengt 465 insertion_point = i+prefix.lengt 469 if(r[0].g.cleared) consider_leng 466 if(r[0].g.cleared) consider_leng 470 writeln(cand, " ", cand[0].g.map.collected_lambda); < 471 } 467 } 472 } 468 } 473 g.command(plan[i]); 469 g.command(plan[i]); 474 } 470 } 475 471 476 if(cand[2]==Fixed && insertion_point!=plan.length && clear_impro 472 if(cand[2]==Fixed && insertion_point!=plan.length && clear_impro 477 sub_solver = cand[0]; 473 sub_solver = cand[0]; ................................................................................................................................................................................ 507 } 503 } 508 if(s.g.cleared) state = Fixed; 504 if(s.g.cleared) state = Fixed; 509 else if(s.g.dead) state = Tentative_Stuck; 505 else if(s.g.dead) state = Tentative_Stuck; 510 return tuple(s, log, state); 506 return tuple(s, log, state); 511 } 507 } 512 } 508 } 513 509 > 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_ > 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_roc > 594 if( is_spacy_t(g.map[yy+1,xx+2]) > 595 return false; > 596 return true; > 597 } > 598 if( is_spacy_t(g.map[yy+1,xx]) && is_roc > 599 if(g.hige_until_rise == 1 && g.m > 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. > 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. > 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' : ' > 654 else > 655 return q.y<p.y ? 'U' : ' > 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 > 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; 514 alias Solver_2!(Solver_1) MainSolver; | 676 //alias Solver_2!(Solver_1) MainSolver; 515 //alias Solver_1 MainSolver; 677 //alias Solver_1 MainSolver; 516 //alias Solver_0 MainSolver; 678 //alias Solver_0 MainSolver;