How many possibilities to get to N spaces away from starting point by rolling 6-faced dice?

Question

I just started python like a week ago and now I am stuck at the question about rolling dice. This is a question that my friend sent to me yesterday and I have just no idea how to solve it myself.

Imagine you are playing a board game. You roll a 6-faced dice and move forward the same number of spaces that you rolled. If the finishing point is “n” spaces away from the starting point, please implement a program that calculates how many possible ways there are to arrive exactly at the finishing point.

So it seems I shall make a function with a parameter with "N" and when it reaches a certain point, let's say 10, so we all can see how many possibilities there are to get to 10 spaces away from the starting point.

I suppose this is something to do with "compositions" but I am not sure how it should be coded in python.

Please, python masters!

Answer 1

This is one way to compute the result that is exact, and uses neither iteration nor recursion:

def ways(n):
    A = 3**(n+6)
    M = A**6 - A**5 - A**4 - A**3 - A**2 - A - 1
    return pow(A, n+6, M) % A

for i in xrange(20):
    print i, '->', ways(i)

The output is in agreement with https://oeis.org/A001592

0 -> 1
1 -> 1
2 -> 2
3 -> 4
4 -> 8
5 -> 16
6 -> 32
7 -> 63
8 -> 125
9 -> 248
10 -> 492
11 -> 976
12 -> 1936
13 -> 3840
14 -> 7617
15 -> 15109
16 -> 29970
17 -> 59448
18 -> 117920
19 -> 233904

Answer 2

After a lot of calculation I found a solution that it creates a Hexanacci series. Now let me explain Hexanacci series a little bit. In the Hexanacci series each element is the summation of previous 6 elements. So I achieved this in Objective-C by just using a for loop which can be easily convert to any language:

-(void)getPossibleWaysFor:(NSInteger)number
 {
  static unsigned long ways;

  unsigned long first = 0;
  unsigned long second = 0;
  unsigned long third = 0;
  unsigned long fourth = 0;
  unsigned long fifth = 0;
  unsigned long sixth = 1;

  for (int i = 0; i<= number; i++) {

    ways = first + second + third + fourth + fifth + sixth;

    if (i>0) {
        first = second;
        second = third;
        third = fourth;
        fourth = fifth;
        fifth = sixth;
        sixth = ways;
    }

    NSLog(@"%d : -> %ld",i,ways);
}
return ways;}

// Result:

[self getPossibleWaysFor:20];

0 : -> 1
1 : -> 1
2 : -> 2
3 : -> 4
4 : -> 8
5 : -> 16
6 : -> 32
7 : -> 63
8 : -> 125
9 : -> 248
10 : -> 492
11 : -> 976
12 : -> 1936
13 : -> 3840
14 : -> 7617
15 : -> 15109
16 : -> 29970
17 : -> 59448
18 : -> 117920
19 : -> 233904
20 : -> 463968