[SOLVED] python Programming (G54PRG) 3rd exercise

Programming (G54PRG) 3rd exercise
Thorsten Altenkirch and Isaac Triguero October 28, 2019
Number of Paths on a Grid with restrictions
You are asked to implement two recursive functions to compute the number of shortest paths (nsp), and the total number of paths (np) in a squared grid with y rows and x columns. For both functions, you can assume that the target point is always at coordinates (0,0). For simplicity, we are going to stick to a squared grid, with the same number of rows and columns (so rectangles are not allowed!).
To make it a bit more interesting: Inside the square is a smaller square which a path is not allowed to enter.
In the figure below, you can find an example of a grid of size 5, with a inner grid of size 3.
Figure 1: Grid with limitations sizeGrid = 5, innerX = 1, sizeInnerGrid = 3. Solution for nsp(5, 1, 3) and np(5, 1, 3); only two paths are actually allowed.
If we solve this grid with both nsp or np, the answer should always be 2 since there are only 2 paths that dont enter the inner square.
1

Both functions have three input parameters:
sizeGrid: Size of the grid (i.e. 3, indicates a 33 grid, coordinates (0,0) to coordinates (2,2)).
inX: Bottom-left coordinate (InX,InX) of the inner grid.
inSize: Size of the inner grid. This should be in the range (0, sizeGrid
1).
Your solution should take care of inconsistent inputs (e.g. negative numbers or inner grid larger than outer grid). Also, if the inner grid covers (0,0) or (sizeGrid 1, sizeGrid 1), both functions should return no paths!
Figure 2: Grid with sizeGrid = 5, innerX = 0, sizeInnerGrid = 1. The inner grid is at the origin, so that, it impossible to get there!
Note that it is allowed to have an inner grid of size 0, which would mean that there are no restrictions, and therefore, this should behave exactly as the example we gave in class for the nsp function.
Below you can see a few results for both functions:
>> nsp(5,1,3)
2
>> nsp(2,0,0)
2
>> nsp(5,0,1)
0
>> nsp(5,4,1)
0
>> nsp(5,2,0)
70
2

>> nsp(5,2,1)
34
>> np(5,1,3)
2
>> np(2,0,0)
2
>> np(5,0,1)
0
>> np(5,4,1)
0
>> np(5,2,1)
1456
>> np(5,2,0)
8512
Hints/Advice:
You are allowed (and encouraged) to define extra functions to improve the quality of your code if necessary. For example, you could implement a function inside(y,x) that checks whether a point is not within the inner squared grid and within the outer grid.
Define first the nsp function based on the one we implemented during the lecture.
Implement the np function using recursion and backtracking. When you find a solution you dont output it but just increase a counter and back- track.
To get full marks:
The code should be as simple as possible and you should use comments to explain how it works.
You should use recursion (and backtracking for the np function).
You are free to use your favourite Python IDE or the jupyter notebook. Once you have completed your program, name your code as ex03.[py|ipynb], and submit it on Moodle. Then, you can demonstrate it in the lab.
Important notes:
Use only the operations that have been introduced in the lectures. Make sure you note down the name of the demonstrator.
We will not give you the marks immediately.
Submission deadline: 12th of November.
Demo deadline: 25th of November.
3