Lab Assignment 2

The mars rover

Due Date (a two-week LA)
Sections(540,543,544,545,951)	2/12/21 @ 11:59pm

Concepts

• Review of CS1110 Concepts such as recursion Python.
• Use flow chart to design a function.

Problem Specification

Develop an application in Python to simulate a mars rover, that is a mission to find the safest path to a given destination since areas some in mars (world) are traversable while others may be dangerous due to high radiation exposure.

You are to write a Python program that creates a world (mars) as a 2D array of cells. The world size is N by N, so each column is size N and each row is size N. Each cell represents a possible location to which the rover can move. The rover cannot move to any cell directly (no jumping) unless it is directly to the right or directly below the current rovers location (cell). To illustrate, consider the following world of 4 by 4 cells:

0

1

X 2

3

y

0 1 2 3

1	4	1	0
1	1	0	1
0	1	1	2
0	0	1	1

Let me summarize the problems as follows:

1. Each value refers to an areas safety. 0 means the area is unsafe (deadly) and 4 means very safe.
2. The rover cant be in a location with zero safety and must be avoided.
3. The start location is always at location (0, 0) and the destination (goal) is always cell (N-1, N-1).
4. If all paths from start to destination involve a cell with 0 safety, then abort the mission.
5. There can be many safe paths as in the example above and these paths are:

(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)

(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)

(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)

(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) [Safest Path]

6. Each path has a total of safety points, which is the sum of all values in cells of their path. In the above example, the safest path has 11 safety points.
7. You must find the safest path for the rover to follow.

Design Requirements

Basic Structure

Define the world matrix (4x4) with exactly as the example above.

Your program should have the following functions:

1. A function (named is_safe) that takes the world matrix and the cell location (x and y) as parameters and returns true only if the cell is inside the world boundary and safe.

2. A recursive function (named find_paths) that takes the world matrix, start cell location (x and y), and an empty list. The list is used temporarily to construct a path while finding all the safe paths. This list consists of items and each item represent a cell with location (x and y) and safety points. This function returns true if one or more safe paths are found; otherwise returns false. Also, this function saves all possible safe paths found to a global list.

3. A function (named find_safest_path) that takes the world matrix as a parameter and calls function find_paths. Print the message This world is very dangerous, abort mission!!! if no safe paths are found. If more than one safe path is found (saved in the global list) then calculate safety points for all paths and print the safest path as a world matrix.

The output and interface should be neat and well-described. See the example provided in the Testing Phase section. All user input must be done with functions and the functions should clearly specify the range for each integer. A comment should be given for each function describing what the function does in terms of parameters and a return value.

Flowchart

You must design a flowchart for each function to illustrate how function is designed. Also, you need to design a flowchart to show how the driver code is designed in terms of how inputs are received, and the functions are called.

Implementation Phase

Using the pseudocode developed, write the Python code for your assignment. This is a two-week assignment.

Testing Phase

• Build your program incrementally, carefully testing each function as you go.

Example:

Using the world matrix in the above example, the output should be:

Safe paths:

[[0, 0, 1], [1, 0, 1], [1, 1, 1], [2, 1, 1], [2, 2, 1], [3, 2, 1], [3, 3, 1]]

[[0, 0, 1], [1, 0, 1], [1, 1, 1], [2, 1, 1], [2, 2, 1], [2, 3, 2], [3, 3, 1]]

[[0, 0, 1], [0, 1, 4], [1, 1, 1], [2, 1, 1], [2, 2, 1], [3, 2, 1], [3, 3, 1]]

[[0, 0, 1], [0, 1, 4], [1, 1, 1], [2, 1, 1], [2, 2, 1], [2, 3, 2], [3, 3, 1]]

Safest path: [[0, 0, 1], [0, 1, 4], [1, 1, 1], [2, 1, 1], [2, 2, 1], [2, 3, 2], [3, 3, 1]] with safety points: 11

Safest path in the world:

1 4 0 0

0 1 0 0

0 1 1 2

0 0 0 1

Additional Requirements

Coding Standards

You must adhere to all conventions in the CS 1120 Python coding standards (discussed in class and in the Lab). This includes the use of white spaces and indentations for readability, and the use of comments to explain the meaning of various functions and attributes. Be sure to follow the conventions also for naming variables, function parameters, and functions.

Assignment Submission

• Generate a .zip file that contains all your files including:
  • Program Files
  • Any input or output files
  • Flowchart.