Foro de elhacker.net

Buenos días a todos, estoy resolviendo un problema en la siguiente web: codingame.com (http://codingame.com) (totalmente recomendada si no la conociais). El caso es que para resolverlo he creado una clase como esta:

class Node {
    int id;
 
    final List<Node> connectedNodes = new List<Nodes>();
 
    Node(this.id);
 
    void connectNodes(Node otherNode) {
        if (otherNode == null) return;
 
        connectedNodes.add(otherNode);
        otherNode.connectedNodes.add(this);
    }
 
    void removeLinks(Node otherNode) {
        if (otherNode == null) return;
 
        connectedNodes.removeWhere((node) => node == otherNode);
        otherNode.connectedNodes.removeWhere((node) => node == this);
    }
}

Y en el main tengo la siguiente lista:

List<Node> nodes = new List<Node>(size);

Ahora bien, necesito una función para encontrar la distancia minima entre dos nodos. Tras devanarme los sesos durante un buen rato, he escrito la siguiente función que (sorpresa, sorpresa), no funciona.

int findDistance(int id1, int id2) {
        int count = 0;
 
        if (id1 == id2) return 0;
 
        Node node1 = nodes[id1];
        Node node2 = nodes[id2];
 
        List<int> idsExpanded = new List<int>();
        List<int> distances = new List<int>();
 
        void expand(Node n1) {
            count++;
 
            for (var subNode in n1.connectedNodes) {
                if (subNode.id == id2) distances.add(count);
 
                if (!idsExpanded.contains(subNode.id)) {
                    idsExpanded.add(subNode.id);
                    expand(subNode);
                }
            }
 
            count--;
        }
 
        expand(node1);
 
        // Las ordena de menor a mayor
        distances.sort();
 
        return distances.first;
    }

He buscado información sobre búsqueda en árboles y grafos por ahí, pero debido a que mis conocimientos de algoritmos son muy limitados (no soy universitario ni nada de eso, he aprendido por mi cuenta) no suelo entender las páginas que encuentro.

Agradecería si alguien me pudiese explicar el método que debería usar o cual es la manera optima de diseñar esta función.

El maravilloso lenguaje que estoy usando es Dart, una especie de mezcla entre javascript y Java, para que nadie se asuste  :xD

Un saludo y gracias de antemano.

PD: El problema es el Skynet Finale - Level 2, de los difíciles, por si alguien ya conocía la página

Yo también estoy en Codingame :O ¿Skynet? xD

Dado que es una página de retos, no has pensado en tomártelo como un reto personal el completar el código? :/

Sí, es el segundo de los difíciles:  http://www.codingame.com/puzzles (http://www.codingame.com/puzzles)


Sí, de hecho es así como me lo estoy tomando y como me tomo todos los retos. Lo que estoy pidiendo no es eso, ni la solución del problema, ni siquiera una sola línea de código :xD

Lo que estoy pidiendo es algún consejo, explicación o página externa con información acerca de búsqueda en diagramas de árbol. O que alguien me diga si voy por buen camino, si hay algún método mejor y más eficiente para hacer eso o si la idea es bueno pero lo estoy implementando mal.

Con lo que llevo hecho (sin hacer búsquedas) he conseguido pasar los cuatro primeros tests, pero los dos últimos se me atascan y creo que no se pueden resolver sin esta función.

Un saludo.