Number of unique sequences of 3 digits, given a length is equal to sum

This is the "Minion's bored game" problem from Google's "Foobar challenge":


There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean.


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


If the die rolls a "Left", the minion 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 minion 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, the minions have leaderboards (one for each \$n,t\$ pair) where each minion submits the game he just played: the sequence of dice rolls. If some minion 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 minions 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

1. Dynamic programming

Recursion-plus-memoization is a standard technique for implementing dynamic programming. The difference is that recursion-plus-memoization works "top-down" (starts with big instances of the problem and recurses to handle smaller instances) whereas the traditional dynamic programming approach works "bottom-up" by filling a table of solutions starting with the smallest instances and proceeding to bigger ones.

The advantages of the top-down approach are:

-
The code is often clearer and simpler. (But not in this case, as we'll see later.)

-
You only have to solve the instances that contribute to the problem you're trying to solve, whereas in the table-filling approach it's often hard to do this and you end up always filling the whole table. (But in this case it is easy to work out which table entries are needed.)

The advantages of the bottom-up approach are:

-
It doesn't need a stack to carry out the recursion (hence there's no need to set sys.setrecursionlimit for large problem instances).

-
In some cases you don't have to keep the whole table in memory: for example in this problem mrec(t, p) depends only on mrec(t - 1, q) and so if you were using the bottom-up approach you'd only have to keep the current and previous rows of the table in memory.

I wrote a couple of blog posts on dynamic programming in Python ("The tabular method", "Square triangulations") that you might be interested in.

1. Review

-
There's no need to pass n to isInvalid since it never changes.

-
In isInvalid, the condition

remaining_steps == 0 and position != 1

is redundant because if this condition is true, then so is the condition:

position - remaining_steps > 1

-
In isInvalid there is an if: ... elif: ... with no else:. The function works because if a function ends with no return, then it returns None, which converts to Boolean as False. But this is tricky: it would be clearer to add:

else:
    return False

And even clearer to use a Boolean expression:

def isInvalid(t, p):
    return (p  n  # position off the board
            or p - t > 1)   # not enough time remaining

This is now so simple that it could be inlined into rec, avoiding a function call. And once you've done the inlining, it's easy to see that the test p

-
In rec, there are the conditions:

if p == 1 and t == 0:
    return 1
elif p == 1 and t > 0:
    return 1

Since the result is the same in both cases, and since t can't be less than 0, there's no point in testing t at all, and the cases can be merged:

if p == 1:
    return 1

-
There's a comment:

# if leftmost cell is reached, the only possible moves are to stay,
# so that is one valid game

According to the problem description, it's the rightmost cell where the only possible move is to stay. This doesn't affect the result, because the problem is symmetric, but it is confusing to the reader. It would be clearer, I think, to stick to the given version of the problem.

-
In mrec, there's no need to turn the pair remaining_steps, position into a string in order to use it as a dictionary key. Dictionaries can use any hashable values as keys, and that includes tuples. So the key can just be the tuple of arguments:

q = remaining_steps, position

-
I think cache and args would be clearer names than d and q.

-
Some further simplifications to mrec:

args = remaining_steps, position
if args in cache:
    return cache[args]
else:
    result = cache[args] = rec(*args)
    return result

-
You don't use any feature of defaultdict, so you could just use a plain dict` for the cache.

1. Revised code

This is about twice as fast as the code in the post:

def answer(t, n, m=123454321):
    """Number of ways to get from 1 to n in exactly t rolls, modulo m."""
    cache = {}
    def a(t, p):
        # Number of ways to get from p to n in exactly t rolls, modulo m.
        args = t, p
        if args in cache:
            return cache[args]
        elif p < 1 or t < n - p:
            return 0
        elif p == n or t == n - p:
            return 1
        else:
            u = t - 1
            result = (a(u, p - 1) + a(u, p) + a(u, p + 1)) % m
            cache[args] = result
            return result
    return a(t, 1)

For comparison, here's the bottom-up version:

def answer(t, n, m=123454321):
    """Number of ways to get from 1 to n in exactly t rolls, modulo m."""
    a = [0] * n + [1]
    b = a[:]
    for i in range(1, t + 1):
        for p in range(max(1, n - i), n):
            b[p] = (a[p-1] + a[p] + a[p+1]) % m
        a, b = b, a
    return a[1]

This runs in roughly the same amount of time as the top-down version, but it's shorter and uses less memory.

1. A note on the Google Foobar challenges

The challenges are written in a very very long-winded style. In this case, the ten paragraphs in the problem description could be boiled do

StackExchange Code Review Q#130012, answer score: 4