Обновление: есть 6 лабиринтов. Они включены в контроллер. Существует tar.gz из лабиринтов и их .bmp файлов здесь (раздаточные). По этой ссылке также есть утилита для создания лабиринтов (файл maze_4.txt неверен в архиве). На данный момент, пожалуйста, не стесняйтесь запустить свою собственную запись и обновить свой счет. Подробности о том, как это сделать, приведены внизу. Если у вас есть вопросы или проблемы, пожалуйста, пингуйте меня в чате.
Ты мышь. Ты в лабиринте. Найди сыр.
концепция
Вы находитесь в лабиринте, который существует на прямоугольной сетке. Каждое пространство сетки содержит одну из нескольких вещей:
!- непроходимая стенаO- Ты, мышь+- сыр, твоя цель
Пожалуйста, используйте те же символы, чтобы мне не пришлось изменять контроллер.
На каждом ходу вам будут выдаваться плитки, которые находятся на севере, юге, востоке и западе от вашей текущей позиции. Затем вы должны вывести направление, в котором хотите путешествовать. Вы выиграете, когда доберетесь до сыра. Чем меньше шагов, тем лучше.
вход
Вы получите ввод через stdin следующим образом: neswгде каждая буква представляет плитку в этой точке компаса. Например, если текущее состояние выглядит
! <--- Wall
!O <--- You
+ <--- Cheese
тогда вам дадут строку ! +!.
В конце игры, контроллер будет посылать вам строку из четырех нулей: 0000. После получения этой строки ваша программа должна завершиться. Никакой другой ввод данных не будет содержать 0символ.
Пожалуйста, игнорируйте все другие входные данные.
Выход
Вы выводить одну букву n, s, eили w, чтобы указать , в каком направлении вы хотите путешествовать, а затем символ новой строки.
счет
Ваша оценка по каждому тесту - это количество шагов, которое вам нужно, чтобы найти сыр.
Ваш общий балл будет суммой вашего среднего балла за лабиринт в группе лабиринтов разных размеров, каждый из которых уместится в квадрат длиной 50.
Например, если вашему боту требуется 100 ходов, чтобы завершить каждый из 6 лабиринтов, то ваш счет равен 600.
Если ваш бот не является детерминированным, попробуйте каждый лабиринт 10 раз и используйте среднее значение в качестве оценки для этого лабиринта. Ваш окончательный результат будет суммой всех средних.
правила
- Каждый лабиринт поместится внутри квадрата 50x50.
- У каждого лабиринта будет хотя бы один действительный путь от начала до сыра.
- Каждый лабиринт будет полностью замурован, за исключением того, что сыр всегда будет на внешней стенке, так что он по сути служит выходом в лабиринт.
- Если вы столкнетесь с стеной, ваше представление будет дисквалифицировано.
- Если ваше представление займет слишком много времени (как я определил, когда я начну тестирование), оно будет дисквалифицировано. Это в значительной степени для предотвращения бесконечных петель. Мягкий предел будет составлять одну минуту на лабиринт, хотя я оставляю за собой право изменить это в любое время в любом направлении.
- Записи не обязательно должны быть детерминированными, но если вы слишком случайны, вы, вероятно, будете дисквалифицированы вышеупомянутым пунктом.
- В какой-то момент батарея лабиринтов будет выпущена, будущие ответы могут не оптимизироваться к ним, и они могут быть изменены.
Материалы :
Ваша заявка представляет собой полную программу, которая принимает ввод через стандартный ввод и вывод через стандартный вывод. Это важно, потому что представление будет взаимодействовать с контроллером лабиринта. Я не собираюсь запрещать языки, которые не находятся в свободном доступе, но знаю, что кто-то еще должен будет предложить свое время для запуска тестов, если у меня нет доступа к языку.
Пожалуйста, включите инструкции о том, как запустить ваше представление.
Пожалуйста, укажите, является ли ваше представление детерминированным или нет, чтобы я знал, нужно ли мне запускать его несколько раз.
Тестовые лабиринты
В тестовых лабиринтах .персонажи обозначают кратчайший путь к сыру. Они такие же, как (пробел). Они не видны для вашего представления. Контроллер заменяет их пробелами.
!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.! !
! !.!.!! !
!!!.!.!! !
! .!.! !!
!!!... !
!!!!!!!!!!
31x31 тестовый лабиринт. Бесстыдно украден .
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! O...!.......! ! .....!.....! ! ! !
!!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! !
! !...! !.! !.! !.!.! !.! ! ! ! ! ! !
! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! !
! ! !.........! !...!...! ! ! ! ! ! ! ! !
! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! !
! ! ! ! !.....! ! ! ! ! ! ! ! ! !
!!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
! ! ! !.! ! ! ! ! !
! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
! ! ! ! ! !...!.! ! ! ! ! !
! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
! ! ! ! ! !.!...! ! ! ! ! ! ! ! ! !
!!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
! ! ! ! ! !...! ! ! ! ! ! ! ! ! ! !
! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
! ! ! !...! ! ! ! ! ! ! !
!!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
! ! !...! ! ! ! ! ! !
! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
! ! ! ! ! !.! ! ! ! ! ! ! ! ! ! ! !
! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
! ! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
! ! ! ! ! !.......! ! ! ! ! ! ! ! !
! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
! ! ! !...! ! ! ! ! ! ! ! !
!!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
! ! ! ! !.! ! ! ! ! ! !
! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
! ! ! ! ! ! !.......! ! ! ! ! !
! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! !
! ! ! ! ! ! ! !.! ! ! ! ! !
!!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! !
! ! ! ! ! !...! ! ! ! ! ! ! ! !
! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
! ! ! ! !.! ! ! ! ! ! ! ! ! !
!!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! !
! ! ! ! ! !.! ! ! ! ! ! ! !
! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
! ! ! ! ! !.! ! ! ! !
! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
! ! ! ! ! ! ! ! !.....! ! ! ! !...............!
! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.!
! ! ! ! ! ! !...! ! ! !.! !...!
!!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!!
! ! ! ! ! !.......! !...!.....! .! !
! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! !
! ! ! ! ! ! !...........!...!...!.....!...!
! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.!
! ! ! ! ! ! ! ! !.!..... !...!.!
!!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.!
! ! ! ! ! ! ! ! ! !...! !.........!.!
! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.!
! ! ! ! ! ! ! ! ! ! !.!.....! !.!
! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.!
! ! ! ! ! ! ! ! ! !.!...! ! !.!
! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.!
! ! ! ! .....! .!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+!
контроллер
Контроллер в 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),
}
}Чтобы проверить больший лабиринт, просто замените строку лабиринта в maze_1функции. Обязательно добавляйте правильные #\символы в каждую строку.
Тестирование вашей записи
Этот скрипт можно использовать для проверки записей
#!/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/pipe2Например, мой скрипт выглядит так:
#!/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/pipe2Он используется следующим образом:
./script <mazes to test>
Например
./script 1 2 3 4 5 6
Он будет печатать все на консоль, а также записывать все в файл с именем transcript.txt
Для разработки вашей записи вы можете раскомментировать
display_maze(&maze, position)
строка в playфункции. Это заставит контроллер отображать лабиринт на каждом шаге.
Ответы:
Boundary Finding Bot, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 шага
Этот бот пытается найти и следовать границам лабиринта, зная, что сыр всегда будет находиться на границе.
Он делает это, обновляя свой внутренний вид лабиринта и создавая текущих кандидатов на север, юг, восток и запад пограничных стен.
* Нахождение пути выполняется для любых неисследованных клеток в этих стенах, и выбирается кратчайший путь, по которому нужно следовать. Однако только подходящие граничные стены, которые не содержат пробелов, могут быть «истинными» граничными стенками, и, таким образом, те, которые содержат пустые ячейки, не учитываются при поиске пути. Неисследованные клетки в пределах пути получают менее желательный счет с последовательными неизученными клетками, составляющими нежелательность.
В этом последнем редакторе бот теперь имеет отрицательный вес для уже посещенных клеток. Это дает небольшое улучшение.
Существует механизм выбора отказоустойчивого движения, который обеспечивает выбор правильного движения в том случае, если пути не могут быть найдены.
Обратите внимание, что эта реализация довольно неэффективна и может занять много секунд, чтобы решить лабиринт в худшем случае.
Детерминированный. Бежать с
java BoundryFindingBotисточник
Python, 132 + 23 + 228 + 218 + 764 + 213 = 1578 шагов
Это следует по кратчайшему пути, который проходит через известные пустые пространства и неизвестные пространства к ограничивающему прямоугольнику известного мира, пока сыр не станет видимым.
Детерминированный. Запустите с
python SCRIPTилиpython3 SCRIPT(проверено в 2.7 и 3.5).источник
MATLAB, 210 + 23 + 394 + 270 + 1272 + 707 = 2876 шагов
Этот подход является модификацией моего другого представления MATLAB . (Однако они используют один и тот же контроллер.)
При таком подходе мышь следует по возможному пути, пока не найдет тупик. Затем он возвращается к предыдущему перекрестку, где был путь, который еще не был исследован. Однако на каждом шаге мышь проверяет, есть ли закрытые неисследованные области. Внутри этих сыров, очевидно, не может быть (как это всегда на границе). Если такая область найдена, она игнорируется впредь.
Это детерминистично. Из доступных путей он всегда выбирает в порядке
NESW.Поскольку я не могу скомпилировать сценарии Matlab, я перевел контроллер в MATLAB. «Программа» теперь просто функция, которая обращается к глобальным переменным для промежуточного хранения.
источник
Python 3, 156 байтов, 37692 + 715 + 50626 + 27806 + 148596 + 172675 = 438110 шагов
Это не код-гольф , но в любом случае гольф - это весело. Это шаги к сыру или занимает наименее пройденный исходящий путь, аналогичный выбрало идее mbomb007 (не полностью реализованной) , но с разрывом связей, если перейти к алфавитному названию последнего направления.
Детерминированный. Запуск с
python3 SCRIPT(проверено в 3.5).источник
fотслеживает, какие шаги между пробелами использовались и как часто. Например,-f[' ', 'n', 3, 6]это количество раз, когда мы шли на север от (3, 5) до (3, 6).PHP 362 + 37 + 1638 + 1508 + 6696 + 1613 = 11854 шага
Запустил бенчмарк по исправленному коду:
источник
MATLAB, 212 + 23 + 416 + 300 + 1806 + 757 = 3514 шагов
При таком подходе мышь следует по возможному пути, пока не найдет тупик. Затем он возвращается к предыдущему перекрестку, где был путь, который еще не был исследован. Это детерминистично. Из доступных путей он всегда выбирает в порядке
NESW(неNSFW, как мне всегда хотелось написать =)Поскольку я не могу скомпилировать сценарии Matlab, я перевел контроллер в MATLAB. «Программа» теперь просто функция, которая обращается к глобальным переменным для промежуточного хранения.
;
источник
Simple Bot, Java 1.4+, 176 + 25 + 1118 + 486 + 10944 + 1847 = 14596 шагов
Этот бот подсчитывает и записывает количество шагов, предпринятых для достижения каждой посещенной ячейки, а затем, решая, в каком направлении двигаться, выбирает направление с наименьшим количеством шагов. В случае ничьей выбирает направление в N, E, S, W порядке.
У меня не установлена ржавчина, поэтому мне пришлось реализовать контроллер в Java, и это был бот, который я использовал для его тестирования. Я буду пытаться более умный решатель в ближайшее время.
Детерминированный. Бежать с
java SimpleBotисточник