Mise à jour: Il y a 6 labyrinthes. Ils sont inclus dans le contrôleur. Il y a un tar.gz des labyrinthes et de leurs fichiers .bmp ici (dropbox). Il existe également un utilitaire pour créer plus de labyrinthes sur ce lien (le fichier maze_4.txt est incorrect dans l'archive). À ce stade, n'hésitez pas à exécuter votre propre entrée et à mettre à jour votre score. Les détails sur la façon de le faire sont inclus en bas. Si vous avez des questions ou des problèmes, envoyez-moi un ping dans le chat.
Tu es une souris. Tu es dans un labyrinthe. Trouvez le fromage.
Concept
Vous êtes dans un labyrinthe qui existe sur une grille rectangulaire. Chaque espace de la grille contient plusieurs éléments:
!- Un mur infranchissableO- Toi, la souris+- Le fromage, votre objectif
Veuillez utiliser les mêmes caractères pour ne pas avoir à modifier le contrôleur.
À chaque tour, vous recevrez les tuiles qui sont au nord, au sud, à l'est et à l'ouest de votre position actuelle. Vous devez ensuite sortir la direction que vous souhaitez parcourir. Vous gagnez en arrivant au fromage. Moins d'étapes, c'est mieux.
Contribution
Vous recevrez une entrée via stdin de la manière suivante:, neswoù chaque lettre représente la tuile à ce point de la boussole. Par exemple, si l'état actuel ressemble à
! <--- Wall
!O <--- You
+ <--- Cheese
alors vous recevrez la chaîne ! +!.
A la fin du jeu, le contrôleur vous envoie une chaîne de quatre zéros: 0000. À la réception de cette chaîne, votre programme devrait se terminer. Aucune autre entrée donnée ne contiendra le 0caractère.
Veuillez ignorer toutes les autres entrées.
Sortie
Vous êtes à la sortie d' une lettre n, s, eou w, pour indiquer dans quelle direction vous voulez Voyage, suivi d'un caractère de nouvelle ligne.
Notation
Votre score à chaque test est le nombre d'étapes qu'il vous faut pour trouver le fromage.
Votre score global sera la somme de votre score moyen par labyrinthe sur une batterie de labyrinthes de tailles variables, qui s'inscriront tous dans un carré de longueur 50.
Par exemple, si cela prend 100 bots à votre robot pour terminer chacun des 6 labyrinthes, alors votre score est de 600.
Si votre bot n'est pas déterministe, veuillez essayer chaque labyrinthe 10 fois et utilisez la moyenne comme score pour ce labyrinthe. Votre score final sera la somme de toutes les moyennes.
Règles
- Chaque labyrinthe rentrera dans un carré de 50x50.
- Chaque labyrinthe aura au moins un chemin valide du début au fromage.
- Chaque labyrinthe sera entièrement clos, sauf que le fromage sera toujours sur la paroi extérieure de sorte qu'il sert essentiellement de sortie au labyrinthe.
- Si vous rencontrez un mur, votre soumission est disqualifiée.
- Si votre soumission prend trop de temps (tel que déterminé par moi, alors que je commence les tests), elle sera disqualifiée. C'est en grande partie pour éviter les boucles infinies. La limite souple sera d'une minute par labyrinthe, bien que je me réserve le droit de la modifier à tout moment dans les deux sens.
- Les inscriptions n'ont pas besoin d'être déterministes, mais si vous êtes trop aléatoire, vous serez probablement disqualifié par le point ci-dessus.
- À un moment donné, la batterie des labyrinthes sera libérée, les réponses futures pourraient ne pas être optimisées à leur égard et elles pourraient changer.
Soumissions :
Votre soumission est un programme complet qui prend l'entrée via stdin et la sortie via stdout. Ceci est important car la soumission interagira avec le contrôleur du labyrinthe. Je ne vais pas interdire les langues qui ne sont pas disponibles gratuitement, mais sachez que quelqu'un d'autre devra offrir son temps pour exécuter les tests si je n'ai pas accès à la langue.
Veuillez inclure des instructions sur la façon d'exécuter votre soumission.
Veuillez indiquer si votre soumission est déterministe ou non, afin que je sache si je dois l'exécuter plusieurs fois.
Labyrinthes d'essai
Dans les labyrinthes d'essai, les .personnages décrivent le chemin le plus court vers le fromage. Ils sont identiques au caractère (espace). Ils ne sont pas visibles pour votre soumission. Le contrôleur les remplace par des espaces.
!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.! !
! !.!.!! !
!!!.!.!! !
! .!.! !!
!!!... !
!!!!!!!!!!
Labyrinthe de test 31x31. Sans vergogne volé .
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! O...!.......! ! .....!.....! ! ! !
!!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! !
! !...! !.! !.! !.!.! !.! ! ! ! ! ! !
! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! !
! ! !.........! !...!...! ! ! ! ! ! ! ! !
! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! !
! ! ! ! !.....! ! ! ! ! ! ! ! ! !
!!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
! ! ! !.! ! ! ! ! !
! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
! ! ! ! ! !...!.! ! ! ! ! !
! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
! ! ! ! ! !.!...! ! ! ! ! ! ! ! ! !
!!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
! ! ! ! ! !...! ! ! ! ! ! ! ! ! ! !
! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
! ! ! !...! ! ! ! ! ! ! !
!!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
! ! !...! ! ! ! ! ! !
! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
! ! ! ! ! !.! ! ! ! ! ! ! ! ! ! ! !
! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
! ! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
! ! ! ! ! !.......! ! ! ! ! ! ! ! !
! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
! ! ! !...! ! ! ! ! ! ! ! !
!!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
! ! ! ! !.! ! ! ! ! ! !
! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
! ! ! ! ! ! !.......! ! ! ! ! !
! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! !
! ! ! ! ! ! ! !.! ! ! ! ! !
!!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! !
! ! ! ! ! !.! ! ! ! ! ! ! !
! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
! ! ! ! ! !.! ! ! ! !
! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
! ! ! ! ! ! ! ! !.....! ! ! ! !...............!
! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.!
! ! ! ! ! ! !...! ! ! !.! !...!
!!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!!
! ! ! ! ! !.......! !...!.....! .! !
! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! !
! ! ! ! ! ! !...........!...!...!.....!...!
! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.!
! ! ! ! ! ! ! ! !.!..... !...!.!
!!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.!
! ! ! ! ! ! ! ! ! !...! !.........!.!
! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.!
! ! ! ! ! ! ! ! ! ! !.!.....! !.!
! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.!
! ! ! ! ! ! ! ! ! !.!...! ! !.!
! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.!
! ! ! ! .....! .!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+!
Manette
Le contrôleur est en rouille (1.11 tous les soirs)
type Maze = Vec<Vec<char>>;
fn str_to_maze(input: &str) -> Result<Maze,i32> {
let mut maze: Vec<Vec<char>> = vec![ vec![] ];
let mut row: Vec<char> = vec![];
for c in input.chars() {
if c == '!' || c == '+' || c == 'O' || c == ' ' {
row.push(c);
}
else if c =='.' {
row.push(' ');
}
else if c == '#' {
maze.push(row);
row = vec![];
}
else if c =='\0' {
break;
}
else {
println!("Bad character in maze: {}, exiting.", c);
return Err(1);
}
}
return Ok(maze);
}
fn display_maze(maze: &Maze, position: [usize;2]) {
for y in 0..maze.len() {
for x in 0..maze[y].len() {
if [x,y] == position {
print!("O");
}
else if maze[y][x] == '#' {
println!("\n");
}
else {
print!("{}",maze[y][x]);
}
}
println!("");
}
println!("\n");
}
fn get_starting_position(maze: &mut Maze) -> Result<[usize;2],&str> {
for y in 0..maze.len() {
for x in 0..maze[y].len() {
if maze[y][x] == 'O' {
maze[y][x] = ' ';
return Ok([x,y]);
}
}
}
return Err("No mouse found");
}
enum State {
Continue([char;4]),
Win,
Disqualify,
}
fn output(maze: &Maze, position: [usize;2]) -> State {
let x = position[0];
let y = position[1];
if maze[y][x] == '+' {
return State::Win;
}
else if maze[y][x] == '!' {
return State::Disqualify;
}
let n = maze[y-1][x];
assert!(y+1<maze.len());
let s = maze[y+1][x];
let w = maze[y][x-1];
assert!(x+1<maze[y].len());
let e = maze[y][x+1];
return State::Continue([n,e,s,w]);
}
fn get_input() -> char {
use std::io;
use std::io::Read;
let mut buffer: [u8;2] = [0;2];
io::stdin().read_exact(&mut buffer).unwrap();
//println!("{:?}", buffer); // to see exactly what the input is
return buffer[0] as char;
}
fn next_position(current_position: [usize;2], direction: char) -> Result<[usize;2],char> {
let mut x = current_position[0];
let mut y = current_position[1];
if direction == 'n' {
y -= 1;
}
else if direction == 'e' {
x += 1;
}
else if direction == 's' {
y += 1;
}
else if direction == 'w' {
x -= 1;
}
else {
return Err(direction);
}
return Ok([x,y]);
}
fn play(maze: &mut Maze) -> (State, usize) {
let mut position: [usize;2];
match get_starting_position(maze) {
Ok(pos) => position = pos,
Err(s) => {
println!("{}",s);
std::process::exit(2);
}
}
let mut moves = 0;
loop {
let state = output(maze, position);
/* uncomment below to view the maze at each step */
//display_maze(&maze, position);
/* ----------------------------------------------*/
match state {
State::Win => {
//println!("You found the cheese");
return(State::Win, moves);
}
State::Disqualify => {
//println!("You were disqualified");
return(State::Disqualify, moves);
}
State::Continue(out) => {
println!("{}{}{}{}",out[0],out[1],out[2],out[3]);
}
}
// only get here with Continue
let input = get_input();
moves += 1;
match next_position(position, input) {
Err(c) => {
println!("Invalid input: {}", c as u8);
return (State::Disqualify, moves);
}
Ok(next_pos) => position = next_pos,
}
}
}
fn main() {
let mut arg_counter = 0;
for argument in std::env::args() {
if arg_counter != 0 {
let mut maze = match argument.as_str(){
"1" => maze_1(),
"2" => maze_2(),
"3" => maze_3(),
"4" => maze_4(),
"5" => maze_5(),
"6" => maze_6(),
_ => {
println!("invalid input: {}, breaking", argument);
break;
}
};
let game_result = play(&mut maze);
println!("0000");
match game_result.0 {
State::Win => println!("WIN"),
State::Disqualify => println!("DISQUALIFY"),
_ => println!("Error"),
}
println!("moves: {}", game_result.1 );
}
arg_counter += 1;
}
}
fn maze_1() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
!O ! ! !#\
!. ! !!!!!!!!!!!!!!!!!! ! !!!!!!#\
!. ! ! ! !#\
!. ! !!!!!!!!!!!!!!!!!!!! ! !! !#\
!. !........... ! !!.+#\
!. !.!!!!!!!!!.!!!!!!!!!!!!!!!.!#\
!.!..! ...............!.!#\
!.!.!! !!!!!!!!!!!!!!!!!!!!!.!.!#\
!.!.!! !!! ! .!.!#\
!.!.!! !!! !!!!!!!!!!!!!!!!.!.!#\
!...!! !!! .!.!#\
! ! !! !!! .!.!#\
! ! !! !!! !!!!!!!!! !!!!!!.!.!#\
! ! !! !!! ! !! ! .!.!#\
! ! !! !!! ! !!!!!!! ! .!.!#\
! ! !! !!! ! !! ! .!.!#\
! ! !! !!! ! !! ! .!.!#\
! ! !! ! ! !! ! .!.!#\
! ! !! ! ! !!!!!! !! ! .!.!#\
! ! !! ! ! ! !! ! ...!#\
! ! !! ! ! ! !! ! !#\
! ! !! ! ! ! !! ! ! !#\
! ! !! ! ! ! !!!!!! ! ! !#\
! ! !! ! ! ! !! ! ! !#\
! ! ! ! !! ! ! !#\
! !!!!!! !!!!!!!! !! ! ! !#\
! ! !! ! ! !#\
! !!!!!!!!!!! !!!! !! ! ! !#\
! ! ! !#\
! !!!!!!!! !!!! ! !#\
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}
fn maze_2() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!#\
! .......!#\
! !!! !.!!!! .!#\
! ! !.!!O!!.!#\
!!! !....! .!#\
! !!!!!!!!!.!#\
! !! ..!#\
! !!!!!!!!!.!!#\
! ..+#\
!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}
fn maze_3() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
! !!!#\
! ! !!! !!!!!!!!!!!!!!!!!! !#\
! ! ! !!! !!! ! !#\
! ! ! !!!!!!!!!!!!!!!! !! !#\
! ! ! !!!! !#\
! !! !!!!!!!!!! !! ! !#\
! ! ! !!!! !!!!! !!! !#\
!! ! ! !!!! ! ! !#\
!! ! ! !!!! !!!!!!!!!!!!!! ! !#\
!! ! ! !!!! ! ! ! !#\
!! ! ! !!!! ! ! !!!! ! ! !#\
!! ! ! !!!! ! ! ! !!! ! ! !#\
! ! ! !!!! ! ! ! !!! ! ! !#\
! ! ! !!!! ! ! !!!!! ! !#\
! ! ! !!!! !!! ! !! ! !!!#\
! ! ! !!! !! ! !!! ! !!!#\
! ! ! ! !! !!!! !! ! !!!#\
! ! !! ! !! ! !! ! !!!#\
! ! ! !! !! !!! ! !!!#\
! !! !!!! !!! !! ! !#\
!! ! !! ! !!! !! !!! !#\
!! ! ! ! ! !#\
!! !!!!!! !! !!!!!!!!!!! !#\
! !!!! !!!!!!!!!!! !#\
! ..........O!!!! !!!!!!!!!!!.+#\
!! .!!!!!! !! !!!!!!!!!!!.!#\
!! .! ! ! ! .!#\
!!..! !! ! !!! !! !!!.!#\
! .!! !!!! !!! !! !...!#\
! .! ! !! !! !!! !.!!!#\
! .! !! ! !! ! !! !.!!!#\
! .! ! ! !! !!!! !! !.!!!#\
! .! ! !!! !! ! !!! !.!!!#\
! .! ! !!!! !!! ! !! !.!!!#\
! .! ! !!!! ! ! !!!!! !...!#\
! .! ! !!!! ! ! ! !!! ! !.!#\
!!.! ! !!!! ! ! ! !!! ! !.!#\
!!.! ! !!!! ! ! !!!! ! !.!#\
!!.! ! !!!! ! ! !.!#\
!!.! ! !!!! !!!!!!!!!!!!!! !.!#\
!!.! ! !!!! ! ! .!#\
!..! ! !!!! !!!!! !!!.!#\
!.!! !!!!!!!!!! !! !.!#\
!.! ! !!!! .!#\
!.! ! !!!!!!!!!!!!!!!! !!.!#\
!.! ! !!! !!! !.!#\
!.! !!! !!!!!!!!!!!!!!!!!!...!#\
!............................!!!#\
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}
fn maze_4() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!!!+!!!!!!!!!!!!!!#\
!................. !!!#\
!.! !!! !!!!!!!!!!!!!!!!!! !#\
!.! ! !!! !!! ! !#\
!.! ! !!!!!!!!!!!!!!!! !! !#\
!.! ! !!!! !#\
!.!! !!!!!!!!!! !! ! !#\
!..! ! !!!! !!!!! !!! !#\
!!.! ! !!!! ! ! !#\
!!.! ! !!!! !!!!!!!!!!!!!! ! !#\
!!.! ! !!!! ! ! ! !#\
!!.! ! !!!! ! ! !!!! ! ! !#\
!!.! ! !!!! ! ! ! !!! ! ! !#\
! .! ! !!!! ! ! ! !!! ! ! !#\
! .! ! !!!! ! ! !!!!! ! !#\
! .! ! !!!! !!! ! !! ! !!!#\
! .! ! !!! !! ! !!! ! !!!#\
! .! ! ! !! !!!! !! ! !!!#\
! .! !! ! !! ! !! ! !!!#\
! .! ! !! !! !!! ! !!!#\
! .!! !!!! !!! !! ! !#\
!!. ! !! ! !!! !! !!! !#\
!!. ! ! ! ! !#\
!!. !!!!!! !! !!!!!!!!!!! !#\
! ........... !!!! !!!!!!!!!!! !#\
! . !!!! !!!!!!!!!!! !#\
!! !!!!!! . !! !!!!!!!!!!! !#\
!! ! ! . ! ! !#\
!! ! !! ! . !!! !! !!! !#\
! !! !!!! . !!! !! ! !#\
! ! ! !!.!! !!! ! !!!#\
! ! !! !.!! ! !! ! !!!#\
! ! ! !.!! !!!! !! ! !!!#\
! ! ! !!!..!! ! !!! ! !!!#\
! ! ! !!!!.!!! ! !! ! !!!#\
! ! ! !!!!.! ! !!!!! ! !#\
! ! ! !!!!.! ! ! !!! ! ! !#\
!! ! ! !!!!.! ! ! !!! ! ! !#\
!! ! ! !!!!.! ! !!!! ! ! !#\
!! ! ! !!!!.! ! ! !#\
!! ! ! !!!!. !!!!!!!!!!!!!! ! !#\
!! ! ! !!!!.....O! ! !#\
! ! ! !!!! !!!!! !!! !#\
! !! !!!!!!!!!! !! ! !#\
! ! ! !!!! !#\
! ! ! !!!!!!!!!!!!!!!! !! !#\
! ! ! !!! !!! ! !#\
! ! !!! !!!!!!!!!!!!!!!!!! !#\
! !!!#\
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}
fn maze_5() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
+......!!!! !!! !!! !!!! !!#\
! .! !! !!!!!#\
! !!!.! !! !!! !!!! !!!!!!!!! !!! !#\
! !!...! !!!!! !! ! !! !! !#\
!!!..!! ! !! ! ! ! !!#\
!! .!!........ !! !!! ! ! ! ! !!#\
!!!. !. ! !. ! !!!!! !! ! ! !! !!!#\
!!!. !. ! !. ! !!!!! ! !! ! !!!#\
!!.. !. ! !.. ! ! ! !! ! ! !!#\
!!.! !.! ! ! .. ! !!!!!! ! ! ! ! !!#\
!!.! !.! ! !! . ! ! ! ! ! ! !!#\
!!.! !.! ! ! . ! !! !! !!!! ! ! ! !!#\
!!.! !.!! ! ! . ! !!! !!!! ! ! !! !!#\
!!.! !. ! ! ! . ! !! ! ! ! ! !!#\
! .!!!. ! ! !!. ! ! ! ! ! ! !#\
! .!!!. ! ! !. ! ! ! ! ! ! !#\
! .! !. ! ! !. ! ! ! ! ! ! !#\
! .! !. ! !! !....!!! ! !! ! ! ! !#\
! .! ..! ! ! ...!!!! ! ! ! ! ! !#\
! .! .! ! !!!!!!.... !!!!!!! ! ! !#\
! .! !!.! !! ! !!!! .! !#\
! .!!!!.! !!!! !!! .! !!!!! !!!!!!!!!!! !#\
! .. !!.! !!! !! !.!! !#\
!!!.. !. ! !!! !..! !!! ! ! !#\
!!! .... ! !!!! ! .! ! !!#\
!!!!!!!!!!!!!!!!!!!!!!! .! !!!!!!!!!!!!!!!!!!!! !!#\
!!! ! .! !!!#\
!! ! !!! !! .! !!#\
!! ! ! !! !!!!!!.! !!!!!! !!#\
!! ! ! !! !!!!!!.! !!!!!!!! ! !!#\
!! ! ! !! !!!!!!!.! !!!!!! !! ! ! !!#\
!! ! ! ! !!!!!!!!.! !!! ! ! ! !!#\
!! ! ! ! !!!!!!!!!.! !!!! ! ! ! ! ! !!#\
!! ! ! ! .! !! ! ! ! ! !!#\
!! !!! ! ! !!!!!! .! ! !! !!#\
!! ! ! ! ! ! !!. ! !!! ! ! !!#\
!! ! ! ! ! ! ! . ! ! !! ! ! !!#\
!! ! ! ! ! ! !! !!. !!! !! ! ! ! !!#\
!! ! ! ! !! ! !!! ! ..... !! ! ! !!#\
!! ! ! ! ! ! !!!!!!! . ! ! !!#\
! ! ! ! ! ! !!! ! .!!!! ! ! !#\
! ! ! ! !! ! ! .! !!.......... !#\
! !! ! ! ! !!!!!!!!! .! !! .! !!!!. !#\
! ! ! ! !! !!! .!!!!! .. ! . !#\
! ! ! !! !!! !!! .......... !!!! . !#\
! ! ! !! !!!! !!!!!!!!!!!! !. !#\
! ! ! !!!!!! O. !#\
! ! !#\
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}
fn maze_6() -> Maze {
let maze_str = "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
! !!!! ....!!! !!! !!!! !!#\
! ! .!!.......... !!!!!#\
! !!! ! !! ...!!! !!!!. !!!!!!!!! !!! !#\
! !! ! !!!!!.. !! !. !! !! !#\
!!! !! !. !! !..... ! ! !!#\
!! !! .. !! !!! . ! ! ! ! !!#\
!!! ! ! ! .! !!!!! . !! ! ! !! !!!#\
!!! ! ! ! .! !!!!!. ! !! ! !!!#\
!! ! ! ! .! ! !. !! ! ! !!#\
!! ! ! ! ! ! . ! !!!!!! ! .. ! ! ! !!#\
!! ! ! ! ! !! . ! ! ! .....! ! ! !!#\
!! ! ! ! ! ! . ! !! !! !!!!.! ! ! !!#\
!! ! ! !! ! ! ..! !!! !!!! .! ! !! !!#\
!! ! ! ! ! ! .! !! ! .! ! ! !!#\
! !!! ! ! !! . ! ! ! .! ! ! !#\
! !!! ! ! ! ..! ! ! . ! ! ! !#\
! ! ! ! ! ! .! ! ! . ! ! ! !#\
! ! ! ! !! ! .!!! ! !! . ! ! ! !#\
! ! ! ! ! ...!!!! ! . ! ! ! ! !#\
! ! ! ! !!!!!!.... !!!!!!! . ! ! !#\
! ! !! ! !! ! !!!! .! . !#\
! !!!! ! !!!! !!! .! !!!!! .!!!!!!!!!!! !#\
! !! ! !!! !! !.!!.......... !#\
!!! ! ! !!! !. !. !!! ! ! !#\
!!! ! !!!! !. !. ! !!#\
!!!!!!!!!!!!!!!!!!!!!!!. !.!!!!!!!!!!!!!!!!!!!! !!#\
!!! ! . !.....................!!!#\
!! ! !!! !! O..... ! ..!!#\
!! ! ! !! !!!!!! ! !!!!!! .!!#\
!! ! ! !! !!!!!! ! !!!!!!!! ! .!!#\
!! ! ! !! !!!!!!! ! !!!!!! !! ! ! .!!#\
!! ! ! ! !!!!!!!! ! !!! ! ! ! .!!#\
!! ! ! ! !!!!!!!!! ! !!!! ! ! ! ! ! .!!#\
!! ! ! ! ! !! ! ! ! ! .!!#\
!! !!! ! ! !!!!!! ! ! !! .!!#\
!! ! ! ! ! ! !! ! !!! ! ! .!!#\
!! ! ! ! ! ! ! ! ! !! ! ! .!!#\
!! ! ! ! ! ! !! !! !!! !! ! ! ! .!!#\
!! ! ! ! !! ! !!! ! !! ! !.!!#\
!! ! ! ! ! ! !!!!!!! ! ! .!!#\
! ! ! ! ! ! !!! ! !!!! ! ! . !#\
! ! ! ! !! ! ! ! !! . !#\
! !! ! ! ! !!!!!!!!! ! !! ! !!!!. !#\
! ! ! ! !! !!! !!!!! ! . !#\
! ! ! !! !!! !!! ! !!!! . !#\
! ! ! !! !!!! !!!!!!!!!!!! !..+#\
! ! ! !!!!!! !#\
! ! ! !#\
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#\
";
match str_to_maze(&maze_str) {
Ok(x) => return x,
Err(i) => std::process::exit(i),
}
}Pour tester le plus grand labyrinthe, remplacez simplement la chaîne de labyrinthe dans la maze_1fonction. Assurez-vous d'ajouter les #\caractères corrects à chaque ligne.
Tester votre entrée
Ce script peut être utilisé pour tester les entrées
#!/bin/bash
mkfifo /tmp/pipe1
mkfifo /tmp/pipe2
for arg in "$@"; do
<path to controller> $arg < /tmp/pipe1 | tee /tmp/pipe2 trascript.txt &
( <path to entry> < /tmp/pipe2 | tee /tmp/pipe1 ) > /dev/null
done
rm /tmp/pipe1
rm /tmp/pipe2Par exemple, mon script ressemble à ceci:
#!/bin/bash
mkfifo /tmp/pipe1
mkfifo /tmp/pipe2
for arg in "$@"; do
./maze/target/release/maze $arg < /tmp/pipe1 | tee /tmp/pipe2 trascript.txt &
( ./maze_test/main < /tmp/pipe2 | tee /tmp/pipe1 ) > /dev/null
done
rm /tmp/pipe1
rm /tmp/pipe2Il est utilisé de la manière suivante:
./script <mazes to test>
Par exemple
./script 1 2 3 4 5 6
Il imprimera tout sur la console ainsi que tout écrire dans un fichier appelé transcript.txt
Afin de développer votre entrée, vous pouvez décommenter le
display_maze(&maze, position)
ligne dans la playfonction. Cela entraînera le contrôleur pour afficher le labyrinthe à chaque étape.
Réponses:
Boundary Finding Bot, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 pas
Ce bot tente de localiser et de suivre les limites du labyrinthe en sachant que le fromage sera toujours situé sur les limites.
Pour ce faire, elle actualise sa vue interne du labyrinthe et construit des candidats actuels pour les murs de délimitation nord, sud, est et ouest.
Une recherche de chemin * est effectuée pour toutes les cellules inexplorées dans ces murs et le chemin le plus court est choisi pour suivre. Cependant, seuls les murs limites candidats qui ne contiennent aucun espace vide peuvent être le "vrai" mur frontière et donc ceux qui contiennent des cellules vides ne sont pas pris en compte pour la recherche de chemin. Les cellules inexplorées dans un chemin reçoivent un score moins souhaitable avec des cellules non explorées consécutives aggravant le caractère indésirable.
Dans cette dernière édition, le bot a désormais un poids négatif pour les cellules déjà visitées. Cela donne une légère amélioration.
Il existe un mécanisme de sélection de mouvement à sécurité intégrée qui garantit qu'un mouvement valide est choisi dans le cas où aucun chemin ne peut être trouvé.
Notez que cette implémentation est assez inefficace et peut prendre plusieurs secondes pour résoudre un labyrinthe dans le pire des cas.
Déterministe. Courir avec
java BoundryFindingBotla source
Python, 132 + 23 + 228 + 218 + 764 + 213 = 1578 pas
Cela suit le chemin le plus court qui traverse des espaces vides connus et des espaces inconnus jusqu'au rectangle englobant du monde connu, jusqu'à ce que le fromage devienne visible.
Déterministe. Exécutez avec
python SCRIPToupython3 SCRIPT(testé en 2.7 et 3.5).la source
MATLAB, 210 + 23 + 394 + 270 + 1272 + 707 = 2876 pas
Cette approche est une modification de mon autre soumission MATLAB . (Ils utilisent cependant exactement le même contrôleur.)
Dans cette approche, la souris suit un chemin possible jusqu'à ce qu'elle trouve une impasse. Ensuite, il revient à l'intersection précédente, où il y avait un chemin qui n'était pas encore exploré. À chaque étape, la souris vérifie cependant s'il y a des zones fermées inexplorées. Au sein de ceux-ci, le fromage ne peut évidemment pas l'être (comme il est toujours à la frontière). Si une telle zone est trouvée, elle est désormais ignorée.
C'est déterministe. Parmi les chemins disponibles, il choisit toujours dans l'ordre
NESW.Comme je ne peux pas compiler de scripts matlab, j'ai traduit le contrôleur en MATLAB. Le "programme" n'est plus qu'une fonction qui accède aux variables globales pour le stockage entre les étapes.
la source
Python 3, 156 octets, 37692 + 715 + 50626 + 27806 + 148596 + 172675 = 438110 pas
Ce n'est pas du golf de code , mais le golf est quand même amusant. Cette étape vers le fromage ou prend le chemin sortant le moins parcouru, similaire à l' idée de mbomb007 (pas entièrement mise en œuvre) , mais avec des liens rompus en allant vers le nom de la dernière direction alphabétique.
Déterministe. Exécutez avec
python3 SCRIPT(testé en 3.5).la source
fgarde une trace des étapes entre les espaces qui ont été utilisées et à quelle fréquence. Par exemple,-f[' ', 'n', 3, 6]est le nombre de fois où nous sommes allés au nord de (3, 5) à (3, 6).PHP 362 + 37 + 1638 + 1508 + 6696 + 1613 = 11854 étapes
Analyse comparative sur le code corrigé:
la source
MATLAB, 212 + 23 + 416 + 300 + 1806 + 757 = 3514 pas
Dans cette approche, la souris suit un chemin possible jusqu'à ce qu'elle trouve une impasse. Ensuite, il revient à l'intersection précédente, où il y avait un chemin qui n'était pas encore exploré. C'est déterministe. Parmi les chemins disponibles, il choisit toujours dans l'ordre
NESW(pasNSFW, comme j'ai toujours été tenté d'écrire =)Comme je ne peux pas compiler de scripts matlab, j'ai traduit le contrôleur en MATLAB. Le "programme" n'est plus qu'une fonction qui accède aux variables globales pour le stockage entre les étapes.
;
la source
Bot simple, Java 1.4+, 176 + 25 + 1118 + 486 + 10944 + 1847 = 14596 étapes
Ce bot compte et enregistre le nombre de pas effectués pour atteindre chaque cellule visitée puis, au moment de décider dans quelle direction se déplacer, choisit la direction qui a le plus petit nombre de pas. En cas d'égalité, choisit la direction dans l'ordre N, E, S, W.
Je n'ai pas installé de rouille, j'ai donc dû implémenter le contrôleur en Java et c'était le bot que j'ai utilisé pour le tester. J'essaierai bientôt un solveur plus intelligent.
Déterministe. Courir avec
java SimpleBotla source