loading...

Daily Challenge #288 - Maze Runner

thepracticaldev profile image dev.to staff ・2 min read

Welcome, Adventurer. Your aim is to navigate the maze and reach the finish point without touching any walls. Doing so will kill you instantly!

You will be given a 2D array of the maze and an array of directions. Your task is to follow the directions given. If you reach the end point before all your moves have gone, you should return Finish. If you hit any walls or go outside the maze border, you should return Dead. If you find yourself still in the maze after using all the moves, you should return Lost.

The Maze array will look like

maze = [[1,1,1,1,1,1,1],
        [1,0,0,0,0,0,3],
        [1,0,1,0,1,0,1],
        [0,0,1,0,0,0,1],
        [1,0,1,0,1,0,1],
        [1,0,0,0,0,0,1],
        [1,2,1,0,1,0,1]]

..with the following key

      0 = Safe place to walk
      1 = Wall
      2 = Start Point
      3 = Finish Point

For the above example, direction = ["N","N","N","N","N","E","E","E","E","E"] should get you to the end!

Rules

  1. The Maze array will always be square i.e. N x N but its size and content will alter from test to test.

  2. The start and finish positions will change for the final tests.

  3. The directions array will always be in upper case and will be in the format of N = North, E = East, W = West and S = South.

  4. If you reach the end point before all your moves have gone, you should return Finish.

  5. If you hit any walls or go outside the maze border, you should return Dead.

  6. If you find yourself still in the maze after using all the moves, you should return Lost.
    Good luck, and stay safe!

Tests

Maze:

var maze = [[1,1,1,1,1,1,1],
            [1,0,0,0,0,0,3],
            [1,0,1,0,1,0,1],
            [0,0,1,0,0,0,1],
            [1,0,1,0,1,0,1],
            [1,0,0,0,0,0,1],
            [1,2,1,0,1,0,1]];

Tests
["N","N","N","N","N","E","E","E","E","E"]
["N","N","N","W","W"]
["N","E","E","E","E"]

Good luck!


This challenge comes from adrian.eyre on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❀️

Discussion

markdown guide
 

ES6

const find = (maze, N, num) => {
    for (let i = 0; i < N; i++) {
        let index = maze[i].indexOf(num)
        if (index > -1) return [i, index]
    }
    return -1
}


const reach = (maze, direction) => {
    if (!maze || !Array.isArray(maze) || maze[0].length !== maze.length) throw new Error("invalid argument")
    const N = maze[0].length
    let start = find(maze, N, 2)
    if (start < 0) throw new Error("start point not found")
    let finish = find(maze, N, 3)
    if (finish < 0) throw new Error("finish point not found")
    for (let i = 0; i < direction.length; i++) {
        switch (direction[i]) {
            case "E":
                start = [start[0], start[1] + 1];
                break;
            case "W":
                start = [start[0], start[1] - 1]
                break;
            case "N":
                start = [start[0] - 1, start[1]]
                break;
            case "S":
                start = [start[0] + 1, start[1]]
                break;
            default:
                throw new Error("unidentified direction")
        }
        if (start[0] < 0 || start[0] >= N || start[1] < 0 || start[1] >= N || maze[start[0]][start[1]] === 1) {
            return "Dead"
        }

    }
    if (start[0] === finish[0] && start[1] === finish[1]) return "Finish"

    return "Lost"
}
 

Here is the simple way with PHP to traverse two dimensional arrays and get current moving states :).

function maze_runner($maze, $directions): string {
  $m = 0;
  $n = 0;
  $startM = 0;
  $startN = 0;
  foreach ($maze as $mazeRow) {
    foreach ($mazeRow as $mazeNumber) {
      if ($mazeNumber === 2) {
        $startM = $m;
        $startN = $n;
        break;
      }
      $n += 1;
    }
    $n = 0;
    $m += 1;
  }

  $currentValue = null;
  foreach ($directions as $direction) {
    if ($direction === 'N') {
      $startM -= 1;
      if ($startM < 0 || $startM >= count($maze[0])) {
        return 'Dead';
      }
    }
    if ($direction === 'S') {
      $startM += 1;
      if ($startM < 0 || $startM >= count($maze[0])) {
        return 'Dead';
      }
    }
    if ($direction === 'E') {
      $startN += 1;
      if ($startN < 0 || $startN >= count($maze[0])) {
        return 'Dead';
      }
    }
    if ($direction === 'W') {
      $startN -= 1;
      if ($startN < 0 || $startN >= count($maze[0])) {
        return 'Dead';
      }
    }

    $currentValue = $maze[$startM][$startN];

    if ($currentValue === 3) {
      return 'Finish';
    }
    if ($currentValue === 1) {
      return 'Dead';
    }
  }

  return 'Lost';
}
 

