How many ways to win this ternary row-game?

Question

Sorry for the vague title. Please edit or comment if you know of a better one.

Game description is below. I have a solution that works but coding it would be O($N!$) time complexity. I know there's a better solution that could be done with a single iteration (or two?).

My first attempt involved running through the entire game tree (a 3-ary tree) where the "left from starting position" and "right from last position" moves are disallowed. The height of the tree is $2^t+1$. The complexity of the tree (i.e. number of leaf nodes) provides the correct answer, but this approach is too computationally intensive at O($3^t$). I'm looking for a faster approach

My second attempt uses the fact that each game is a series of R/L/S moves (right, left, stay). Every valid game must have at least $n-1$ R moves to get from start to finish. The first valid game is thus a series of R's followed by $t-n+1$ S's. Every permutation of this sequence is a valid game.

e.g. for t = 5, n = 3 (5 moves on a board size 3), these are valid games: RRSSS, RSRRR, SRSRR, etc.

Thereafter we can iterate by removing 2 S's in the sequence and replacing them with an LR, e.g.: RLRRS, RRLRS, SRLRR, etc.

We iterate down until there are <= 1 S's remaining in the sequence.

Each game has $\frac {T!} {(R!L!S!)}$ possible games (valid and invalid). To remove the invalid ones we need to calculate how many of those games will have the token on the starting point and then move L, or the token at the end and then move R.

This is where my stats/combinatorics knowledge is broken. Can anyone help me to learn the math for finding the total number of invalid games given a sequence like above?

My sample code for this second approach is copied below. I'm just missing implementations of the two method to find the invalid games.

Game Description

The game is a single player game, played on a board with n squares in a horizontal row. The player places a token on the left-most square and rolls a special three-sided die.

If the die rolls a "Left", the player moves the token to a square one space to the left of where it is currently. If there is no square to the left, the game is invalid, and you start again.

If the die rolls a "Stay", the token stays where it is.

If the die rolls a "Right", the player moves the token to a square, one space to the right of where it is currently. If there is no square to the right, the game is invalid and you start again.

The aim is to roll the dice exactly t times, and be at the rightmost square on the last roll. If you land on the rightmost square before t rolls are done then the only valid dice roll is to roll a "Stay". If you roll anything else, the game is invalid (i.e., you cannot move left or right from the rightmost square).

To make it more interesting, players have leaderboards (one for each n,t pair) where each player submits the game he just played: the sequence of dice rolls. If some player has already submitted the exact same sequence, they cannot submit a new entry, so the entries in the leader-board correspond to unique games playable.

Since the players refresh the leaderboards frequently on their mobile devices, as an infiltrating hacker, you are interested in knowing the maximum possible size a leaderboard can have.

Write a function answer(t, n), which given the number of dice rolls t, and the number of squares in the board n, returns the possible number of unique games modulo 123454321. i.e. if the total number is S, then return the remainder upon dividing S by 123454321, the remainder should be an integer between 0 and 123454320 (inclusive).

n and t will be positive integers, no more than 1000. n will be at least 2.

Sample Code

import math

def answer(t, n):
    # Min board size is 2
    if n < 2:
        return 0

    # Need to have at least as many moves as needed to make it to the final square
    if t < n - 1:
        return 0

    # Number of each type of move to start with.
    # Always start with the simple case of enough R moves to get to the final square, then stay there
    L = 0
    R = n - 1
    S = t - n + 1

    t_fact = math.factorial(t)
    t_less1_fact = math.factorial(t-1)
    total = 0

    count = math.ceil((t-n+1)/2) + 1
    for i in range(0,count):
        S = S - 2 * i
        R += i
        L += i

        R_fact = math.factorial(R)
        S_fact = math.factorial(S)
        L_fact = math.factorial(L)

        total += t_fact/R_fact/L_fact/S_fact
        if L > 0:
            total -= GetInvalidLeftMoveGames(t,n,R,L,S)
        if R > n-1:
            total -= GetInvalidRightMoveGames(t,n,R,L,S)

    return total

Answer 1

My second attempt at this. However, the stack overflows for large game sizes (1000,1000). If there were a generator for the permutations that didn't use O(N!) space then this could work out.

import math

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=2
                for g in perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1

