Number of unique sequences of 3 digits (-1,0,1) gi

Question

Say you have a vertical game board of length n (being the number of spaces). And you have a three-sided die that has the options: go forward one, stay and go back one. If you go below or above the number of board game spaces it is an invalid game. The only valid move once you reach the end of the board is "stay". Given an exact number of die rolls t, is it possible to algorithmically work out the number of unique dice rolls that result in a winning game?

So far I've tried producing a list of every possible combination of (-1,0,1) for the given number of die rolls and sorting through the list to see if any add up to the length of the board and also meet all the requirements for being a valid game. But this is impractical for dice rolls above 20.

For example: t=1, n=2; Output=1 t=3, n=2; Output=3

Answer 1

Let M[i, j] be an N by N matrix with M[i, j] = 1 if |i-j| <= 1 and 0 otherwise (and the special case for the "stay" rule of M[N, N-1] = 0)

This matrix counts paths of length 1 from position i to position j.

To find paths of length t, simply raise M to the t'th power. This can be performed efficiently by linear algebra packages.

The solution can be read off: M^t[1, N].

For example, computing paths of length 20 on a board of size 5 in an interactive Python session:

>>> import numpy
>>> M = numpy.matrix('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')
>>> M
matrix([[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]])
>>> M ** 20
matrix([[31628466, 51170460, 51163695, 31617520, 19535230],
        [51170460, 82792161, 82787980, 51163695, 31617520],
        [51163695, 82787980, 82792161, 51170460, 31628465],
        [31617520, 51163695, 51170460, 31628466, 19552940],
        [       0,        0,        0,        0,        1]])

So there's M^20[1, 5], or 19535230 paths of length 20 from start to finish on a board of size 5.

Answer 2

Try a backtracking algorithm. Recursively "dive down" into depth t and only continue with dice values that could still result in a valid state. Propably by passing a "remaining budget" around.

For example, n=10, t=20, when you reached depth 10 of 20 and your budget is still 10 (= steps forward and backwards seemed to cancelled), the next recursion steps until depth t would discontinue the 0 and -1 possibilities, because they could not result in a valid state at the end.

A backtracking algorithms for this case is still very heavy (exponential), but better than first blowing up a bubble with all possibilities and then filtering.

Answer 3

You can use a dynamic programming approach. The sketch of a recurrence is:

M(0, 1) = 1
M(t, n) = T(t-1, n-1) + T(t-1, n) + T(t-1, n+1) 

Of course you have to consider the border cases (like going off the board or not allowing to exit the end of the board, but it's easy to code that).

Here's some Python code:

def solve(N, T):
    M, M2 = [0]*N, [0]*N

    M[0] = 1
    for i in xrange(T):
        M, M2 = M2, M
        for j in xrange(N):
            M[j] = (j>0 and M2[j-1]) + M2[j] + (j+1<N-1 and M2[j+1])

    return M[N-1]

print solve(3, 2) #1
print solve(2, 1) #1
print solve(2, 3) #3
print solve(5, 20) #19535230

Bonus: fancy "one-liner" with list compreehension and reduce

def solve(N, T):
    return reduce(
        lambda M, _: [(j>0 and M[j-1]) + M[j] + (j<N-2 and M[j+1]) for j in xrange(N)], 
        xrange(T), [1]+[0]*N)[-1]

Answer 4

Since zeros can be added anywhere, we'll multiply those possibilities by the different arrangements of (-1)'s:

X (space 1) X (space 2) X (space 3) X (space 4) X

(-1)'s can only appear in spaces 1,2 or 3, not in space 4. I got help with the mathematical recurrence that counts the number of ways to place minus ones without skipping backwards.

JavaScript code:

function C(n,k){if(k==0||n==k)return 1;var p=n;for(var i=2;i<=k;i++)p*=(n+1-i)/i;return p}

function sumCoefficients(arr,cs){
  var s = 0, i = -1;
  while (arr[++i]){
    s += cs[i] * arr[i];
  }
  return s;
}

function f(n,t){
  var numMinusOnes = (t - (n-1)) >> 1
      result = C(t,n-1),
      numPlaces = n - 2,
      cs = [];

  for (var i=1; numPlaces-i>=i-1; i++){
    cs.push(-Math.pow(-1,i) * C(numPlaces + 1 - i,i));
  }

  var As = new Array(cs.length),
      An;

  As[0] = 1;

  for (var m=1; m<=numMinusOnes; m++){
    var zeros = t - (n-1) - 2*m;
    An = sumCoefficients(As,cs);
    As.unshift(An);
    As.pop();
    result += An * C(zeros + 2*m + n-1,zeros);
  }
  return result;
}

Output:

console.log(f(5,20))
19535230