How to Solve the Maze Runner in C

4 min read 821 words

Table of Contents

The challenge

Introduction

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

Task

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
  directions = "NNNNNEEEEE" == "Finish" // (directions passed as a string)

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.

The solution in C

Option 1:

#include <stddef.h>

char *maze_runner(const int *maze, size_t n, const char *directions) 
{
  int x, y, cur;
  
  // locate the start
  for (y = 0; y < n; y++) for (x = 0; x < n; x++) if (maze[y*n+x] == 2) goto moves;
  
  moves:
  for (char *d = directions; *d; d++) 
  {
    switch (*d) {
      case 'N': y--; break;
      case 'S': y++; break;
      case 'E': x++; break;
      case 'W': x--; break;
    }
    if (x < 0 || y < 0 || y > n-1 || x > n-1)  return "Dead"; // out of bounds
    if ((cur = maze[y*n+x]) == 1)              return "Dead"; // hit wall 
    if (cur == 3)                              return "Finish"; // found exit
  }
  
  return "Lost";
}

Option 2:

#include <stddef.h>
#include <iso646.h>

#define NORTH 'N'
#define SOUTH 'S'
#define EAST  'E'
#define WEST  'W'

#define START   2
#define WALL    1
#define FINISH  3

char *maze_runner(const int *maze, size_t n, const char *directions) {
    size_t x, y;
    for (size_t i = 0; i < n; i++){
        for (size_t j = 0; j < n; j++)
            if (maze[i * n + j] == START){
                x = j;
                y = i;
            }
    }
    for (size_t i = 0; directions[i]; i++){
        x += (directions[i] == EAST) - (directions[i] == WEST);
        y += (directions[i] == SOUTH) - (directions[i] == NORTH);
        if (maze[y * n + x] == WALL or x >= n or y >= n)
            return "Dead";
        if (maze[y * n + x] == FINISH)
            return "Finish";
    }
    return "Lost";
}

Option 3:

#include <stddef.h>

#define DEAD(N, MAX) N < 0 || N > MAX - 1

void move(int *x, int *y, char dir) {
  switch (dir) {
      case 'N': *y -= 1; break;
      case 'S': *y += 1; break;
      case 'E': *x += 1; break;
      case 'W': *x -= 1; break;
  }
}

char *maze_runner(const int *maze, size_t n, const char *directions) {
  int nums[n][n], x, y, i, *p;

  for (p = maze, i = 0; i < n * n; i++) {
    nums[i/n][i%n] = maze[i];
    if (*p++ == 2) x = i%n, y = i/n;
  }

  while (*directions) {
    move(&x, &y, *directions++);
    if (DEAD(x, n) || DEAD(y, n) || nums[y][x] == 1) return "Dead";
    if (nums[y][x] == 3) return "Finish";
  }

  return "Lost";
}

Test cases to validate our solution

#include <criterion/criterion.h>

void tester(const int *maze, size_t n, const char *directions, char *outcome);

Test(Example_Tests, should_pass_all_the_tests_provided) {

    #define N 7

    const int maze[N * N] = {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};
  
  //  maze is passed in as a 1-D int array with length n
  //  directions are passed in as a null-terninated string
  //  do not allocate memory, instead return a string literal
  
  { const char *directions = "NNNNNEEEEE";     tester(maze, N, directions, "Finish"); }
  { const char *directions = "NNNNNEESSEENNE"; tester(maze, N, directions, "Finish"); }
  { const char *directions = "NNNNNEEEEEWW";   tester(maze, N, directions, "Finish"); }
  { const char *directions = "NEEEE";          tester(maze, N, directions,   "Lost"); }
  { const char *directions = "NNNWW";          tester(maze, N, directions,   "Dead"); }
  { const char *directions = "NNNNNEESSSSSS";  tester(maze, N, directions,   "Dead"); }
  
}
Tags:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags