Assignment 8: Planet X Solution

Introduction



We have received a distress call from a spaceship (the USS Java) that just crash-landed on an unknown planet somewhere in space, on Planet X. Fleet Admirals Birrell and Gries have dispatched you, as Captain of our fastest spaceship, to rendezvous with the ship and provide assistance. You will explore this uncharted region of space and return to Earth. Something suggests this may not be as trivial as it sounds. . .

The assignment has two stages, each of which involves writing a method in Java.




Collaboration Policy and Academic Integrity



\Alone we can do so little; together we can do




so much."




|Helen Keller




You may complete this assignment with one other person. If you plan to work with a partner, login to CMS and form a group as soon as possible |at least a day before you submit the assignment. Both people must do something to form the group: one proposes and the other accepts.




If you complete this assignment with another person, you must actually work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping. You should both take turns driving |using the keyboard and mouse.




With the exception of your CMS-registered partner, you may not look at anyone else's code, in any form, or show your code to anyone else, in any form. You may not show or give your code to another person in the class. You can talk to others about the assignment at a high level, but your discussions should not include writing code or copying it down.




If you don't know where to start, if you are lost, etc., please see someone immediately: a course instructor, a TA or a consultant. Do not wait. A little in-person help can do wonders to get you unstuck.




Assignment Overview



\Ipsa scientia potestas est."




|Sir Francis Bacon




This assignment has two stages: the search phase and the rescue phase. We present a high-level view of the two phase. Low-level details of the implementation appear in the pinned Piazza note A8 FAQs.




3.1 Search Phase




Implement method search in MySpaceShip.java in package student.




The USS Java is on Planet X and is emitting a distress signal. Your ship is on Earth, and you have been commanded to search space to rescue the USS Java. It's a rather random search, because you have no idea






where Planet X is. You just have to traverse space until you nd it. From each planet you can travel only to certain other planets. (The planets are nodes of an undirected graph.)




Your ship must travel from planet to planet until it reaches Planet X, the site of the distressed ship.




Your objective is to get to planet X in as short a distance as possible.




You can use the strength of the distress signal to help. The closer a planet is to Planet X, the stronger the signal. So, try ying rst to neighboring planets where the signal is strongest. But that doesn't always help. The path the ship must y to get to Planet X from that geographically closer planet may actually be longer.




3.2 Rescue Phase




Implement method rescue in MySpaceShip.java in package student.




Upon successfully reaching the USS Java, its captain, who has perhaps 1 year of coding experience, tells you that some planets contain valuable SpaceGemsTM1. The captain wants you to plan a strategy to pick up as many gems as possible while still returning to Earth before running out of fuel. Here's your chance to show your mettle! There is no known best algorithm for that! How will you gure out a path around the planets to pick up as many gems as possible? Sure, you can get back home by traversing the shortest path to Earth. But how many gems will you pick up doing that?




The GUI



Fig. 1 on the next page is a picture of the GUI associated with the program. The right side is a 2D map of the planets, projected into whatever sized window the GUI is running in. The coordinates of the map are to scale: the actual distance between two planets is proportional to their apparent distance on the map. However, the actual bounds of the graph of planets is square, while your displayed map is most likely rectangular. This will result in a certain direction appearing to be more compressed than it actually is.




