Hacker Challenge: Prison Break

The prison break problem

The prison break problem constitutes a matrix comprising 0s, 1s, and a single entry of 2. The 0 represents moveable space, 1 represents the wall, and 2 represents the prisoner. The prisoner can pass through 0s but not 1s. Solving the prison break problem means figuring out whether the prisoner is trapped inside the room (made up of 1s), and if so, then is there a way out?

For this problem, we assume the following:

1. The matrix has a lot of moveable space (a lot of 0s).

2. The matrix contains a rectangular room made up of walls (a shape made of 1s).

3. The room may not be closed – meaning there may be one or more moveable spaces (0) in the boundary of the rectangular room.

4. The prisoner (represented by 2) may be inside or outside the room.

Task

Write a program that reads a matrix (from a file) with a max size of 40 x 80 and should print one of the following results:

1. The prisoner is already free which means that the prisoner is outside the rectangular prison.

2. The prisoner is trapped forever, meaning that the prisoner is inside the prison, and the walls have no holes.

3. The prisoner is trapped but can escape — the prisoner is inside the prison, which is breakable (there's at least one hole in the rectangular wall).

Examples

Your implementation

Understand the format of Maps.txt and write your code in the widget below.

Implementation walk-through

From here onward, we provide you with a guide on implementing the solution for the prison break problem that you can follow along in the playground above. The guide contains both an explanation and the implementation of the functions. You should look at the solution if you are completely stuck. Best of luck!

The main() function

As you can see in Maps.txt, we have several test cases followed by different maps with different scenarios.

We need the following variables:

After reading noOfMaps, we need to check for each scenario. Hence, we iterate the loop noOfMaps times.

In each iteration, we'll do the following:

1. Load a 2-D map: Call the function load2DArray() that loads the dimension of the 2D map followed by loading the map in aPrisonMap, rows, and cols.

2. Print the 2-D map: Call the print2DArray() function so the program can be tested to ensure that all the maps are loaded correctly.

3. Write the prison_BreakSolver() function that takes aPrisonMap, rows, and cols as arguments. Let's discuss this function in the next section of this lesson.

Instruction: Write the code in the playground to complete the main() function, including the above first 2 mentioned steps load2DArray() and print2DArray() functions. Your main program should only load the prison map and print it on the screen. Try yourself, if needed, then look at the solution below.

Working of the prison_BreakSolver() function

Given that we have a map in a two-dimensional array, aPrisonMap with its dimension rows and cols, we need to figure out in this function whether the prisoner is already free, imprisoned forever, or prisoned but can break it.

Let's dig down what should be the steps involved in solving this challenge:

Step 0: Memory requirement

We need rectangleStartR, rectangleStartC, rectangleEndR, and rectangleEndC, for storing the prison's boundary. Similarly, for storing the prisoner's position, we need to have prisonerR, and prisonerC. Also, we need to have two more variables, isFree and isBreakable. The isFree variable determines whether the prisoner is outside the prison or not. The isBreakable variable determines if the prison is breakable. Hence, we will have the following memory:

Step 1: Find the prison's boundary positions.

In this step, we'll assign rectangleStartR and rectangleStartC as the starting point (the top left corner) of the prison and rectangleEndR and, rectangleEndC as an endpoint (the right bottom corner) of the prison. For this purpose, we'll make a findWallBoundary() function, which will receive each of these parameters as references (as it will write the locations of the two corners in the corresponding variables).

Here is the prototype of the function and the function call:

Step 2: Find the prisoner's position.

We'll find the prisoner's location by searching for 2 in the grid. For this purpose, we'll pass aPrisonMap in findPrisonerLocation() function, which will store the prisoner's location in prisonerR, and prisonerC reference variables (received as parameters). Here is the prototype of the function and the function call:

Step 3: Find out if the prisoner is already free

The isPrisonerAlreadyFree() function will check whether the prisoner's location is outside the boundaries or not. If the prisoner is free, this function will return 1, otherwise, 0.

Here is the prototype of the function and the function call:

Step 4: Find out if the prison is breakable

In this step, we'll figure out whether the prison room has any space. For that, we need to make a function, isPrisonBreakable(), that will check if the prisoner can escape from the boundaries. This function will return true if the prison can break it. Else, return false. This function must work on the aPrisonMap and prisoner's boundary points such as rectangleStartR, rectangleStartC, rectangleEndR, and rectangleEndC. The step should look like this:

Step 5: Display the solution message

In this step, depending on the value received in Free and Breakable, we will decide what to display.

Complete implementation of the main-flow of prison_BreakSolver()

Here is what the complete implementation of prison_BreakSolver() looks like:

Instruction: Add the implementation in your playground.

Implementing all step functions of prison_BreakSolver()

First, we need to check the start boundary of a wall from the top and the wall end boundary from the bottom. These two points will help us determine whether the wall is breakable and whether the prisoner is already outside or inside.

Step 1: Implementing the FindWallBoundary() function

In this function, we will have two nested loops.

• The first nested loop traverses each index from the start of the map:

  • For each row, ri from 0 onwards.

    • For each column, ci, from 0 onwards.

      • We check whether the value at aPrisonMap[ri][ci] is 1 or not. Whenever we find 1, save the location (ri, ci) in rectangleStartR and rectangleStartC. As soon as we find the top corner of the prison, we need to end this nested loop.

Now, we need to find the end location of the prison.

• In the same way, the second nested loop traverses each index from the bottom of the map:

  • For each row, ri, from rows-1 to backward.

    • For each column, ci, from cols-1 to backward.

      • Checks whether the number is 1 or not. Whenever we find 1, store the location of the row and column in rectangleEndR and rectangleEndC.

Instruction: Write the code for FindWallBoundary() and test it by displaying inside the prison_BreakSolver() to see if, for each map, the rectangular walls are correctly found.Only look at the hint below if you are stuck.

Step 2: Implementing the findPrisonerLocation() function

Now, we'll find the location of the prison. How can we do that?

As discussed, 2 represents the prison on the map. So we will traverse the map from the top and compare each map value, to see if that value is 2. If we find 2 on the map, store the location of the prison in prisonerR and prisonerC.

Instruction: Write the code of the findPrisonerLocation() function, in your implementation. Test it by printing on the console if, for all the cases, the prisoner's location is correctly found.

Step 3: Implementing the isPrisonerAlreadyFree() function

We have a prison location, start and end of the prison. Now, we can check whether the prison is located inside the wall boundaries or not. To check this, we will create a isPrisonerAlreadyFree() function in which we'll compare the prison row and column with the start and endpoint of the prison. If the prisoner is inside the boundaries, this function will return false, otherwise, true.

Instruction: Write the code of the isPrisonerAlreadyFree() function in your implementation. Test it by printing a proper message whether, for each case, the prisoner is inside the prison or already free.

Step 4: Implementing the isPrisonBreakable() function

Now, we want to check whether the prison is breakable or not. How can we do that?

We have to compare each boundary value to check whether the walls are breakable. If any value on the boundary is 0, the prisoner can easily escape.

Let's create a isPrisonBreakable() function in which we have two loops.

• The first loop will start from the rectangleStartC and end on rectangleEndC. Inside the loop, we'll simultaneously compare the top and bottom rows to see whether these rows have a 0.

• The second loop will start from the rectangleStartR and end on rectangleEndR. Inside the loop, we'll simultaneously compare the vertical walls to determine whether these columns have a 0.

• In case of 0, this function will return true, otherwise, return false.

Instruction: Write the code of the isPrisonBreakable() function in your implementation. Test it by printing a proper message about whether, for each case, the prison is breakable or not.

Now, we have the complete implementation. Our program should print the proper message for every puzzle properly.

Complete implementation of prison break

Here is the complete implementation in case you had difficulty integrating each step above. You can take guidance from here.