Advertisement
ptownhero

Javascript Sets and Djikstra

Nov 23rd, 2022
640
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Takes a coordinate pair and tests to see if it's valid in the maximum grid value N
  2. const isValid = (x, y, N) => {
  3.     if ((x > 0 && x <= N) && (y > 0 && y <= N)) {
  4.         return true;
  5.     }
  6. }
  7.  
  8. const isEqual = (object1, object2) => {
  9.     console.log(object1)
  10.     console.log(object2)
  11.     let equal = true;
  12.     if ((object1.x !== object2.x) || (object1.y !== object2.y)) {
  13.         equal = false;
  14.     }
  15.     console.log(equal)
  16.     return equal;
  17. }
  18.  
  19. // Node factory function
  20. const coordinate = (x, y, distance = 0) => {
  21.     return {
  22.         x: x,
  23.         y: y,
  24.         distance: distance,
  25.     }
  26. }
  27.  
  28. // All possible routes a knight can take
  29. const col = [2, 2, -2, -2, 1, -1, 1, -1];
  30. const row = [1, -1, 1, -1, 2, 2, -2, -2];
  31.  
  32.  
  33. const knightTravels = (start, finish, N) => {
  34.  
  35.     // A new set to check if a chess space has been visited before
  36.     let visited = new Set();
  37.  
  38.     // Creating a queue and inserting node1
  39.     let queue = [];
  40.     queue.push(start);
  41.  
  42.     let count = 0;
  43.     // Loop queue until i t's empty
  44.     while (queue) {
  45.         // dequeue node 1
  46.         if(count === 12) break;
  47.         count++;
  48.         let node = queue.shift();
  49.         let x = node.x;
  50.         let y = node.y;
  51.         let d = node.distance;
  52.  
  53.         // If the current node is finish node
  54.         if (x === finish.x && y === finish.y) {
  55.             console.log(visited);
  56.             console.log(visited.size);
  57.             return d;
  58.         }
  59.  
  60.         // Adding current node to visited
  61.         visited.add(node);
  62.  
  63.         // Iterating over set to check for visited squares
  64.         // If a node is in visited we skip the node
  65.         // Check each movement for the knight and queue the valid moves
  66.         for (let i = 0; i <= row.length; i++) {
  67.             let x1 = x + row[i];
  68.             let y1 = y + col[i];
  69.            
  70.             if (isValid(x1, y1, N) === true) {
  71.                 let node = coordinate(x1, y1, d + 1);
  72.                 let hasVisited = false;
  73.  
  74.                 visited.forEach(item => {
  75.                     if(isEqual(item, node) === true) hasVisited = true;
  76.                 })
  77.  
  78.                 if (hasVisited === false) queue.push(node);
  79.             }
  80.         }
  81.     }
  82.     // return Infinity;
  83.     return visited;
  84. }
  85.  
  86. const gridSize = 7;
  87. const start = coordinate(0, 0);
  88. const end = coordinate(7, 7);
  89.  
  90. console.log(knightTravels(start, end, gridSize));
  91.  
  92. const getMoves = (x, y) => {
  93.     let coordinates = []
  94.     for(let i = 0; i <= row.length; i++) {
  95.         let x1 = x + row[i]
  96.         let y1 = y + col[i]
  97.         if (isValid(x1, y1, 7) === true) {
  98.             coordinates.push({x: x1, y: y1})
  99.         }
  100.     }
  101.     return coordinates;
  102. }
  103.  
  104. console.log(getMoves(1, 2));
  105. console.log(getMoves(2, 1));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement