0

Preamble:

When asking the staircase problem the usual given array of allowable paces is [1,2,3]

See lots of examples of the same problem on SO such as n-steps-with-1-2-or-3-steps-taken-how-many-ways-to-get-to-the-top

My question relates to this but on finding proof for cases where the allowed paces includes negative and zero.

Somethings are obvious such as

  • if all the step sizes are positive then the number of possible ways is finite and solvable.
  • if any step size is zero then then the number of possible ways becomes infinite.
  • If at least one negative step size is allowed AND any combination of step sizes sum to zero then the number of possible ways becomes infinite.

Examples:

countSteps(stairSize:=5, [  1,2,3]) // 17
countSteps(stairSize:=5, [0,1,2,3]) // 17...

countSteps(stairSize:=5, [-2,-1  ]) // zero ways
countSteps(stairSize:=5, [-2,-1,0]) // infinitely zero ways

countSteps(stairSize:=5, [2,4]) // zero ways

countSteps(stairSize:=5, [   3]) // zero ways
countSteps(stairSize:=5, [-1,3]) // infinite ways

countSteps(stairSize:=5, [6,7,8]) // zero ways

Question:

? Can you determine whether given
    a stair size (1.. for now)
    and an array of allowable steps
    is the result find-able ?
John Griffiths
  • 3,263
  • 4
  • 21
  • 19
  • 2
    This is mostly a math question (is `stairSize` in the additive closure of the given set, i.e. can `stairSize` be written as a sum of positive integer multiples of the given integers?). [This answer](https://math.stackexchange.com/a/470330) to a related question should be a decent starting point. – manveti Jun 12 '19 at 23:21
  • As you can see from the comments to my answer, there seems to be some disagreement about what "the staircase problem" is supposed to be. To address this disagreement, can you add an example of `countSteps(stairSize:=5, [-1,6,7,8])`? (Specifically: is that infinite ways, or zero ways?) – ruakh Jun 13 '19 at 23:56
  • Thank you for looking at my post which I had not addressed in the title as a question. – John Griffiths Jun 14 '19 at 09:29
  • One difficulty in expressing the question was that the original questions dealt with a staircase which deliberately constrains the problem to simple cases because once you are on the ground moving negatively makes no change to your state. Which means that going down 10 steps from step 3 will get you to the ground only and no further exactly the same as stepping back 3 steps. Similarly stepping forwards from step 3, once you reach the landing any further steps take you forward not higher. – John Griffiths Jun 14 '19 at 09:48
  • Previously on StackOverflow https://stackoverflow.com/search?q=stair+1+2+3 – John Griffiths Jun 14 '19 at 09:49
  • Every other description and code given is dependant on exactly reaching the top most stair (landing). Which means that at the ground floor of a 3 step stair then "countSteps(stairSize:=3, [1,2,3])" is not four (1,1,1),(1,2),(2,1),(3) but six (1,1,1),(1,2),(2,1),(3),(1,3),(2,3) – John Griffiths Jun 14 '19 at 11:08
  • @JohnGriffiths: I'm sorry, I don't understand your last few comments. Instead of talking about *other* questions, how about you carefully explain *yours*? – ruakh Jun 15 '19 at 00:22

1 Answers1

0

You can do this in two parts:

  • First, create a boolean array of size stairSize representing whether a given step is reachable from the bottom step. Initialize all values to 'false' (including the bottom step), then use a search algorithm (such as BFS or DFS) to find all reachable steps and set them to 'true'.
    • If the top step never becomes 'true', then there's no way to reach the topmost step from the bottom; return 0.
    • Otherwise, if the bottom step ends up 'true', then there's a loop; return ∞. (Due to the symmetries in the problem, the bottom step will always end up 'true' if there's a loop.)
  • Next, create an integer array of size stairSize representing the number of ways to reach a given step. Initialize the bottom step to 1 and all other values to 0, then use recursion to populate this array. (For example, something like this: 
    private int getNumWaysToReachStep(
        final int targetStep,
        final boolean[] isStepReachable,
        final int[] numWaysToReachStep,
        final int[] numStepsAtATimeArr) {
    if (targetStep == 0) {
        return 1;
    } else if (targetStep < 0 || targetStep >= isStepReachable.length) {
        return 0;
    } else if (numWaysToReachStep[targetStep] != 0 || ! isStepReachable[targetStep]) {
        return numWaysToReachStep[targetStep];
    }
    int result = 0;
    for (final int numSteps : numStepsAtATimeArr) {
        result += getNumWaysToReachStep(targetStep - numSteps, isStepReachable,
                      numWaysToReachStep, numStepsAtATimeArr);
    }
    numWaysToReachStep[targetStep] = result;
    return result;
}
    )

Overall, this requires O(stairSize · |numStepsAtATimeArr|) time and O(stairSize) extra space.

ruakh
  • 175,680
  • 26
  • 273
  • 307
  • Unfortunately, there's no good upper bound to the size of the arrays in this solution. Consider a valid steps array like `[-1, MAX_INT]`; every step is reachable, but most of them are only reachable from the top (unless there's a big basement into which you can step down before making your big `MAX_INT` step up). – manveti Jun 13 '19 at 00:06
  • @CraigMeier: I'm not sure what you mean. The goal of the problem is to find the number of ways to get from the bottom step to the top step. You can hardly claim that "there's no good upper bound to the size of the arrays", when the size of the arrays is literally just *stairSize*. – ruakh Jun 13 '19 at 00:41
  • 1
    The example with `stairSize=5` and valid steps `[6,7,8]` led me to believe that `stairSize` actually meant target stair in a staircase with arbitrarily many stairs, rather than the total size of the staircase. Otherwise, yeah, if `stairSize` is the index of the top step then the arrays just need to be sized `stairSize + 1`. – manveti Jun 13 '19 at 00:57
  • 1
    @CraigMeier: Oh, I see. I took the example with `stairSize=5` and valid steps `[6,7,8]` to mean that no steps are actually possible, because the staircase isn't tall enough for any of the options. I guess the OP doesn't explicitly indicate what "the staircase problem" is, but he describes https://stackoverflow.com/questions/22562023/n-steps-with-1-2-or-3-steps-taken-how-many-ways-to-get-to-the-top as "the same problem", and that one clearly indicates that it's about getting to the *top* of the staircase. – ruakh Jun 13 '19 at 23:55