elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Distancia en una estructura de nodos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Distancia en una estructura de nodos  (Leído 1,486 veces)
SrCooper

Desconectado Desconectado

Mensajes: 137


Bazinga!


Ver Perfil
Distancia en una estructura de nodos
« en: 23 Diciembre 2014, 22:36 pm »

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

Código
  1. class Node {
  2.    int id;
  3.  
  4.    final List<Node> connectedNodes = new List<Nodes>();
  5.  
  6.    Node(this.id);
  7.  
  8.    void connectNodes(Node otherNode) {
  9.        if (otherNode == null) return;
  10.  
  11.        connectedNodes.add(otherNode);
  12.        otherNode.connectedNodes.add(this);
  13.    }
  14.  
  15.    void removeLinks(Node otherNode) {
  16.        if (otherNode == null) return;
  17.  
  18.        connectedNodes.removeWhere((node) => node == otherNode);
  19.        otherNode.connectedNodes.removeWhere((node) => node == this);
  20.    }
  21. }

Y en el main tengo la siguiente lista:

Código
  1. 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.

Código
  1. int findDistance(int id1, int id2) {
  2.        int count = 0;
  3.  
  4.        if (id1 == id2) return 0;
  5.  
  6.        Node node1 = nodes[id1];
  7.        Node node2 = nodes[id2];
  8.  
  9.        List<int> idsExpanded = new List<int>();
  10.        List<int> distances = new List<int>();
  11.  
  12.        void expand(Node n1) {
  13.            count++;
  14.  
  15.            for (var subNode in n1.connectedNodes) {
  16.                if (subNode.id == id2) distances.add(count);
  17.  
  18.                if (!idsExpanded.contains(subNode.id)) {
  19.                    idsExpanded.add(subNode.id);
  20.                    expand(subNode);
  21.                }
  22.            }
  23.  
  24.            count--;
  25.        }
  26.  
  27.        expand(node1);
  28.  
  29.        // Las ordena de menor a mayor
  30.        distances.sort();
  31.  
  32.        return distances.first;
  33.    }

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


En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Distancia en una estructura de nodos
« Respuesta #1 en: 24 Diciembre 2014, 00:19 am »

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? :/


En línea

SrCooper

Desconectado Desconectado

Mensajes: 137


Bazinga!


Ver Perfil
Re: Distancia en una estructura de nodos
« Respuesta #2 en: 24 Diciembre 2014, 01:01 am »

¿Skynet? xD

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

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

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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
interconexión de nodos
Redes
nosoqui 4 4,425 Último mensaje 10 Mayo 2011, 13:06 pm
por T0rete
nodos
Programación C/C++
alea 1 2,094 Último mensaje 3 Marzo 2012, 10:45 am
por Xandrete
No se eliminan nodos
Programación C/C++
BJM 2 1,977 Último mensaje 22 Enero 2013, 21:19 pm
por BJM
conexión inalambrica a distancia a distancia
Hacking Wireless
MAXIMUS33 2 2,809 Último mensaje 22 Agosto 2013, 16:15 pm
por MAXIMUS33
guardar nodos en txt
Programación C/C++
d91 1 5,089 Último mensaje 21 Abril 2014, 10:17 am
por eferion
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines