# Farthest Nodes Coderbyte Solution

0

Have the function FarthestNodes(strArr) read strArr which will be an array of hyphenated letters representing paths between those two nodes.

For example: ["a-b","b-c","b-d"] means that there is a path from node a to b (and b to a), b to c, and b to d. Your program should determine the longest path that exists in the graph and return the length of that path. So for the example above, your program should return 2 because of the paths a-b-c and d-b-c. The path a-b-c also means that there is a path c-b-a. No cycles will exist in the graph and every node will be connected to some other node in the graph.

Farthest Nodes Coderbyte Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class FarthestNodes {
int FarthestNodes(String[] strArr) {
List<String> nodes = new ArrayList<String>();
List<String> connections = new ArrayList<String>();

for (String connection : strArr) {

String[] connectionNodes = connection.split("-");
for (String node : connectionNodes) {
if (!nodes.contains(node)) {
}
}
}

Field field = build(nodes, connections);
int longestDist = 0;
for (Node node : field.nodes) {
int longestDistTraveled = travel(node, new ArrayList<Node>(), 0);
if (longestDistTraveled > longestDist) {
longestDist = longestDistTraveled;
}
}
return longestDist;
}

Field build(List<String> nodeNames, List<String> connections) {
Field field = new Field();
for (String nodeName : nodeNames) {
Node node = new Node(nodeName);
}

for (String connection : connections) {
String[] neighbours = connection.split("-");
Node from = field.findNode(neighbours[0]);
Node to = field.findNode(neighbours[1]);
}

return field;
}

int travel(Node node, List<Node> visited, int distance) {

List<Connection> connections = node.getConnections(visited);
if (connections.size() == 0) {
return distance;
}

int longestDistance = distance;
for (Connection connection : connections) {
int travelDistance = travel(connection.to, visited, distance + 1);
if (travelDistance > longestDistance) {
longestDistance = travelDistance;
}
}

return longestDistance;
}

class Field {
List<Node> nodes;

Field() {
this.nodes = new ArrayList<Node>();
}

}

Node findNode(String nodeName) {
for (Node node : nodes) {
if (node.name.equals(nodeName)) {
return node;
}
}
return null;
}
}

class Node {
String name;
int weight;
List<Connection> connections;

Node(String name) {
this.name = name;
this.weight = 0;
this.connections = new ArrayList<Connection>();
}

Connection connection = new Connection(this, node);
}

List<Connection> getConnections(List<Node> visited) {
List<Connection> connections = new ArrayList<Connection>();
for (Connection connection : this.connections) {
boolean valid = true;
for (Node node : visited) {
if (connection.to == node) {
valid = false;
}
}

}
return connections;
}
}

class Connection {
Node from;
Node to;

Connection(Node from, Node to) {
this.from = from;
this.to = to;
}
}

public static void main (String[] args) {
// keep this function call here
Scanner s = new Scanner(System.in);
FarthestNodes c = new FarthestNodes();
System.out.print(c.FarthestNodes(new String[] {"b-a","c-e","b-c","d-c"}));
}

}