Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
3.3 kB
2
Indexable
Never
import java.util.*;

public class HelloWorld{

     public static void main(String []args){
        System.out.println("Hello World");
        
        List<List<Integer>> allLocations = new ArrayList();
        int numDeliveries = 2;
        
        List<Integer> p1 = new ArrayList<Integer>(
            Arrays.asList(1, 2));
    
        List<Integer> p2 = new ArrayList<Integer>(
            Arrays.asList(3, 4));
    
        List<Integer> p3 = new ArrayList<Integer>(
            Arrays.asList(1, -1));
    
    
        allLocations.add(p1);
        allLocations.add(p2);
        allLocations.add(p3);
        
        
        List<List<Integer>> result = deliveryPlan(allLocations, numDeliveries);
        
        System.out.println(result);
        
     }
     
     public static List<List<Integer>> deliveryPlan(List<List<Integer>> allLocations,
        int numDeliveries) {
            List<List<Integer>> result = new ArrayList();
            HashMap<String, Boolean> visited = new HashMap<>();
            int x = 0, y = 0;
            
            for (List<Integer> l : allLocations) {
                visited.put(l.toString(), false);
            }
            
            HashMap<List<Integer>, Double> distances = 
                    findDistancesFromPoint(allLocations, visited, 0, 0);
                    // System.out.println(distances);
                    
            
            
            for (int i = 0; i < numDeliveries; i++) {
                List<Integer> nextPoint = findNextUnvisitedPoint(distances, visited);
                visited.put(nextPoint.toString(), true);
                result.add(nextPoint);
            }
            
            // for (List<Integer> l : allLocations) {
            //     visited.put(l.toString(), true);
            //     // Visit the point and calculate the answer from there
            // }
            
            // System.out.println(visited);
            return result;
        }
        
    public static HashMap<List<Integer>, Double> findDistancesFromPoint(List<List<Integer>> allLocations, HashMap<String, Boolean> visited, int x, int y) {
        HashMap<List<Integer>, Double> distances = new HashMap();
        for (List<Integer> l : allLocations) {
            if (!visited.get(l.toString())) {
                int a = l.get(0), b = l.get(1);
                double distance = Math.sqrt(a*a + b*b);
                distances.put(l, distance);
            }
        }
        return distances;
    }
    
    public static List<Integer> findNextUnvisitedPoint(HashMap<List<Integer>, Double> distances, HashMap<String, Boolean> visited) {
        List<Integer> result = null;
        double min = Double.MAX_VALUE;
        
        // System.out.println("Visited : " + visited);
        
        for (List<Integer> l : distances.keySet()) {
            if (!visited.get(l.toString())) {
                double d = distances.get(l);
                // System.out.println("Distance : " + l + d);
                if (d < min) {
                    result = l;
                    min = d;
                }
                if ( d == min ) {
                    if (l.get(0) < result.get(0)) {
                        result = l;
                    }
                }
            }
        }
        
        return result;
    }
    
}