Learning Outcomes
In this project you will demonstrate your understanding of dynamic memory and linked data structures, and extend your skills in terms of program design, testing, and debugging. You will also learn about graph labeling, and implement a simple shortest path mechanism (broadly speaking, the equivalent of bubblesort) in preparation for the more principled approaches that are introduced in comp20007 Design of Algorithms.
Path Planning
Any process that involves movement requires path planning. If we are at location A and wish to get to location B, we seek out and follow the “best” route between them, where “best” might be shortest (in terms of distance), or fastest (in terms of time taken), or cheapest (in terms of cost), or most scenic (in terms of appeal), or any weighted combination of those factors. This simple operation happens when we use Google maps, when we request quotes for airline tickets, and when we use our phone to request an Uber pickup.
Rectangular Grids
The founders of Gridsville were a mix of mathematicians and computer scientists. So when they discovered an uninhabited rectangular island off the south coast of Antarctica that they could use for their new colony, they planned a town using a rectangular grid of streets running north-south and eastwest. The diagram on the next page shows the seven north-south streets that they built, and the five east-west streets. Streets are named with digits (“0” to “6”) or letters (“a” to “e”), and intersections are labeled by their locations on the grid that results, for example, “4c”. (They were very boring people.)
Hundreds of years later, Gridsville is finally getting an Uber-like service, provided courtesy of the Gridsville City Council (gcc, get it?). But the Gridsville Council has remained very traditional and is insisting that pick-ups and drop-offs may only happen at street corners, that is, locations that are addressable via the grid coordinates. To help prepare for the arrival of the new service, the Council has approached a local software company, Algs-R-Fun, and has commissioned software to help manage the vehicle fleet. In particular, each time a customer (standing at an intersection in the grid) calls for a pickup, the “best available” car should be directed to go and pick them, where “best” means “the one that can get there the fastest”. The Council has already collected some travel-time measurements, and has recorded for each street, and for each city block on that street, how long it takes to travel in that direction along that block. For example, looking at Figure 1, travel east from “4c” to “5c” takes 34 seconds. Some streets cannot be used in some directions because they are one-way, and in that case the Council notes them as having a cost of 999 seconds. In the example in Figure 1, it is not possible to travel south from “4c” to get to “4d”.
Stage 1 - Reading the Data
Write a program that reads data from stdin in the format illustrated on the right-hand side of Figure 1 (see test2.txt linked from the LMS page for the full file) where the two numbers on the first line are always the grid dimensions, x and y (they will be 7 and 5 respectively for Gridsville, but might be different for other towns elsewhere in the world, and the GCC has bold ideas about being able to sell
Your program should build an internal representation of the specified intersections, using structs where ever appropriate. You may assume that all input files you will be provided with will be “correct”, according to the description given above, that all of the times will be strictly positive integers, and that there won’t be any tricksy-wicksy special cases introduced during the testing, nor any missing lines, nor any incorrect or wacky values in the lines; but you may not assume any upper limit on the number of streets involved in the city grid. Note also that the input values will be int, to keep it simple and avoid the rounding problems associated with floating point representations.
The grid size line and grid cost data lines are is followed by a third section of data in the input file: one or more grid references, one per line. You are also to read those grid references into a suitable data structure. Required output from this stage is the following summary:
mac: ass2-soln < test2.txt
S1: grid is 7 x 5, and has 35 intersections
S1: of 140 possibilities, 37 of them cannot be used
S1: total cost of remaining possibilities is 2115 seconds
S1: 3 grid locations supplied, first one is 4c, last one is 1e
You may use any data structure that you feel to be appropriate for the grid and cost data, including a two-dimensional array of struct, a one-dimensional array of struct, or a linked structure. For what it’s worth, my sample solution uses a one-dimensional array of struct as the storage component for the city grid and the travel times. All storage used for input data should be created using malloc() and/or realloc(), and free()’ed at the end of the program.
Stage 2 - Path Finding
Suppose you are a driver currently at location “4c”. There is a minimum travel cost from there to every other location in the grid, based on the per-block travel times. To see how these costs can be computed, suppose we label “4c” with a cost of 0, and every other grid location with a cost of 999 (meaning, not yet reached). If we then use nested loops to explore each possible direction out of every possible grid location, we’ll find that some of those cost estimates were too high, and can be reduced. For example, after one cycle of reductions, it will be known that grid reference “4b” has a cost of 15, that “5c” has a cost of 34 (or less, because there is a cheaper route found later, via “4b”), and that grid location “3c” has a cost of 26 of less - all of them labeled from “4c”, using the streets out of it. The second iteration - again, over every grid location and every edge out of it - will then allow initial costings to be established for the grid locations connected to “4b”, “5c”, and “3c”. For example, “3b” will be checked via both “3c” and “4b”. Every time a path is considered, the least cost one should be retained. In the case of ties, retain the labeling that comes from the lexicographically smallest grid location.
If we continue to repeat that whole process until we have an iteration (over all grid locations and directions) in which there are no more changes made, then the costs have stabilized and reached their final minimum values. Can you see now why I compared this (relatively inefficient) algorithm to bubblesort? [If you want to try and implement a more efficient mechanism, look up “Dijkstra’s Algorithm” at the wikipedia. But remember, there are no marks in this project for courage. Get a simple version working first.] While you are working through getting this process implemented, you should use a DEBUG mode to generate detailed output in any form that you wish. Turn the debugging off again before your final submission.
For this stage, the required output is the path (and cost of it) from the first additional grid location in the third part of the input file to each of the other grid locations in the third part of the input file (that is, compute all of the costs, and then print out a selected subset of them). For test2.txt:
S2: start at grid 4c, cost of 0
S2: then to 4b, cost of 15
S2: then to 5b, cost of 23
S2: then to 5c, cost of 32
S2: start at grid 4c, cost of 0
S2: then to 3c, cost of 26
S2: then to 3d, cost of 36
S2: then to 3e, cost of 48
S2: then to 2e, cost of 70
S2: then to 1e, cost of 80
Hint: as you label each grid location with a better cost, make a note of where that labeling came from. Then unstack that path (think recursion) when you need to trace it back to the starting point. You may assume that every grid location can be entered and exited somehow, and do not need to worry about dead ends being created.
Stage 3 - Send the Closest Car
Ok, now for the fun part. Suppose that the grid coordinates supplied in the third part of the input file are the locations of the currently available cars. For each pickup location in the city grid, compute which car can get there the fastest from its start position. Present your solution visually, as shown in Figure 2. My program to implement all three stages is around 450 lines long, including detailed comments and some debugging output, about 100 lines longer than the solution for Assignment 1. But it is also rather more complex. Start early if you intend to try and obtain these last two marks!
The boring stuff…
This project is worth 15% of your final mark. A rubric explaining the marking expectations will be provided on the FAQ page.
Submission will again be done via dimefox and the submit system. You can (and should) use submit both early and often - to get used to the way it works, and also to check that your program compiles and executes correctly on our test system, which has some different characteristics to the lab machines. Only the last submission that you make before the deadline will be marked.