Last active
March 22, 2018 15:18
-
-
Save vitaliiznak/1bf50f6ff582495be9a5cb05388dc281 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * TASK DESCRIPTION | |
| * | |
| * 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( | |
| (acc, el) => | |
| Math.abs(el) | |
| .toString(10) | |
| .split("") | |
| .map(num => Number(num)) | |
| .concat(acc), | |
| [] | |
| ) | |
| .reduce((acc, val) => acc + val, 0); | |
| /** | |
| * | |
| * @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 = []; | |
| 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; | |
| } | |
| /** | |
| * 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, | |
| 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) return", | |
| countStepsImperatively([0], 1) | |
| ); | |
| //return 3, trivial points with coordinates [0],[-1],[1] in 1 dimensional space | |
| console.log( | |
| "countStepsImperatively([0,0], 1) return", | |
| countStepsImperatively([0, 0], 2) | |
| ); | |
| /** | |
| * 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment