Update: Es gibt 6 Labyrinthe. Sie sind in der Steuerung enthalten. Es gibt eine tar.gz der Labyrinthe und ihrer .bmp-Dateien hier (Dropbox). Es gibt auch ein Hilfsprogramm, mit dem Sie unter diesem Link mehr Labyrinthe erstellen können (die Datei maze_4.txt ist im Archiv nicht korrekt). Zu diesem Zeitpunkt können Sie Ihren eigenen Eintrag erstellen und Ihre Punktzahl aktualisieren. Details dazu finden Sie unten. Wenn Sie Fragen oder Probleme haben, rufen Sie mich bitte im Chat an.
Du bist eine Maus. Du bist in einem Labyrinth. Finde den Käse.
Konzept
Sie befinden sich in einem Labyrinth, das sich auf einem rechteckigen Raster befindet. Jeder Bereich des Gitters enthält eines von mehreren Dingen:
!- Eine unpassierbare WandO- Du, die Maus+- Der Käse, dein Ziel
Bitte verwenden Sie die gleichen Zeichen, damit ich den Controller nicht ändern muss.
In jedem Zug erhalten Sie die Kacheln, die sich nördlich, südlich, östlich und westlich Ihrer aktuellen Position befinden. Sie müssen dann die Richtung ausgeben, in die Sie fahren möchten. Sie gewinnen, wenn Sie zum Käse kommen. Weniger Schritte sind besser.
Eingang
Sie erhalten eine Eingabe über stdin wie folgt: neswwobei jeder Buchstabe die Kachel an diesem Kompasspunkt darstellt. Zum Beispiel, wenn der aktuelle Zustand so aussieht
! <--- Wall
!O <--- You
+ <--- Cheese
Dann erhalten Sie die Zeichenfolge ! +!.
Am Ende des Spiels, wird die Controller Ihnen eine Reihe von vier Nullen senden: 0000. Nach Erhalt dieser Zeichenfolge sollte Ihr Programm beendet werden. Keine andere Eingabe enthält das 0Zeichen.
Bitte ignorieren Sie alle anderen Eingaben.
Ausgabe
Sie sind in der Ausgabe eines Buchstaben n, s, e, oderw , um anzuzeigen , in welche Richtung Sie reisen möchten, durch eine neue Zeile Zeichen folgt.
Wertung
Ihre Punktzahl bei jedem Test ist die Anzahl der Schritte, die Sie benötigen, um den Käse zu finden.
Ihre Gesamtpunktzahl ist die Summe Ihrer Durchschnittspunktzahl pro Labyrinth über eine Reihe von Labyrinthen variabler Größe, die alle in ein Quadrat mit einer Länge von 50 passen.
Wenn Ihr Bot beispielsweise 100 Züge benötigt, um jedes der 6 Labyrinthe abzuschließen, beträgt Ihre Punktzahl 600.
Wenn Ihr Bot nicht deterministisch ist, versuchen Sie es bitte zehnmal mit jedem Labyrinth und verwenden Sie den Durchschnitt als Punktzahl für dieses Labyrinth. Ihre endgültige Punktzahl ist die Summe aller Durchschnittswerte.
Regeln
- Jedes Labyrinth passt in ein 50x50 Quadrat.
- Jedes Labyrinth hat mindestens einen gültigen Pfad vom Start bis zum Käse.
- Jedes Labyrinth ist vollständig eingemauert, mit der Ausnahme, dass sich der Käse immer an der Außenwand befindet so dass er im Wesentlichen als Ausgang zum Labyrinth dient.
- Wenn Sie auf eine Mauer stoßen, wird Ihr Beitrag disqualifiziert.
- Wenn Ihre Einreichung zu lange dauert (wie von mir festgelegt, während ich mit dem Testen beginne), wird sie disqualifiziert. Dies dient zum großen Teil der Vermeidung von Endlosschleifen. Die weiche Grenze wird eine Minute pro Labyrinth sein, obwohl ich mir das Recht vorhalte, dies jederzeit in beide Richtungen zu ändern.
- Die Einträge müssen nicht deterministisch sein, aber wenn Sie zu zufällig sind, werden Sie wahrscheinlich durch den obigen Punkt disqualifiziert.
- Irgendwann wird die Batterie der Irrgärten freigegeben, zukünftige Antworten werden möglicherweise nicht für sie optimiert und sie können sich ändern.
Einreichungen :
Ihr Beitrag ist ein vollständiges Programm, das Eingaben über stdin und Ausgaben über stdout akzeptiert. Dies ist wichtig, da die Übermittlung mit dem Labyrinth-Controller interagiert. Ich werde keine Sprachen verbieten, die nicht frei verfügbar sind, aber ich weiß, dass jemand anderes seine Zeit anbieten muss, um die Tests durchzuführen, wenn ich keinen Zugriff auf die Sprache habe.
Bitte geben Sie an, wie Ihre Einreichung ausgeführt werden soll.
Bitte geben Sie an, ob Ihre Übermittlung deterministisch ist oder nicht, damit ich weiß, ob ich sie mehrmals ausführen muss.
Testen Sie Labyrinthe
In den Testlabyrinthen .skizzieren die Charaktere den kürzesten Weg zum Käse. Sie sind identisch mit dem (Leer-) Zeichen. Sie sind für Ihren Beitrag nicht sichtbar. Der Controller ersetzt sie durch Leerzeichen.
!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.! !
! !.!.!! !
!!!.!.!! !
! .!.! !!
!!!... !
!!!!!!!!!!
31x31 Test Labyrinth. Schamlos gestohlen .
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! O...!.......! ! .....!.....! ! ! !
!!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! !
! !...! !.! !.! !.!.! !.! ! ! ! ! ! !
! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! !
! ! !.........! !...!...! ! ! ! ! ! ! ! !
! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! !
! ! ! ! !.....! ! ! ! ! ! ! ! ! !
!!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
! ! ! !.! ! ! ! ! !
! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
! ! ! ! ! !...!.! ! ! ! ! !
! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
! ! ! ! ! !.!...! ! ! ! ! ! ! ! ! !
!!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
! ! ! ! ! !...! ! ! ! ! ! ! ! ! ! !
! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
! ! ! !...! ! ! ! ! ! ! !
!!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
! ! !...! ! ! ! ! ! !
! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
! ! ! ! ! !.! ! ! ! ! ! ! ! ! ! ! !
! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
! ! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
! ! ! ! ! !.......! ! ! ! ! ! ! ! !
! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
! ! ! !...! ! ! ! ! ! ! ! !
!!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
! ! ! ! !.! ! ! ! ! ! !
! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
! ! ! ! ! ! !.......! ! ! ! ! !
! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! !
! ! ! ! ! ! ! !.! ! ! ! ! !
!!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! !
! ! ! ! ! !.! ! ! ! ! ! ! !
! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
! ! ! ! ! !.! ! ! ! !
! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
! ! ! ! ! ! ! ! !.....! ! ! ! !...............!
! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.!
! ! ! ! ! ! !...! ! ! !.! !...!
!!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!!
! ! ! ! ! !.......! !...!.....! .! !
! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! !
! ! ! ! ! ! !...........!...!...!.....!...!
! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.!
! ! ! ! ! ! ! ! !.!..... !...!.!
!!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.!
! ! ! ! ! ! ! ! ! !...! !.........!.!
! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.!
! ! ! ! ! ! ! ! ! ! !.!.....! !.!
! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.!
! ! ! ! ! ! ! ! ! !.!...! ! !.!
! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.!
! ! ! ! .....! .!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+!
Regler
Der Controller ist in Rust (1.11 Nächtlich)
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),
}
}Um das größere Labyrinth zu testen, ersetzen Sie einfach die Labyrinthzeichenfolge in der maze_1Funktion. Stellen Sie sicher, dass Sie das richtige anhängen#\ Zeichen an jede Zeile .
Testen Sie Ihren Eintrag
Dieses Skript kann zum Testen von Einträgen verwendet werden
#!/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/pipe2Zum Beispiel sieht mein Skript so aus:
#!/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/pipe2Es wird folgendermaßen verwendet:
./script <mazes to test>
Beispielsweise
./script 1 2 3 4 5 6
Es druckt alles auf die Konsole und schreibt alles in eine Datei mit dem Namen transcript.txt
Zum Entwickeln Ihres Eintrags können Sie das Kommentarzeichen entfernen
display_maze(&maze, position)
Zeile in der playFunktion. Dadurch zeigt der Controller das Labyrinth bei jedem Schritt an.
maze
fewest-operations
Liam
quelle
quelle
Antworten:
Boundary Finding Bot, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 Schritte
Dieser Bot versucht, die Grenzen des Labyrinths zu lokalisieren und ihnen zu folgen, da er weiß, dass sich der Käse immer an der Grenze befindet.
Dazu aktualisiert es seine interne Ansicht des Labyrinths und erstellt aktuelle Kandidaten für die Nord-, Süd-, Ost- und Westgrenzmauern.
Eine * -Pfadsuche wird für alle unerforschten Zellen in diesen Wänden durchgeführt, und der kürzeste Pfad wird ausgewählt, dem zu folgen ist. Jedoch können nur die Kandidaten-Grenzwände, die keine Leerzeichen enthalten, die "wahre" Grenzwand sein, und daher werden diejenigen, die leere Zellen enthalten, nicht für die Wegsuche berücksichtigt. Nicht erforschte Zellen innerhalb eines Pfades erhalten eine weniger wünschenswerte Bewertung, wobei aufeinanderfolgende nicht erforschte Zellen die Unerwünschtheit verstärken.
In dieser letzten Änderung hat der Bot jetzt ein negatives Gewicht für bereits besuchte Zellen. Dies ergibt eine leichte Verbesserung.
Es gibt einen ausfallsicheren Bewegungsmechanismus, der sicherstellt, dass für den Fall, dass keine Pfade gefunden werden können, eine gültige Bewegung ausgewählt wird.
Beachten Sie, dass diese Implementierung sehr ineffizient ist und es im schlimmsten Fall viele Sekunden dauern kann, bis ein Labyrinth gelöst ist.
Deterministisch. Laufen Sie mit
java BoundryFindingBotquelle
Python, 132 + 23 + 228 + 218 + 764 + 213 = 1578 Schritte
Dies folgt dem kürzesten Weg, der durch bekannte leere Räume und unbekannte Räume zum Begrenzungsrechteck der bekannten Welt führt, bis der Käse sichtbar wird.
Deterministisch. Laufen Sie mit
python SCRIPToderpython3 SCRIPT(getestet in 2.7 und 3.5).quelle
MATLAB, 210 + 23 + 394 + 270 + 1272 + 707 = 2876 Schritte
Dieser Ansatz ist eine Modifikation meines anderen MATLAB-Beitrags . (Sie verwenden jedoch genau den gleichen Controller.)
Bei diesem Ansatz folgt die Maus einem möglichen Pfad, bis sie eine Sackgasse findet. Dann kehrt es zur vorherigen Kreuzung zurück, wo es einen Pfad gab, der noch nicht erkundet wurde. Die Maus prüft hier jedoch in jedem Schritt, ob noch unerforschte Bereiche eingeschlossen sind. Darin kann der Käse natürlich nicht sein (da er immer an der Grenze ist). Wenn ein solcher Bereich gefunden wird, wird er von nun an ignoriert.
Es ist deterministisch. Aus den verfügbaren Pfaden wählt es immer in der Reihenfolge
NESW.Da ich keine Matlab-Skripte kompilieren kann, habe ich den Controller in MATLAB übersetzt. Das "Programm" ist jetzt nur eine Funktion, die auf globale Variablen zugreift, um sie zwischen den Schritten zu speichern.
quelle
Python 3, 156 Bytes, 37692 + 715 + 50626 + 27806 + 148596 + 172675 = 438110 Schritte
Das ist kein Code-Golf , aber Golf macht trotzdem Spaß. Dies führt zum Käse oder nimmt den am wenigsten befahrenen ausgehenden Weg, ähnlich der Idee von mbomb007 (nicht vollständig implementiert) , aber mit Unentschieden, indem zum alphabetisch neuesten Richtungsnamen gewechselt wird .
Deterministisch. Laufen Sie mit
python3 SCRIPT(getestet in 3.5).quelle
fwelche Schritte zwischen Leerzeichen wie oft verwendet wurden. Zum Beispiel,-f[' ', 'n', 3, 6]wie oft wir von (3, 5) nach (3, 6) nach Norden gefahren sind.PHP 362 + 37 + 1638 + 1508 + 6696 + 1613 = 11854 Schritte
Ran Benchmark auf Bugfix Code:
quelle
MATLAB, 212 + 23 + 416 + 300 + 1806 + 757 = 3514 Schritte
Bei diesem Ansatz folgt die Maus einem möglichen Pfad, bis sie eine Sackgasse findet. Dann kehrt es zur vorherigen Kreuzung zurück, wo es einen Pfad gab, der noch nicht erkundet wurde. Es ist deterministisch. Aus den verfügbaren Pfaden wählt es immer in der Reihenfolge
NESW(nichtNSFW, da ich immer versucht war zu schreiben =)Da ich keine Matlab-Skripte kompilieren kann, habe ich den Controller in MATLAB übersetzt. Das "Programm" ist jetzt nur eine Funktion, die auf globale Variablen zugreift, um sie zwischen den Schritten zu speichern.
;
quelle
Simple Bot, Java 1.4+, 176 + 25 + 1118 + 486 + 10944 + 1847 = 14596 Schritte
Dieser Bot zählt und zeichnet die Anzahl der Schritte auf, die unternommen wurden, um jede besuchte Zelle zu erreichen, und wählt dann bei der Entscheidung, in welche Richtung bewegt werden soll, die Richtung mit der niedrigsten Schrittanzahl. Wählt im Falle eines Gleichstands die Richtung in der Reihenfolge N, E, S, W.
Ich habe keinen Rost installiert, also musste ich den Controller in Java implementieren und dies war der Bot, mit dem ich ihn getestet habe. Ich werde bald versuchen, einen klügeren Löser zu finden.
Deterministisch. Laufen Sie mit
java SimpleBotquelle