Number of unique 3-digit sequences (-1,0,1), specified by the length corresponding to the sum
Let's say you have a vertical game board of length n (number of spaces). And you have a three-way death that has options: go forward, stay, and come back. If you go below or above the number of play areas, this is an invalid game. The only valid step when you reach the end of the board is "stay." Given the exact number of rolls m, is it possible to algorithmically determine the number of unique dice rolls that lead to a winning game?
So far I have tried listing all possible combinations (-1,0,1) for a given number of dice rolls and sorting through the list to see if any amount goes to the length of the board and also meets all the requirements for an actual game ... But this is impractical for dice rolls above 20.
For example: t = 1, n = 2; Output = 1 t = 3, n = 2; Output = 3
source to share
You can use a dynamic programming approach. Repeat sketch:
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 border cases (for example, leaving the board or not letting go out of the end of the board, but it's easy to code).
Here is the 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: fantastic "one-line" list and shrink
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]
source to share
Let M[i, j]
a N
matrix N
with M[i, j] = 1
if |i-j| <= 1
and 0
otherwise (and special case for "stay" rule M[N, N-1] = 0
)
This matrix counts the paths of length 1
from position i
to position j
.
To find paths of length t
, simply raise M
the t
'th power. This can be done efficiently with linear algebra packages.
The decision can be considered: M^t[1, N]
.
For example, compute 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, M^20[1, 5]
or 19535230 paths of length 20 from start to finish on a board of size 5.
source to share
Try a backtracking algorithm. Recursively "dive" into depth t
and only continue with values ββin the bone that could lead to a valid state. Appropriate, skipping "remaining budget".
For example, n=10, t=20
when you have reached a depth of 10 out of 20 and your budget is still 10 (= steps back and forth seemed to be canceled), the next steps of the recursion until the depth t
stops 0
and -1
because they cannot lead to a valid state at the end.
Backtracking algorithms for this case are still very heavy (exponential), but better than first blowing a bubble with all the possibilities and then filtering.
source to share
Since zeros can be added anywhere, we will multiply these possibilities by different locations (-1):
X (space 1) X (space 2) X (space 3) X (space 4) X
(- 1) can only appear in spaces 1, 2 or 3, not space 4. I got help with math backtracking that counts the number of ways to put minus without going 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
source to share