import java.util.*;
public class Solution11 extends Solution {
public Solution11() { super(11); }
public static void main(String[] args) {
Solution11 solution = new Solution11();
solution.testPartTwo();
}
@Override
String solvePartOne(String inputData) {
Map> graph = buildGraph(inputData);
return String.valueOf(countPaths(graph, "you", "out"));
}
@Override
String solvePartTwo(String inputData) {
Map> graph = buildGraph(inputData);
Set required = new HashSet<>(Arrays.asList("dac", "fft"));
int total = countPathsRequiredNodes(graph, "svr", "out", new ArrayList<>(), required);
return String.valueOf(total);
}
private Map> buildGraph(String inputData) {
Map> graph = new HashMap<>();
for (String line : inputData.split("\n")) {
String[] parts = line.split(":");
String from = parts[0].trim();
List 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> 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> graph, String current, String end,
List path, Set required) {
List 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;
}
}