Pembaruan: Ada 6 labirin. Mereka termasuk dalam pengontrol. Ada tar.gz dari labirin dan file .bmp mereka di sini (dropbox). Ada juga utilitas untuk membuat lebih banyak labirin di tautan itu (file maze_4.txt salah dalam arsip). Pada titik ini, silakan jalankan entri Anda sendiri dan perbarui skor Anda. Rincian tentang cara melakukannya termasuk di bagian bawah. Jika Anda memiliki pertanyaan atau masalah, harap ping saya di chat.
Kamu adalah tikus. Anda berada dalam labirin. Temukan keju.
Konsep
Anda berada di labirin yang ada di kotak persegi panjang. Setiap ruang kisi berisi salah satu dari beberapa hal:
!- Dinding yang tidak bisa dilewatiO- Kamu, mouse+- Keju, tujuan Anda
Silakan gunakan karakter yang sama sehingga saya tidak perlu memodifikasi controller.
Pada setiap belokan, Anda akan diberikan ubin yang berada di Utara, Selatan, Timur, dan Barat dari posisi Anda saat ini. Anda kemudian harus menampilkan arah yang ingin Anda tuju. Anda menang saat mendapatkan keju. Lebih sedikit langkah yang lebih baik.
Memasukkan
Anda akan diberikan masukan melalui stdin dengan cara berikut:, di neswmana setiap huruf mewakili ubin pada titik kompas itu. Misalnya, jika keadaan saat ini terlihat seperti
! <--- Wall
!O <--- You
+ <--- Cheese
maka Anda akan diberikan string ! +!.
Pada akhir pertandingan, controller akan mengirimkan serangkaian empat angka nol: 0000. Setelah menerima string ini, program Anda harus berakhir. Tidak ada input lain yang diberikan akan mengandung 0karakter.
Abaikan semua input lainnya.
Keluaran
Anda untuk output satu huruf n, s, e, atauw , untuk menunjukkan arah mana Anda ingin perjalanan, diikuti oleh karakter baris baru.
Mencetak gol
Skor Anda pada setiap tes adalah jumlah langkah yang Anda perlukan untuk menemukan keju.
Skor keseluruhan Anda akan menjadi jumlah skor rata-rata per labirin di seluruh baterai labirin dengan ukuran variabel, yang semuanya akan masuk dalam kuadrat panjang 50.
Misalnya, jika bot Anda bergerak 100 untuk menyelesaikan masing-masing dari 6 labirin, maka skor Anda adalah 600.
Jika bot Anda tidak deterministik, silakan coba setiap labirin 10 kali dan gunakan rata-rata sebagai skor untuk labirin itu. Skor akhir Anda akan menjadi jumlah dari semua rata-rata.
Aturan
- Setiap labirin akan muat di dalam persegi 50x50.
- Setiap labirin akan memiliki setidaknya satu jalur yang valid dari awal hingga keju.
- Setiap labirin akan sepenuhnya ditembok, kecuali keju akan selalu berada di dinding luar sehingga pada dasarnya berfungsi sebagai jalan keluar ke labirin.
- Jika Anda menabrak tembok, kiriman Anda didiskualifikasi.
- Jika pengiriman Anda terlalu lama (seperti yang ditentukan oleh saya, saat saya mulai pengujian), itu akan didiskualifikasi. Ini sebagian besar untuk mencegah loop tak terbatas. Batas lunak akan menjadi satu menit per labirin, meskipun saya berhak untuk mengubah ini kapan saja di kedua arah.
- Entri tidak perlu bersifat deterministik, tetapi jika Anda terlalu acak, kemungkinan Anda akan didiskualifikasi oleh poin di atas.
- Pada titik tertentu, baterai labirin akan dilepaskan, jawaban di masa depan mungkin tidak dioptimalkan untuk mereka, dan mereka dapat berubah.
Pengajuan :
Kiriman Anda adalah program lengkap yang mengambil input melalui stdin dan output melalui stdout. Ini penting karena pengiriman akan berinteraksi dengan pengontrol labirin. Saya tidak akan mencekal bahasa yang tidak tersedia secara bebas, tetapi tahu bahwa orang lain harus menawarkan waktu mereka untuk menjalankan tes jika saya tidak memiliki akses ke bahasa tersebut.
Harap sertakan instruksi tentang cara menjalankan kiriman Anda.
Harap sebutkan apakah kiriman Anda bersifat deterministik atau tidak, sehingga saya tahu apakah saya perlu menjalankannya beberapa kali.
Labirin Uji
Dalam labirin uji, .karakter menguraikan rute terpendek ke keju. Mereka sama dengan karakter (spasi). Mereka tidak terlihat oleh kiriman Anda. Kontroler menggantikannya dengan spasi.
!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.! !
! !.!.!! !
!!!.!.!! !
! .!.! !!
!!!... !
!!!!!!!!!!
Labirin uji 31x31. Dicuri tanpa malu-malu .
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! O...!.......! ! .....!.....! ! ! !
!!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! !
! !...! !.! !.! !.!.! !.! ! ! ! ! ! !
! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! !
! ! !.........! !...!...! ! ! ! ! ! ! ! !
! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! !
! ! ! ! !.....! ! ! ! ! ! ! ! ! !
!!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
! ! ! !.! ! ! ! ! !
! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
! ! ! ! ! !...!.! ! ! ! ! !
! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
! ! ! ! ! !.!...! ! ! ! ! ! ! ! ! !
!!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
! ! ! ! ! !...! ! ! ! ! ! ! ! ! ! !
! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
! ! ! !...! ! ! ! ! ! ! !
!!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
! ! !...! ! ! ! ! ! !
! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
! ! ! ! ! !.! ! ! ! ! ! ! ! ! ! ! !
! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
! ! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
! ! ! ! ! !.......! ! ! ! ! ! ! ! !
! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
! ! ! !...! ! ! ! ! ! ! ! !
!!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
! ! ! ! !.! ! ! ! ! ! !
! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
! ! ! ! ! ! !.......! ! ! ! ! !
! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! !
! ! ! ! ! ! ! !.! ! ! ! ! !
!!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! !
! ! ! ! ! !.! ! ! ! ! ! ! !
! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
! ! ! ! ! !.! ! ! ! !
! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
! ! ! ! ! ! ! ! !.....! ! ! ! !...............!
! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.!
! ! ! ! ! ! !...! ! ! !.! !...!
!!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!!
! ! ! ! ! !.......! !...!.....! .! !
! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! !
! ! ! ! ! ! !...........!...!...!.....!...!
! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.!
! ! ! ! ! ! ! ! !.!..... !...!.!
!!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.!
! ! ! ! ! ! ! ! ! !...! !.........!.!
! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.!
! ! ! ! ! ! ! ! ! ! !.!.....! !.!
! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.!
! ! ! ! ! ! ! ! ! !.!...! ! !.!
! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.!
! ! ! ! .....! .!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+!
Pengendali
Pengontrol ada di Rust (1.11 Nightly)
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),
}
}Untuk menguji labirin yang lebih besar, cukup ganti string labirin di maze_1fungsi. Pastikan untuk menambahkan yang benar#\ karakter yang ke setiap baris.
Menguji entri Anda
Script ini dapat digunakan untuk menguji entri
#!/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/pipe2Misalnya, skrip saya terlihat seperti:
#!/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/pipe2Ini digunakan dengan cara berikut:
./script <mazes to test>
Sebagai contoh
./script 1 2 3 4 5 6
Ini akan mencetak semuanya ke konsol serta menulis semuanya ke file bernama transcript.txt
Untuk tujuan mengembangkan entri Anda, Anda dapat menghapus komentar
display_maze(&maze, position)
baris dalam playfungsi. Ini akan menyebabkan pengontrol untuk menampilkan labirin di setiap langkah.
maze
fewest-operations
Liam
sumber
sumber
Jawaban:
Bot Pencarian Batas, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 langkah
Bot ini berusaha menemukan dan mengikuti batas-batas labirin dengan mengetahui bahwa keju akan selalu berada di perbatasan.
Ini dilakukan dengan memperbarui pandangan internal labirin dan membangun kandidat saat ini untuk dinding batas utara, selatan, timur dan barat.
Penemuan jalur * dilakukan untuk sel yang belum dijelajahi di dinding ini dan jalur terpendek dipilih untuk diikuti. Namun hanya dinding batas kandidat yang tidak mengandung ruang kosong yang dapat menjadi dinding batas "benar" dan dengan demikian dinding yang mengandung sel kosong tidak dipertimbangkan untuk pencarian jalur. Sel yang tidak dijelajahi dalam jalur diberi skor yang kurang diinginkan dengan sel yang tidak dieksplorasi berturut-turut menambah ketidaktertarikan.
Dalam pengeditan terbaru ini, bot sekarang memiliki bobot negatif untuk sel-sel yang sudah dikunjungi. Ini memberikan sedikit peningkatan.
Ada mekanisme pemilihan gerakan gagal yang aman yang memastikan gerakan yang valid dipilih jika tidak ada jalur yang dapat ditemukan.
Perhatikan bahwa implementasi ini sangat tidak efisien dan dapat memakan waktu beberapa detik untuk menyelesaikan masalah yang paling parah.
Deterministik. Jalankan dengan
java BoundryFindingBotsumber
Python, 132 + 23 + 228 + 218 + 764 + 213 = 1578 langkah
Ini mengikuti jalur terpendek yang melewati ruang-ruang kosong yang diketahui dan ruang-ruang yang tidak diketahui menuju persegi panjang pembatas dari dunia yang diketahui, sampai keju menjadi terlihat.
Deterministik. Jalankan dengan
python SCRIPTataupython3 SCRIPT(diuji dalam 2.7 dan 3.5).sumber
MATLAB, 210 + 23 + 394 + 270 + 1272 + 707 = 2876 langkah
Pendekatan ini merupakan modifikasi dari pengajuan MATLAB saya yang lain . (Namun mereka menggunakan controller yang sama persis.)
Dalam pendekatan ini, mouse mengikuti jalur yang mungkin sampai menemukan jalan buntu. Kemudian kembali ke persimpangan sebelumnya, di mana ada jalan yang belum dijelajahi. Di setiap langkah, tetikus di sini akan memeriksa, apakah ada area yang belum dijelajahi yang tertutup. Di dalamnya, keju jelas tidak bisa (karena selalu di perbatasan). Jika daerah seperti itu ditemukan, maka diabaikan sejak saat itu.
Itu deterministik. Dari jalur yang tersedia selalu dipilih dalam urutan
NESW.Karena saya tidak dapat mengkompilasi skrip matlab, saya menerjemahkan controller ke MATLAB. "Program" sekarang hanya fungsi yang mengakses variabel global untuk penyimpanan di antara langkah.
sumber
Python 3, 156 byte, 37692 + 715 + 50626 + 27806 + 148596 + 172675 = 438110 langkah
Ini bukan kode-golf , tetapi golf tetap menyenangkan. Ini langkah ke keju atau mengambil jalan keluar paling sedikit bepergian, mirip dengan ide mbomb007 (tidak sepenuhnya diimplementasikan) , tetapi dengan ikatan rusak dengan pergi ke nama arah terbaru abjad.
Deterministik. Jalankan dengan
python3 SCRIPT(diuji dalam 3,5).sumber
fmelacak langkah-langkah mana di antara spasi yang telah digunakan dan seberapa sering. Sebagai contoh,-f[' ', 'n', 3, 6]adalah berapa kali kita pergi ke utara dari (3, 5) ke (3, 6).PHP 362 + 37 + 1638 + 1508 + 6696 + 1613 = 11854 langkah
Berlakukan patokan pada kode bug-fix:
sumber
MATLAB, 212 + 23 + 416 + 300 + 1806 + 757 = 3514 langkah
Dalam pendekatan ini, mouse mengikuti jalur yang mungkin sampai menemukan jalan buntu. Kemudian kembali ke persimpangan sebelumnya, di mana ada jalan yang belum dijelajahi. Itu deterministik. Dari jalur yang tersedia selalu dipilih dalam urutan
NESW(tidakNSFW, karena saya selalu tergoda untuk menulis =)Karena saya tidak dapat mengkompilasi skrip matlab, saya menerjemahkan controller ke MATLAB. "Program" sekarang hanya fungsi yang mengakses variabel global untuk penyimpanan di antara langkah.
;
sumber
Bot Sederhana, Java 1.4+, 176 + 25 + 1118 + 486 + 10944 + 1847 = 14596 langkah
Bot ini menghitung dan mencatat jumlah langkah yang diambil untuk mencapai setiap sel yang dikunjungi kemudian, ketika memutuskan arah mana yang akan dipindahkan, memilih arah yang memiliki jumlah langkah terendah. Dalam hal seri, pilih arah dalam urutan N, E, S, W.
Saya tidak memiliki karat yang diinstal jadi saya harus mengimplementasikan controller di java dan ini adalah bot yang saya gunakan untuk mengujinya. Saya akan mencoba pemecah yang lebih pintar segera.
Deterministik. Jalankan dengan
java SimpleBotsumber