Skip to content

Instantly share code, notes, and snippets.

@bluenex
Last active August 19, 2022 05:54
Show Gist options
  • Save bluenex/2d96340d6cef0565fb46577c43736e83 to your computer and use it in GitHub Desktop.
Save bluenex/2d96340d6cef0565fb46577c43736e83 to your computer and use it in GitHub Desktop.
Visualize the possibility of https://leetcode.com/problems/climbing-stairs. Can be run up to around n=18 before memory allocation error occurs.
// 1 -> 1
// 2 -> 11 2
// 3 -> 111 12 21
// 4 -> 1111 112 121 211 22
// 5 -> 11111 1112 1121 1211 122 2111 212 221
// 6 -> 111111 11112 11121 11211 12111 1122 1212 1221 21111 2112 2121 2211 222
const getAllScenarios = (current, collection) => {
if (!collection.has(current)) {
collection.set(current, "");
}
if (current.includes("11")) {
for (let i = 0; i < current.length; i++) {
if (`${current[i]}${current[i + 1]}` === "11") {
const thisIter = current.slice(0, i) + "2" + current.slice(i + 2);
getAllScenarios(thisIter, collection);
}
}
}
return collection;
};
var climbStairs = function (n) {
const first = "1".repeat(n);
const result = [...getAllScenarios(first, new Map()).keys()].sort();
console.log(result.join("\n"));
return result;
};
// n = 8 yields the following
// 11111111 
// 1111112 
// 1111121 
// 1111211 
// 111122 
// 1112111 
// 111212 
// 111221 
// 1121111 
// 112112 
// 112121 
// 112211 
// 11222 
// 1211111 
// 121112 
// 121121 
// 121211 
// 12122 
// 122111 
// 12212 
// 12221 
// 2111111 
// 211112 
// 211121 
// 211211 
// 21122 
// 212111 
// 21212 
// 21221 
// 221111 
// 22112 
// 22121 
// 22211 
// 2222 
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment