Goods Delivery by Robot using Python Assignment Solution

Robot Delivery

Write a python assignment where a robot is delivering products for a company in a city with only one-way streets. The robot is required to deliver to at least one household on every street and then return to its original destination for refit and repair. The city charges the robot a small fee per street that it traverses; this fee is charged every time that the robot crosses from one intersection to the next. Fees vary depending on the street, but every street that the robot is allowed to travel on requires a fee of at least 1; any streets that have 0 fees mean that the robot is not allowed to travel there. The robot’s goal is to minimize the total fees that it is charged for delivering all of its products, respecting the constraints.

Example

The input file (input.txt) may look like the following:

5

0 22566 46247 86550 85679

0 0 17214 0 0

77002 0 0 31972 0

0 0 0 0 12066

63767 0 0 6302 0

The output file (output.txt) could look like the following (and remember that there will be multiple correct answers for any given input):

0 4 3 4 0 3 4 0 2 3 4 0 1 2 0

Solution

import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Robot { private static Scanner scanner = new Scanner(System.in); private static int[][] getCostMatrix(String fileName) throws FileNotFoundException { FileInputStream fis = new FileInputStream(fileName); Scanner sc = new Scanner(fis); //file to be scanned int num = Integer.parseInt(sc.nextLine()); int[][] output = new int[num][num]; int i = 0; while (sc.hasNextLine()) { String[] values = sc.nextLine().split(" "); //returns the line that was skipped int j = 0; for (String value : values) { output[i][j] = Integer.parseInt(value); j++; } i++; } sc.close(); //closes the scanner return output; } private static List minPath(int[][] matrix) { List path = new ArrayList<>(); path.add(0); for(int i = matrix.length - 1; i > 0; i--) { List bestTo = bestPathTo(0, i, matrix, new Path(new ArrayList<>(), 0)).points; //System.out.println(i + " From 0" + bestTo); path.addAll(bestTo); List bestBack =bestPathTo(i, 0, matrix, new Path(new ArrayList<>(), 0)).points; //System.out.println(i + " Back To 0" + bestBack); path.addAll(bestBack); } return path; } static class Path { public List points; public int cost; Path(List points, int cost) { this.points = points; this.cost = cost; } } private static Path min(List paths) { int min = 0; int minCost = Integer.MAX_VALUE; for(int i = 0; i < paths.size(); i++) { if(paths.get(i).cost < minCost) { min = i; minCost = paths.get(i).cost; } } return paths.get(min); } private static Path bestPathTo(int from, int destination, int[][] matrix, Path currentPath) { if(from == destination) { return currentPath; } List paths = new ArrayList<>(); for(int i = 0; i < matrix.length; i++) { if(matrix[from][i] != 0 && from != i && !currentPath.points.contains(i)) { List points = new ArrayList<>(currentPath.points); points.add(i); paths.add(bestPathTo(i, destination, matrix, new Path(points, currentPath.cost + matrix[from][i]))); } } if(paths.size() == 0) { return new Path(Collections.emptyList(), Integer.MAX_VALUE); } return min(paths); } private static void toOutput(String fileName, List path) throws IOException { FileWriter myWriter = new FileWriter(fileName); for(Integer i : path) { myWriter.write(i + " "); } myWriter.close(); } public static void main(String[] args) throws IOException { int[][] matrix = getCostMatrix("input.txt"); toOutput("output.txt", minPath(matrix)); } }