Use menu item File!New Map to switch to a new, randomly generated map. You may entering a number (the seed) of your choice. If you leave the seed blank, the simulation will use a randomly chosen seed. To test your solution on a small map, try seed -2466017765573610414 (don't forget the negation sign). To see why you might want to optimize your search phase, try seed -1. To see a case where (most) optimizations don't work well, try running your algorithm on the graph produced with seed 16. We may put other interesting seeds on the pinned Piazza note Assignment A8 as they are discovered.




The panel on the left side of the GUI displays information of possible interest. This information changes as the search and rescue proceeds. In Fig. 1, the search phase is complete; it took fuel 9287 to reach Planet X. The rescue phase is underway. The spaceship left Planet X and is on its way to planet Hidesac. We paused the game at this point in order to make this image. The left Panel gives the previous planet, Planet X, and the current score.




The ship has a limited amount of fuel, and the left panel shows that it has only enough fuel to go the remaining distance, in this case, 10028. If the ship tries to travel farther than that, it fails and never reaches Earth. The score will be 0.




Click a planet and its name and the number of gems on it appear in the right-hand panel. The number of gems will update in real time. Planet Nathanmonroe has 4233 gems on it. In returning back to Earth, it's good to pick up as many gems as possible. So, the ship will want to visit as many planets as possible while still getting back to




Slider \Simulation speed" can be used to make the simulation run faster. Use the slider to fast-forward past parts of the simulation in which you are not interested.




The \zoom" slider allows you to visually zoom in on the map, for situations where too many planets are in a small area, making them di cult to distinguish.




If you check box \Camera follows ship", the view of the map will keep the ship centered as the ship moves from planet to planet. If you do not check the box, you can manually move the view via the arrow keys, WASD, or even the vi-keys (hjkl) if you are so inclined.







1We do not endorse any product or institution that happens to carry this name









2






Figure 1: Example GUI screen







We paused the simulation. Uncheck box \Pause" to have the simulation proceed. You can also have the simulation pause automatically when Planet X is reached at the end of the search phase.




Menu \File" in the top left has options for controlling the simulation. Choose \start" to start the simulation, \Reset" to reset the current map, and \New map" to generate a new map. A simulation can be run only once, starting from the paused state. To rerun it, use menu item File ! Reset.




As the ship moves along, edges change color. Edges are initially gray; on the rst traversal, they turn green; on the second traversal, yellow; and on subsequent traversals, red.




Setting up Eclipse



\A journey of a thousand miles begins with a




single step."




|Laozi





Download and unzip the release-code le. Start a new Eclipse project |name it anything you want, like a8. Then copy items to the project:




Drag the directories in directory src over \src" in the Eclipse project.



Drag directory data over the project itself.



Drag a8util.jar over the project itself.



When you do this, when asked, tell it to copy rather than to link.




The end result should look like the image on the right, except that there should be an error, denoted by a red x. To get rid of it,




Select a8util.jar, right click to get a contextual menu, and use item Build Path - Add to Build Path.






Running the Program



Method main needed to run the program is in class PlanetX of package controllers. The speci cation for main gives more details about possible arguments, though you may not need any of them. By default, the program runs on a single map with a random seed. It is possible to run in headless mode, in which you do not have a GUI. This allows you to estimate how much \real time" your simulation takes. We'll discuss this later in the Piazza A8 FAQs note.




Grading



\...programmers have spent far too much time




worrying about e ciency in the wrong places




and at the wrong times; premature




optimization is the root of all evil..."




|Donald Knuth




The vast majority of points on this assignment will come from a correct solution that always nds Planet X and returns to Earth safely (within the given distance limit), so your priority is to make sure that your code always does this successfully.




However, in order to receive full credit for the assignment, your solution must also get a reasonably high score, so think about ways to optimize your solution, to pick up as many gems as possible.




The use of Java Re ection mechanisms aside from method getClass() and eld class in method equals() is strictly forbidden and will result in signi cant penalties.




What to Submit



Zip package student and submit it on CMS. Be sure that you have not changed the interfaces to methods search() and rescue(), because doing so would make your solution fail to compile, resulting in a very poor score.




You may add helper methods or additional classes to package student, but specify everything well.




It is crucial that you submit a zip archive that contains package student: nothing more and nothing less. As a check, unzip your zip le. It should be a directory named student, which contains only your .java les.




Finally, your submission should be well-written. Don't leave any traces of debugging code, such as print statements.





What you can do



\The world is your oyster."




|William Shakespeare




This is your chance to do what you want. You can write helper methods (but for your bene t, write precise and complete Javadoc specs for them.) You can add elds (but have comments that say what they are for, what they mean). You can change the shortest-path method in class Paths to do something di erent.




We suggest rst getting a solution that is simple and works. This will give you a minimum grade of about 85. Save this version so you have something to submit.




Then, begin looking for ways of optimizing |always making sure you have something that works that you can submit.




10 Acknowledgements




\If I have seen further, it is by standing on




the shoulders of giants."




|Sir Isaac Newton




We are grateful to past and previous members of the CS2110 course sta for their assistance and con-tributions, including but not limited to: Michael Patashnik, Alex Fusco, Eric Perdew, Nate Foster, Joe Antonakakis, Matthew Weidman, Elizabeth VanDenburgh, Jason Liu, Ramya Babu, Adam Gleisner, Lucas Png, and Devin Lehmacher.




Jason Liu has been the main guy in hammering this assignment into shape! Thanks, Jason!




Good luck and have some fun!






































































































5