Find the nearest clone

Sort by

recency

|

190 Discussions

|

  • + 0 comments

    Java 8 solution (passes all test cases):

    static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, long[] ids, int val) {
        // Start by finding all nodes of the target color.
        List<Integer> targetNodes = new ArrayList<Integer>();
        for (int h = 0; h < ids.length; h++) {
            if (ids[h] == val) targetNodes.add(h);
        }
        for (int x : targetNodes) {
            System.out.println(x);
        }
        //Set up visited indicator and placeholder min. path lengths.
    		boolean[] visited = new boolean[graphNodes];
        int[] pathLengths = new int[targetNodes.size()];
        for (int l = 0; l < pathLengths.length; l++) pathLengths[l] = -1;
        
        //Create the graph in the form of a list of neighbor node lists.
    		List<List<Integer>> neighbors = new ArrayList<List<Integer>>();
        for (int i = 0; i < graphNodes; i++) neighbors.add(new ArrayList<Integer>());
        for (int j = 0; j < graphFrom.length; j++) {
            int nodeFrom = graphFrom[j]-1;
            int nodeTo = graphTo[j]-1;
            neighbors.get(nodeFrom).add(nodeTo);
            neighbors.get(nodeTo).add(nodeFrom);
        }
        
        //Reset the visited boolean array for each target node. Then use DFS to find the shortest path to the nearest node of the same color.
    		for (int k = 0; k < targetNodes.size(); k++) {
            visited = new boolean[graphNodes];
            int node = targetNodes.get(k);
            //System.out.println("Node " + node);
            DFS(neighbors, visited, ids, val, 0, pathLengths, k, node);
        }
        
        //Lastly, find the shortest path if present by sorting the array and looking for the first non-negative number.
    		Arrays.sort(pathLengths);
        for (int m = 0; m < pathLengths.length; m++) {
            //System.out.println(pathLengths[m]);
            if (pathLengths[m] > 0) return pathLengths[m];
        }
        
        return -1;
    }
    
    static void DFS(List<List<Integer>> neighbors, boolean[] visited, long[] ids, int val, int len, int[] pathLengths, int node, int curr) {
        //System.out.println("START: Node " + node);
        visited[curr] = true;
        List<Integer> nodeNeighbors = neighbors.get(curr);
        if (ids[curr] == val && len > 0) { //If the function isn't at the starting node and the current node is of the target color, update the path length for the starting node. If the starting node already has a path length assigned, pick the minimum of len and the previous path length.
            //System.out.println("MATCH: Node " + curr);
            if (pathLengths[node] == -1) {
                //System.out.println("ADD: Node " + node);
                pathLengths[node] = len;
            }
            else {
                //System.out.println("UPDATE: Node " + node);
                pathLengths[node] = Math.min(pathLengths[node], len);
            }
        }
    		
    		//Run the DFS function recursively with all neighbors that haven't been visited yet, adding 1 to the previous path length.
        for (int neighbor : nodeNeighbors) {
            if (!visited[neighbor]) {
            //System.out.println("Node " + curr + " (" + ids[curr] + "), Neighbor " + neighbor);
            DFS(neighbors, visited, ids, val, len+1, pathLengths, node, neighbor); }
        }
    }
    
  • + 1 comment

    What the **** is the need for the variable val?

  • + 0 comments

    Python

    def findShortest(graph_nodes, graph_from, graph_to, ids, val):
        graph = defaultdict(set)
        for start, end in zip(graph_from, graph_to):
            graph[start].add(end)
            graph[end].add(start)
        
        min_path_len = math.inf
        for node, node_color in enumerate(ids, start=1):
            if node_color != val:
                continue
            visited = set([node])
            queue = deque(graph[node])
            curr_path_len = 0
            found_at = None
            while queue:
                curr = queue.popleft()
                if curr in visited:
                    continue
                visited.add(curr)
                curr_path_len += 1
                curr_color = ids[curr-1]
                if curr_color == node_color:
                    found_at = curr_path_len
                    break
                queue.extend(graph[curr])
            if found_at:
                min_path_len = min(min_path_len, found_at)
        if min_path_len == math.inf:
            return -1
        return min_path_len
    
  • + 0 comments

    javascript

    function findShortest(graphNodes, graphFrom, graphTo, ids, val) {
      let map = new Map()
      for (let i = 0; i < graphFrom.length; i++) {
        if (!map.has(graphFrom[i])) map.set(graphFrom[i], [])
        map.get(graphFrom[i]).push(graphTo[i])
        if (!map.has(graphTo[i])) map.set(graphTo[i], [])
        map.get(graphTo[i]).push(graphFrom[i])
      }
    
      let nodesToInvestigate = []
      for (let i = 1; i <= ids.length; i++) {
        if (ids[i - 1] == val) nodesToInvestigate.push(i)
      }
    
      if (nodesToInvestigate.length < 2) return -1
    
      let visited = new Set(), distances = []
      for (let i = 0; i < nodesToInvestigate.length; i++) {
        let queue = [[nodesToInvestigate[i], 0]]
        visited.add(nodesToInvestigate[i])
        while (queue.length > 0) {
          let [cur, steps] = queue.shift()
          visited.add(cur)
          if (ids[cur - 1] == val && cur != nodesToInvestigate[i]) {
            distances.push(steps)
            continue
          }
          queue.push(...map.get(cur).filter(to => !visited.has(to))
            .map(node => [node, steps + 1]))
        }
      }
      return Math.min(...distances)
    }
    
  • + 1 comment

    Test Case 12 has no answer and is the wrong expected output. There is no edge linking the nodes with colour 2 in the graph.