25
\$\begingroup\$

Update: There are 6 mazes. They are included in the controller. There is a tar.gz of the mazes and their .bmp files here (dropbox). There is also a utility for making more mazes at that link (the maze_4.txt file is incorrect in archive). At this point, please feel free to run your own entry and update your score. Details on how to do so are included at the bottom. If you have questions or trouble, please ping me in chat.


You're a mouse. You're in a maze. Find the cheese.

Concept

You are in a maze that exists on a rectangular grid. Each space of the grid contains one of several things:

  • ! - An impassable wall
  • - An empty space, which is traversable
  • O - You, the mouse
  • + - The cheese, your goal

Please use the same characters so that I do not have to modify the controller.

On each turn, you will be given the tiles that are North, South, East, and West of your current position. You must then output the direction that you wish to travel. You win when you get to the cheese. Fewer steps is better.

Input

You will be given input through stdin in the following fashion: nesw, where each letter represents the tile at that compass point. For example, if the current state looks like

  !          <--- Wall
 !O          <--- You
  +          <--- Cheese

then you will be given the string ! +!.

At the end of the game, the controller will send you a string of four zeroes: 0000. Upon receiving this string, your program should terminate. No other input given will contain the 0 character.

Please ignore all other inputs.

Output

You are to output one letter n, s, e, or w, to indicate which direction you want to travel, followed by a new line character.

Scoring

Your score on each test is the number of steps it takes you to find the cheese.

Your overall score will be the sum of your average score per maze across a battery of mazes of variable sizes, all of which will fit inside a square of length 50.

For example, if it takes your bot 100 moves to complete each of the 6 mazes, then your score is 600.

If your bot is not deterministic, please try each maze 10 times and use average as the score for that maze. Your final score will be the sum of all the averages.

Rules

  • Each maze will fit inside a 50x50 square.
  • Each maze will have at least one valid path from start to cheese.
  • Each maze will be entirely walled in, except that the cheese will always be on the outer wall so that it essentially serves as an exit to the maze.
  • If you run into a wall, your submission is disqualified.
  • If your submission takes too long (as determined by me, as I start testing), it will be disqualified. This is in large part to prevent infinite loops. The soft limit will be one minute per maze, although I reserve the right to change this at any time in either direction.
  • Entries need not be deterministic, but if you are too random, you will likely be disqualified by the above point.
  • At some point, the battery of mazes will be released, future answers may not optimize toward them, and they are subject to change.

Submissions:

Your submission is a full program that takes input via stdin and output via stdout. This is important because the submission will be interacting with the maze controller. I'm not going to ban languages that are not freely available, but know that someone else will have to offer their time to run the tests if I do not have access to the language.

Please include instructions on how to run your submission.

Please state whether your submission is deterministic or not, so that I know whether I need to run it multiple times.

Test Mazes

In the test mazes, . characters outline the shortest route to the cheese. They are the same as the (space) character. They are not visible to your submission. The controller replaces them with spaces.

!!!!!!!!+!
!O..!....!
! !.!.! !!
! !.!.!  !
! !.!.!! !
!!!.!.!! !
!  .!.! !!
!!!...   !
!!!!!!!!!!

31x31 test maze. Shamelessly stolen.

 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 ! O...!.......!   !  .....!.....!           !             !   ! 
 !!!!!.!.! !!!.! !!! !.!!!.!.!!!.!!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !...!   !.!     !.! !.!.! !.!       !   !         !   ! ! ! 
 ! !!!!! !!! !.!!!!!!!.! !.!.! !.! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !.........! !...!...!     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!!.!!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !.....!     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! !.!!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       !.!             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!!.! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !...!.!           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!!.!.!.! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       !.!...! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! !.!!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !...!     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!!.! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !...! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! !.!!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !...!       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!!.!!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !...!       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! !.!!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! !.! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! !.! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! !.!     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! !.!!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !.......!       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!!.!!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !...!       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! !.!!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! !.!       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!!.!!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !.......! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!!.! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     !.!       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!!.! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !...! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! !.!!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! !.! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! !.! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! !.!   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! !.!!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       !.!           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!!.! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !.....!   !   !     ! !...............! 
 ! ! !!! !!! ! !!!!! !!! !.!!!!! ! ! ! !!!!!!! !.!!!!!!!!!!!!!.! 
 ! !   !   ! !   !       !...!   !   !         !.!         !...! 
 !!!!! !!! ! !!! ! !!!!!!!!!.!!!!!!! !!!!!!!!!!!.!!!!! !!!!!.!!! 
 !     !   !   !   !       !.......!       !...!.....!      .! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!!.!!!!!!!!!.!.!!!!!.!!!!!!!.! ! 
 !           !     ! !   !   !   !...........!...!...!.....!...! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!!.!.!!!.!!!.!!!.! 
 ! !     !       ! !     !     !     !         !.!.....  !...!.! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!!.! !!!!!!!!!.!.! 
 !   !     !   !   !   ! !       ! !         !...! !.........!.! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! !.!!!!!.!!!!!!!!!.! 
 !       !   !   ! !   !         !   ! !   ! !.!.....!       !.! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! !.!.!!!!! !!!!! !.! 
 ! !     !           !         ! ! ! !   !   !.!...!   !     !.! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!!.!!!.! !!!!!!!!!.! 
 ! !                     !         !          .....!          .! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!+! 

Controller

The controller is in 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),
    }
}

To test the larger maze, simply replace the maze string in the maze_1 function. Make sure to append the correct #\ characters to each line.

Testing your entry

This script can be used to test entries

#!/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

For example, my script looks like:

#!/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

It is used in the following way:

./script <mazes to test>

For example

./script 1 2 3 4 5 6

It will print everything to the console as well as writing everything to a file called transcript.txt

For the purpose of developing your entry, you can uncomment the

display_maze(&maze, position)

line in the play function. This will cause the controller to display the maze at each step.

\$\endgroup\$
  • 8
    \$\begingroup\$ So the walls are made of mouse traps. Got it. \$\endgroup\$ – mbomb007 Jun 22 '16 at 18:22
  • 2
    \$\begingroup\$ @JuliePelletier I don't think we need deadlines, we can independently run the programs. Most contests here are open ended. \$\endgroup\$ – flawr Jun 22 '16 at 21:49
  • 1
    \$\begingroup\$ @Liam I see no point in withholding the test battery, as optimizing for the test cases woud considered a standard loophole and therefore not allowed anyway. \$\endgroup\$ – flawr Jun 23 '16 at 15:54
  • 1
    \$\begingroup\$ @JuliePelletier Yeah, I'm going to try to make this as easy as possible \$\endgroup\$ – Liam Jun 23 '16 at 21:56
  • 1
    \$\begingroup\$ @JuliePelletier It is done. \$\endgroup\$ – Liam Jun 23 '16 at 22:55
4
\$\begingroup\$

Boundary Finding Bot, Java 1.5+, 124 + 37 + 206 + 324 + 248 + 223 = 1172 steps

enter image description here

This bot attempts to locate and follow the boundaries of the maze knowing that the cheese will always be located on the boundary.

It does this by updating its internal view of the maze and constructing current candidates for the north, south, east and west boundary walls.

A* path finding is performed for any unexplored cells in these walls and the shortest path is chosen to follow. However only the candidate boundary walls that do not contain any blank spaces are able to be the "true" boundary wall and thus those that do contain blank cells are not considered for path finding. Unexplored cells within a path are given less desirable score with consecutive unexplored cells compounding the undesirability.

In this latest edit, the bot now has a negative weight to cells already visited. This gives a slight improvement.

A fail safe movement selection mechanism exists that ensures valid movement is chosen in the event that no paths are able to be found.

Note that this implementation is quite inefficient and can take many seconds to solve a maze in the worst case.

Deterministic. Run with java BoundryFindingBot

import java.io.IOException;
import java.io.InputStream;

public class BoundryFindingBot {
    private static final char[] DIRECTION = {'n','e','s','w'};
    private static final int MAP_SIZE = 102;
    private static final int PATH_FINDING_MAX_STEPS = 50000;
    private static final int[][] offsets = new int[][]{{0,-1},{1,0},{0,1},{-1,0}};

