We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jeanie's Route
  5. Discussions

Jeanie's Route

Sort by

recency

|

26 Discussions

|

  • shanefostersmith
     + 0 comments

    Java solution. First, remove outer, non-letter cities (will never be visited). Then, from the (new) outer letter cities, go inward until you reach an intersection city (3 or more edges) and calculate the minimum and maximum subtree value. You can consider a 'minimum' subtree is where you start or end a path at that subtree. A maximum subtree will double value of all "lines" in the subtree. Eventually, you will reach an inner city in which all subtrees are calculated. From there you can calculate an intersection's cities minimum path will add two minimum subtrees with the rest as maximum subtrees. Once you've reached the most inner intersection city, you can calculate it's minimum path and move back outerwards to calcuate the rest of the intersections minimum paths (with optimizations). One of the intersections will have the minimum path, and that's what you will return. Minimum is O(# cities), maximum is O(# cities + # edges).

    static int jeanisRoute(int[] k, int[][] roads) {
        int biggestCity = roads.length + 1;
        // Trivial Cases
        if (biggestCity == 2) {
            return roads[0][2];
        }
        if (biggestCity == 3 && k.length == 3 ) {
            int sum = 0;
            for (int i = 0; i < 2; i++) {
                sum += roads[i][2];
            }
            return sum;
        }
        Set<Integer> letterCities = new HashSet<>();
        for (int i = 0; i < k.length; i++) {
            letterCities.add(k[i]);
        }
        Map<Integer,List<Integer>> adjList = new HashMap<>();
        Map<Edge,Integer> weights = new HashMap<>();
        // Create adjacency list
        for (int i = 1; i <= biggestCity; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int i = 0; i < roads.length; i++) {
            int[] currRoad = roads[i];
            int vertex1 = currRoad[0];
            int vertex2 = currRoad[1];
            adjList.get(vertex1).add(vertex2);
            adjList.get(vertex2).add(vertex1);
            Edge newEdge = new Edge(vertex1,vertex2);
            weights.put(newEdge,currRoad[2]);
        }
        if (biggestCity == 3) {
            int sum = 0;
            for (int i = 0; i < k.length; i++) {
                List<Integer> connected = adjList.get(k[i]);
                if (connected.size() == 1) {
                    int connectedCity = connected.get(0);
                    Edge newEdge = new Edge(k[i],connectedCity);
                    if (letterCities.contains(connectedCity)) {
                        return weights.get(newEdge);
                    } else {
                        sum += weights.get(newEdge);
                    }
                }
            }
            return sum;
        }
        int citiesLeft = biggestCity;
        Set<Integer> outerCities = new HashSet<>();
        
        // Remove non-letter cities that will never be visited (outer of graph)
        // Create set of "outer cities"
        for (int i = 1; i <= biggestCity; i++) {
            List<Integer> connectedCities = adjList.get(i);
            if (connectedCities.size() != 1) {
                continue;
            }
            if (letterCities.contains(i)) {
                outerCities.add(i);
            } else { // Current City will never be visited
                int currCity = i;
                while (true) {
                    int adjCity = adjList.get(currCity).get(0);
                    adjList.get(currCity).remove(0);
                    List<Integer> connectedToAdj = adjList.get(adjCity);
                    for (int j = 0; j < connectedToAdj.size(); j++) {
                        if (connectedToAdj.get(j) == currCity) {
                            connectedToAdj.remove(j);
                            break;
                        }
                    }
                    citiesLeft--;
                    if (adjCity > i || connectedToAdj.size() != 1) {
                        break;
                    }
                    if (letterCities.contains(adjCity)) {
                        outerCities.add(adjCity);
                        break;
                    }
                    currCity = adjCity;
                }
            }
        }
        
        // For every 'intersection' can choose two subtrees to be minimum and 
        // rest be maximum. Choose intersection that is minimal. 
        Map<Integer, int[][]> interToMinMaxSubtrees = new HashMap<>();
        Map<Integer, Integer> interMaxTotal = new HashMap<>();
        Map<Integer, int[]> interDiffMaxMin = new HashMap<>();
        Map<Integer, Set<Integer>> interToVisitedEdges = new HashMap<>();
        Map<Integer, Integer> interNumTreesCalculated = new HashMap<>();
        int noIntersection = 0;
        Set<Integer> nextCities = new HashSet<>();
        // Start with Outer Cities to Intersection Cities
        for (int outer : outerCities) {
            System.out.println("Curr Outer: " + outer);
            citiesLeft--;
            int prevCity = outer;
            int currCity = adjList.get(outer).get(0);
            int currLen = weights.get(new Edge(prevCity,currCity));
            while (true) {
                List<Integer> connectedToCurr = adjList.get(currCity);
                int numConnected = connectedToCurr.size();
                if (numConnected > 2) { // Found intersection city
                    // Find edge index it currently intersected with
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    // Update maps
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    int[][] minMax = interToMinMaxSubtrees.computeIfAbsent(currCity, key ->
                    new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currLen;
                    minMax[edgeIntersect][1] = 2*currLen; 
                    
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + minMax[edgeIntersect][1]);
                    
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    interNumTreesCalculated.put(currCity, edgesSeen);
                    
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    if (edgesSeen == numConnected - 1) {
                        nextCities.add(currCity);
                    }
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (currLen < currLargest[0]) {
                        break;
                    }
                    if (currLen > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = currLen;
                    } else {
                        currLargest[0] = currLen;
                    }
                    break;
                }
                // This city is part of a 'line'
                if (numConnected == 2) {
                    citiesLeft--;
                    int nextCity = connectedToCurr.get(0) == prevCity ? 
                    connectedToCurr.get(1) : connectedToCurr.get(0);
                    currLen += weights.get(new Edge(currCity, nextCity));
                    prevCity = currCity;
                    currCity = nextCity;
                    continue;
                }
                // Went from outer city to outer city, no intersections
                noIntersection = currLen;
                break;
            }
            if (noIntersection > 0) {
                return noIntersection;
            }
        }
        // Only one intersection
        if (citiesLeft == 1) {
            int intersection = (int) interMaxTotal.keySet().toArray()[0];
            int[] largestSubTrees = interDiffMaxMin.get(intersection);
            int result = interMaxTotal.get(intersection) - 
            largestSubTrees[0] - largestSubTrees[1];
            return result;
        }
        Queue<Integer> toCalculate = new LinkedList<>();
        Map<Integer,int[][]> interToInterCityAndLen = new HashMap<>();
        
        int totalMax = 0;
        boolean[] calculated = new boolean[biggestCity];
        while (true) {
            Set<Integer> newCities = new HashSet<>();
            for (int inter : nextCities) {
                List<Integer> connectedToInter = adjList.get(inter);
                Set<Integer> edgesVisited = interToVisitedEdges.get(inter);
                if (edgesVisited.size() == connectedToInter.size()) {
                    continue;
                }
                int prevCity = inter;
                int lineStartIdx = 0;
                int currCity = 0;
                for (int i = 0; i < connectedToInter.size(); i++) {
                    if (!edgesVisited.contains(i)) {
                        currCity = connectedToInter.get(i);
                        lineStartIdx = i;
                        break;
                    }
                }
                
                // If intersection to intersection already calculated
                if (interToInterCityAndLen.get(inter) != null && interToInterCityAndLen.get(inter)[lineStartIdx][0] != 0) {
                    continue;
                }
                int currLen = weights.get(new Edge(prevCity,currCity));
                while (true) {
                    List<Integer> connectedToCurr = adjList.get(currCity);
                    int numConnected = connectedToCurr.size();
                    
                    // This city is part of a 'line'
                    if (numConnected == 2) {
                        int nextCity = connectedToCurr.get(0) == prevCity ? 
                        connectedToCurr.get(1) : connectedToCurr.get(0);
                        currLen += weights.get(new Edge(currCity,nextCity));
                        prevCity = currCity;
                        currCity = nextCity;
                        continue;
                    }
                    // Found intersection
                    
                    // Find edge index that was intersected
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    // Update intersection connections
                    int[] connectCurrToInter = {currCity,edgeIntersect,currLen};
                    int[] connectInterToCurr = {inter,lineStartIdx,currLen};
                    interToInterCityAndLen.computeIfAbsent(currCity, 
                    key -> new int[numConnected][3])[edgeIntersect] = connectInterToCurr;
                    interToInterCityAndLen.computeIfAbsent(inter, 
                    key -> new int[numConnected][3])[lineStartIdx] = connectCurrToInter;
                    
                    // Find min and max of current subtree
                    int previousMax = interMaxTotal.get(inter);
                    int prevLargestSubTree = interDiffMaxMin.get(inter)[1];
                    int previousMin = interMaxTotal.get(inter) - prevLargestSubTree;
                    int currentMax =  2*currLen + previousMax;
                    int currentMin = previousMin + currLen;
                    int diffMaxMin = currentMax - currentMin;
                    
                    // Update maps
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + currentMax);
                    
                    int minMax[][] = interToMinMaxSubtrees.computeIfAbsent(currCity ,
                    key -> new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currentMin;
                    minMax[edgeIntersect][1] = currentMax;
                    
                    interNumTreesCalculated.put(currCity, 
                    interNumTreesCalculated.getOrDefault(currCity, 0) + 1);
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (diffMaxMin > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = diffMaxMin;
                    } else if (diffMaxMin > currLargest[0]) {
                        currLargest[0] = diffMaxMin;
                    }
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    if (edgesSeen == numConnected - 1) {
                        newCities.add(currCity);
                    } else if (edgesSeen == numConnected) {
                        newCities.remove(currCity);
                        if (interNumTreesCalculated.get(currCity) == numConnected) {
                            totalMax = interMaxTotal.get(currCity);
                            toCalculate.add(currCity);
                        }
                    }
                    break;
                } // while loop inner end
            } // for loop end
            if (newCities.isEmpty()) {
                break;
            } 
            nextCities = newCities;
        }
        
        int minSeen = Integer.MAX_VALUE;
        // only visit intersections where all subtrees have been calculated
        while (!toCalculate.isEmpty()) {
            int currInter = toCalculate.poll();
            if (calculated[currInter - 1]) {
                continue;
            }
            // Calculate minimum path for this city
            calculated[currInter - 1] = true;
            int[] currLargest = interDiffMaxMin.get(currInter);
            int result = totalMax - currLargest[1] - currLargest[0];
            if (result < minSeen) {
                minSeen = result;
            }
            // Calculate subtree for neighboring city
            int[][] connectedToCurr = interToInterCityAndLen.get(currInter);
            for (int i = 0; i < connectedToCurr.length; i++) {
                int connectedCity = connectedToCurr[i][0];
                if (connectedCity == 0 || calculated[connectedCity - 1]) {
                    continue;
                }
                int numSubTreesTotal = adjList.get(connectedCity).size();
                int numSubTreesCalculated = interNumTreesCalculated.get(connectedCity);
                int treesLeft= numSubTreesTotal - numSubTreesCalculated;
                if (treesLeft == 0) {
                    continue;
                }
                // Calculate subtree from connected to current
                int connectedLen = connectedToCurr[i][2];
                int[][] currMaxMin = interToMinMaxSubtrees.get(currInter);
                int maxRemoved = currMaxMin[i][1];
                int minRemoved = currMaxMin[i][0];
                int diffRemoved = maxRemoved - minRemoved;
                int connectedMaxSubTree = totalMax - maxRemoved + 2*connectedLen;
                int connectedMinSubTree;
                if (diffRemoved < currLargest[1]) {
                    connectedMinSubTree = connectedMaxSubTree - currLargest[1];
                }
                else  {
                    connectedMinSubTree= connectedMaxSubTree - currLargest[0];
                }
                connectedMinSubTree += connectedLen;
                int connectedDiff = connectedMaxSubTree - connectedMinSubTree;
                int[] largestDiffs = interDiffMaxMin.get(connectedCity);
                if (connectedDiff > largestDiffs[1]) {
                    largestDiffs[0] = largestDiffs[1];
                    largestDiffs[1] = connectedDiff;
                } else if (connectedDiff > largestDiffs[0]) {
                    largestDiffs[0] = connectedDiff;
                }
                // This city will never be the minimum
                if (largestDiffs[1] + largestDiffs[0] <= currLargest[1] + currLargest[0]) {
                    continue;
                }
                // Update maps for connected
                interNumTreesCalculated.put(connectedCity,++numSubTreesCalculated);
                if (--treesLeft == 0) {
                    toCalculate.add(connectedCity);
                } 
                int subTreeIdx = connectedToCurr[i][1];
                int[][] connectedMinMax = interToMinMaxSubtrees.get(connectedCity);
                connectedMinMax[subTreeIdx][0] = connectedMinSubTree;
                connectedMinMax[subTreeIdx][1] = connectedMaxSubTree;
            }
        }
        return minSeen;
    }

  • callummequigley
     + 0 comments

    python3

    def jeanisRoute(n, cities, roads):
    """The strategy of this approach is to:
    1) Prune off any branches of the tree that aren't visited
    2) Note that to visit each remaining node and return to start
    has length = 2 * sum(all remaining edge weights)
    3) Since we need not return to start, the most by which we can
    reduce total length is the max distance b/w 2 nodes
    i.e. the tree's diameter."""
    
    # Make the adjacency list and sum (2x) total graph weight
    adj = {i: [] for i in range(1, n+1)}
    total = 0
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
        total += 2*w
    
    # Iteratively, prune leaves that are not visited (adjusting total)
    flag = True  # track if any changes made this pass
    non_dest = set(range(1, n+1)).difference({*cities})
    while flag:
        flag = False
        for u in non_dest:
            if len(adj[u]) == 1:
                v, w = adj[u].pop()
                adj[v].remove((u, w))
                flag = True
                total -= 2*w
                
    # Compute the pruned tree's diameter by running DFS twice.
    # First time, start at any city and find the furthest leaf.
    # Second time, start at first endpoint. Result is the diameter
    u, d = dfs(cities[0], adj)
    v, diameter = dfs(u, adj)
    
    return total - diameter
        

def dfs(start, adj):
    "Conduct DFS to find the node of max distance from node <start>"
    
    seen = set([start])
    queue = [(start, 0)]
    end, max_dist = start, 0
    
    while queue:
        curr, dist = queue.pop()
        for nxt, wt in adj[curr]:
            if nxt not in seen:
                seen.add(nxt)
                new_dist = dist + wt
                queue.append((nxt, new_dist))
                if new_dist > max_dist:
                    end, max_dist = nxt, new_dist
    
    return end, max_dist

  • gjtnwjd40
     + 0 comments

    how can we know which city is must delivered or not ?? The thing we could know is the number of letter.. isn't it??

  • yashparihar729
     + 1 comment

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Jeanie’s Route Problem Solution

  • mineman1012221
     + 0 comments

    Here is the solution of Jeanie's Route Click Here