Skip to content

Instantly share code, notes, and snippets.

@aeisenberg
Last active May 15, 2016 03:01
Show Gist options
  • Save aeisenberg/88eac6bcb0cfa8081072b62553ec436b to your computer and use it in GitHub Desktop.
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.
// 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