# Find the number of ways to climb a stairway

Challenge:

Find the number of ways to climb some stairs with n steps and with some limitations. You should be able to run the tests below on TIO https://tio.run/ without timing out. – 60 seconds. (Typically a fraction of a second is well within reach for most languages if a good optimizing strategy is applied).

The input is a list of positive numbers:

• the first number in the input is the total number of steps in the stairway
• the rest of the input is the different number of steps you are allowed to climb at once, but you're only allowed to use n steps a maximum n times if n>1. So if 2 is allowed you're only allowed to take 2 steps a maximum of 2 times. And 3 steps maximum 3 times and so on for all n>1. So if 1 is allowed, you can take 1 step as many times as you like.
• you should not "overstep", with a stairway of 5 steps and only 2 steps at once are allowed, there is no way to climb it (output 0)

Allowed assumptions: all input numbers are positive integers, at least 1 (0, negative and fractional numbers need no special handling). The list of allowed steps are unique numbers and ordered if it helps. Also the size of the stairs can be the last number or a separate part of the input if that's helpful to your implementation ("reorganizing" input don't need to be a part of the problem)

Output:

• a number which is the number of ways to climb the stairs

Examples:

• Input: 3,1 Output: 1 (as there is only one way when you're only allowed one step at a time)
• Input: 3,1,2 Output: 3 (since you can climb in three ways: 1+1+1 or 1+2 or 2+1)
• Input: 3,4 Output: 0 (you should always end at the top, you cannot take 4 steps since the stairs only has 3)
• Input: 4,1,2,3 Output: 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3)
• Input: 6,2 Output: 0 (since you're not allowed to take 2 steps 3 times)
• Input: 6,2,1 Output: 12 (2+2+1+1, 2+1+2+1, 2+1+1+2, 2+1+1+1+1, 1+2+2+1, 1+2+1+2, 1+2+1+1+1, 1+1+2+2, 1+1+2+1+1, 1+1+1+2+1, 1+1+1+1+2, 1+1+1+1+1+1. But 2+2+2 isn't allowed)
• Input: 99,99,1 Output: 2 (99 or 1+1+1+1+...99 times)

More tests:

2,1        → 1
10,1       → 1
3,1,2      → 3
3,4        → 0
3,2        → 0
4,1,2      → 5
4,1,2,3    → 7
6,2        → 0
6,2,1      → 12
7,1,2      → 17
5,1,2,3    → 13
15,1,2,7   → 266
39,3,2,7   → 301
99,11,3,2  → 1981

• Can we assume the list is always sorted in increasing/decreasing order? – Giuseppe Dec 18 '20 at 20:40
• @Giuseppe – Yes, you may assume the list of allowed steps are ordered, if that helps. – Kjetil S. Dec 18 '20 at 20:56
• Why should input 0,1 give output 0? Half the existing answers output 1 in this case (which sounds correct to me given your specification: there is exactly one way to do nothing!), while another wastes characters wrapping the answer in If[#<1,0,...] just to "fix" that case. – A. Rex Dec 18 '20 at 23:48
• @A.Rex – Hm, in my own test implementation 0,1 → 0 was the easy one and 0,1 → 1 would have required extra code. If your comment get at least three upvotes, I'll be willing to add steps>0 as a constraint to the problem and remove that test case. – Kjetil S. Dec 19 '20 at 10:37
• I removed the zero corner case from the tests. It was 0,1 → 0. – Kjetil S. Dec 20 '20 at 4:07

# JavaScript (ES6), 71 bytes

Expects (list)(n).

(a,t=0)=>g=n=>n>0?a.map(x=>--g[(g[x]=-~g[x])+~x|x<2&&g(n-x),x])|t:t+=!n


Try it online!

### Commented

(a, t = 0) =>           // a[] = input list, t = output
g = n =>                // g is a recursive function taking the number of steps n
n > 0 ?               // if n is positive:
a.map(x =>          //   for each value x in a[]:
--g[              //     decrement g[x] afterwards
(g[x] = -~g[x]) //       increment g[x]
+ ~x |          //       if g[x] is not equal to x + 1
x < 2 &&        //       or x = 1:
g(n - x),     //         do a recursive call with n - x
x               //       actual index to update g[x]
]                 //     end of entry update: this is guaranteed to be 0 on
//     the first iteration; therefore, .map() is coerced to
//     0 by the the bitwise OR even if a[] is a singleton
) | t               //   end of map(); yield t
:                     // else:
t += !n             //   increment t if n = 0


# Charcoal, 62 bytes

⊞υ⟦Ｅη⟦ι⎇⊖ιιθ⟧⁰⟧ＦυＦ‹§ι¹θＦ§ι⁰⊞υ⟦ΦＥ§ι⁰Ｅμ⁻ξ∧π⁼μλ§μ¹⁺§ι¹§λ⁰⟧Ｉ№Ｅυ⊟ιθ


Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦Ｅη⟦ι⎇⊖ιιθ⟧⁰⟧


Start a breadth-first search with a tuple of a list of steps and remaining counts (except that the count for a single step is the total number of steps) and the number of steps taken so far.

Ｆυ


Loop over every possible permutation of steps.

Ｆ‹§ι¹θ


If the total has not been reached, then...

Ｆ§ι⁰


... loop over the remaining steps, and...

⊞υ⟦ΦＥ§ι⁰Ｅμ⁻ξ∧π⁼μλ§μ¹⁺§ι¹§λ⁰⟧


... push a tuple of the list with one step removed (entirely if the count falls to zero) and the new position reached.

Ｉ№Ｅυ⊟ιθ


Count the number of times the desired total was reached exactly.

• It's always good to start climbing stairs by looking for bread. – Ethan Chapman Dec 19 '20 at 18:22
• @EthanChapman Also known as the Hansel and Gretel search? – Neil Dec 19 '20 at 18:26

# R, 171 bytes

function(N,S){s=S;s[s==1]=N
for(i in 1:N){m=expand.grid(rep(list(S),i))
m=t(m[rowSums(m)==N,])
if(z<-ncol(m))for(j in 1:z){R=m[,j]
t=table(factor(R,S))
F=F+all(t<=s)}}
+F}


Try it online!

Times out for large N.

This is rough for R. Looking at this recursive solution which is still wrong, but a decent start, should anyone want to pick up where I left off -- note that it requires S to be sorted ascending due to split.

• Yes, the f(39,c(2,3,7)) case timed out on TIO. It's not just rough for R. As intended, this problem is rough for any language unless you optimize the right way. In my test, in a language not known for being fast, this test case has a runtime of 7 milliseconds. – Kjetil S. Dec 19 '20 at 10:19

# Wolfram Language (Mathematica), 119 bytes

If[#<1,0,Length@Flatten[Permutations/@(S=Select)[IntegerPartitions[#,All,#2],And@@(#>=#2&@@@S[Tally@#,#&@@#>1&])&],1]]&


Try it online!

# Python 3, 120 bytes

def f(z,w,a=0,s=0,i=0):
for x in w:b=(a or w)[:];b[i]-=1;s+=b[i]*(x-1)>=0and(f(z-x,w,b)if z>x else z==x);i+=1
return s


Try it online!

# Python 3, 75 bytes

f=lambda n,s,p=[]:0**n+sum(f(n-d,s,p+1%d*[d])for d in s if p.count(d)<d<=n)


Try it online!

Based on Donat's solution.

# Scala, 123118 115 bytes

Thanks to user x2

% =>b=>1 to%map{b.flatMap($=>Seq.fill(if($<2)%else $)($))combinations _ flatMap(_.permutations)count(_.sum== %)}sum


Input: (#steps)=>(list). The algorithm creates the list of all allowed steps, analyzes all the permutations of the combinations of n elements (n from 1 to the number of stairs) and counts the ones that sum up to the number of steps

Try it online!

• 118 bytes with some modifications. – user Dec 22 '20 at 23:18
• Actually, the % can get you to 115 bytes – user Dec 22 '20 at 23:29

# Java (JDK), 129 bytes

int f(int z,int[]...v){int s=1/~z,i=0,a[];for(int y:v[0])s-=--(a=v[v.length-1].clone())[i++]<0&y>1|y>z?0:f(z-y,v[0],a);return-s;}


Try it online!

Reduced from 167 to 161 with hint by ceilingcat.

Further reduced to 153, 136, 132 now.

From 132 to 129, thanks to ceilingcat.

• @ceilingcat: Nice, thank you. – Donat Dec 25 '20 at 11:48

# Wolfram Language (Mathematica), 7465 63 bytes

Sum[UnitStep@@(--+#(#-a))Multinomial@@a,{a,FrobeniusSolve@##}]&


Try it online!

Sum[                                   ,{a,FrobeniusSolve@##}]& (* for each way to climb with the given step increments, sum *)
Multinomial@@a                         (* the number of rearrangements *)
UnitStep@@(--+#(#-a))                                       (* if no quotas are surpassed *)


### 66 bytes

If[#>0,If[##3'~Count~i>=i>1,0,#0[#-i,##2,i]]~Sum~{i,#2},1+Sign@#]&


Try it online!

A recursive function. Move the outer condition into the sum to conform to the initial spec: 68 bytes.

If[#>0,                     (* if there are still stairs to climb, *)
If[##3'~Count~i>=i>1,0,   (*   and we haven't used up our quota of i-steps, *)
#0[#-i,##2,i]]          (*     check how many ways there are after an i-step, *)
~Sum~{i,#2},             (*   and add those up for all possible step sizes. *)
1+Sign@#]&                (* otherwise, check if we overshot. *)


# Perl 5, 75 bytes

sub f($z,$w,%a){$z&&map{%b=%a;++$b{$_}>$_&$_>1|$_>$z?():f($z-$_,$w,%b)}@\$w}


Try it online!

The function returns a list of zeros. Perl will convert it to the number of its elements, when evaluated in scalar context. This will be the result.

Evaluation in scalar context can be forced by a helper function like this:

sub g{+&f}


In my test cases this not necessary because the result is treated as a scalar value.