Instantly share code, notes, and snippets.

@sobstel /README
Last active Jan 6, 2018

Embed
What would you like to do?
Climb the stairs (brain friendly, not so cpu friendly)
There's a staircase with N steps, and you can climb 1 or 2 steps at a time.
Given N, write a function that returns the number of unique ways you can
climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could
climb any number from a set of positive integers X?
For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
Generalize your function to take in X.
def steps(x, n)
raw_tree = x.map { |i| [i] }
final_tree = []
loop do
raw_tree, final_leaves = raw_tree
.each_with_object([]) { |leaf, tree| x.each { |i| tree << leaf.dup.push(i) } }
.delete_if { |leaf| leaf.inject(:+) > n }
.partition { |leaf| leaf.inject(:+) < n }
final_tree.concat final_leaves
break if raw_tree.empty?
end
final_tree
end
puts steps([1,2],4).to_s
puts steps([1,3,5],10).to_s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment