2
\$\begingroup\$

There's a board with n squares in a horizontal row.

You start in the leftmost square, and roll a 3-faced dice.

3 possible outcomes for a single roll of the die:

  1. Left: you move 1 step to the left, if possible.
  2. None: you stay where you are
  3. Right: you move 1 step to the right, if possible.

You want to roll the dice exactly t times, and end up at the rightmost square on the last roll.

If you arrive at the rightmost square before t rolls, your only valid move is None.

You need to determine the number of valid (meaning, for instance, that you don't count sequences that try to move left or right from the rightmost square), unique sequences of dice rolls, for given (t,n) pairs. As the answer may be large, give it modulo 1000000007 (ie. 10^9+7).

  • t is a positive integer s.t. t <= 1000
  • n is a positive integer s.t. 2 <= n <= 1000

Sample testcases:

  • t=1, n=2, answer=1
  • t=3, n=2, answer=3
  • t=4, n=3, answer=7

The shortest code in bytes wins.

\$\endgroup\$
18
  • 3
    \$\begingroup\$ Seems like you were redirected here from Stack Overflow. It's a good question, but there's two things I'd like to ask: 1) PPCG questions need an objective winning criterion - how are you going to decide the winner here? (My suggestion would be code-golf), and 2) Is this a question from an ongoing contest? \$\endgroup\$
    – Sp3000
    Feb 23, 2015 at 4:16
  • \$\begingroup\$ This question will get put on hold or closed as off topic if you don't give it an objective winning criterion. I would suggest code-golf (shortest code, in bytes) as it will be easy to determine the winner. Fastest code is likely to attract less answers (though they might be more interesting) and it requires you to test the answers to determine the winner. \$\endgroup\$ Feb 23, 2015 at 5:53
  • \$\begingroup\$ I'm getting an answer of 4, not 3, for t=3, n=2, with the sequences RSS, SRS, SSR, RLR. Am I missing a rule? \$\endgroup\$
    – xnor
    Feb 23, 2015 at 6:52
  • 4
    \$\begingroup\$ If this is from another contest, permanent or not, I still don't think it's a good idea to post it here, in particular, because it might violate their copyright. \$\endgroup\$ Feb 23, 2015 at 7:56
  • 2
    \$\begingroup\$ In view of our policy on posting challenges from competitions, I'm putting this on hold for now. \$\endgroup\$
    – Doorknob
    Feb 23, 2015 at 12:49

1 Answer 1

6
\$\begingroup\$

Python, 74

f=lambda t,n,i=1:i==n or t*i and sum(f(t-1,n,i+d)for d in[-1,0,1])%(1e9+7)

A recusive solution. The current position i is stored 1-indexed as an optional argument.

  • If the current position i==n, we've arrived at the final square and are forced to stay still, giving 1 path.
  • Otherwise,
    • If the remaining time t==0, we've run out of time, so there's 0 paths.
    • If the current position i==0, we've run off the left end already, so there's 0 paths.
  • If neither of those was true, there we recurse. We add up the path counts for each of the directions left, none, and right, corresponding to displacements [-1,0,1], and take the result modulo 1e9+7 as required.

An alternative solution that uses eval with string substitution to do the sum. Same number of chars. Note the use of unary + to start the sum.

f=lambda t,n,i=1:i==n or t*i and eval(3*'+f(t-1,n,i+%d)'%(-1,0,1))%(1e9+7)

Here's another a solution that is surely short for any language with built-in matrices, so anyone who can golf it is welcome to take it.

Let M be the n*n transition matrix for the walk, which is a tridiagonal banded matrix with 1's on the main diagonal and the diagonals above and below it, except for a 0 for movement left from the rightmost cell.

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

Then, the output is (1,n) entry of the matrix power M^t.

\$\endgroup\$
2
  • \$\begingroup\$ Nice and short! The faster way to do it would be to set up an array with one cell for each square of the board and iterate t times. Then on each iteration, add the values of the cells to left and right to it, similar to Pascal's triangle. I have a 126 byte ruby solution based on that approach, which I can't post now :-S Matrix idea is cool too. \$\endgroup\$ Feb 23, 2015 at 14:26
  • \$\begingroup\$ Thks; pls share more details how you came up with/derived the n*n transition matrix? \$\endgroup\$
    – StChong8
    Feb 23, 2015 at 15:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.