Last active
May 15, 2016 03:01
-
-
Save aeisenberg/88eac6bcb0cfa8081072b62553ec436b to your computer and use it in GitHub Desktop.
Here is a generalized solution to the [path-counting brain teaser from Kahn Academy](https://www.khanacademy.org/math/math-for-fun-and-glory/puzzles/brain-teasers/v/3-d-path-counting-brain-teaser). You can run this in node passing the size and number of dimensions as arguments.
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
// argv: size, dims | |
'strict mode'; | |
var size = process.argv[2]; | |
var dims = process.argv[3]; | |
var grid = initializeGrid(size, dims); | |
setValueAt(createArray(dims, 0), grid, 1); | |
var initialLoc = createArray(dims, size-1); | |
countPaths(initialLoc); | |
console.log(JSON.stringify(grid)); | |
console.log(getValueAt(createArray(dims, size-1), grid)); | |
/** | |
* Initializes the n-cube grid. The result is an array of arrays n-deep. | |
* | |
* @param {number} s size of the n-cube | |
* @param {number} d number of dimensions of the n-cube. | |
* 1 is a line, 2 is a square, 3 is a cube, etc. | |
* | |
* @return {Array} the n-cude with all entries initialized to 0 | |
*/ | |
function initializeGrid(s, d) { | |
if (d <= 1) { | |
return createArray(size, null); | |
} | |
var line = []; | |
for (var j = 0; j < s; j++) { | |
line.push(initializeGrid(s, d - 1)); | |
} | |
return line; | |
} | |
function countPaths(loc) { | |
var neighbors = getNeighbors(loc); | |
var sums = neighbors.map(neighbor => { | |
// use memoized value if possible | |
var value = getValueAt(neighbor, grid); | |
if (value === null) { | |
value = countPaths(neighbor); | |
} | |
return value; | |
}); | |
myValue = sums.reduce((acc, pathCount) => acc + pathCount, 0); | |
setValueAt(loc, grid, myValue); | |
return myValue; | |
} | |
function getNeighbors(loc) { | |
var neighbors = []; | |
for (var i = 0; i < dims; i++) { | |
if (loc[i] > 0) { | |
var neighbor = copyLoc(loc); | |
neighbor[i]--; | |
neighbors.push(neighbor); | |
} | |
} | |
return neighbors; | |
} | |
function getValueAt(loc, gridPiece) { | |
if (loc.length === 1) { | |
return gridPiece[loc[0]]; | |
} | |
return getValueAt(loc.slice(1), gridPiece[loc[0]]); | |
} | |
function setValueAt(loc, gridPiece, value) { | |
if (loc.length === 1) { | |
gridPiece[loc[0]] = value; | |
return; | |
} | |
setValueAt(loc.slice(1), gridPiece[loc[0]], value); | |
} | |
function copyLoc(loc) { | |
return JSON.parse(JSON.stringify(loc)); | |
} | |
/** | |
* Creates an array of the given size with all elements set to val. | |
* | |
* @param number length The length of the array | |
* @param any val The value to set all elements to. | |
* @return Array<any> The array | |
*/ | |
function createArray(length, val) { | |
var array = []; | |
array.length = length; | |
array.fill(val); | |
return array; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment