count number of valid, unique sequences for moving on a 1xn board

Question

There's a board with n squares in a horizontal row.

You start in the leftmost square, and roll a 3-faced dice.

3 possible outcomes for a single roll of the die:

1. Left: you move 1 step to the left, if possible.
2. None: you stay where you are
3. Right: you move 1 step to the right, if possible.

You want to roll the dice exactly t times, and end up at the rightmost square on the last roll.

edit: If you arrive at the rightmost square before t rolls, your only valid move is None.

You need to determine the number of valid (meaning, for instance, that you don't count sequences that try to move left or right from the rightmost square), unique sequences of dice rolls, for given (t,n) pairs. As the answer may be large, give it modulo 1000000007 (ie. 10^9+7).

• t is a positive integer s.t. t <= 1000
• n is a positive integer s.t. 2 <= n <= 1000

Sample testcases:

• t=1, n=2, answer=1
• t=3, n=2, answer=3
• t=4, n=3, answer=7

The Shortest code in Bytes wins

Answer 1

Python, 74

f=lambda t,n,i=1:i==n or t*i and sum(f(t-1,n,i+d)for d in[-1,0,1])%(1e9+7)

A recusive solution. The current position i is stored 1-indexed as an optional argument.

• If the current position i==n, we've arrived at the final square and are forced to stay still, giving 1 path.
• Otherwise,
  • If the remaining time t==0, we've run out of time, so there's 0 paths.
  • If the current position i==0, we've run off the left end already, so there's 0 paths.
• If neither of those was true, there we recurse. We add up the path counts for each of the directions left, none, and right, corresponding to displacements [-1,0,1], and take the result modulo 1e9+7 as required.

An alternative solution that uses eval with string substitution to do the sum. Same number of chars. Note the use of unary + to start the sum.

f=lambda t,n,i=1:i==n or t*i and eval(3*'+f(t-1,n,i+%d)'%(-1,0,1))%(1e9+7)

---

Here's another a solution that is surely short for any language with built-in matrices, so anyone who can golf it is welcome to take it.

Let M be the n*n transition matrix for the walk, which is a tridiagonal banded matrix with 1's on the main diagonal and the diagonals above and below it, except for a 0 for movement left from the rightmost cell.

1 1 0 0 0
1 1 1 0 0
0 1 1 1 0
0 0 1 1 1
0 0 0 0 1

Then, the output is (1,n) entry of the matrix power M^t.