[dev-tasks] Pathfinding

readme.txt

Você está lá, naquela imensa lata velha, preso na órbita de Plutão sabe lá por quantos anos...5, 10, quem sabe?
Todos os dias você verifica os equipamentos, os sistemas, realiza testes no reator e aguarda novas instruções do controle da missão.
O que você ainda não sabe é que hoje o seu dia será menos monótono. Ocorreu uma sobrecarga no velho reator da estação durante um
dos testes de rotina e todos os sistemas de suporte a vida estão desligados.
Você sabe que tem pouco tempo de ida, seu oxigênio está acabando e você tem que percorrer o longo e tortuoso labirinto
de corredores e chegar a tempo na capsula de salvamento.

Desculpem, eu gosto de storytelling :D

Basicamente é um problema de pathfinding. Existem muitos algoritmos para se resolver isso,
 mas deixo a escolha p/ vocês... porém, quem conseguir levar o astronauta moribundo pelo caminho mais curto ganha mais pontos :)

Estou enviando um mapa em forma de matriz, apenas como exemplo (vocês podem usar a estrutura de dados que quiserem )

Zero (0): são caminhos possíveis de serem percorridos,
Um (1): o astronauta
Dois (2): a capsula de salvamento
Nove (9): Obstaculos (local não pode ser visitado nem atravessado. )

maze = [
  [0,0,0,9,9,0,0,0,0,0],
  [0,9,0,0,0,0,0,0,0,0],
  [0,9,9,0,9,9,9,9,0,0],
  [0,0,9,0,0,0,1,9,0,0],
  [0,0,9,0,9,9,9,9,0,0],
  [0,0,9,0,0,0,0,0,0,0],
  [0,0,9,0,9,9,9,9,9,0],
  [0,0,0,0,0,0,0,0,9,0],
  [9,9,9,9,9,9,9,9,9,2],

]

O programa deverá imprimir como saída o caminho que o astronauta deverá fazer.

Quem se interessar em fazer o algoritmo utilizando o melhor caminho, sugiro dar uma olhada no Algoritmo do Caminho de Custo Mínimo de Dijkstra.

http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html

P.S.: Os códigos foram desenvolvidos e testados usando o Chrome.
A solução para o problema é o último caso de testes em dijkstra_test.js

dijkstra.js

/**
 *  Author: Dhiego R. Pinto ( dhiegorp at gmail.com )
 *  Lots of improvements todo
 *
 *
 *
 */
function ShortestPath(_graph, _source, _target) {

  var graph = _graph;
  var source = _source;
  var target = _target;

  this.dijkstra = function() {

    var unchecked_vert = Object.keys(graph);

    var initialize = function () {
      for(key in graph) {
        graph[key]['previous'] = null;
        graph[key]['cost'] = Infinity; //some huge dumb number
        if( key == source ) {
          graph[key]['cost'] = 0;
        }
      }
    };

    var minimun_cost_vertex = function() {
        var minval = null;
        var minvert = null;
        
        for( var i=0, length = unchecked_vert.length; i < length; i++) {
          if( minval == null || (minval > graph[unchecked_vert[i]].cost) ){
            minval = graph[unchecked_vert[i]].cost;
            minvert = unchecked_vert[i];
          }
        }

      return minvert;
    };

    var relax = function () {

      //already checked every vertex, relax function is over
      if (unchecked_vert.length == 0) {
        return;
      }

      //get the vertex that was not checked yet with the minimun calculated cost
      var uvert = minimun_cost_vertex();

      // remove the uvert from the unchecked_vert. 
      unchecked_vert.splice(unchecked_vert.indexOf(uvert), 1);

      //for every adjacent vertexes of uvert, relax edges
      var adjacents = Object.keys(graph[uvert].edges);
      var dist_u = graph[uvert].cost;
      var dist_v = null;
      var weight_uv = null;

      for(var i = 0, length = adjacents.length; i < length; i++ ) {
        if(unchecked_vert.indexOf(adjacents[i]) >= 0 ) {

          dist_u =graph[uvert].cost;
          weight_uv = graph[uvert].edges[adjacents[i]];
          dist_v = graph[adjacents[i]].cost;

          if( dist_u + weight_uv < dist_v) {
            graph[adjacents[i]]['cost'] = dist_u + weight_uv;

            //when a vertex's cost update occurs, also updates the source (previous) vertex of the current vertex.
            //it will be used to reconstruct the shortest path
            graph[adjacents[i]]['previous'] = uvert;
          }
        }

      }

      relax();

    };

    var path_until_source = function() {
      if( target != null ) {
        var path = [];
        var vertex = graph[target];
        if( vertex != null && vertex.previous != null) {
          path.push(target);
          while(vertex != null && vertex.previous != null) {
                path.push(vertex.previous);
                vertex = graph[vertex.previous];
          }
          path = path.reverse();
          graph[target]['path_to_source'] = path;
        }
      }
    };

    initialize();
    relax();
    path_until_source();
    return graph[target].path_to_source || [];
  }

}

