Programming Assignment 7 – Wormholes1 CS 321 – Fall 2025 Due November 25, 10:00 PM2 1 This assignment is based on a problem from a prior ACM Intercollegiate Programming Contest. Much of the text here is from that problem. Introduction With our time on Earth coming to an end, Cooper and Amelia have volunteered to undertake what could be the most important mission in human history: travelling beyond this galaxy to discover whether mankind has a future among the stars. Fortunately, astronomers have identified several potentially habitable planets and have also discovered that some of these planets have wormholes joining them, which effectively makes travel distance between these wormhole-connected planets zero. Note that the wormholes in this problem are considered to be one-way. For all other planets, the travel distance between them is simply the Euclidian distance between the planets. Given the locations of planets, wormholes, and a list of pairs of planets, find the shortest travel distance between the listed pairs of planets. Format This problem, as mentioned on the first page, is based directly on an ACM programming contest that we encountered a few years ago. Typically, program contestants write their code to expect input and output to be from stdin & stdout respectively. Instead, we will implement our code to expect input from an input file indicated by the user at runtime with output written to a file indicated by the user. Concise descriptions of the input format and expected output format are provided below. For full credit, your output must EXACTLY match the expected output for a given input file. Do not hard code things like the number of planets in your code, your program will have to run on files that I create for testing purposes separate from the sample files I provide for you for this assignment. You will find one sample input file and one sample output file: input.txt and output.txt. Input • The first line of input is a single integer, T (1 ≤ T ≤ 10): the the number of test cases. • Each test case consists of planets, wormholes, and a set of distance queries as pairs of planets. • The planets list for a test case starts with a single integer, p (1 ≤ p ≤ 60): the number of planets. Following this are p lines, where each line contains a planet name (a single string with no spaces) along with the planet’s integer coordinates, i.e. name x y z (0 ≤ x, y, z ≤ 2 * 106). The names of the planets will consist only of ASCII letters and numbers, and will always start with an ASCII letter. Planet names are case-sensitive (Earth and earth are distinct planets). The length of a planet name will never be greater than 50 characters. All coordinates are given in parsecs (for theme. Don’t expect any correspondence to actual astronomical distances). • The wormholes list for a test case starts with a single integer, w (1 ≤ w ≤ 40): the number of wormholes, followed by the list of w wormholes. Each wormhole consists of two planet names separated by a space. The first planet name marks the entrance of a wormhole, and the second planet name marks the exit from the wormhole. The planets that mark wormholes will be chosen from the list of planets given in the preceding section. Note: you can’t enter a wormhole at its exit. • The queries list for a test case starts with a single integer, q (1 ≤ q ≤ 20), the number of queries. Each query consists of two planet names separated by a space. Both planets will have been listed in the planet list. Output For each test case, output a line, “Case i:”, the number of the ith test case. Then, for each query in that test case, output a line that states “The distance from planet1 to planet2 is d parsecs.” where the planets are the names from the query and d is the shortest possible travel distance between the two planets. Round d to the nearest integer. Time limit Your program has a time limit of five seconds to produce the complete output file for a given input file. Hints Here’s where I’m being nice – the ACM contest competitors didn’t get any of the information below. • This is a graph problem, and can be solved by a simple variation on one of the graph algorithms in our textbook. You should figure out what type of graph you need, how to represent the graph, and which algorithm to use (there are actually a couple different algorithms that will give the correct answer). If you get stuck, ask me. • Think about the connectivity of the graph. Is your graph highly connected or sparsely connected? Figuring this out will help you pick a graph representation. • Is the graph directed or undirected? (Think about how the wormholes work.) • Even though the input and output values are integers, you should represent everything in your program as doubles and perform all distance calculations using doubles. Only round your answer once before your print the answer to the output file. • My solution to this problem used the following header files: #include <iostream> #include <fstream> #include <string> #include <cmath> #include <cstdlib> #include <climits> You might not need all of these, or maybe you will elect to use more. Since I wrote my original solution, it occurred to me that a STL map object would be useful to convert a planet name to an array index. • I put all of my code in a single file, though I did use a class to represent a graph. My file for my solution contains 435 lines. A healthy chuck of that is comments and or white space, but it can give you a rough idea of how long my solution was. I have seen other solutions written in significantly fewer lines. If you are pushing 1000 lines of code or more, you are doing something wrong. • Two-dimensional dynamically-allocated arrays are your friends. I used dynamically allocated 1-D and 2-D arrays at several points in my solution. You should explicitly define any dynamically- allocated C++ arrays. Use new and delete as necessary. • If there were no wormholes at all, this becomes a trivially easy problem. Try solving that as a starting point, then add in consideration of wormholes. If you get at least that far, I’ve got something to evaluate for partial credit. • You need a convenient way to convert a planet name (a string) into a corresponding array index (an integer). The STL’s map class might be a good way to do this. Submission Turn in your code for this assignment on GitHub. You can use Lamaku if you have to, but I strongly prefer a GitHub submission.