Advent of Code 2024 - Queréis problemas?

He construido un grafo basado en listas (bueno, en mi caso, conjuntos) de adyacencia y un conjunto de candidatos de ordenadores por lo que buscar.

Luego, he cogido el conjunto de candidatos y he aplicado un algoritmo recursivo que busca ciclos de tamaño 3 que empiecen y acaben por el nodo de origen esperado.

public class LANParty {

private final
Map<String, Set<String>> graph = new HashMap<>();
private final Set<String> computerCandidates = new HashSet<>();

public LANParty(List<String> inputs) {
    for(String input : inputs) {
        String[] data = input.split("-");
        String pc1 = data[0];
        String pc2 = data[1];

        Set<String> connectedPcs = graph.getOrDefault(pc1, new HashSet<>());
        connectedPcs.add(pc2);
        graph.put(pc1, connectedPcs);

        if(pc1.startsWith("t")) {
            computerCandidates.add(pc1);
        }

        connectedPcs = graph.getOrDefault(pc2, new HashSet<>());
        connectedPcs.add(pc1);
        graph.put(pc2, connectedPcs);

        if(pc2.startsWith("t")) {
            computerCandidates.add(pc2);
        }
    }

}

public long solveA() {

    Set<Set<String>> networks = new HashSet<>();

    for(String computer : computerCandidates) {
        findNetworks(0,computer,computer, new ArrayList<>(), networks);
    }

    return networks.size();
}

private void findNetworks(int pathSize, final String initialComputer, String computer, List<String> path, Set<Set<String>> networks) {

    if((pathSize == 3) && (initialComputer.equals(computer))) {
        networks.add(new HashSet<>(path));
        return;
    } else if(pathSize == 3) {
        return;
    } else if((pathSize > 1) && (initialComputer.equals(computer))) {
        return;
    }

    Set<String> childComputers = graph.get(computer);
    for(String childComputer : childComputers) {
        path.add(childComputer);
        findNetworks(pathSize+1, initialComputer, childComputer, path, networks);
        path.remove(childComputer);
    }

}

}

He tenido una idea feliz para la parte 2 que además me ha funcionado a la primera tanto para el sample como el input.

Barajé dos opciones: tirar por clustering o por cliques. Opté por clustering.

Partí de la premisa de que allá donde esté la solución debe haber una mayor densidad de vértices. Igual que Mandarino, tiré de mi librería de confianza para grafos, en mi caso JGraphT.

Construí el grafo, y a continuación usé la clase ClusteringCoefficient que permite calcular para cada vértice del grafo un score que indica lo conectado que está a otros vértices. Lancé una ejecución de prueba con el ejemplo para analizar los resultados que me arrojaba y vi que de todos los vértices, había 8 que tenían el mayor score (0.5). Entre esos 8 vértices estaban los 4 que eran solución.

Pensé:

• "Vale, y ahora como distingo los vértices/ordenadores que son solución respecto a los que no lo son?".

Fue entonces tuve la idea feliz en cuestión:

Me imaginé que aquellos vértices que sean solución, además de tener el máximo score, la mayor parte de sus vecinos tendrían también el mismo máximo score. Para verificar la idea, cogí la ejecución de prueba y examiné los vecinos de todos los vértices que tenían score 0.5 (candidatos), poniendo en mayúsculas aquellos vecinos que estuvieran también en la lista de candidatos:

de -> cg, CO, TA, KA - 3 de 4 vecinos están en candidatos.
co -> KA, TA, DE, tc - 3 de 4 vecinos están en candidatos.
vc -> aq, ub, WQ, tb - 1 de 4 vecinos están en candidatos.
ta -> CO, KA, DE, kh - 3 de 4 vecinos están en candidatos.
td -> tc, WH, qp, yn - 1 de 4 vecinos están en candidatos.
wh -> tc, TD, yn, qp - 1 de 4 vecinos están en candidatos.
ka -> CO, tb, TA, DE - 3 de 4 vecinos están en candidatos.
wq -> tb, ub, aq, VC - 1 de 4 vecinos están en candidatos.

Efectivamente, los vértices que forman parte de la solución (de, co, ka y ka), tienen una mayor proporción de vecinos que también forman parte de candidatos (75%) frente a los que no (25%).

Con esto, ya tenía todo para montar el algoritmo:

• Ejecuto ClusteringCoefficient para prefiltrar y quedarme con los candidatos con el score más alto.
• Para cada candidato, obtengo dos conjuntos: el de sus vecinos, y el de los vecinos que además son candidatos (intersección).
• Genero un segundo score para el candidato: score = nº de vecinos que son candidatos / nº vecinos totales.
• Si este score es el score más alto hasta el momento, actualizo el score más alto y me guardo en un conjunto los vértices que forman parte de dicho score.

Finalmente, es una cuestión de recolectar todos los elementos del conjunto resultado y ordenarlos alfabéticamente y separado por comas.
¡Me sorprendió mucho ver que funcionó a la primera tanto para el sample como para el input!

public class LANParty2 {

private Graph<String, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

public LANParty2(List<String> inputs) {
    for(String input : inputs) {

        String[] data = input.split("-");
        String pc1 = data[0];
        String pc2 = data[1];

        graph.addVertex(pc1);
        graph.addVertex(pc2);
        graph.addEdge(pc1,pc2);

    }

}

public String solveB() {

    ClusteringCoefficient<String, DefaultEdge> clustering = new ClusteringCoefficient<>(graph);

    Map<String,Double> scores = clustering.getScores();

    Optional<Double> maxScore = scores.values().stream().max(Double::compareTo);

    if(maxScore.isEmpty()) {
        return StringUtils.EMPTY;
    }

    Set<String> candidates = scores.entrySet()
            .stream()
            .filter(entry -> entry.getValue().equals(maxScore.get()))
            .map(Map.Entry::getKey).collect(Collectors.toSet());

 
    
    float bestScore = 0;
    Set<String> bestCluster = new HashSet<>();
    for(String candidate : candidates) {
        Set<String> neighbours = Graphs.neighborSetOf(graph, candidate);
        Set<String> commonVertexes = SetUtils.intersection(candidates, neighbours);
        float score = (float) commonVertexes.size() / (float) neighbours.size();
        if(score > bestScore) {
            bestCluster = new HashSet<>(commonVertexes);
            bestCluster.add(candidate);
            bestScore = score;
        }
    }
    return bestCluster.stream().sorted().collect(Collectors.joining(","));
}