One with full typing info in typescript...

// Input
type Maze = MazeSquare[][];
type Directions = Direction[];
// Output
type FinishState = 'Finish' | 'Dead' | 'Lost';

// component types
enum MazeSquare {
  space = 0,
  wall = 1,
  start = 2,
  end = 3,
}
type Direction = 'N' | 'E' | 'W' | 'S';
type Coor = { row: number; col: number };

// Functions to move a coor around
const coorUpdaterByDirection = {
  N: (coor: Coor) => {
    coor.row--;
  },
  E: (coor: Coor) => {
    coor.col++;
  },
  W: (coor: Coor) => {
    coor.col--;
  },
  S: (coor: Coor) => {
    coor.row++;
  },
};


function mazeRunner(maze: Maze, directions: Directions): FinishState {
  // Find starting point
  const coor_row = maze.findIndex(v => v.indexOf(MazeSquare.start) !== -1);
  if (coor_row === -1) throw new Error('Maze has no starting point');

  const coor: Coor = {
    row: coor_row,
    col: maze[coor_row].indexOf(MazeSquare.start),
  };


  let foundEnd = false; // The closure will set this if it finds the end

  // Iterate through the directions array until we finish or hit a wall/boundary
  // I'll use `findIndex` since it can early-stop as needed
  return directions.findIndex(direction => {
    // move the coor based on direction
    coorUpdaterByDirection[direction](coor);

    const square = maze[coor.row]?.[coor.col];
    // (note that square will be undefined if coor is off the map)

    foundEnd = square === MazeSquare.end;
    // return true if we want to keep going (i.e. are on a clear square)
    return square !== MazeSquare.space && square !== MazeSquare.start;
  }) === -1
    ? 'Lost'
    : foundEnd
    ? 'Finish'
    : 'Dead';
}

Some sanity checking


const testMaze: Maze = [
    [1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 3],
    [1, 0, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1],
    [1, 2, 1, 0, 1, 0, 1],
  ],
  tests: [Directions, FinishState][] = [
    [['N', 'N', 'N', 'N', 'N', 'E', 'E', 'E', 'E', 'E'], 'Finish'],
    [['N', 'N', 'N', 'N', 'N', 'E', 'E', 'S', 'S', 'E', 'E', 'N', 'N', 'E'], 'Finish'],
    [['N', 'N', 'N', 'N', 'N', 'E', 'E', 'E', 'E', 'E', 'W', 'W'], 'Finish'],
    [['N', 'N', 'N', 'W', 'W'], 'Dead'],
    [['N', 'N', 'N', 'N', 'N', 'E', 'E', 'S', 'S', 'S', 'S', 'S', 'S'], 'Dead'],
    [['N', 'E', 'E', 'E', 'E'], 'Lost'],
  ];

tests.forEach(([directions, expectation], testi) => {
  const actual = mazeRunner(testMaze, directions);
  console.log(`Test #${testi}: ${directions.join(', ')}
  Result: ${actual}, expected ${expectation}, which is a ${expectation === actual ? 'pass! woop' : 'FAILURE rofl'})
`);
});

/* -->

Test #0: N, N, N, N, N, E, E, E, E, E
  Result: Finish, expected Finish, which is a pass! woop)

a.ts:83
Test #1: N, N, N, N, N, E, E, S, S, E, E, N, N, E
  Result: Finish, expected Finish, which is a pass! woop)

a.ts:83
Test #2: N, N, N, N, N, E, E, E, E, E, W, W
  Result: Finish, expected Finish, which is a pass! woop)

a.ts:83
Test #3: N, N, N, W, W
  Result: Dead, expected Dead, which is a pass! woop)

a.ts:83
Test #4: N, N, N, N, N, E, E, S, S, S, S, S, S
  Result: Dead, expected Dead, which is a pass! woop)

woop πŸ•ΊπŸ’ƒ