Find the number of ways to climb a stairway

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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!

Answer 5

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!

Answer 6

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.

Answer 7

Scala, 123 118 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!

Answer 8

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.

Answer 9

Wolfram Language (Mathematica), 74 65 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. *)

Answer 10

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.