def answer(number_of_moves, board_size):
    # Min board size is 2
    if board_size < 2:
        return 0

    # Need to have at least as many moves as needed to make it to the final square
    if number_of_moves < board_size - 1:
        return 0

    # Number of each type of move to start with.
    # Always start with the simple case of enough R moves to get to the final square, then stay there
    L = 0
    R = board_size - 1
    S = number_of_moves - board_size + 1

    total = 0

    count = math.ceil((number_of_moves-board_size+1)/2) + 1
    i = 0
    while True:
        s = S - 2*i
        r = R + i
        l = L + i

        # This sequence and all its permutations will get from start to finish.
        # However, some permutations are not valid as they go off the board.
        winning_sequence = [0] * s + [1] * r + [-1] * l

        # Check each permutation to see if it's valid or not
        for sequence in perm_unique(winning_sequence):
            # Trim out all the S's because they don't advance the game at all
            filtered_sequence = list(filter(lambda a: a != 0, sequence))

            # any sequence starting with a move to the left is not valid
            if sequence[0] == -1:
                continue

            position = 1
            for p in filtered_sequence:
                position += p
                # if the position ever goes < 1, or > the board_size it's an invalid sequence
                if position < 1 or position > board_size:
                    #print("Failed: %s" % (sequence,))
                    break

            # If we've made it all the way to the last position without falling off it's a win!
            if position == board_size:
                #print("Success: %s" % (sequence,))
                total += 1

        i += 1
        if s < 2:
            break

    return total % 123454321

Answer 2

I don't know of any simple way to count the number of invalid permutations. One method is to use some Random Walk theory. Particularly the Ballot Theorem, which will give you the number of permutations that don't go off the left end of the board. Or, alternatively, there is a Hitting Time Theorem which gives the number that don't go off the right end of the board (these two theorems are closely related).

Unfortunately, to apply both restrictions together is not easy. Progress can be made by repeated use of these theorems, along with the Reflection Principle, to firstly apply one restriction and then apply the second one, but this leads to the need to keep re-applying the logic until you get a $0$ count and it is not straightforward. So, while a solution is possible here, I think it's too complex to be practical.

One altogether different approach to the problem you might like to consider is as follows.

Start with an array of length $n$ with initial value $[1,0,0,\ldots,0]$. At each roll of the die we re-calculate this array. After the $k^{th}$ roll, the $i^{th}$ entry represents the number of unique sequences of length $k$ going from Square $1$ to Square $i$. The initial value above is with $k=0$, which is to say before the first roll, and it means that we have $1$ unique path of length $0$ from Square $1$ to Square $1$.

At each iteration we use the $k^{th}$ generation of this array to create the $(k+1)^{th}$ generation of it by extending the paths by an extra step. Say after roll $k$ we had array $[c_1, c_2,\ldots,c_n]$. So, for example, we have $c_1$ valid paths of length $k$ from Square $1$ to Square $1$; we have $c_2$ valid paths of length $k$ from Square $1$ to Square $2$, and so on. Then for all the $c_1$ paths leading to Square $1$ we can always add an $R$ taking them to Square $2$ so this will contribute $c_1$ to the second entry (representing Square $2$) in the $k+1$ array. Alternatively, for these $c_1$ paths we can add an $S$ as long as there are at least $n-1$ further rolls remaining to allow the paths to reach Square $n$ after roll $t$. So this will contribute $c_1$ to the first entry (representing Square $1$) in the $k+1$ array. Note that no $L$s are permitted for these $c_1$ paths because that would push the paths off the left end of the board. Next, work similarly on the other entries in the $k$ array to generate all entries in the $k+1$ array, then advance to the next iteration to begin generation of the $k+2$ array until finally you have the $t$ array. The last entry in this $t$ array, representing Square $n$, will be your answer. At each point where you update an array value you should take the modulus of it (mod 123454321).

As an example, suppose $t=5$ and $n=3$. The generations of our array, from $k=0$ to $k=t$ are:

\begin{eqnarray*} k=0 && \qquad [1,0,0] \\ k=1 && \qquad [1,1,0] \\ k=2 && \qquad [2,2,1] \\ k=3 && \qquad [4,4,3] \\ k=4 && \qquad [0,8,7] \\ k=5 && \qquad [0,0,15]. \end{eqnarray*}

This gives the answer of $15$.

I don't know if I've explained this well... the concept might be simpler than my explanation of it! I think it should perform quite quickly as it is an iterative solution rather than a recursive one.