Description
Problem
You are in charge of directing water through an aqueduct from a source to several bath houses. The aqueduct consists of stations connected by ramps that carry water. The stations are laid out in an m x n grid, in which the source station S is located at position (0,0). From any station located at position (x,y), where 0 <= x < m and 0 <= y < n, there is a ramp leading to the station at position (x-1,y), (x+1,y), (x,y-1), and (x,y+1), so long as the target station lies inside the grid. Each station is at some height above the ground, and the time it takes for water to move along a ramp from station (x,y) to station (x’,y’) is
time((x,y),(x’,y’)) = max(-1, 1 + (height(x’,y’) – height(x,y))).
Given a set B = {b_1 = (x_1,y_1),…,b_n = (x_n,y_n)} of positions of stations that supply water to baths, a supply path is a (not necessarily simple) path in the aqueduct that starts from the source station S, visits every station in B, and ends at when it reaches the last station in B that it has not yet visited. The cost of a supply path is the total time it takes water to move along this path. Note that if such a path visits station (x,y), followed by station (x+1,y), followed by station (x,y), then the time it takes for water to move between these stations is
time((x,y),(x+1,y)) + time((x+1,y),(x,y))
Goal: given the set B, compute the minimum cost of any supply path.
Note: The path should end in one of the stations B
Submission/Grade Details
● Submit to Canvas a zip file named UFID_4533PA1_Lang, replacing UFID with your UFID and Lang with the programming language you used (Py, C, or Cpp). The zip file should contain your write-up and all files necessary to run your code. Further details below.
● (30 points) Write-up: write 1-2 paragraphs explaining your solution. You should include the definitions of dynamic programming problems you designed, and their recursive equations. Also, briefly discuss the time-complexity of your algorithm.
● (70 points) Program: submit the correct option below for your language
○ C/C++ – makefile and source code. To test this, we will run the commands (with grid.txt in the folder).
make
./aqueduct
○ Python – aqueduct.py. We will test this using (with grid.txt in the folder):
py ./aqueduct.py
Program Input Details
Your program should read a file called “grid.txt” in the root directory (where the program is running). This file contains the following information:
1. Number of rows and columns in the grid – e.g. 5, 5
2. Station height, x-coordinate, and y-coordinate – e.g., 5, 1, 2. Each station is written on its own line. The stations are listed row by row, starting with the station at position (0,0). For example:
2, 0, 0
4, 1, 0
…
1, m, 0
7, 0, 1
…
3. x-coordinate and y-coordinate of the station “S” on its own line.
4. x-coordinate and y-coordinate of the stations in B, each written on their own line.
For example:
3, 2
4, 5
…
Expected output
“pathLength.txt” file with the path length as an integer
You do NOT have to find the path itself
Constraints
Number of stations in B will be between 1 and 100
The height of a station will be an integer between 1 and 25
The dimensions of the grid will be between 1 and 100
Examples
Here is a simple example if grid.txt looks like this:
3, 3
7, 0, 0
5, 1, 0
1, 2, 0
1, 0, 1
3, 1, 1
4, 2, 1
6, 0, 2
5, 1, 2
5, 2, 2
0, 0
0, 2
The output solution is 3.
Please find a more complex example grid and corresponding answer in a folder on the assignment page
