Is this doable?Microsoft Word - assignment_1.docx 1 EG21007 – INTRODUCTION TO PROGRAMMING ...

Question

Is this doable?Microsoft Word - assignment_1.docx  1  EG21007 – INTRODUCTION TO PROGRAMMING  Assignment 1: Downhill path in a city  Due on: Sunday, 3rd November 2019 at 23:59  (for rules and submission instructions, please see page 6) Introduction  In this assignment your task is to write a Python 3 program that finds a downhill path on a  city map. For simplicity, we assume that all streets are straight, go either in the north-south  (vertical) or east-west (horizontal) direction and traverse the entire city. Every “north-south”  street crosses every “east-west” street and there are no intersections with more than two  streets meeting. We also assume that the number of horizontal streets is equal to the  number of vertical streets. An altitude is assigned to each intersection.   In this case, the map of the city can be represented as a matrix where each element of the  matrix represents the altitude of the intersection between one horizontal and one vertical  street. In other words, matrix element ?"# represents the altitude of the intersection of streets  ? and ?. In order to make things simple, we also assume so-called periodic boundary  conditions. That means that neighbours to the right of the last column are in the first column  of the matrix, etc. (Fig. 1). Fig. 1: City map is represented as a square matrix of size ? × ?. Each matrix element  represents the altitude of the intersection of two streets. Periodic boundary conditions are  assumed, as indicated by blue dashed lines with arrows. The traveller is allowed to move  downhill only. For example, the path marked with green arrows is allowed.    A traveller is allowed to move between neighbouring intersections downhill only. That is if the  traveller starts at the intersection (?, ?), in each step she is allowed to move to any of the  immediate neighbouring intersections (i.e., north, west, south or east) as long as the altitude   2  of the neighbouring intersection is lower than the altitude of her current location. For  example, if ?"+,,#  altitude of curr_pos return false (illegal uphill move)        otherwise return true (valid site)  3    In this assignment you need to complete the following tasks.   Tasks (100 points in total)  Note that partial credits will be given. The maximum number of points for a given task is  shown in brackets.  Task 1 (10 points)  Prompt the user (using Python’s input function) to enter the locations of starting and final  intersections. The intersections are given as a comma separated pairs of indices in the city  map matrix (the city map matrix is defined in Task 2 below).  Example:  Please enter the starting position : 2,2  Please enter the final position : 4,6  (This means that the traveller starts at the intersection of the 3rd horizontal and the 3rd  vertical street and needs to travel to the intersection of the 5th horizontal and 7th vertical  street. Remember, indices in Python start at 0!)  Task 2 (10 points)  Using Python’s input function, prompt the user to enter the name of a file containing a city  map matrix. Example of such file (called roads.dat) can be found on myDundee Assignment  1 page.  Read the content of this file and store it in a matrix (list of lists) called city_map. Make sure to  convert all the entries in the file to integers. Box 2: Pseudocode for the backtracking algorithm (function find_path)  find_path(pos, city_map, path, end)      pos à current position (intersection) on the map      city_map à matrix with altitudes of all intersections      path à list of all intersections visited during this path search      end à final intersection (traveller’s destination point)        append pos to path      if pos == end return true      repeat for new_pos in [north, west, south, east] from pos          if is_valid(new_pos, pos, city_map, path) and find_path(new_pos, city_map, path, end)  are both true              return true  (we can proceed in this direction)      pop pos from path      return false (we are stuck)   4  Task 3 (10 points)  Check whether the starting and the final position entered in Task 1 are valid, that is if they  are not outside the range of the total number of available streets. If the entry is invalid, print  an error message and exit.  Example:  Please enter the starting position : 87,12  Please enter the final position : 3,4  Please enter the grid file name : roads.dat  Error! Initial position (row) has to be between 0 and 21.  Task 4 (15 points)  Implement in Python 3 the function is_valid discussed in Box 1.  Task 5 (30 points)  Implement in Python 3 the function find_path described in Box 2. (This is the backtracking  algorithm.)  Task 6 (10 points)  If a path between the starting and the final intersections exists, print:    Found a path with XX steps.    (XX should be replaced by the actual number of steps in the path. Make sure to use proper  formats!)  If, however, no paths exist, print:  No suitable paths exist.  Example 1:  Please enter the starting position : 8,8  Please enter the final position : 3,4  Please enter the grid file name : roads.dat  Found a path with 12 steps.  Example 2:    Please enter the starting position :2,2  Please enter the final position :4,6  Please enter the grid file name : roads.dat  No suitable paths.  Task 7 (15 points)  If the path exists, print it in the following format (note that first four lines are printed by  previous tasks):    Please enter the starting position : 8,8  Please enter the final position : 3,4   5  Please enter the grid file name : roads.dat  Found a path with 12 steps.  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __ 11 12 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __ 10 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __   9 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  __ __ __   8 __ __ __ __ __ __ __ __ __ __ __

Microsoft Word - assignment_1.docx 1 EG21007 – INTRODUCTION TO PROGRAMMING Assignment 1: Downhill path in a city Due on: Sunday, 3rd November 2019 at 23:59 (for rules and submission instructions,...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment