public Solution11() { super(11); }

public static void main(String[] args) {

Solution11 solution = new Solution11();

solution.testPartTwo();

}

@Override

String solvePartOne(String inputData) {

Map<String, List<String>> graph = buildGraph(inputData);

return String.valueOf(countPaths(graph, "you", "out"));

}

@Override

String solvePartTwo(String inputData) {

Map<String, List<String>> graph = buildGraph(inputData);

Set<String> required = new HashSet<>(Arrays.asList("dac", "fft"));

int total = countPathsRequiredNodes(graph, "svr", "out", new ArrayList<>(), required);

return String.valueOf(total);

}

private Map<String, List<String>> buildGraph(String inputData) {

Map<String, List<String>> graph = new HashMap<>();

for (String line : inputData.split("\n")) {

String[] parts = line.split(":");

String from = parts[0].trim();

List<String> toList = new ArrayList<>();

if (parts.length > 1 && !parts[1].trim().isEmpty()) {

for (String s : parts[1].trim().split("\\s+")) toList.add(s.trim());

}

graph.put(from, toList);

}

return graph;

}

private int countPaths(Map<String, List<String>> graph, String current, String end) {

if (current.equals(end)) return 1;

int count = 0;

for (String next : graph.getOrDefault(current, Collections.emptyList())) {

count += countPaths(graph, next, end);

}

return count;

}

private int countPathsRequiredNodes(Map<String, List<String>> graph, String current, String end,

List<String> path, Set<String> required) {

List<String> newPath = new ArrayList<>(path);

newPath.add(current);

if (current.equals(end)) {

if (newPath.containsAll(required)) return 1;

return 0;

}

int count = 0;

for (String next : graph.getOrDefault(current, Collections.emptyList())) {

count += countPathsRequiredNodes(graph, next, end, newPath, required);

}

return count;

}