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

Question

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 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.

I'm new to dynamic programming, so the only solution I could implement without looking for hints was recursion + memoization. The code works on my own workstation and returns results really fast, but keeps failing in the challenge terminal. My hunch is that I miss some aspect of optimization that is obvious for a more experienced person. What could be improved about this code? Also, if possible, what would you normally do, if you want to convert this to bottom-up dynamic programming solution? Looking forward to your comments, and thank you in advance for your ideas!

from collections import defaultdict
import sys
sys.setrecursionlimit(5000)

def answer(t, n):
    """
    t - number of steps, n - length of the board
    """
    def isInvalid(remaining_steps, position, n):
        """
        utility to check if route is invalid
        """
        # went outside the board
        if position < 1 or position > n:
            return True
        # didn't get to the end by the time steps ran out
        elif remaining_steps == 0 and position != 1:
            return True
        # not enough steps left to finish anyway
        elif position - remaining_steps > 1:
            return True

    def rec(remaining_steps, position):
        ## Check if game is valid
        if isInvalid(remaining_steps, position, n):
            return 0
        ## base condition
        # if we are at the end and the steps are exhausted
        if position == 1 and remaining_steps == 0:
            return 1
        # if leftmost cell is reached, the only possible moves are to stay, so that is one valid game
        elif position == 1 and remaining_steps > 0:
            return 1
        else:
            return (mrec(remaining_steps-1, position) + mrec(remaining_steps-1, position+1) + mrec(remaining_steps-1, position-1)) % 123454321

    def mrec(remaining_steps, position):
        """
        Use hash table for memoization.
        """
        # I wonder if here I could get some sort of integer overflow issues?
        q = "{0},{1}".format(remaining_steps, position)
        if d.get(q):
            return d.get(q)
        else:
            retval = rec(remaining_steps, position)
            d[q] = retval
        return retval

    d = defaultdict()
    return mrec(t, n)

Answer 1

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:

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

2. 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:

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

2. 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.

2. Review

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

2. 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
   

3. 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 < 1 or 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 < 1 is unnecessary, because p never goes below 1 — when p == 1 the code returns 1 immediately and doesn't recurse.

4. 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
   

5. 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.

6. 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
   

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

8. Some further simplifications to mrec:

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

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

3. 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.

4. 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 down to one sentence:

Given \$t\$ and \$n\$, how many sequences \$a_1, \ldots, a_t\$ are there, where \$a_i \in \{-1, 0, +1\}\$ and there exists \$t_0 \le t\$ such that \$0 \le \sum_1^u{a_i} < n\$ if \$1 \le u < t_0\$ and \$\sum_1^u{a_i} = n\$ if \$t_0 \le u \le t\$?

But I think the extreme verbosity must be deliberate: the idea being to make the candidate do the work of extracting the essence of the problem from the surrounding verbiage, which is a valuable software development skill.