dijkstra_test.js

(
  function() {
      console.log('testing ShortestPath.dijkstra');
      this.maze = [];

      this.test = function(name, text, expected, result) {
        var _result = result;
        var _expected = expected;
        console.log("["+( JSON.stringify(_expected) === JSON.stringify(_result) ) +"] " + name +'::' + text + "-> expected = " + expected + " result=" + result);
      };

        (function testSimplePath() {
          maze = {
            "A": { edges:{ "B":3, "C":1 }, cost:null },
            "B": { edges:{  }, cost:null },
            "C": { edges:{ "B":1 }, cost: null}
          };
          var expected = ["A", "C", "B"];
          var result = new ShortestPath(this.maze, "A", "B").dijkstra();
          test("testSimplePath", "from A to B", expected, result);
        })();

        (function testDiffPath() {
          maze = {
            "A": { edges:{ "B":5, "D":10 }, cost:null },
            "B": { edges:{ "C":1, "D" :4 }, cost:null },
            "C": { edges:{ "D":2 }, cost: null},
            "D": { edges:{  }, cost: null}
          };
          var expected = ["A", "B", "C", "D"];
          var result = new ShortestPath(this.maze, "A", "D").dijkstra();
          test("testDiffPath", "from A to D", expected, result);
        })();

        (function testUnreachable() {
          maze = {
            "A": { edges:{ "B":1 }, cost: null},
            "B": { edges:{ "C":1, "D":1, "E":1 }, cost: null },
            "C": { edges:{ "F":1, "G":1 }, cost: null },
            "D": { edges:{ "H":1 }, cost: null },
            "E": { edges:{ "I":1, "J":1 }, cost: null },
            "F": { edges:{       }, cost: null },
            "G": { edges:{       }, cost: null },
            "H": { edges:{ "N":1 }, cost: null },
            "I": { edges:{ "K":1 }, cost: null },
            "J": { edges:{ "L":1, "M":1 }, cost: null },
            "K": { edges:{  }, cost: null },
            "N": { edges:{  }, cost: null },
          };
          var expected = [];
          var result = new ShortestPath(this.maze, "C", "N").dijkstra();
          test("testUnreachable", "from C to N", expected, result);
        })();

        (function testAtoF() {
          maze = {
            "A":{edges:{"B":5, "C":10}, cost : null},
            "B":{edges:{"D":6, "E":3 }, cost : null},
            "C":{edges:{ }, cost : null},
            "D":{edges:{"F":6 }, cost : null},
            "E":{edges:{"C":2, "D":2, "G":2 }, cost : null},
            "F":{edges:{ }, cost : null},
            "G":{edges:{"F":2 }, cost : null}
          };
          var expected = ["A", "B", "E", "G", "F"];
          var result = new ShortestPath(this.maze, "A", "F").dijkstra();
          test("testAtoF", "from A to F", expected, result);
        })();

        (function testDyingCosmonaut(){
          /*
            A B C D E F G H I J
          A[0,0,0,9,9,0,0,0,0,0],
          B[0,9,0,0,0,0,0,0,0,0],
          C[0,9,9,0,9,9,9,9,0,0],
          D[0,0,9,0,0,0,1,9,0,0],
          E[0,0,9,0,9,9,9,9,0,0],
          F[0,0,9,0,0,0,0,0,0,0],
          G[0,0,9,0,9,9,9,9,9,0],
          H[0,0,0,0,0,0,0,0,9,0],
          I[9,9,9,9,9,9,9,9,9,2],
          */

          maze = {
            "AA":{edges:{"AB":1, "BA":1}, cost:null},
            "AB":{edges:{"AA":1, "AC":1, "BB":Infinity}, cost:null},
            "AC":{edges:{"AB":1, "AD":Infinity, "BC":1}, cost:null},
            "AD":{edges:{"AC":Infinity, "AE":Infinity, "BD":Infinity}, cost:null},
            "AE":{edges:{"AD":Infinity, "AF":Infinity, "BE":Infinity}, cost:null},
            "AF":{edges:{"AE":Infinity, "AG":1, "BF": 1}, cost:null},
            "AG":{edges:{"AF":1, "AH":1, "BG": 1}, cost:null},
            "AH":{edges:{"AG":1, "AI":1, "BH": 1}, cost:null},
            "AI":{edges:{"AH":1, "AJ":1, "BI": 1}, cost:null},
            "AJ":{edges:{"AI":1, "BJ":1}, cost:null},
            "BA":{edges:{"AA":1, "BB":Infinity },cost:null}, //falta o "CA":1
            "BB":{edges:{"AB": Infinity, "BA":Infinity, "BC":Infinity, "CB":Infinity},cost:null},//falta o "CB":Infinity
            "BC":{edges:{"AC":1, "BB":Infinity, "BD":1, "CC":Infinity },cost:null},//falta o "CC":Infinity
            "BD":{edges:{"AD":Infinity, "BC":1, "BE":1, "CD":1 },cost:null},//falta o "CD":1
            "BE":{edges:{"BD":1, "BF":1, "AE":Infinity, "CE":Infinity },cost:null},//falta o "CE":Infinity
            "BF":{edges:{"AF":1, "BE":1, "BG":1, "CF":Infinity },cost:null},//falta o "CF":Infinity
            "BG":{edges:{"AG":1, "BF":1, "BH":1, "CG":Infinity },cost:null},//falta o "CG":Infinity
            "BH":{edges:{"AH":1, "BG":1, "BI":1, "CH":Infinity },cost:null},//falta o "CH":Infinity
            "BI":{edges:{"AI":1, "BH":1, "BJ":1, "CI":1},cost:null},//falta o "CI":1
            "BJ":{edges:{"AJ":1, "BI":1, "CJ":1},cost:null}, //falta o "CJ":1
            "CA":{edges:{"BA":1, "CB": Infinity, "DA":1}, cost:null},
            "CB":{edges:{"BB":Infinity, "CA":Infinity, "CC":Infinity, "DB":Infinity }, cost:null},
            "CC":{edges:{"BC":Infinity, "CB":Infinity, "CD":Infinity, "DC":Infinity}, cost:null},
            "CD":{edges:{"BD":1, "CC":Infinity, "CE":Infinity, "DD":1, }, cost:null},
            "CE":{edges:{"BE":Infinity, "CD":Infinity, "CF":Infinity, "DE":Infinity}, cost:null},
            "CF":{edges:{"BF":Infinity, "CD":Infinity, "CG":Infinity, "DF":Infinity}, cost:null},
            "CG":{edges:{"BG":Infinity, "CF":Infinity, "CH":Infinity, "DG":Infinity}, cost:null},
            "CH":{edges:{"BH":Infinity, "CG":Infinity, "CI":Infinity, "DH":Infinity}, cost:null},
            "CI":{edges:{"BI":1, "CH":Infinity, "CJ":1, "DI":1}, cost:null},
            "CJ":{edges:{"BJ":1, "CI":1, "DJ":1}, cost: null},
            "DA":{edges:{"CA":1, "DB":1, "EA":1}, cost: null},
            "DB":{edges:{"CB":Infinity, "DA":1, "DC":Infinity, "EB":1}, cost: null},
            "DC":{edges:{"CC":Infinity, "DB":Infinity, "DD":Infinity, "EC":Infinity}, cost: null},
            "DD":{edges:{"CD":1, "DC":Infinity, "DE":1, "ED":1}, cost: null},
            "DE":{edges:{"CE":Infinity, "DD":1, "DF":1, "EE":Infinity}, cost: null},
            "DF":{edges:{"CF":Infinity, "DE":1, "DG":1, "EF":Infinity}, cost: null},
            "DG":{edges:{"CG":Infinity, "DF":1, "DH":Infinity, "EG":Infinity}, cost: null},
            "DH":{edges:{"CH":Infinity, "DG":Infinity, "DI":Infinity, "EH":Infinity}, cost: null},
            "DI":{edges:{"CI":1, "DH":Infinity, "DJ":1, "EI":1}, cost: null},
            "DJ":{edges:{"CJ":1, "DI":1, "EJ":1}, cost: null},
            "EA":{edges:{"DA":1, "EB":1, "FA":1}, cost: null},
            "EB":{edges:{"DB":1, "EA":1, "EC":Infinity, "FB":1}, cost: null},
            "EC":{edges:{"DC":Infinity, "EB":Infinity, "ED":Infinity, "FC":Infinity}, cost: null},
            "ED":{edges:{"DD":1, "EC":Infinity, "EE":Infinity, "FD":1}, cost: null},
            "EE":{edges:{"DE":Infinity, "ED":Infinity, "EF":Infinity, "FE":Infinity}, cost: null},
            "EF":{edges:{"DF":Infinity, "EE":Infinity, "EG":Infinity, "FF":Infinity}, cost: null},
            "EG":{edges:{"DG":Infinity, "EF":1, "EH":Infinity, "FG":Infinity}, cost: null},
            "EH":{edges:{"DH":Infinity, "EG":Infinity, "EI":Infinity, "FH":Infinity}, cost: null},
            "EI":{edges:{"DI":1, "EH":Infinity, "EJ":1, "FI":1}, cost: null},
            "EJ":{edges:{"DJ":1, "EI":1, "FJ":1}, cost: null},
            "FA":{edges:{"EA":1, "FB":1, "GA":1}, cost: null},
            "FB":{edges:{"EB":1, "FA":1, "FC":Infinity, "GB":1}, cost: null},
            "FC":{edges:{"EC":Infinity, "FB":Infinity, "FD":Infinity, "GC":Infinity}, cost: null},
            "FD":{edges:{"ED":1, "FC":Infinity, "FE":1, "GD":1}, cost: null},
            "FE":{edges:{"EE":Infinity, "FD":1, "FF":1, "GE":Infinity}, cost: null},
            "FF":{edges:{"EF":Infinity, "FE":1, "FG":1, "GF":Infinity}, cost: null},
            "FG":{edges:{"EG":Infinity, "FF":1, "FH":1, "GG":Infinity}, cost: null},
            "FH":{edges:{"EH":Infinity, "FG":1, "FI":1, "GH":Infinity}, cost: null},
            "FI":{edges:{"EI":1, "FH":1, "FJ":1, "GI":1}, cost: null},
            "FJ":{edges:{"EJ":1, "FI":1, "GJ":1}, cost: null},
            "GA":{edges:{"FA":1, "GB":1, "HA":1}, cost: null},
            "GB":{edges:{"FB":1, "GA":1, "GC":Infinity, "HB":1}, cost: null},
            "GC":{edges:{"FC":Infinity, "GB":Infinity, "GD":Infinity, "HC":Infinity}, cost: null},
            "GD":{edges:{"FD":1, "GC":Infinity, "GE":Infinity, "HD":1}, cost: null},
            "GE":{edges:{"FE":Infinity, "GD":Infinity, "GF":Infinity, "HE":Infinity}, cost: null},
            "GF":{edges:{"FF":Infinity, "GE":Infinity, "GG":Infinity, "HF":Infinity}, cost: null},
            "GG":{edges:{"FG":Infinity, "GF":Infinity, "GH":Infinity, "HG":Infinity}, cost: null},
            "GH":{edges:{"FH":Infinity, "GG":Infinity, "GI":Infinity, "HH":Infinity}, cost: null},
            "GI":{edges:{"FI":Infinity, "FH":Infinity, "FJ":Infinity, "GI":Infinity}, cost: null},
            "GJ":{edges:{"FJ":1, "GI":Infinity, "HJ":1}, cost: null},
            "HA":{edges:{"GA":1, "HB":1, "IA":Infinity}, cost: null},
            "HB":{edges:{"GB":1, "HA":1, "HC":1, "IB":Infinity}, cost: null},
            "HC":{edges:{"GC":Infinity, "HB":1, "HD":1, "IC":Infinity}, cost: null},
            "HD":{edges:{"GD":Infinity, "HC":1, "HE":1, "ID":Infinity}, cost: null},
            "HE":{edges:{"GE":Infinity, "HD":1, "HF":1, "IE":Infinity}, cost: null},
            "HF":{edges:{"GF":Infinity, "HE":1, "HG":1, "IF":Infinity}, cost: null},
            "HG":{edges:{"GG":Infinity, "HF":1, "HH":1, "IG":Infinity}, cost: null},
            "HH":{edges:{"GH":Infinity, "HG":1, "HI":1, "IH":Infinity}, cost: null},
            "HI":{edges:{"GI":Infinity, "HH":Infinity, "HJ":Infinity, "II":Infinity}, cost: null},
            "HJ":{edges:{"GJ":1, "HI":Infinity, "IJ":1}, cost: null},
            "IA":{edges:{"HA":Infinity, "IB":Infinity}, cost: null},
            "IB":{edges:{"HB":Infinity, "IA":Infinity, "IC":Infinity}, cost: null},
            "IC":{edges:{"HC":Infinity, "IB":Infinity, "ID":Infinity}, cost: null},
            "ID":{edges:{"HD":Infinity, "IC":Infinity, "IE":Infinity}, cost: null},
            "IE":{edges:{"HE":Infinity, "ID":Infinity, "IF":Infinity}, cost: null},
            "IF":{edges:{"HF":Infinity, "IE":Infinity, "IG":Infinity}, cost: null},
            "IG":{edges:{"HG":Infinity, "IF":Infinity, "IH":Infinity}, cost: null},
            "IH":{edges:{"HH":Infinity, "IG":Infinity, "II":Infinity}, cost: null},
            "II":{edges:{"HI":Infinity, "IH":Infinity, "IJ":Infinity}, cost: null},
            "IJ":{edges:{"HJ":1, "II":Infinity}, cost: null}
          }

          var expected = ["DG", "DF", "DE", "DD", "ED", "FD", "FE", "FF", "FG", "FH", "FI", "FJ", "GJ", "HJ", "IJ"];
          var result = new ShortestPath(this.maze, "DG", "IJ").dijkstra();
          test("testDyingCosmonaut", "from DG to IJ", expected, result);
        })();

  }
)();