    public static void main(String[] args) throws Exception
    {
        char[][] map = new char[MAP_SIZE][MAP_SIZE];
        int[][] visitCount = new int[MAP_SIZE][MAP_SIZE];
        int mx=MAP_SIZE/2-1, my=MAP_SIZE/2-1;
        int direction=0;

        String line=readLine(System.in);
        out:
        while (line!=null && !"0000".equals(line))
        {
            // update map with new information
            for (int i=0;i<4;i++)
            {
                map[mx+offsets[i][0]][my+offsets[i][1]] = line.charAt(i);

                // immediately move toward cheese if found.
                if (line.charAt(i) == '+')
                {
                    System.out.println(DIRECTION[i]);
                    break out;
                }
            }

            // determine the current boundary walls information
            int currentNorthWallY=-1,currentSouthWallY=-1,currentWestWallX=-1,currentEastWallX=-1;
            boolean currentNorthWallHasBlanks=false,currentSouthWallHasBlanks=false,currentEastWallHasBlanks=false,currentWestWallHasBlanks=false;
            for (int y=0;y<MAP_SIZE;y++)
            {
                for (int x=0;x<MAP_SIZE;x++)
                {
                    if (map[x][y]!=0)
                    {
                        if (currentNorthWallY > -1)
                        {
                            if (currentSouthWallY !=y)
                            {
                                currentSouthWallHasBlanks = false;
                            }
                            currentSouthWallY=y;
                            currentSouthWallHasBlanks|=map[x][y]==' ';
                        }
                        else
                        {
                            currentNorthWallY=y;
                        }

                        if (currentNorthWallY == y)
                        {
                            currentNorthWallHasBlanks|=map[x][y]==' ';
                        }

                    }
                }
            }
            for (int x=0;x<MAP_SIZE;x++)
            {
                for (int y=0;y<MAP_SIZE;y++)
                {
                    if (map[x][y]!=0)
                    {

                        if (currentWestWallX > -1)
                        {
                            if (currentEastWallX !=x)
                            {
                                currentEastWallHasBlanks = false;
                            }
                            currentEastWallX=x;
                            currentEastWallHasBlanks|=map[x][y]==' ';
                        }
                        else
                        {
                            currentWestWallX=x;
                        }

                        if (currentWestWallX == x)
                        {
                            currentWestWallHasBlanks|=map[x][y]==' ';
                        }

                    }
                }
            }

            int closestUnvisitedWallCellResult =0xFFFFFF; 

            // attempt to find paths to undiscovered cells in the current north wall, setting the shortest path if shortest of any path
            if (!currentNorthWallHasBlanks)
            {
                for (int x=currentWestWallX;x<=currentEastWallX;x++)
                {
                    if (map[x][currentNorthWallY] == 0)
                    {
                        int result = pathFind(mx, my, x, currentNorthWallY, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current south wall, setting the shortest path if shortest of any path
            if (!currentSouthWallHasBlanks)
            {
                for (int x=currentWestWallX;x<=currentEastWallX;x++)
                {
                    if (map[x][currentSouthWallY] == 0)
                    {
                        int result = pathFind(mx, my, x, currentSouthWallY, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current east wall, setting the shortest path if shortest of any path
            if (!currentEastWallHasBlanks)
            {
                for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
                {
                    if (map[currentEastWallX][y] == 0)
                    {
                        int result = pathFind(mx, my, currentEastWallX, y, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }

                }
            }

            // attempt to find paths to undiscovered cells in the current west wall, setting the shortest path if shortest of any path
            if (!currentWestWallHasBlanks)
            {
                for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
                {
                    if (map[currentWestWallX][y] == 0 )
                    {
                        int result = pathFind(mx, my, currentWestWallX, y, map,visitCount,currentWestWallX,currentNorthWallY,currentEastWallX,currentSouthWallY);
                        if ((result &0xFFFFFF) <(closestUnvisitedWallCellResult &0xFFFFFF))
                        {
                            closestUnvisitedWallCellResult = result;
                        }
                    }
                }
            }

            // fail-safe if we are unable to find a path to a wall (i.e. initial game frame or all current boundary walls are known to have blanks and thus
            // not wall to head for. Simply tries to go north if possible or failing that try to head east, south, west consecutively
            if (closestUnvisitedWallCellResult == 0xFFFFFF)
            {
                for (int i=0;i<4;i++)
                {
                    if (map[mx+offsets[i][0]][my+offsets[i][1]] == ' ')
                    {
                        direction = i;
                        break;
                    }
                }
            }
            else
            {
                direction = closestUnvisitedWallCellResult >> 24;
            }

            mx +=offsets[direction][0];
            my +=offsets[direction][1];
            visitCount[mx][my]+=5;

            System.out.println(DIRECTION[direction]);

//// uncomment to bot's view of maze solving
//          System.err.println();
//          for (int y=currentNorthWallY;y<=currentSouthWallY;y++)
//          {
//              for (int x=currentWestWallX;x<=currentEastWallX;x++)
//              {
//                  if (x==mx && y==my)
//                  {
//                      System.err.print("O");
//                  }
//                  else
//                  {
//                      System.err.print(map[x][y]);
//                  }
//              }
//              System.err.println();
//          }
            line=readLine(System.in);
        }
        System.err.println("Exited");
    }

/**
 * returns a result that is the combination of movement direction and path length of a path found from the given start position to the target
 * position for cells within the given bounding box. Only empty cells and unexplored cells are traversable. Sequential cells of unexplored cells 
 * are given increasing magnitude negative score to reduce desirability.
 */
static int pathFind(int startX, int startY, int targetX,int targetY,char[][] map,int[][] visitCount,int boundMinX,int boundMinY,int boundMaxX,int boundMaxY)
{
    // A*
    if (!(startX==targetX && startY==targetY))
    {

        int[] tileX = new int[PATH_FINDING_MAX_STEPS];
        int[] tileY = new int[PATH_FINDING_MAX_STEPS];
         int[] fscore = new int[PATH_FINDING_MAX_STEPS];
         int[] gscore = new int[PATH_FINDING_MAX_STEPS];
         int[] openList = new int[PATH_FINDING_MAX_STEPS];
         int[] tileParent = new int[PATH_FINDING_MAX_STEPS];
         int[] unexploredCellRun = new int[PATH_FINDING_MAX_STEPS];
         int[][] tileIsClosed = new int[MAP_SIZE][MAP_SIZE];
         int currentIndex = -1;     

        int openListSize=1;
        int tileId=1;

        tileX[0]=targetX;
        tileY[0]=targetY;
        fscore[0]=1;
        gscore[0]=1;



        do
        {
          int currentBestIndex=-1;
          int currentBestScore=Integer.MAX_VALUE;
          //  Look for the lowest F cost square on the open list
          for (int ii=0;ii<openListSize;ii++)
          {
            if (fscore[openList[ii]]<currentBestScore)
            {
              currentBestScore=fscore[openList[ii]];
              currentBestIndex=ii;
            }
          }
          if (currentBestIndex==-1)
          {
            break;
          }
          currentIndex=openList[currentBestIndex];
          int currentTileX=tileX[currentIndex];
          int currentTileY=tileY[currentIndex];

          // found path
          if (startX==currentTileX && startY==currentTileY)
          {
            break;
          }

          // if not in closed list
          if (tileIsClosed[currentTileX][currentTileY]==0)
          {
                // Switch it to the closed list.
                tileIsClosed[currentTileX][currentTileY]=1;
                // remove from openlist
                openList[currentBestIndex]=openList[--openListSize];   

                // add neigbours to the open list if necessary
                for (int i=0;i<4;i++)
                {

                        int surroundingCurrentTileX=currentTileX+offsets[i][0];
                        int surroundingCurrentTileY=currentTileY+offsets[i][1];
                        if (surroundingCurrentTileX>=boundMinX-1 && surroundingCurrentTileX<=boundMaxX+1 &&
                            surroundingCurrentTileY>=boundMinY-1 && surroundingCurrentTileY<=boundMaxY+1 )
                        {
                          tileX[tileId]=surroundingCurrentTileX;
                          tileY[tileId]=surroundingCurrentTileY;
                          if (map[surroundingCurrentTileX][surroundingCurrentTileY]==0)
                          {
                              unexploredCellRun[tileId]=0;
                          }
                          else if (map[surroundingCurrentTileX][surroundingCurrentTileY]=='!')
                          {
                              continue;
                          }
                          else
                          {
                              unexploredCellRun[tileId]=unexploredCellRun[currentIndex]+1;
                          }
                          int surroundingCurrentGscore=gscore[currentIndex]+visitCount[surroundingCurrentTileX][surroundingCurrentTileY]+1+((int) (unexploredCellRun[tileId]*10));
                          gscore[tileId]=surroundingCurrentGscore;
                          fscore[tileId]=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          tileParent[tileId]=currentIndex;
                          openList[openListSize++]=tileId++;
                     }
                }
          }
          else
          {
          // remove from openlist
          openList[currentBestIndex]=openList[--openListSize];    
          }
        } while(true);

        if (tileX[tileParent[currentIndex]]-startX<0) return (3 <<24) + currentIndex;
        else if (tileX[tileParent[currentIndex]]-startX>0) return (1 <<24) + currentIndex;
        else if (tileY[tileParent[currentIndex]]-startY<0) return (0 <<24) + currentIndex;
        else if (tileY[tileParent[currentIndex]]-startY>0) return (2 <<24) + currentIndex;
    }
    throw new RuntimeException("Path finding failed");
 }

    /**
     * Reads a line of text from the input stream. Blocks until a new line character is read.
     * NOTE: This method should be used in favor of BufferedReader.readLine(...) as BufferedReader buffers data before performing
     * text line tokenization. This means that BufferedReader.readLine() will block until many game frames have been received. 
     * @param in a InputStream, nominally System.in
     * @return a line of text or null if end of stream.
     * @throws IOException
     */
    private static String readLine(InputStream in) throws IOException
    {
       StringBuilder sb = new StringBuilder();
       int readByte = in.read();
       while (readByte>-1 && readByte!= '\n')
       {
          sb.append((char) readByte);
          readByte = in.read();
       }
       return readByte==-1?null:sb.toString();
    }

}
\$\endgroup\$
3
\$\begingroup\$

Python, 132 + 23 + 228 + 218 + 764 + 213 = 1578 steps

This follows the shortest path that goes through known empty spaces and unknown spaces to the bounding rectangle of the known world, until the cheese becomes visible.

Deterministic. Run with python SCRIPT or python3 SCRIPT (tested in 2.7 and 3.5).

import collections, sys

def neighbors(p):
    x, y = p
    return [("n", (x, y + 1)), ("e", (x + 1, y)), ("s", (x, y - 1)), ("w", (x - 1, y))]

ne = sw = loc = 0, 0
maze = {loc: ' '}

while True:
    cells = sys.stdin.readline()
    if cells == '0000\n':
        break
    for (dir1, loc1), cell in zip(neighbors(loc), cells):
        maze[loc1] = cell
        if cell == ' ':
            ne = tuple(map(max, loc1, ne))
            sw = tuple(map(min, loc1, sw))
    visited = {loc}
    queue = collections.deque()
    for dir1, loc1 in neighbors(loc):
        visited.add(loc1)
        queue.append((dir1, loc1, loc1))
    while True:
        dir1, loc1, loc2 = queue.popleft()
        if maze.get(loc2, ' ') == ' ':
            if loc2 not in maze and \
               (any(a >= b for a, b in zip(loc2, ne)) or
                any(a <= b for a, b in zip(loc2, sw))):
                break
            for dir3, loc3 in neighbors(loc2):
                if loc3 not in visited:
                    visited.add(loc3)
                    queue.append((dir1, loc1, loc3))
        elif maze[loc2] == '+':
            break
    sys.stdout.write(dir1 + "\n")
    sys.stdout.flush()
    loc = loc1
\$\endgroup\$
2
\$\begingroup\$

MATLAB, 210 + 23 + 394 + 270 + 1272 + 707 = 2876 steps

This approach is a modification of my other MATLAB submission. (They use however the exact same controller.)

In this approach, the mouse follows a possible path until it finds a dead end. Then it returns to the previous intersection, where there was a path that was not yet explored. In every step, the mouse does here however check, whether there are enclosed unexplored areas. Within these, the cheese can obviously not be (as it is always on the border). If such an area is found, it is ignored henceforth.

It is deterministic. From the available paths it always chooses in the order NESW.

As I cannot compile matlab scripts, I translated the controller to MATLAB. The "program" is now just a function that accesses global variables for in-between-step-storage.

function find_the_cheese_controller()
clc;clear;
    global State;
    clearvars -global State;
    %uncomment the maze you want to test
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!O !                    !      !';'!. ! !!!!!!!!!!!!!!!!!! ! !!!!!!';'!. !                    ! !    !';'!. ! !!!!!!!!!!!!!!!!!!!! ! !! !';'!. !...........           ! !!.+';'!. !.!!!!!!!!!.!!!!!!!!!!!!!!!.!';'!.!..!        ...............!.!';'!.!.!! !!!!!!!!!!!!!!!!!!!!!.!.!';'!.!.!! !!!  !               .!.!';'!.!.!! !!!  !!!!!!!!!!!!!!!!.!.!';'!...!! !!!                  .!.!';'! ! !! !!!                  .!.!';'! ! !! !!!  !!!!!!!!! !!!!!!.!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !! !!!  ! !!!!!!! !     .!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !!   !  !      !! !     .!.!';'! ! !! ! !  !!!!!! !! !     .!.!';'! ! !! ! !  !      !! !     ...!';'! ! !! ! !  !      !! !        !';'! ! !! ! !  !      !! !      ! !';'! ! !! ! !  !  !!!!!! !      ! !';'! ! !! ! !  !      !! !      ! !';'! !    !    !      !! !      ! !';'! !!!!!!  !!!!!!!! !! !      ! !';'!                ! !! !      ! !';'! !!!!!!!!!!! !!!! !! !      ! !';'!                     !      ! !';'! !!!!!!!! !!!!       !        !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!';'!      .......!';'! !!! !.!!!! .!';'!   ! !.!!O!!.!';'!!!   !....! .!';'!   !!!!!!!!!.!';'! !!        ..!';'!  !!!!!!!!!.!!';'!           ..+';'!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!                            !!!';'! !  !!!  !!!!!!!!!!!!!!!!!!   !';'! !  ! !!!              !!!  ! !';'! !  ! !!!!!!!!!!!!!!!!     !! !';'! !  !                  !!!!   !';'! !! !!!!!!!!!!        !!    ! !';'!  ! !        !!!! !!!!!   !!! !';'!! ! ! !!!!      !         !   !';'!! ! ! !!!!   !!!!!!!!!!!!!! ! !';'!! ! ! !!!! ! !              ! !';'!! ! ! !!!! ! ! !!!!       ! ! !';'!! ! ! !!!! ! ! !   !!!    ! ! !';'!  ! ! !!!! ! ! !     !!!  ! ! !';'!  ! ! !!!! ! ! !!!!!      !   !';'!  ! ! !!!! !!! !   !!     ! !!!';'!  ! !  !!!  !! !    !!!   ! !!!';'!  ! !     ! !! !!!!   !!  ! !!!';'!  ! !!    ! !! !  !!      ! !!!';'!  !  !   !! !!     !!!    ! !!!';'!  !! !!!!     !!!    !!   !   !';'!!  ! !! !       !!!   !!  !!! !';'!!  !    !    !    !           !';'!!  !!!!!!    !!   !!!!!!!!!!! !';'!             !!!! !!!!!!!!!!! !';'!  ..........O!!!! !!!!!!!!!!!.+';'!! .!!!!!!    !!   !!!!!!!!!!!.!';'!! .!    !    !    !          .!';'!!..! !! !       !!!   !!  !!!.!';'! .!! !!!!     !!!    !!   !...!';'! .!  !   !! !!     !!!    !.!!!';'! .! !!    ! !! !  !!      !.!!!';'! .! !     ! !! !!!!   !!  !.!!!';'! .! !  !!!  !! !    !!!   !.!!!';'! .! ! !!!! !!! !   !!     !.!!!';'! .! ! !!!! ! ! !!!!!      !...!';'! .! ! !!!! ! ! !     !!!  ! !.!';'!!.! ! !!!! ! ! !   !!!    ! !.!';'!!.! ! !!!! ! ! !!!!       ! !.!';'!!.! ! !!!! ! !              !.!';'!!.! ! !!!!   !!!!!!!!!!!!!! !.!';'!!.! ! !!!!      !         !  .!';'!..! !        !!!! !!!!!   !!!.!';'!.!! !!!!!!!!!!        !!    !.!';'!.!  !                  !!!!  .!';'!.!  ! !!!!!!!!!!!!!!!!     !!.!';'!.!  ! !!!              !!!  !.!';'!.!  !!!  !!!!!!!!!!!!!!!!!!...!';'!............................!!!';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!+!!!!!!!!!!!!!!';'!.................           !!!';'!.!  !!!  !!!!!!!!!!!!!!!!!!   !';'!.!  ! !!!              !!!  ! !';'!.!  ! !!!!!!!!!!!!!!!!     !! !';'!.!  !                  !!!!   !';'!.!! !!!!!!!!!!        !!    ! !';'!..! !        !!!! !!!!!   !!! !';'!!.! ! !!!!      !         !   !';'!!.! ! !!!!   !!!!!!!!!!!!!! ! !';'!!.! ! !!!! ! !              ! !';'!!.! ! !!!! ! ! !!!!       ! ! !';'!!.! ! !!!! ! ! !   !!!    ! ! !';'! .! ! !!!! ! ! !     !!!  ! ! !';'! .! ! !!!! ! ! !!!!!      !   !';'! .! ! !!!! !!! !   !!     ! !!!';'! .! !  !!!  !! !    !!!   ! !!!';'! .! !     ! !! !!!!   !!  ! !!!';'! .! !!    ! !! !  !!      ! !!!';'! .!  !   !! !!     !!!    ! !!!';'! .!! !!!!     !!!    !!   !   !';'!!. ! !! !       !!!   !!  !!! !';'!!. !    !    !    !           !';'!!. !!!!!!    !!   !!!!!!!!!!! !';'! ........... !!!! !!!!!!!!!!! !';'!           . !!!! !!!!!!!!!!! !';'!!  !!!!!!  . !!   !!!!!!!!!!! !';'!!  !    !  . !    !           !';'!!  ! !! !  .    !!!   !!  !!! !';'!  !! !!!!  .  !!!    !!   !   !';'!  !  !   !!.!!     !!!    ! !!!';'!  ! !!    !.!! !  !!      ! !!!';'!  ! !     !.!! !!!!   !!  ! !!!';'!  ! !  !!!..!! !    !!!   ! !!!';'!  ! ! !!!!.!!! !   !!     ! !!!';'!  ! ! !!!!.! ! !!!!!      !   !';'!  ! ! !!!!.! ! !     !!!  ! ! !';'!! ! ! !!!!.! ! !   !!!    ! ! !';'!! ! ! !!!!.! ! !!!!       ! ! !';'!! ! ! !!!!.! !              ! !';'!! ! ! !!!!.  !!!!!!!!!!!!!! ! !';'!! ! ! !!!!.....O!         !   !';'!  ! !        !!!! !!!!!   !!! !';'! !! !!!!!!!!!!        !!    ! !';'! !  !                  !!!!   !';'! !  ! !!!!!!!!!!!!!!!!     !! !';'! !  ! !!!              !!!  ! !';'! !  !!!  !!!!!!!!!!!!!!!!!!   !';'!                            !!!';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'+......!!!!       !!!        !!!       !!!!     !!';'!     .!       !!                            !!!!!';'!  !!!.! !!      !!!  !!!!  !!!!!!!!!      !!!   !';'! !!...!   !!!!!   !!    !          !!    !!     !';'!!!..!!         !    !!  !           !    !     !!';'!! .!!........        !! !!!     !    !   !  !  !!';'!!!. !.  !  !.   !      !!!!!    !!   !   ! !! !!!';'!!!. !.  !  !.   !       !!!!!    !   !!    !  !!!';'!!.. !.  !  !..  !        !  !    !!   !    !   !!';'!!.! !.!  ! ! ..  ! !!!!!!  !      !   !    !   !!';'!!.! !.!  ! !! .  ! !      !        !  !    !   !!';'!!.! !.!  !  ! .  ! !!   !!    !!!! !  !    !   !!';'!!.! !.!! !  ! .  !  !!!   !!!!     !  !    !!  !!';'!!.! !. ! !  ! .  !    !!        !  !   !    !  !!';'! .!!!. ! !  !!.   !    !        !  !   !    !   !';'! .!!!. ! !   !.   !     !       !   !  !    !   !';'! .! !. ! !   !.   !     !       !   !   !   !   !';'! .! !. ! !!  !....!!!   !      !!   !     ! !   !';'! .!  ..!  !  !   ...!!!!       !    !     ! ! ! !';'! .!   .!  !  !!!!!!.... !!!!!!!             ! ! !';'! .! !!.!  !! !  !!!!  .!                        !';'! .!!!!.!   !!!! !!!   .!   !!!!!   !!!!!!!!!!!  !';'! .. !!.!    !!!  !!  !.!!                       !';'!!!.. !. !   !!!      !..!        !!!   !   !    !';'!!! .... !  !!!!      ! .!        !             !!';'!!!!!!!!!!!!!!!!!!!!!!! .! !!!!!!!!!!!!!!!!!!!! !!';'!!!  !                  .!                     !!!';'!!   !   !!!  !!        .!                      !!';'!!   !  !     !!  !!!!!!.!  !!!!!!              !!';'!!   !  !    !!   !!!!!!.! !!!!!!!!          !  !!';'!!  !   !   !!   !!!!!!!.! !!!!!! !!   !  !     !!';'!!  !   !   !   !!!!!!!!.! !!!  !  !   !        !!';'!!  !   !   !  !!!!!!!!!.! !!!! !   !  !  !  !  !!';'!!  !   !   !           .!  !!  !   !  !     !  !!';'!! !!!  !   !   !!!!!!  .!      !    !!         !!';'!! ! !   !  !   !     !!. !    !!!    !    !    !!';'!! ! !   !  !   ! !     .  !   ! !!    !     !  !!';'!! ! !   !  !   ! !!  !!.   !!!   !!   !   ! !  !!';'!! ! !   !  !!  ! !!! ! .....     !!   !      ! !!';'!! ! !   !   !  ! !!!!!!!   .     !    !        !!';'!  ! !   !   !  !  !!!  !   .!!!!     !  !       !';'!  ! !   !   !! !       !   .!      !!.......... !';'! !! !   !    !  !!!!!!!!!  .!    !!  .!   !!!!. !';'! !  !   !    !!       !!!  .!!!!!   ..   !    . !';'! !  !    !!   !!!     !!!  .......... !!!!    . !';'! !  !     !!     !!!!      !!!!!!!!!!!!      !. !';'! !         !         !!!!!!                  O. !';'!           !                                    !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!      !!!!   ....!!!        !!!       !!!!     !!';'!      !      .!!..........                  !!!!!';'!  !!! ! !!   ...!!!  !!!!. !!!!!!!!!      !!!   !';'! !!   !   !!!!!.. !!    !.         !!    !!     !';'!!!  !!         !.   !!  !.....      !    !     !!';'!!  !!          ..    !! !!!  .  !    !   !  !  !!';'!!!  !   !  !   .!      !!!!! .  !!   !   ! !! !!!';'!!!  !   !  !   .!       !!!!!.   !   !!    !  !!!';'!!   !   !  !   .!        !  !.   !!   !    !   !!';'!! ! ! !  ! !   . ! !!!!!!  ! ..   !   !    !   !!';'!! ! ! !  ! !!  . ! !      !   .....!  !    !   !!';'!! ! ! !  !  !  . ! !!   !!    !!!!.!  !    !   !!';'!! ! ! !! !  !  ..!  !!!   !!!!    .!  !    !!  !!';'!! ! !  ! !  !   .!    !!        ! .!   !    !  !!';'!  !!!  ! !  !!  . !    !        ! .!   !    !   !';'!  !!!  ! !   !  ..!     !       ! . !  !    !   !';'!  ! !  ! !   !   .!     !       ! . !   !   !   !';'!  ! !  ! !!  !   .!!!   !      !! . !     ! !   !';'!  !    !  !  !   ...!!!!       !  . !     ! ! ! !';'!  !    !  !  !!!!!!.... !!!!!!!   .         ! ! !';'!  ! !! !  !! !  !!!!  .!          .             !';'!  !!!! !   !!!! !!!   .!   !!!!!  .!!!!!!!!!!!  !';'!    !! !    !!!  !!  !.!!..........             !';'!!!   !  !   !!!      !. !.       !!!   !   !    !';'!!!      !  !!!!      !. !.       !             !!';'!!!!!!!!!!!!!!!!!!!!!!!. !.!!!!!!!!!!!!!!!!!!!! !!';'!!!  !                 . !.....................!!!';'!!   !   !!!  !!  O..... !                    ..!!';'!!   !  !     !!  !!!!!! !  !!!!!!             .!!';'!!   !  !    !!   !!!!!! ! !!!!!!!!          ! .!!';'!!  !   !   !!   !!!!!!! ! !!!!!! !!   !  !    .!!';'!!  !   !   !   !!!!!!!! ! !!!  !  !   !       .!!';'!!  !   !   !  !!!!!!!!! ! !!!! !   !  !  !  ! .!!';'!!  !   !   !            !  !!  !   !  !     ! .!!';'!! !!!  !   !   !!!!!!   !      !    !!        .!!';'!! ! !   !  !   !     !!  !    !!!    !    !   .!!';'!! ! !   !  !   ! !        !   ! !!    !     ! .!!';'!! ! !   !  !   ! !!  !!    !!!   !!   !   ! ! .!!';'!! ! !   !  !!  ! !!! !           !!   !      !.!!';'!! ! !   !   !  ! !!!!!!!         !    !       .!!';'!  ! !   !   !  !  !!!  !    !!!!     !  !     . !';'!  ! !   !   !! !       !    !      !!         . !';'! !! !   !    !  !!!!!!!!!   !    !!   !   !!!!. !';'! !  !   !    !!       !!!   !!!!!        !    . !';'! !  !    !!   !!!     !!!   !         !!!!    . !';'! !  !     !!     !!!!      !!!!!!!!!!!!      !..+';'! !         !         !!!!!!                     !';'!           !              !                     !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!']



    %replace dot with space
    maze(maze=='.')=' ';
    %position of mouse
    [u,v]=find(maze=='O'); 
    maze(maze=='O') = ' ';
    step_counter = 0;
    while true; %game loop
        %test if mouse found cheese
        if maze(u,v) == '+';
            disp(['mouse found cheese after ', num2str(step_counter), ' steps']);
            break;
        end

        %extract NESW tiles
        nesw = [maze(u-1,v),maze(u,v+1),maze(u+1,v),maze(u,v-1)];

        %get result and move accordingly
        answer = find_the_cheese(nesw);
        switch answer;
            case 'n';
                u = u-1;
            case 'e';
                v = v+1;
            case 's';
                u = u+1;
            otherwise;
                v = v-1;
        end

        %make sure, mouse did not run into wall
        assert(maze(u,v) ~= '!','mouse ran into wall!');
        step_counter = step_counter + 1;
    end
end


function step = find_the_cheese(nesw)
    global State;
    NESW = 'nesw';
    NESW_REVERSE = 'swne';

    if all(nesw == '0000');
        return;
    elseif ~isfield(State,'maze');
        State = struct('maze', zeros(140)+' ','u',75,'v',75,'state','E');
        State.maze(State.u,State.v) = 'S';
    end    
    if State.maze(State.u-1,State.v) == ' '
        State.maze(State.u-1,State.v) = nesw(1);
    end
    if State.maze(State.u,State.v+1) == ' '
        State.maze(State.u,State.v+1) = nesw(2);
    end
    if State.maze(State.u+1,State.v) == ' '
        State.maze(State.u+1,State.v) = nesw(3);
    end
    if State.maze(State.u,State.v-1) == ' '
        State.maze(State.u,State.v-1) = nesw(4);
    end

    current_nesw = [State.maze(State.u-1,State.v),State.maze(State.u,State.v+1),State.maze(State.u+1,State.v),State.maze(State.u,State.v-1)];

    if any(current_nesw == '+'); % if there is cheese, go there
        nesw_index = find(current_nesw == '+',1);

    elseif any(current_nesw == ' '); % if there is a path that we did not walk, go there
        nesw_index = find(current_nesw == ' ',1);
        State.state = 'E';

    else % return to previous crossing
        nesw_index = find(NESW == State.maze(State.u,State.v),1);
        assert(numel(nesw_index)>0,'not enough indices')

        State.state = 'R';
    end

    %execute the step
    if State.state == 'E';
        step = NESW(nesw_index);
    else %State.state = 'R'
        step = State.maze(State.u, State.v);
    end

    switch step;
        case 'n';
            State.u = State.u-1;
        case 'e';
            State.v = State.v+1;
        case 's';
            State.u = State.u+1;
        otherwise;
            State.v = State.v-1;
    end

    if State.maze(State.u,State.v) == ' '; %if we do not have a reverse poniter yet
        State.maze(State.u,State.v) = NESW_REVERSE(nesw_index); %reverse pointer
    end

    %check whether we have any enclosed areas, where the cheese obviously cannot be
    M = imfill(State.maze ~= ' ','holes'); 
    %fill those areas with walls
    State.maze(M & State.maze == ' ') = '!';


    %disp_important(State.maze); %uncomment for display
end


function disp_important(m) %just show the important stuff of the maze
    if any(m(:) ~= ' ');
        for k=1:4
            m = rot90(m);
            while all(m(:,1) == ' ');
                m = m(:,2:end);
            end
        end
    end
    if numel(m) == 0;
        m = 'X';
    end
    m = padarray(m,[1,1],35,'both');
    disp([m,'']);
end
\$\endgroup\$
  • \$\begingroup\$ FYI, these mazes aren't the mazes you're scored on. "There will likely be 10 total mazes and each submission will likely attempt each maze several times, from several different starting positions and cheese positions." \$\endgroup\$ – mbomb007 Jun 23 '16 at 13:46
  • \$\begingroup\$ I know but there's nothing else I could write in the title :D No for real, I just thought these two test cases at least give some impression on how the submissions perform. \$\endgroup\$ – flawr Jun 23 '16 at 15:49
  • \$\begingroup\$ The battery has been released now by the way \$\endgroup\$ – Liam Jun 24 '16 at 3:05
  • \$\begingroup\$ Cool, thanks! I'm gonna update as soon as I'm done with work=) \$\endgroup\$ – flawr Jun 24 '16 at 9:16
  • \$\begingroup\$ @Liam I updated them! \$\endgroup\$ – flawr Jun 24 '16 at 19:12
1
\$\begingroup\$

Python 3, 156 bytes, 37692 + 715 + 50626 + 27806 + 148596 + 172675 = 438110 steps

This isn’t , but golf is fun anyway. This steps to the cheese or takes the least traveled outgoing path, similar to mbomb007’s (not fully implemented) idea, but with ties broken by going to the alphabetically latest direction name.

Deterministic. Run with python3 SCRIPT (tested in 3.5).

x=y=0
f={}
for l in iter(input,'0000'):c,d,x,y=p=max((f.setdefault(p,0),p)for p in zip(l,'nesw',[x,x+1,x,x-1],[y+1,y,y-1,y])if'!'!=p[0])[1];print(d);f[p]-=1
\$\endgroup\$
  • \$\begingroup\$ @mbomb007 f keeps track of which steps between spaces have been used and how often. For example, -f[' ', 'n', 3, 6] is the number of times we went north from (3, 5) to (3, 6). \$\endgroup\$ – Anders Kaseorg Jun 23 '16 at 18:56
  • \$\begingroup\$ So it tracks direction too? \$\endgroup\$ – mbomb007 Jun 23 '16 at 19:09
  • \$\begingroup\$ @mbomb007 Yes, but only because that happens to save a couple of bytes—remembering the direction actually makes it take many more steps. \$\endgroup\$ – Anders Kaseorg Jun 23 '16 at 19:11
1
\$\begingroup\$

PHP 362 + 37 + 1638 + 1508 + 6696 + 1613 = 11854 steps

Ran benchmark on bug-fixed code:

<?php

class Maze {
    public $map, $pos;
    public $prevPos = FALSE;
    public $intersections = [];

    public $n = 75, $e = 75, $w = 75, $s = 75;

    public function __construct() {
        // since we don't know where we start, build a 150x150 map and position ourselves at the middle
        $this->map = array_pad([], 150, array_pad([], 150, 0)); // 0 is unknown
        $this->pos = ['x'=> 75, 'y'=> 75];
    }

    public function play($input){
        $this->updateMap($input);
        $this->move();
    }

    private function updateField($x, $y, $inData) {
        if ($inData == '!' || $this->map[$x][$y] >= 1000) {                 // avoid overwriting our observations
            $this->map[$x][$y] = 1000;
            return;
        }

        // update our known borders
        if ($x <= $this->w) {
            $this->w = $x - 1;
        }
        elseif ($x >= $this->e) {
            $this->e = $x + 1;
        }
        elseif ($y <= $this->n) {
            $this->n = $y - 1;
        }
        elseif ($y >= $this->s) {
            $this->s = $y + 1;
        }

        if (!$this->map[$x][$y]) {
            $this->map[$x][$y] = $inData == '+' ? -1 : 1;
        }
    }

    private function checkForIntersection($input) {
        if (array_key_exists('x' . $this->pos['x'] . 'y' . $this->pos['y'], $this->intersections)) {
            if ($this->intersections['x' . $this->pos['x'] . 'y' . $this->pos['y']] > 0) {
                $this->intersections['x' . $this->pos['x'] . 'y' . $this->pos['y']] --;
                return TRUE;                                        // intersection already crossed
            }
        }
        elseif ($c = substr_count($input, ' ') > 2) {
            $this->intersections['x' . $this->pos['x'] . 'y' . $this->pos['y']] = $c - 1;
        }

        return FALSE;
    }

    private function updateMap($input) {
        if ($this->checkForIntersection($input)) {
            // if we're at a known intersection, we know that the path we come from lead nowhere
            $this->updateField($this->prevPos['x'], $this->prevPos['y'], '!');
        }

        // update discovered information
        $this->updateField($this->pos['x'], $this->pos['y'] - 1, $input[0]);
        $this->updateField($this->pos['x'] + 1, $this->pos['y'], $input[1]);
        $this->updateField($this->pos['x'], $this->pos['y'] + 1, $input[2]);
        $this->updateField($this->pos['x'] - 1, $this->pos['y'], $input[3]);
    }

    private function move() {
        if ($this->prevPos) {

            $this->map[$this->prevPos['x']][$this->prevPos['y']] ++;    // count times stepped on   
        }

        $best = ['w' => 1000];

        foreach ([
            ['x' => $this->pos['x'], 'y' => $this->pos['y'] - 1, 'w' => $this->map[$this->pos['x']][$this->pos['y'] - 1], 'd' => 'n'],
            ['x' => $this->pos['x'] + 1, 'y' => $this->pos['y'], 'w' => $this->map[$this->pos['x'] + 1][$this->pos['y']], 'd' => 'e'],
            ['x' => $this->pos['x'], 'y' => $this->pos['y'] + 1, 'w' => $this->map[$this->pos['x']][$this->pos['y'] + 1], 'd' => 's'],
            ['x' => $this->pos['x'] - 1, 'y' => $this->pos['y'], 'w' => $this->map[$this->pos['x'] - 1][$this->pos['y']], 'd' => 'w']]
        as $direction) {
            if ($direction['w'] < $best['w'] || ($direction['w'] == $best['w'] && $best['w'] < 1000 && max($this->e - $direction['x'],  $direction['x'] - $this->w, $direction['y'] - $this->n, $this->s - $direction['y']) > max($best['x'] - $this->e, $this->w - $best['x'], $best['y'] - $this->n, $this->s - $best['y']))) { 
            // encourage searching for borders which will later allow to block certain dead end paths without walking them
            // testing with middle search instead
                $best = $direction;
            }
        }

        echo $best['d'] . "\n";

        $this->prevPos = $this->pos;
        $this->pos = $best;
    }
}

$maze = new Maze();

while (strncmp(($input = fgets(STDIN)), '0000', 4)) {
    $len = strlen($input);
    if (($len > 6) || $len < 3) { continue; }

    $maze->play($input);
}
\$\endgroup\$
1
\$\begingroup\$

MATLAB, 212 + 23 + 416 + 300 + 1806 + 757 = 3514 steps

In this approach, the mouse follows a possible path until it finds a dead end. Then it returns to the previous intersection, where there was a path that was not yet explored. It is deterministic. From the available paths it always chooses in the order NESW (not NSFW, as I was always tempted to write =)

As I cannot compile matlab scripts, I translated the controller to MATLAB. The "program" is now just a function that accesses global variables for in-between-step-storage.

function find_the_cheese_controller()
clc;clear;
    global State;
    clearvars -global State;
    %uncomment the maze you want to test
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!O !                    !      !';'!. ! !!!!!!!!!!!!!!!!!! ! !!!!!!';'!. !                    ! !    !';'!. ! !!!!!!!!!!!!!!!!!!!! ! !! !';'!. !...........           ! !!.+';'!. !.!!!!!!!!!.!!!!!!!!!!!!!!!.!';'!.!..!        ...............!.!';'!.!.!! !!!!!!!!!!!!!!!!!!!!!.!.!';'!.!.!! !!!  !               .!.!';'!.!.!! !!!  !!!!!!!!!!!!!!!!.!.!';'!...!! !!!                  .!.!';'! ! !! !!!                  .!.!';'! ! !! !!!  !!!!!!!!! !!!!!!.!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !! !!!  ! !!!!!!! !     .!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !! !!!  !      !! !     .!.!';'! ! !!   !  !      !! !     .!.!';'! ! !! ! !  !!!!!! !! !     .!.!';'! ! !! ! !  !      !! !     ...!';'! ! !! ! !  !      !! !        !';'! ! !! ! !  !      !! !      ! !';'! ! !! ! !  !  !!!!!! !      ! !';'! ! !! ! !  !      !! !      ! !';'! !    !    !      !! !      ! !';'! !!!!!!  !!!!!!!! !! !      ! !';'!                ! !! !      ! !';'! !!!!!!!!!!! !!!! !! !      ! !';'!                     !      ! !';'! !!!!!!!! !!!!       !        !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!';'!      .......!';'! !!! !.!!!! .!';'!   ! !.!!O!!.!';'!!!   !....! .!';'!   !!!!!!!!!.!';'! !!        ..!';'!  !!!!!!!!!.!!';'!           ..+';'!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!                            !!!';'! !  !!!  !!!!!!!!!!!!!!!!!!   !';'! !  ! !!!              !!!  ! !';'! !  ! !!!!!!!!!!!!!!!!     !! !';'! !  !                  !!!!   !';'! !! !!!!!!!!!!        !!    ! !';'!  ! !        !!!! !!!!!   !!! !';'!! ! ! !!!!      !         !   !';'!! ! ! !!!!   !!!!!!!!!!!!!! ! !';'!! ! ! !!!! ! !              ! !';'!! ! ! !!!! ! ! !!!!       ! ! !';'!! ! ! !!!! ! ! !   !!!    ! ! !';'!  ! ! !!!! ! ! !     !!!  ! ! !';'!  ! ! !!!! ! ! !!!!!      !   !';'!  ! ! !!!! !!! !   !!     ! !!!';'!  ! !  !!!  !! !    !!!   ! !!!';'!  ! !     ! !! !!!!   !!  ! !!!';'!  ! !!    ! !! !  !!      ! !!!';'!  !  !   !! !!     !!!    ! !!!';'!  !! !!!!     !!!    !!   !   !';'!!  ! !! !       !!!   !!  !!! !';'!!  !    !    !    !           !';'!!  !!!!!!    !!   !!!!!!!!!!! !';'!             !!!! !!!!!!!!!!! !';'!  ..........O!!!! !!!!!!!!!!!.+';'!! .!!!!!!    !!   !!!!!!!!!!!.!';'!! .!    !    !    !          .!';'!!..! !! !       !!!   !!  !!!.!';'! .!! !!!!     !!!    !!   !...!';'! .!  !   !! !!     !!!    !.!!!';'! .! !!    ! !! !  !!      !.!!!';'! .! !     ! !! !!!!   !!  !.!!!';'! .! !  !!!  !! !    !!!   !.!!!';'! .! ! !!!! !!! !   !!     !.!!!';'! .! ! !!!! ! ! !!!!!      !...!';'! .! ! !!!! ! ! !     !!!  ! !.!';'!!.! ! !!!! ! ! !   !!!    ! !.!';'!!.! ! !!!! ! ! !!!!       ! !.!';'!!.! ! !!!! ! !              !.!';'!!.! ! !!!!   !!!!!!!!!!!!!! !.!';'!!.! ! !!!!      !         !  .!';'!..! !        !!!! !!!!!   !!!.!';'!.!! !!!!!!!!!!        !!    !.!';'!.!  !                  !!!!  .!';'!.!  ! !!!!!!!!!!!!!!!!     !!.!';'!.!  ! !!!              !!!  !.!';'!.!  !!!  !!!!!!!!!!!!!!!!!!...!';'!............................!!!';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!+!!!!!!!!!!!!!!';'!.................           !!!';'!.!  !!!  !!!!!!!!!!!!!!!!!!   !';'!.!  ! !!!              !!!  ! !';'!.!  ! !!!!!!!!!!!!!!!!     !! !';'!.!  !                  !!!!   !';'!.!! !!!!!!!!!!        !!    ! !';'!..! !        !!!! !!!!!   !!! !';'!!.! ! !!!!      !         !   !';'!!.! ! !!!!   !!!!!!!!!!!!!! ! !';'!!.! ! !!!! ! !              ! !';'!!.! ! !!!! ! ! !!!!       ! ! !';'!!.! ! !!!! ! ! !   !!!    ! ! !';'! .! ! !!!! ! ! !     !!!  ! ! !';'! .! ! !!!! ! ! !!!!!      !   !';'! .! ! !!!! !!! !   !!     ! !!!';'! .! !  !!!  !! !    !!!   ! !!!';'! .! !     ! !! !!!!   !!  ! !!!';'! .! !!    ! !! !  !!      ! !!!';'! .!  !   !! !!     !!!    ! !!!';'! .!! !!!!     !!!    !!   !   !';'!!. ! !! !       !!!   !!  !!! !';'!!. !    !    !    !           !';'!!. !!!!!!    !!   !!!!!!!!!!! !';'! ........... !!!! !!!!!!!!!!! !';'!           . !!!! !!!!!!!!!!! !';'!!  !!!!!!  . !!   !!!!!!!!!!! !';'!!  !    !  . !    !           !';'!!  ! !! !  .    !!!   !!  !!! !';'!  !! !!!!  .  !!!    !!   !   !';'!  !  !   !!.!!     !!!    ! !!!';'!  ! !!    !.!! !  !!      ! !!!';'!  ! !     !.!! !!!!   !!  ! !!!';'!  ! !  !!!..!! !    !!!   ! !!!';'!  ! ! !!!!.!!! !   !!     ! !!!';'!  ! ! !!!!.! ! !!!!!      !   !';'!  ! ! !!!!.! ! !     !!!  ! ! !';'!! ! ! !!!!.! ! !   !!!    ! ! !';'!! ! ! !!!!.! ! !!!!       ! ! !';'!! ! ! !!!!.! !              ! !';'!! ! ! !!!!.  !!!!!!!!!!!!!! ! !';'!! ! ! !!!!.....O!         !   !';'!  ! !        !!!! !!!!!   !!! !';'! !! !!!!!!!!!!        !!    ! !';'! !  !                  !!!!   !';'! !  ! !!!!!!!!!!!!!!!!     !! !';'! !  ! !!!              !!!  ! !';'! !  !!!  !!!!!!!!!!!!!!!!!!   !';'!                            !!!';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'+......!!!!       !!!        !!!       !!!!     !!';'!     .!       !!                            !!!!!';'!  !!!.! !!      !!!  !!!!  !!!!!!!!!      !!!   !';'! !!...!   !!!!!   !!    !          !!    !!     !';'!!!..!!         !    !!  !           !    !     !!';'!! .!!........        !! !!!     !    !   !  !  !!';'!!!. !.  !  !.   !      !!!!!    !!   !   ! !! !!!';'!!!. !.  !  !.   !       !!!!!    !   !!    !  !!!';'!!.. !.  !  !..  !        !  !    !!   !    !   !!';'!!.! !.!  ! ! ..  ! !!!!!!  !      !   !    !   !!';'!!.! !.!  ! !! .  ! !      !        !  !    !   !!';'!!.! !.!  !  ! .  ! !!   !!    !!!! !  !    !   !!';'!!.! !.!! !  ! .  !  !!!   !!!!     !  !    !!  !!';'!!.! !. ! !  ! .  !    !!        !  !   !    !  !!';'! .!!!. ! !  !!.   !    !        !  !   !    !   !';'! .!!!. ! !   !.   !     !       !   !  !    !   !';'! .! !. ! !   !.   !     !       !   !   !   !   !';'! .! !. ! !!  !....!!!   !      !!   !     ! !   !';'! .!  ..!  !  !   ...!!!!       !    !     ! ! ! !';'! .!   .!  !  !!!!!!.... !!!!!!!             ! ! !';'! .! !!.!  !! !  !!!!  .!                        !';'! .!!!!.!   !!!! !!!   .!   !!!!!   !!!!!!!!!!!  !';'! .. !!.!    !!!  !!  !.!!                       !';'!!!.. !. !   !!!      !..!        !!!   !   !    !';'!!! .... !  !!!!      ! .!        !             !!';'!!!!!!!!!!!!!!!!!!!!!!! .! !!!!!!!!!!!!!!!!!!!! !!';'!!!  !                  .!                     !!!';'!!   !   !!!  !!        .!                      !!';'!!   !  !     !!  !!!!!!.!  !!!!!!              !!';'!!   !  !    !!   !!!!!!.! !!!!!!!!          !  !!';'!!  !   !   !!   !!!!!!!.! !!!!!! !!   !  !     !!';'!!  !   !   !   !!!!!!!!.! !!!  !  !   !        !!';'!!  !   !   !  !!!!!!!!!.! !!!! !   !  !  !  !  !!';'!!  !   !   !           .!  !!  !   !  !     !  !!';'!! !!!  !   !   !!!!!!  .!      !    !!         !!';'!! ! !   !  !   !     !!. !    !!!    !    !    !!';'!! ! !   !  !   ! !     .  !   ! !!    !     !  !!';'!! ! !   !  !   ! !!  !!.   !!!   !!   !   ! !  !!';'!! ! !   !  !!  ! !!! ! .....     !!   !      ! !!';'!! ! !   !   !  ! !!!!!!!   .     !    !        !!';'!  ! !   !   !  !  !!!  !   .!!!!     !  !       !';'!  ! !   !   !! !       !   .!      !!.......... !';'! !! !   !    !  !!!!!!!!!  .!    !!  .!   !!!!. !';'! !  !   !    !!       !!!  .!!!!!   ..   !    . !';'! !  !    !!   !!!     !!!  .......... !!!!    . !';'! !  !     !!     !!!!      !!!!!!!!!!!!      !. !';'! !         !         !!!!!!                  O. !';'!           !                                    !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'];
    %maze=['!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!';'!      !!!!   ....!!!        !!!       !!!!     !!';'!      !      .!!..........                  !!!!!';'!  !!! ! !!   ...!!!  !!!!. !!!!!!!!!      !!!   !';'! !!   !   !!!!!.. !!    !.         !!    !!     !';'!!!  !!         !.   !!  !.....      !    !     !!';'!!  !!          ..    !! !!!  .  !    !   !  !  !!';'!!!  !   !  !   .!      !!!!! .  !!   !   ! !! !!!';'!!!  !   !  !   .!       !!!!!.   !   !!    !  !!!';'!!   !   !  !   .!        !  !.   !!   !    !   !!';'!! ! ! !  ! !   . ! !!!!!!  ! ..   !   !    !   !!';'!! ! ! !  ! !!  . ! !      !   .....!  !    !   !!';'!! ! ! !  !  !  . ! !!   !!    !!!!.!  !    !   !!';'!! ! ! !! !  !  ..!  !!!   !!!!    .!  !    !!  !!';'!! ! !  ! !  !   .!    !!        ! .!   !    !  !!';'!  !!!  ! !  !!  . !    !        ! .!   !    !   !';'!  !!!  ! !   !  ..!     !       ! . !  !    !   !';'!  ! !  ! !   !   .!     !       ! . !   !   !   !';'!  ! !  ! !!  !   .!!!   !      !! . !     ! !   !';'!  !    !  !  !   ...!!!!       !  . !     ! ! ! !';'!  !    !  !  !!!!!!.... !!!!!!!   .         ! ! !';'!  ! !! !  !! !  !!!!  .!          .             !';'!  !!!! !   !!!! !!!   .!   !!!!!  .!!!!!!!!!!!  !';'!    !! !    !!!  !!  !.!!..........             !';'!!!   !  !   !!!      !. !.       !!!   !   !    !';'!!!      !  !!!!      !. !.       !             !!';'!!!!!!!!!!!!!!!!!!!!!!!. !.!!!!!!!!!!!!!!!!!!!! !!';'!!!  !                 . !.....................!!!';'!!   !   !!!  !!  O..... !                    ..!!';'!!   !  !     !!  !!!!!! !  !!!!!!             .!!';'!!   !  !    !!   !!!!!! ! !!!!!!!!          ! .!!';'!!  !   !   !!   !!!!!!! ! !!!!!! !!   !  !    .!!';'!!  !   !   !   !!!!!!!! ! !!!  !  !   !       .!!';'!!  !   !   !  !!!!!!!!! ! !!!! !   !  !  !  ! .!!';'!!  !   !   !            !  !!  !   !  !     ! .!!';'!! !!!  !   !   !!!!!!   !      !    !!        .!!';'!! ! !   !  !   !     !!  !    !!!    !    !   .!!';'!! ! !   !  !   ! !        !   ! !!    !     ! .!!';'!! ! !   !  !   ! !!  !!    !!!   !!   !   ! ! .!!';'!! ! !   !  !!  ! !!! !           !!   !      !.!!';'!! ! !   !   !  ! !!!!!!!         !    !       .!!';'!  ! !   !   !  !  !!!  !    !!!!     !  !     . !';'!  ! !   !   !! !       !    !      !!         . !';'! !! !   !    !  !!!!!!!!!   !    !!   !   !!!!. !';'! !  !   !    !!       !!!   !!!!!        !    . !';'! !  !    !!   !!!     !!!   !         !!!!    . !';'! !  !     !!     !!!!      !!!!!!!!!!!!      !..+';'! !         !         !!!!!!                     !';'!           !              !                     !';'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!']

;

    %replace dot with space
    maze(maze=='.')=' ';
    %position of mouse
    [u,v]=find(maze=='O'); 
    maze(maze=='O') = ' ';
    step_counter = 0;
    while true; %game loop
        %test if mouse found cheese
        if maze(u,v) == '+';
            disp(['mouse found cheese after ', num2str(step_counter), ' steps']);
            break;
        end

        %extract NESW tiles
        nesw = [maze(u-1,v),maze(u,v+1),maze(u+1,v),maze(u,v-1)];

        %get result and move accordingly
        answer = find_the_cheese(nesw);
        switch answer;
            case 'n';
                u = u-1;
            case 'e';
                v = v+1;
            case 's';
                u = u+1;
            otherwise;
                v = v-1;
        end

        %make sure, mouse did not run into wall
        assert(maze(u,v) ~= '!','mouse ran into wall!');
        step_counter = step_counter + 1;
    end
end


function step = find_the_cheese(nesw)
    global State;
    NESW = 'nesw';
    NESW_REVERSE = 'swne';

    if all(nesw == '0000');
        return;
    elseif ~isfield(State,'maze');
        State = struct('maze', zeros(140)+' ','u',75,'v',75,'state','E');
        State.maze(State.u,State.v) = 'S';
    end    
    if State.maze(State.u-1,State.v) == ' '
        State.maze(State.u-1,State.v) = nesw(1);
    end
    if State.maze(State.u,State.v+1) == ' '
        State.maze(State.u,State.v+1) = nesw(2);
    end
    if State.maze(State.u+1,State.v) == ' '
        State.maze(State.u+1,State.v) = nesw(3);
    end
    if State.maze(State.u,State.v-1) == ' '
        State.maze(State.u,State.v-1) = nesw(4);
    end

    current_nesw = [State.maze(State.u-1,State.v),State.maze(State.u,State.v+1),State.maze(State.u+1,State.v),State.maze(State.u,State.v-1)];

    if any(current_nesw == '+'); % if there is cheese, go there
        nesw_index = find(current_nesw == '+',1);

    elseif any(current_nesw == ' '); % if there is a path that we did not walk, go there
        nesw_index = find(current_nesw == ' ',1);
        State.state = 'E';

    else % return to previous crossing
        nesw_index = find(NESW == State.maze(State.u,State.v),1);
        assert(numel(nesw_index)>0,'not enough indices')

        State.state = 'R';
    end

    %execute the step
    if State.state == 'E';
        step = NESW(nesw_index);
    else %State.state = 'R'
        step = State.maze(State.u, State.v);
    end

    switch step;
        case 'n';
            State.u = State.u-1;
        case 'e';
            State.v = State.v+1;
        case 's';
            State.u = State.u+1;
        otherwise;
            State.v = State.v-1;
    end

    if State.maze(State.u,State.v) == ' '; %if we do not have a reverse poniter yet
        State.maze(State.u,State.v) = NESW_REVERSE(nesw_index); %reverse pointer
    end

    %disp_important(State.maze); %uncomment for display
end


function disp_important(m) %just show the important stuff of the maze
    if any(m(:) ~= ' ');
        for k=1:4
            m = rot90(m);
            while all(m(:,1) == ' ');
                m = m(:,2:end);
            end
        end
    end
    if numel(m) == 0;
        m = 'X';
    end
    m = padarray(m,[1,1],35,'both');
    disp([m,'']);
end
\$\endgroup\$
1
\$\begingroup\$

Simple Bot, Java 1.4+, 176 + 25 + 1118 + 486 + 10944 + 1847 = 14596 steps

This bot counts and records the number of steps taken to reach each visited cell then, when deciding which direction to move, chooses the direction that has the lowest step count. In the event of a tie, chooses the direction in N,E,S,W order.

I do not have rust installed so I had to implement the controller in java and this was the bot i used to test it. I will be attempting a more clever solver soon.

Deterministic. Run with java SimpleBot

import java.io.IOException;
import java.io.InputStream;

public class SimpleBot 
{
    private static final char[] DIRECTION = {'n','e','s','w'};
    public static void main(String[] args) throws Exception
    {
        int[][] stepMap = new int[100][100];
        int mx=49, my=49;
        int[][] offsets = new int[][]{{0,-1},{1,0},{0,1},{-1,0}};

        String line=readLine(System.in);
        int step=0;
        while (line!=null && !"0000".equals(line))
        {
            stepMap[mx][my]=step++;

            int minStep = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int i=0;i<4;i++)
            {
                if (line.charAt(i) == '+')
                {
                    minIndex=i;
                    break;
                }
                else if (line.charAt(i) == ' ')
                {
                    if (stepMap[mx+offsets[i][0]][my+offsets[i][1]]<minStep)
                    {
                        minStep = stepMap[mx+offsets[i][0]][my+offsets[i][1]];
                        minIndex=i;
                    }
                }
            }
            mx +=offsets[minIndex][0];
            my +=offsets[minIndex][1];

            System.out.println(DIRECTION[minIndex]);
            line=readLine(System.in);
        }
    }

    /**
     * Reads a line of text from the input stream. Blocks until a new line character is read.
     * NOTE: This method is used in favor of BufferedReader.readLine(...) as BufferedReader buffers data before performing
     * text line tokenization. This means that BufferedReader.readLine() will block until sufficient input have been received. 
     * @param in a InputStream, nominally System.in
     * @return a line of text or null if end of stream.
     * @throws IOException
     */
    private static String readLine(InputStream in) throws IOException
    {
       StringBuilder sb = new StringBuilder();
       int readByte = in.read();
       while (readByte>-1 && readByte!= '\n')
       {
          sb.append((char) readByte);
          readByte = in.read();
       }
       return readByte==-1?null:sb.toString();
    }

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.