Commits

Lazar Sumar  committed 20ac4c2

Basic solution implemented in C and C++.

  • Participants

Comments (0)

Files changed (16)

File C Solution/README.txt

+MAZE SOLVER
+
+PROBLEM:
+========
+Write a C or C++ program to be a virtual maze walking mouse for a two dimensional maze of X columns and Y rows.
+int maze[x][y];
+maze[?][?] == 1 means empty corridor.
+maze[?][?] == 0 means solid wall.
+ 
+The entry point is fixed from (1,0); (i.e. maze[1][0] will always be 1).
+The exit point is a 1 at the edge of the maze.
+The output of the program is a set of (x,y) coordinates that leads from entry (1,0) to (?,?) the exit.
+ 
+Example:
+0,1,0,0,0,0,0,0,0,0,0
+0,1,1,1,1,1,1,0,0,0,0
+0,0,0,1,0,0,1,1,0,0,0
+0,0,1,1,0,0,1,0,0,0,0
+0,0,0,0,0,1,1,1,1,0,0
+0,0,1,1,1,1,0,0,1,0,0
+0,0,0,1,0,0,0,0,0,0,0
+Entry at (1,0)
+ 
+Virtual mouse should print out below:
+Solution: (1,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(6,2)(6,3)(6,4)(5,4)(5,5)(4,5)(3,5)(3,6)
+Exit at (3,6)
+
+Instructions:
+·         Follow the K.I.S.S. concept.
+·         Readability first, performance next.(i.e. the more thinking needed to understand the code the lower the score).
+·         Minimum C++ approach (for readability and portability), keep it simple.(i.e. the more C++ specific expression the lower the score).
+·         Code should for the most part be self documenting.
+
+
+SOLUTION:
+=========
+The solver works by eliminating dead ends and is not optimized to find 
+the shortest path (KISS requirement).
+
+A makefile is included so run make to compile the program.
+
+The maze.txt file contains the assigned maze and will be loaded and solved each
+time the program is run. Alter it to test different mazes. Note, that the format
+of the file must remain "the same", i.e. there must be no comma at the end of a line, 
+only 0's, 1's and ',' are allowed (though whitespace should be ignored this was not 
+tested) and there must be a new line at the end of the file.
+
+Kind regards
+
+Lazar Sumar
+
+Note: The C version of the program was derived from the C++ attempt and follows
+      a seemingly OO approach. Depending on the requirement it might be better
+      to rewrite it using structured programming. It was left as is due to references
+      to C++ in the instructions...

File C Solution/makefile

+CC=gcc
+CFLAGS=-Wall
+LIB=
+EXEC=maze_solver
+
+$(EXEC): maze_solver.c
+	$(CC) $(CFLAGS) -o $(EXEC) maze_solver.c

File C Solution/maze.txt

+0,1,0,0,0,0,0,0,0,0,0
+0,1,1,1,1,1,1,0,0,0,0
+0,0,0,1,0,0,1,1,0,0,0
+0,0,1,1,0,0,1,0,0,0,0
+0,0,0,0,0,1,1,1,1,0,0
+0,0,1,1,1,1,0,0,1,0,0
+0,0,0,1,0,0,0,0,0,0,0

File C Solution/maze_solver

Binary file added.

File C Solution/maze_solver.c

+/* Author: Lazar Sumar
+ * Date 27th March 2012
+ */
+#include <stdlib.h>
+#include <stdio.h>
+
+#define ERROR 0
+#define MAX_MAZE_X 1000
+#define MAX_MAZE_Y 1000
+
+typedef struct {
+    int x, y;
+} Coord;
+typedef Coord Direction;
+
+Direction left;
+Direction right;
+Direction up;
+Direction down;
+
+typedef struct {
+    int maze[MAX_MAZE_X][MAX_MAZE_Y];
+    Coord size;
+    Coord position;
+    int marker;
+    Coord lastPosition;
+} Maze;
+
+void initialize_globals() {
+    left.x = -1; left.y = 0;
+    right.x = 1; right.y = 0;
+    up.x = 0; up.y = -1;
+    down.x = 0; down.y = 1;
+}
+
+Coord add(Coord c1, Coord c2) {
+    Coord res;
+    res.x = c1.x + c2.x; res.y = c1.y + c2.y;
+    return res;
+}
+
+Coord sub(Coord c1, Coord c2) {
+    Coord res;
+    res.x = c1.x - c2.x; res.y = c1.y - c2.y;
+    return res;
+}
+
+int equal(Coord c1, Coord c2) {
+    return c1.x == c2.x && c1.y == c2.y;
+}
+
+int not_equal(Coord c1, Coord c2) {
+    return !equal(c1, c2);
+}
+
+int set_room(Maze* m, int x, int y, int val) {
+    if (m != NULL && x < m->size.x && y < m->size.y) {
+        m->maze[x][y] = val;
+        return 1;
+    }
+    return 0;
+}
+
+int mark_here(Maze* m) {
+    if (!m) return ERROR;
+    return set_room(m, m->position.x, m->position.y, m->marker);
+}
+
+int move_to_start(Maze* m) {
+    if (!m) return ERROR;
+    m->position.x = 1;
+    m->position.y = 0;
+    return 1;
+}
+
+void load_maze(Maze* m, const char* filename) {
+    FILE * pFile;
+    int c;
+    int x = 0, y = 0;
+    pFile=fopen (filename,"r");
+    if (pFile==NULL) {
+        perror ("Error opening file");
+    } else {
+        do {
+            c = fgetc (pFile);
+            if (x >= MAX_MAZE_X || y >= MAX_MAZE_Y) {
+                printf("error: maximum number of rows or columns exceeded. max x=%d, max y=%d.\n", MAX_MAZE_X, MAX_MAZE_Y);
+                exit(1);
+            }
+            if (c == '\n') {
+                if (x > 0) {
+                    if (m->size.x > 0 && m->size.x != x + 1) {
+                        printf("error: Not all rows have the same length. check row %d.\n", y + 1);
+                        exit(1);
+                    } else {
+                        m->size.x = x + 1;
+                    }
+                    x = 0;
+                    ++y;
+                }
+            } else if (c == ',') {
+                ++x;
+            } else if (c == '0' || c == '1') {
+                m->maze[x][y]=c-'0';
+            }
+        } while (c != EOF);
+        m->size.y = y;
+        fclose (pFile);
+    }
+}
+
+void print_maze(Maze* m) {
+    int x, y;
+    
+    for (y = 0; y < m->size.y; ++y) {
+        for (x = 0; x < m->size.x; ++x) {
+            if (m->maze[x][y] > 0) {
+                printf("%d", m->maze[x][y]);
+            } else if (m->maze[x][y] == 0) {
+                printf(".");
+            } else {
+                printf("X");
+            }
+        }
+        printf("\n");
+    }
+}
+
+int try_move(Maze* m, Coord d) {
+    if (!m) return ERROR;
+    
+    Coord newPosition = add(m->position, d);
+    
+    if (newPosition.x < 0 || newPosition.x >= m->size.x ||
+        newPosition.y < 0 || newPosition.y >= m->size.y) {
+        return 0; // invalid position
+    }
+    
+    return m->maze[newPosition.x][newPosition.y];
+}
+
+int move(Maze* m, Coord d) {
+    if (!m) return ERROR;
+    
+    int success = 0;
+    Coord newPosition = add(m->position, d);
+    
+    if (try_move(m, d)) {
+        m->lastPosition = m->position;
+        m->position = newPosition;
+    
+        success = m->maze[m->lastPosition.x][m->lastPosition.y];
+        m->maze[m->position.x][m->position.y] = m->marker;
+    }
+    
+    return success;
+}
+
+int road_count(Maze* m) {
+    if (!m) return ERROR;
+    
+    int i, sum, p;
+    
+    for (sum = 0, i = -1; i < 2; i+=2) {
+        p = m->position.x + i;
+        if (p >= 0 && p < m->size.x) {
+            sum+=(m->maze[p][m->position.y] != 0)?1:0;
+        }
+        p = m->position.y + i;
+        if (p >= 0 && p < m->size.y) {
+            sum+=(m->maze[m->position.x][p] != 0)?1:0;
+        }
+    }
+    
+    return sum;
+}
+
+int is_cross_roads(Maze* m) {
+    if (!m) return ERROR;
+    
+    return road_count(m) > 2;
+}
+
+int is_dead_end(Maze* m) {
+    if (!m) return ERROR;
+    
+    return road_count(m) <= 1;
+}
+
+int is_next_to_wall(Maze* m) {
+    if (!m) return ERROR;
+    
+    if (m->position.x == 0 || m->position.x == m->size.x - 1 ||
+        m->position.y == 0 || m->position.y == m->size.y - 1) {
+        return 1;
+    }
+    
+    return 0;
+}
+
+// mark paths
+int solve_maze(Maze* m) {
+    if (!m) return ERROR;
+    
+    int path_marker = 1;
+    int dead_end_path_marker = -1;
+    Coord direction;
+    int pathCost, lowestPathCost;
+    int isDeadEnd = 0;
+    
+    m->marker = path_marker;
+    mark_here(m);
+    move(m, down);
+    
+    while(!is_next_to_wall(m)) {
+        Coord back = sub(m->lastPosition, m->position);
+        if (is_cross_roads(m)) {
+            if (!isDeadEnd) {
+                m->marker = ++path_marker;
+                mark_here(m);
+            } else {
+                isDeadEnd = 0;
+                m->marker = --path_marker;
+                mark_here(m); // update this marker
+            }
+        } else if (is_dead_end(m)) {
+            isDeadEnd = 1;
+            m->marker = dead_end_path_marker;
+            mark_here(m);
+            move(m, back);
+            continue;
+        }
+        
+        lowestPathCost = pathCost = try_move(m, left);
+        if (not_equal(left, back) && pathCost > 0) {
+            direction = left;
+        }
+        pathCost = try_move(m, right);
+        if (not_equal(right, back) && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = right;
+            }
+        }
+        pathCost = try_move(m, up);
+        if (not_equal(up, back) && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = up;
+            }
+        }
+        pathCost = try_move(m, down);
+        if (not_equal(up, back) && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = down;
+            }
+        }
+        move(m, direction);
+    }
+    
+    return 1;
+}
+
+// Go to highest valued path at intersections
+int print_solution(Maze* m) {
+    if (!m) return ERROR;
+    
+    int path_marker = 1;
+    Coord direction;
+    int pathCost, highestPathCost;
+    
+    move_to_start(m);
+    m->marker = path_marker;
+    mark_here(m);
+    printf("Solution: (%d,%d)", m->position.x, m->position.y);
+    move(m, down);
+    
+    while(!is_next_to_wall(m)) {
+        Coord back = sub(m->lastPosition, m->position);
+        
+        highestPathCost = pathCost = try_move(m, left);
+        if (not_equal(left, back) && pathCost > 0) {
+            direction = left;
+        }
+        pathCost = try_move(m, right);
+        if (not_equal(right, back) && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = right;
+            }
+        }
+        pathCost = try_move(m, up);
+        if (not_equal(up, back) && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = up;
+            }
+        }
+        pathCost = try_move(m, down);
+        if (not_equal(down, back) && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = down;
+            }
+        }
+        
+        printf("(%d,%d)", m->position.x, m->position.y);
+        move(m, direction);
+    }
+    
+    printf("(%d,%d)\n", m->position.x, m->position.y);
+    printf("Exit at (%d, %d)\n", m->position.x, m->position.y);
+    
+    return 1;
+}
+
+int main() {
+    Maze maze;
+    
+    initialize_globals();
+
+    move_to_start(&maze);
+    load_maze(&maze, "maze.txt");
+    solve_maze(&maze);
+    print_solution(&maze);
+    
+    return 0;
+}
+

File C++ Solution/README.txt

+MAZE SOLVER
+
+PROBLEM:
+========
+Write a C or C++ program to be a virtual maze walking mouse for a two dimensional maze of X columns and Y rows.
+int maze[x][y];
+maze[?][?] == 1 means empty corridor.
+maze[?][?] == 0 means solid wall.
+ 
+The entry point is fixed from (1,0); (i.e. maze[1][0] will always be 1).
+The exit point is a 1 at the edge of the maze.
+The output of the program is a set of (x,y) coordinates that leads from entry (1,0) to (?,?) the exit.
+ 
+Example:
+0,1,0,0,0,0,0,0,0,0,0
+0,1,1,1,1,1,1,0,0,0,0
+0,0,0,1,0,0,1,1,0,0,0
+0,0,1,1,0,0,1,0,0,0,0
+0,0,0,0,0,1,1,1,1,0,0
+0,0,1,1,1,1,0,0,1,0,0
+0,0,0,1,0,0,0,0,0,0,0
+Entry at (1,0)
+ 
+Virtual mouse should print out below:
+Solution: (1,0)(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(6,2)(6,3)(6,4)(5,4)(5,5)(4,5)(3,5)(3,6)
+Exit at (3,6)
+
+Instructions:
+·         Follow the K.I.S.S. concept.
+·         Readability first, performance next.(i.e. the more thinking needed to understand the code the lower the score).
+·         Minimum C++ approach (for readability and portability), keep it simple.(i.e. the more C++ specific expression the lower the score).
+·         Code should for the most part be self documenting.
+
+
+SOLUTION:
+=========
+The solver works by eliminating dead ends and is not optimized to find 
+the shortest path (KISS requirement).
+
+There is a makefile included so run "make" to compile the program.
+
+The maze.txt file contains the assigned maze and will be loaded and solved each
+time the program is run. Alter it to test different mazes. Note, that the format
+of the file must remain "the same", i.e. there must be no comma at the end of a line, 
+only 0's, 1's and ',' are allowed (though whitespace should be ignored this was not 
+tested) and there must be a new line at the end of the file.
+
+Kind regards
+
+Lazar Sumar

File C++ Solution/main.cpp

+/* Author: Lazar Sumar
+ * Date 27th March 2012
+ */
+#include "maze.h"
+#include "mouse.h"
+
+int main() {
+    Maze maze;
+    Mouse mouse;
+    
+    maze.load("maze.txt");
+    mouse.setMaze(&maze);
+    mouse.solveMaze();
+    mouse.printSolution();
+    return 0;
+}

File C++ Solution/makefile

+CC=g++
+CFLAGS=-Wall
+LIB=
+EXEC=maze_solver
+
+$(EXEC): main.cpp maze.o mouse.o
+	$(CC) $(CFLAGS) -o $(EXEC) main.cpp maze.o mouse.o
+    
+maze.o: maze.h maze.cpp
+	$(CC) $(CFLAGS) -c maze.cpp
+
+mouse.o: mouse.h mouse.cpp
+	$(CC) $(CFLAGS) -c mouse.cpp

File C++ Solution/maze.cpp

+#include "maze.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+Coord left(-1, 0);
+Coord right(1, 0);
+Coord up(0, -1);
+Coord down(0, 1);
+
+
+Maze::Maze() {
+    position = Coord(1,0);
+    lastPosition = Coord(1,0);
+    marker = 1;
+}
+    
+void Maze::load(const char* filename) {
+    FILE * pFile;
+    int c;
+    int x = 0, y = 0;
+    pFile=fopen (filename,"r");
+    if (pFile==NULL) {
+        perror ("Error opening file");
+    } else {
+        do {
+            c = fgetc (pFile);
+            if (x >= MAX_MAZE_X || y >= MAX_MAZE_Y) {
+                printf("error: maximum number of rows or columns exceeded. max x=%d, max y=%d.\n", MAX_MAZE_X, MAX_MAZE_Y);
+                exit(1);
+            }
+            if (c == '\n') {
+                if (x > 0) {
+                    if (size.x > 0 && size.x != x + 1) {
+                        printf("error: Not all rows have the same length. check row %d.\n", y + 1);
+                        exit(1);
+                    } else {
+                        size.x = x + 1;
+                    }
+                    x = 0;
+                    ++y;
+                }
+            } else if (c == ',') {
+                ++x;
+            } else if (c == '0' || c == '1') {
+                maze[x][y]=c-'0';
+            }
+        } while (c != EOF);
+        size.y = y;
+        fclose (pFile);
+//        printf("Loaded %d x %d maze (rows x columns).\n", size.y, size.x);
+    }
+}
+
+void Maze::print() const {
+    int x, y;
+    
+    for (y = 0; y < size.y; ++y) {
+        for (x = 0; x < size.x; ++x) {
+            if (maze[x][y] > 0) {
+                printf("%d", maze[x][y]);
+            } else if (maze[x][y] == 0) {
+                printf(".");
+            } else {
+                printf("X");
+            }
+        }
+        printf("\n");
+    }
+}
+
+int Maze::setPathMarker(int marker) {
+    return this->marker = marker;
+}
+
+int Maze::tryMove(Coord d) const {
+    Coord newPosition = position + d;
+    if (newPosition.x < 0 || newPosition.x >= size.x ||
+        newPosition.y < 0 || newPosition.y >= size.y) {
+        return 0; // invalid position
+    }
+    return maze[newPosition.x][newPosition.y];
+}
+
+int Maze::move(Coord d) {
+    int success = 0;
+    Coord newPosition = position + d;
+    
+    if (tryMove(d)) {
+        lastPosition = position;
+        position = newPosition;
+    
+        success = maze[lastPosition.x][lastPosition.y];
+        maze[position.x][position.y] = marker;
+    }
+    
+    return success;
+}
+
+void Maze::moveToStart() {
+    position = Coord(1, 0);
+}
+
+void Maze::moveTo(Coord c) {
+    position = c;
+}
+
+void Maze::markPath() {
+    maze[position.x][position.y] = marker;
+}
+
+int Maze::roadCount() const {
+    int i, sum, p;
+    
+    for (sum = 0, i = -1; i < 2; i+=2) {
+        p = position.x + i;
+        if (p >= 0 && p < size.x) {
+            sum+=(maze[p][position.y] != 0)?1:0;
+        }
+        p = position.y + i;
+        if (p >= 0 && p < size.y) {
+            sum+=(maze[position.x][p] != 0)?1:0;
+        }
+    }
+    
+    return sum;
+}
+
+int Maze::isCrossRoads() const {
+    return roadCount() > 2;
+}
+
+int Maze::isDeadEnd() const {
+    return roadCount() <= 1;
+}
+
+Coord Maze::getSize() const {
+    return this->size;
+}
+
+Coord Maze::getPosition() const {
+    return this->position;
+}
+
+Coord Maze::getLastPosition() const {
+    return this->lastPosition;
+}
+
+int Maze::isNextToWall() const {
+    if (position.x == 0 || position.x == size.x - 1 ||
+        position.y == 0 || position.y == size.y - 1) {
+        return 1;
+    }
+    
+    return 0;
+}

File C++ Solution/maze.h

+/* Author: Lazar Sumar
+ * Date 27th March 2012
+ */
+#ifndef MAZE_H
+#define MAZE_H
+
+#define MAX_MAZE_X 1000
+#define MAX_MAZE_Y 1000
+
+class Coord {
+public:
+    int x, y;
+
+    Coord(int x = 0, int y = 0) : x(x), y(y) {}
+    Coord(const Coord& c) : x(c.x), y(c.y) {}
+    
+    Coord& operator=(const Coord& c) {
+        x = c.x; y = c.y;
+        return *this;
+    }
+    
+    bool operator==(const Coord& c) const {
+        return x == c.x && y == c.y;
+    }
+    
+    bool operator!=(const Coord& c) const {
+        return !(*this == c);
+    }
+    
+    Coord operator-(const Coord& c) const {
+        return Coord(x - c.x, y - c.y);
+    }
+    
+    Coord operator+(const Coord& c) const {
+        return Coord(x + c.x, y + c.y);
+    }
+};
+
+typedef Coord Direction;
+
+extern Coord left;
+extern Coord right;
+extern Coord up;
+extern Coord down;
+
+class Maze {
+    int maze[MAX_MAZE_X][MAX_MAZE_Y];
+    Coord size;
+    Coord position;
+    int marker;
+    Coord lastPosition;
+    
+    int roadCount() const;
+public:
+    Maze();
+    
+    void load(const char* filename);
+    void print() const;
+    
+    int setPathMarker(int marker);
+    
+    int tryMove(Direction d) const;
+    int move(Direction d);
+    void moveToStart();
+    void moveTo(Coord c);
+    void markPath();
+    int isCrossRoads() const;
+    int isDeadEnd() const;
+    
+    Coord getSize() const;
+    Coord getPosition() const;
+    Coord getLastPosition() const;
+    
+    int isNextToWall() const;
+};
+
+#endif

File C++ Solution/maze.o

Binary file added.

File C++ Solution/maze.txt

+0,1,0,0,0,0,0,0,0,0,0
+0,1,1,1,1,1,1,0,0,0,0
+0,0,0,1,0,0,1,1,0,0,0
+0,0,1,1,0,0,1,0,0,0,0
+0,0,0,0,0,1,1,1,1,0,0
+0,0,1,1,1,1,0,0,1,0,0
+0,0,0,1,0,0,0,0,0,0,0

File C++ Solution/maze_solver

Binary file added.

File C++ Solution/mouse.cpp

+/* Author: Lazar Sumar
+ * Date 27th March 2012
+ */
+#include "mouse.h"
+#include <stdio.h>
+
+Mouse::Mouse() {
+    maze = NULL;
+}
+
+void Mouse::setMaze(Maze* maze) {
+    this->maze = maze;
+}
+
+void Mouse::solveMaze() {
+    int path_marker = 1;
+    int dead_end_path_marker = -1;
+    Coord direction;
+    int pathCost, lowestPathCost;
+    int isDeadEnd = 0;
+    
+    maze->setPathMarker(path_marker);
+    maze->markPath();
+    maze->move(down);
+    
+    while(!maze->isNextToWall()) {
+        Coord back = maze->getLastPosition() - maze->getPosition();
+        if (maze->isCrossRoads()) {
+            if (!isDeadEnd) {
+                maze->setPathMarker(++path_marker);
+                maze->markPath();
+            } else {
+                isDeadEnd = 0;
+                maze->setPathMarker(--path_marker);
+                maze->markPath(); // update this marker
+            }
+        } else if (maze->isDeadEnd()) {
+            isDeadEnd = 1;
+            maze->setPathMarker(dead_end_path_marker);
+            maze->markPath();
+            maze->move(back);
+            continue;
+        }
+        
+        lowestPathCost = pathCost = maze->tryMove(left);
+        if (left != back && pathCost > 0) {
+            direction = left;
+        }
+        pathCost = maze->tryMove(right);
+        if (right != back && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = right;
+            }
+        }
+        pathCost = maze->tryMove(up);
+        if (up != back && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = up;
+            }
+        }
+        pathCost = maze->tryMove(down);
+        if (up != back && pathCost > 0) {
+            if (lowestPathCost <= 0 || lowestPathCost > pathCost) {
+                lowestPathCost = pathCost;
+                direction = down;
+            }
+        }
+        maze->move(direction);
+    }
+}
+
+void Mouse::printSolution() const {
+    int path_marker = 1;
+    Coord direction;
+    int pathCost, highestPathCost;
+    
+    maze->moveToStart();
+    maze->setPathMarker(path_marker);
+    maze->markPath();
+    printf("Solution: (%d,%d)", maze->getPosition().x, maze->getPosition().y);
+    maze->move(down);
+    
+    while(!maze->isNextToWall()) {
+        Coord back = maze->getLastPosition() - maze->getPosition();
+        
+        highestPathCost = pathCost = maze->tryMove(left);
+        if (left != back && pathCost > 0) {
+            direction = left;
+        }
+        pathCost = maze->tryMove(right);
+        if (right != back && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = right;
+            }
+        }
+        pathCost = maze->tryMove(up);
+        if (up != back && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = up;
+            }
+        }
+        pathCost = maze->tryMove(down);
+        if (down != back && pathCost > 0) {
+            if (highestPathCost < pathCost) {
+                highestPathCost = pathCost;
+                direction = down;
+            }
+        }
+        
+        printf("(%d,%d)", maze->getPosition().x, maze->getPosition().y);
+        maze->move(direction);
+    }
+    
+    Coord mazeExit = maze->getPosition();
+    printf("(%d,%d)\n", mazeExit.x, mazeExit.y);
+    printf("Exit at (%d, %d)\n", mazeExit.x, mazeExit.y);
+}

File C++ Solution/mouse.h

+/* Author: Lazar Sumar
+ * Date 27th March 2012
+ */
+#ifndef MOUSE_H
+#define MOUSE_H
+
+#include "maze.h"
+#include <stdlib.h>
+
+class Mouse {
+    Maze* maze;
+public:
+    Mouse();
+    void setMaze(Maze* maze);
+    void solveMaze();
+    void printSolution() const;
+};
+
+#endif

File C++ Solution/mouse.o

Binary file added.