Skip to content

Instantly share code, notes, and snippets.

@davidnormo
Last active April 14, 2020 14:43
Show Gist options
  • Save davidnormo/46f71a8e05de8be1e3f2da0481dea611 to your computer and use it in GitHub Desktop.
Save davidnormo/46f71a8e05de8be1e3f2da0481dea611 to your computer and use it in GitHub Desktop.
Jumping steps problem (javascript)
/*
A flight of stairs has `n` steps, you are able to jump 1, 2, or 3 steps at a time.
How many different ways are you able to climb the stairs in different combinations of jumps?
E.g. n = 3 then the answer is 4 because: 111, 21, 12, 3
*/
const replaceIndexWithNum = (str, i, num) => {
return str.substring(0, i)+num+str.substring(i+num)
}
/**
* consumeAndIterate will loop through `str` replacing: 11 with 2 and 111 with 3
* then call itself with the resulting string to recurse until all
* combinations are found. Therefore results can be found like a tree structure
*
* It will mutate the `results` object e.g.
* consumeAnditerate(3, '111', {}) => {'111': true, '21': true, '3': true, '12': true }
*/
const consumeAndIterate = (n, str, results = {}) => {
results[str] = true
for (let i = 0; i < str.length; i++) {
const add2 = parseInt(str[i]) + parseInt(str[i+1])
const strWith2 = replaceIndexWithNum(str, i, 2)
if (add2 === 2 && !results[strWith2]) {
consumeAndIterate(n, strWith2, results)
}
const add3 = add2 + parseInt(str[i+2])
const strWith3 = replaceIndexWithNum(str, i, 3)
if (add3 === 3 && !results[strWith3]) {
consumeAndIterate(n, strWith3, results)
}
}
return results
}
const solution = (n) => {
// start recursing with string of 1s
const results = consumeAndIterate(n, Array(n).fill(1).join(''))
return Object.keys(result).length
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment