MIT Problem Set Solution

As part of my degree program I had to do a coursework which had a Problem Set to be Solved which was given as part of the Introduction to Algorithms module of Electrical Engineering and Computer Science course taught at the prestigious Massachusetts Institute of Technology (MIT).

The problem set I had to solve is available in this PDF as Problem Set 8-2 Video Game Design.

In short the problem is that there is a Game with Rooms and Corridors connecting those rooms. Each Room will have either a monster or a life potion. Encountering the monster decreases life and drinking life potion increases life. The objective of the algorithm was to find the minimum life points required to start the Game.

I used Floyd and Warshall Algorithm as the base to solve the problem and modified it to get the output. I had the following assumptions in place;

• Maximum life points a player can have is 100. If a maze requires more than 100 at the start of the maze to finish the maze that maze is not r-admissible.
• The mazes will only have a maximum of 100 rooms or less. This is because the player will be frustrated to finish the maze if it is longer than that.
• From start room there is at least two paths to the destination.

Following are the two part flow chart diagrams of the algorithm.



Implementation of the algorithm is seen below;

public double RAdmissible() {

      if (maze != null) {

          // Variable to store the result

          double r = 0d;

          // Constant to store No of vertices in the Maze

          final int MAZE_LENGTH = maze.getSize();

          // Variable to store Adjacency Matrix of the Maze

          double matrix[][] = maze.getAdjacencyMatrix();

          // Variable to store Predecessor of the Longest path

          double pred[][] = new double[MAZE_LENGTH][MAZE_LENGTH];

          /*

           *

           * If there is a positive cycle

           * then with minimum of r = 1 maze is navigable

           * Else have to find the least costly path from start to end of the maze

           *

           *

           */

          // Variable to store whether this maze contains a positive cycle

          boolean positiveCycle = false;

          /*

           * Modified version of Floyd-Warshall Algorithm. Runs at O(N^3).

           * This is used to find the least cost path from start to finish

           * and to find whether there are positive cycles in the maze.

           */

          for (int k = 0; k < MAZE_LENGTH && !positiveCycle; k++) {                 

               for (int i = 0; i < MAZE_LENGTH && !positiveCycle; i++) {                     

                     for (int j = 0; j < MAZE_LENGTH && !positiveCycle; j++) {                         if (matrix[k][j] != Double.NEGATIVE_INFINITY &&                                 matrix[i][k] + matrix[k][j] > matrix[i][j]) {

                          // Assigning the new least cost path

                          matrix[i][j] = matrix[i][k] + matrix[k][j];

                          // Assigning the new predecessor

                          pred[i][j] = k;

                          /*

                           * If i == j then it is a cycle.

                           * But we have to determine whether it is a positive cycle.

                           * For that we check whether the new path is not Negative Infinity and it is positive.

                           */

                          if (i == j && matrix[i][j] != Double.NEGATIVE_INFINITY && matrix[i][j] > 0) {

                              positiveCycle = true;

                          }

                      }

                  }

              }



              // Minimum r is the cost to go from start to finish

              double minimumR = matrix[0][MAZE_LENGTH - 1];

              // If Minimum r is Negative Infinity then cost from start to next to finish is taken

              minimumR = minimumR == Double.NEGATIVE_INFINITY ? matrix[0][MAZE_LENGTH - 2] : minimumR;

              /*

               * If a positive cycle is available then Minimum r is 1

               * This is because life points necessary to safely navigate

               * the maze can be gained by going through the positive cycle.

               *

               * If no positive cycle is found then

               * If Minimum r is Negative or Zero the Minimum r should be

               * one greater than the absolute value of Minimum r.

               *

               * If Minimum r is Positive then

               * Minimum r is 1 this is because there is safe path

               * from start to end where the player's lifepoints will

               * never become 0 or less.

               *

               */

              minimumR = positiveCycle ? 1.0 : minimumR <= 0 ? abs(minimumR) + 1.0 : 1.0;                 /*   

                              * If Minimum r is greater than 100 then                          * r is 0 which means there is no safe path in the maze.                         *

                              * Note : This is based on the assumption that a player can have a maximum of         * 100 life points.                  

                              */

              r = minimumR > 100 ? 0 : minimumR;

          }

          // Return the Minimum r

          return r;

      } else {

          throw new IllegalStateException("Maze is invalid");

      }

  }

The Maze is a Adjacency Matrix implementation with Two Dimensional Double array. I used the following maze designs to test the algorithm.



Many couldn't finish this task in my batch and I was awarded highest marks (91) for the coursework.