vitaliiznak · March 22, 2018 15:18 · Mar 22, 2018 · Mar 22, 2018 · Mar 22, 2018 · Mar 22, 2018
diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -49,7 +49,6 @@ function countStepsImperatively(startCoords, digitsSumLimit = 21) {
 
   while (queue.length > 0) {
     let coords = queue.pop();
-    console.log(JSON.stringify(coords));
     ++steps;
 
     coords.forEach((coord, index, coordsArray) => {
@@ -143,12 +142,11 @@ console.log(
 /**
  * return 13, number of points in 2 dimensional space
  * points are - [0,0] [0,-1] [0,-2] [-1,-1] [1,-1] [0,1] [0,2] [-1,1] [1,1] [-1,0] [-2,0] [1,0] [2,0]
-*/
+ */
 
 console.log(
   "countStepsImperatively([0,0], 21) return",
   countStepsImperatively([0, 0], 21)
 );
 //a lot of points I will not paste it here
 //return 287881
-
diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -49,6 +49,7 @@ function countStepsImperatively(startCoords, digitsSumLimit = 21) {
 
   while (queue.length > 0) {
     let coords = queue.pop();
+    console.log(JSON.stringify(coords));
     ++steps;
 
     coords.forEach((coord, index, coordsArray) => {
@@ -137,12 +138,17 @@ console.log(
 
 console.log(
   "countStepsImperatively([0,0], 1) return",
-  countStepsImperatively([0, 0], 1)
+  countStepsImperatively([0, 0], 2)
 );
-//return 5,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimensional space
+/**
+ * return 13, number of points in 2 dimensional space
+ * points are - [0,0] [0,-1] [0,-2] [-1,-1] [1,-1] [0,1] [0,2] [-1,1] [1,1] [-1,0] [-2,0] [1,0] [2,0]
+*/
 
 console.log(
   "countStepsImperatively([0,0], 21) return",
   countStepsImperatively([0, 0], 21)
 );
+//a lot of points I will not paste it here
 //return 287881
+
diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -130,18 +130,19 @@ function countStepsRecursively(
 }
 
 console.log(
-  "countStepsImperatively([0,0], 1) gives",
+  "countStepsImperatively([0,0], 1) return",
   countStepsImperatively([0], 1)
 );
-//gives 3,  trivial  points with coordinates [0],[-1],[1] in 1 dimensional space
+//return 3,  trivial  points with coordinates [0],[-1],[1] in 1 dimensional space
 
 console.log(
-  "countStepsImperatively([0,0], 1) gives",
+  "countStepsImperatively([0,0], 1) return",
   countStepsImperatively([0, 0], 1)
 );
-//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimensional space
+//return 5,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimensional space
 
 console.log(
-  "countStepsImperatively([0,0], 21) gives",
-  countStepsImperatively([0, 0, 0], 21)
+  "countStepsImperatively([0,0], 21) return",
+  countStepsImperatively([0, 0], 21)
 );
+//return 287881
diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -32,7 +32,7 @@ const coordsDigitsCalcSum = coords =>
     .reduce((acc, val) => acc + val, 0);
 
 /**
- * Represents a book.
+ *
  * @constructor
  * @param {[number,...]} coords - The coordinatesof a starting point for an arbytrary dimension
  * f.e [0,0] - 2 dimesnional space, [0,0,0] -threee dimensional space

diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -78,6 +78,12 @@ function countStepsImperatively(startCoords, digitsSumLimit = 21) {
   return steps;
 }
 
+/**
+ * For relatively large nambers you will recive a stack overflow error in your machine
+ * @param {*} coords
+ * @param {*} digitsSumLimit
+ * @param {*} processedNodes
+ */
 function countStepsRecursively(
   coords,
   digitsSumLimit = 21,

diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -127,13 +127,13 @@ console.log(
   "countStepsImperatively([0,0], 1) gives",
   countStepsImperatively([0], 1)
 );
-//gives 3,  trivial  points with coordinates [0],[-1],[1] in 1 dimension space
+//gives 3,  trivial  points with coordinates [0],[-1],[1] in 1 dimensional space
 
 console.log(
   "countStepsImperatively([0,0], 1) gives",
   countStepsImperatively([0, 0], 1)
 );
-//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimension space
+//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimensional space
 
 console.log(
   "countStepsImperatively([0,0], 21) gives",

diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -127,15 +127,15 @@ console.log(
   "countStepsImperatively([0,0], 1) gives",
   countStepsImperatively([0], 1)
 );
-//gives 3,  trivial  points with coordinates [0],[-1],[1]
+//gives 3,  trivial  points with coordinates [0],[-1],[1] in 1 dimension space
 
 console.log(
   "countStepsImperatively([0,0], 1) gives",
   countStepsImperatively([0, 0], 1)
 );
-//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0]
+//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0] in 3 dimension space
 
 console.log(
   "countStepsImperatively([0,0], 21) gives",
-  countStepsImperatively([0, 0], 21)
+  countStepsImperatively([0, 0, 0], 21)
 );
diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -1,5 +1,5 @@
 /**
- *  TASK DESCRIPTIONJ:
+ *  TASK DESCRIPTION
  *
  *  Consider 2 dimensional space, with discreate coordinates
  *  - a given starting point ex. (0, 0)

diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -1,3 +1,23 @@
+/**
+ *  TASK DESCRIPTIONJ:
+ *
+ *  Consider 2 dimensional space, with discreate coordinates
+ *  - a given starting point ex. (0, 0)
+ *  - you allow to move as  (x+1, y), (x-1,y), (x, y+1) , (x,y-1)
+ *  - RESTRICTION: you can not step into the point if the absolute number of a coordinates digits are grater than some N
+ *   f.e if N=21 and a point is (59, -79), sum of digits in coordinates os (5 + 9 + 7 + 9) = 30 > 27 (N)
+ *  the point is prohibited
+ *  - you can not step over the points
+ *
+ *  WHAT TO DO:
+ *  Create a function which recives as input
+ *    - arbitrary starting point for arbitrary space dimension
+ *    - sum digits limit
+ *  And outputs the number of points accessible from a starting point
+ *
+ *
+ * */
+
 const coordsDigitsCalcSum = coords =>
   coords
     .reduce(
@@ -11,6 +31,13 @@ const coordsDigitsCalcSum = coords =>
     )
     .reduce((acc, val) => acc + val, 0);
 
+/**
+ * Represents a book.
+ * @constructor
+ * @param {[number,...]} coords - The coordinatesof a starting point for an arbytrary dimension
+ * f.e [0,0] - 2 dimesnional space, [0,0,0] -threee dimensional space
+ * @param {number} number
+ */
 function countStepsImperatively(startCoords, digitsSumLimit = 21) {
   const queue = [];
 

diff --git a/bfs_search_excersice.js b/bfs_search_excersice.js
@@ -0,0 +1,114 @@
+const coordsDigitsCalcSum = coords =>
+  coords
+    .reduce(
+      (acc, el) =>
+        Math.abs(el)
+          .toString(10)
+          .split("")
+          .map(num => Number(num))
+          .concat(acc),
+      []
+    )
+    .reduce((acc, val) => acc + val, 0);
+
+function countStepsImperatively(startCoords, digitsSumLimit = 21) {
+  const queue = [];
+
+  let startCoordsDigitsSum = coordsDigitsCalcSum(startCoords);
+  if (startCoordsDigitsSum > digitsSumLimit) return 0;
+  let steps = 0;
+  queue.push(startCoords);
+  const processedNodes = { [startCoords]: [startCoords] };
+
+  while (queue.length > 0) {
+    let coords = queue.pop();
+    ++steps;
+
+    coords.forEach((coord, index, coordsArray) => {
+      const newCoordsPlus = coordsArray.slice();
+      newCoordsPlus[index] = coord + 1;
+      let coordsPlusDigitsSum = coordsDigitsCalcSum(newCoordsPlus);
+      if (
+        coordsPlusDigitsSum <= digitsSumLimit &&
+        !processedNodes[newCoordsPlus]
+      ) {
+        queue.push(newCoordsPlus);
+        processedNodes[newCoordsPlus] = newCoordsPlus;
+      }
+
+      const newCoordsMinus = coordsArray.slice();
+      newCoordsMinus[index] = coord - 1;
+      let coordsMinusDigitsSum = coordsDigitsCalcSum(newCoordsMinus);
+      if (
+        coordsMinusDigitsSum <= digitsSumLimit &&
+        !processedNodes[newCoordsMinus]
+      ) {
+        queue.push(newCoordsMinus);
+        processedNodes[newCoordsMinus] = newCoordsMinus;
+      }
+    });
+  }
+  return steps;
+}
+
+function countStepsRecursively(
+  coords,
+  digitsSumLimit = 21,
+  processedNodes = {}
+) {
+  if (processedNodes[coords]) {
+    return 0;
+  }
+  processedNodes[coords] = coords;
+  const digitsSum = coordsDigitsCalcSum(coords);
+
+  if (digitsSum > digitsSumLimit) {
+    return 0;
+  }
+  const [x, y] = coords;
+  return (
+    1 +
+    coords
+      .map((coord, index, coordsArray) => {
+        const newCoordsPlus = coordsArray.slice();
+        newCoordsPlus[index] = coord + 1;
+
+        const newCoordsMinus = coordsArray.slice();
+        newCoordsMinus[index] = coord - 1;
+        return (
+          (processedNodes[newCoordsPlus]
+            ? 0
+            : countStepsRecursively(
+                newCoordsPlus,
+                digitsSumLimit,
+                processedNodes
+              )) +
+          (processedNodes[newCoordsMinus]
+            ? 0
+            : countStepsRecursively(
+                newCoordsMinus,
+                digitsSumLimit,
+                processedNodes
+              ))
+        );
+      })
+      .reduce((acc, val) => acc + val, 0)
+  );
+}
+
+console.log(
+  "countStepsImperatively([0,0], 1) gives",
+  countStepsImperatively([0], 1)
+);
+//gives 3,  trivial  points with coordinates [0],[-1],[1]
+
+console.log(
+  "countStepsImperatively([0,0], 1) gives",
+  countStepsImperatively([0, 0], 1)
+);
+//gives 3,  trivial points with coordinate [0,0], [0,1], [0,-1], [-1,0]
+
+console.log(
+  "countStepsImperatively([0,0], 21) gives",
+  countStepsImperatively([0, 0], 21)
+);
No results found