Computer Science Java: Part 1 – Finding Least Expensive Routes (50 points) Consi
ID: 3707824 • Letter: C
Question
Computer Science
Java:
Part 1 – Finding Least Expensive Routes (50 points)
Consider the problem of finding the least expensive routes to all cities in a network from a given starting point. For example, in the network shown on the map below, the least expensive route from Pendleton to Peoria has cost 8 (going through Pierre and Pueblo).
The following helper class expresses the distance to another city:
public class DistanceTo implements Comparable<DistanceTo>
{
private String target;
private int distance;
public DistanceTo(String city, int dist)
{
target = city; distance = dist;
}
public String getTarget() { return target; }
public int getDistance() { return distance; }
public int compareTo(DistanceTo other)
{
return distance - other.distance;
}
}
All direct connections between cities are stored in a Map<String, TreeSet<DistanceTo>>.
The algorithm now proceeds as follows:
Let from be the starting point.
Add DistanceTo(from, 0) to a priority queue.
Construct a map shortestKnownDistance from city names to distances.
While the priority queue is not empty
Get its smallest element.
If its target is not a key in shortestKnownDistance
Let d be the distance to that target.
Put (target, d) into shortestKnownDistance.
For all cities c that have a direct connection from target
Add DistanceTo(c, d + distance from target to c) to the priority queue.
When the algorithm has finished, shortestKnownDistance contains the shortest distance from the starting point to all reachable targets.
Your task is to write a program that implements this algorithm. Your program should read in lines of the form city1 city2 distance. The starting point is the first city in the first line. Print the shortest distances to all other cities
Part 2 – Reversing a Linked-List using Stack (50 points)
Write a program that creates a Linked-List object of 10 Strings of Ransom sizes, then:
• creates a second Linked-List object containing a copy of the first list, but in reverse order. You must use a stack to reverse the Strings.
• creates a third Linked-List object containing a copy of the first list, but after sorting it based on the length of strings as well as alphabetically (in ascending order).
The program will print all three Linked-Lists.
Part 3 – Implementation (Bonus worth 50 points)
Suppose you buy 100 shares of a stock at $12 per share, then another 100 at $10 per share, and then sell 150 shares at $15. You have to pay taxes on the gain, but exactly what is the gain? In the United States, the FIFO rule holds: You first sell all shares of the first batch for a profit of $300, then 50 of the shares from the second batch, for a profit of $250, yielding a total profit of $550. Write a program that can make these calculations for arbitrary purchases and sales of shares in a single company. The user enters commands buy quantity price, sell quantity (which causes the gain to be displayed), and quit. Hint: Keep a queue of objects of a class Block that contains the quantity and price of a block of shares.
Then write a program that can handle shares of multiple companies. The user enters commands buy symbol quantity price and sell symbol quantity. Hint: Keep a Map<String, Queue<Block>> that manages a separate queue for each stock symbol.
Part 1 - Finding Least Expensive Routes (50 points) Consider the problem of finding the least expensive routes to all cities in a network from a given starting point. For example, in the network shown on the map below, the least expensive route from Pendleton to Peoria has cost 8 (going through Pierre and Pueblo) The following helper class expresses the distance to another city: public class DistanceTo implements Comparable private String target private int distance; public DistanceTo (String city, int dist) targetcity; distance -dist: public String getTarget) return target; public int getDistance ) return distance; public int compareTo (DistanceTo other) return distance - other.distance; All direct connections between cities are stored in a Map?String, TreeSet> The algorithm now proceeds as follows: Let from be the starting point Add DistanceTo(from, 0) to a priority queue. Construct a map shortestKnownDistance from city names to distances. While the priority queue is not empty Get its smallest element If its target is not a key in shortestKnownDistance Let d be the distance to that target. Put (target, d) into shortestKnownDistance. For all cities c that have a direct connection from target Add DistanceTo(c, d + distance from target to c) to the priority queue.Explanation / Answer
ANSWER
My current solution goes like this:
Pre-process the list such that we have a hashmap which points a location (left), to a list of locations (right) Create a hashmap to keep track of "visited locations". Create a list to store "found paths".Store X (starting-location) to the "visited locations" hashmap. Search for X in the first hashmap, (Location A will give us (B, C, Q) in O(1) time).
For-each found location (B, C, Q), check if it is the final destination (Z). If so store it in the "found paths" list. Else if it doesn't already exist in "visited locations" hashmap, Recurl to step 3 now with that location as "X". (actual code below)
With this current solution, it takes forever to map all (not shortest) possible routes from "BKI" to "SIN" for this provided data.I was wondering if there's a more effective (time-wise) way of doing it. Does anyone know of a better algorithm to find all the paths from an arbitrary position A to an arbitrary position Z ?
Actual Code for current solution:
import java.util.*;
import java.io.*;
public class Test {
private static HashMap<String, List<String>> left_map_rights;
public static void main(String args[]) throws Exception {
left_map_rights = new HashMap<>();
BufferedReader r = new BufferedReader(new FileReader("routes.text"));
String line;
HashMap<String, Void> lines = new HashMap<>();
while ((line = r.readLine()) != null) {
if (lines.containsKey(line)) { // ensure no duplicate lines
continue;
}
lines.put(line, null);
int space_location = line.indexOf(' ');
String left = line.substring(0, space_location);
String right = line.substring(space_location + 1);
if(left.equals(right)){ // rejects entries whereby left = right
continue;
}
List<String> rights = left_map_rights.get(left);
if (rights == null) {
rights = new ArrayList<String>();
left_map_rights.put(left, rights);
}
rights.add(right);
}
r.close();
System.out.println("start");
List<List<String>> routes = GetAllRoutes("BKI", "SIN");
System.out.println("end");
for (List<String> route : routes) {
System.out.println(route);
}
}
public static List<List<String>> GetAllRoutes(String start, String end) {
List<List<String>> routes = new ArrayList<>();
List<String> rights = left_map_rights.get(start);
if (rights != null) {
for (String right : rights) {
List<String> route = new ArrayList<>();
route.add(start);
route.add(right);
Chain(routes, route, right, end);
}
}
return routes;
}
public static void Chain(List<List<String>> routes, List<String> route, String right_most_currently, String end) {
if (right_most_currently.equals(end)) {
routes.add(route);
return;
}
List<String> rights = left_map_rights.get(right_most_currently);
if (rights != null) {
for (String right : rights) {
if (!route.contains(right)) {
List<String> new_route = new ArrayList<String>(route);
new_route.add(right);
Chain(routes, new_route, right, end);
}
}
}
}
}
class GraphFindAllPaths<T> implements Iterable<T> {
private final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();
public boolean addNode(T node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;
graph.put(node, new HashMap<T, Double>());
return true;
}
public void addEdge (T source, T destination, double length) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
/* A node would always be added so no point returning true or false */
graph.get(source).put(destination, length);
}
public void removeEdge (T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
graph.get(source).remove(destination);
}
public Map<T, Double> edgesFrom(T node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
Map<T, Double> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("Source node does not exist.");
}
return Collections.unmodifiableMap(edges);
}
@Override public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
/**
* Given a connected directed graph, find all paths between any two input points.
*/
public class FindAllPaths<T> {
private final GraphFindAllPaths<T> graph;
public FindAllPaths(GraphFindAllPaths<T> graph) {
if (graph == null) {
throw new NullPointerException("The input graph cannot be null.");
}
this.graph = graph;
}
private void validate (T source, T destination) {
if (source == null) {
throw new NullPointerException("The source: " + source + " cannot be null.");
}
if (destination == null) {
throw new NullPointerException("The destination: " + destination + " cannot be null.");
}
if (source.equals(destination)) {
throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
}
}
/**
* Returns the list of paths, where path itself is a list of nodes.
*
* @param source the source node
* @param destination the destination node
* @return List of all paths
*/
public List<List<T>> getAllPaths(T source, T destination) {
validate(source, destination);
List<List<T>> paths = new ArrayList<List<T>>();
recursive(source, destination, paths, new LinkedHashSet<T>());
return paths;
}
private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
path.add(current);
if (current == destination) {
paths.add(new ArrayList<T>(path));
path.remove(current);
return;
}
final Set<T> edges = graph.edgesFrom(current).keySet();
for (T t : edges) {
if (!path.contains(t)) {
recursive (t, destination, paths, path);
}
}
path.remove(current);
}
public static void main(String[] args) {
GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
graphFindAllPaths.addNode("A");
graphFindAllPaths.addNode("B");
graphFindAllPaths.addNode("C");
graphFindAllPaths.addNode("D");
graphFindAllPaths.addEdge("A", "B", 10);
graphFindAllPaths.addEdge("A", "C", 10);
graphFindAllPaths.addEdge("B", "D", 10);
graphFindAllPaths.addEdge("C", "D", 10);
graphFindAllPaths.addEdge("B", "C", 10);
graphFindAllPaths.addEdge("C", "B", 10);
FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);
List<List<String>> paths = new ArrayList<List<String>>();
List<String> path1 = new ArrayList<String>();
path1.add("A"); path1.add("B"); path1.add("D");
List<String> path2 = new ArrayList<String>();
path2.add("A"); path2.add("B"); path2.add("C"); path2.add("D");
List<String> path3 = new ArrayList<String>();
path3.add("A"); path3.add("C"); path3.add("D");
List<String> path4 = new ArrayList<String>();
path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
paths.add(path1);
paths.add(path2);
paths.add(path3);
paths.add(path4);
findAllPaths.getAllPaths("A", "D");
assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.