Game of Stones
A playing board consists of 50 squares arranged side-by-side from left to right. You start with a stone on the leftmost square. During each turn of the game you are allowed to move the stone to the right by 1, 2, 3, 4 or 5 squares.
Let M be the number of different ways in which you can reach the rightmost square in at most 15 moves. Find the last three digits of M .
The answer is 714.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
11 solutions
You made it easy to understand... Nice solution!
To learn to use recursion you must first learn recursion (Had to say it :D)...
This problem is a variant of the Coin Sum Problem . The coin sum problem asks for the number of ways of making n dollars using a list of coins. This problem is essentially the same as the Coin Sum Problem because it asks the number of ways of making 5 0 − 1 $ = 4 9 $ (because one square is already occupied) from a list of denominations( [ 1 $ , 2 $ , 3 $ , 4 $ , 5 $ ]).
So the problem boils down to finding the number of ways of partitioning 4 9 as a sum of [ 1 , 2 , 3 , 4 , 5 ] .Because a path from the leftmost square to the right most square is just a list of jumps that must sum up to 4 9 . The only constraint that this problem has is that it limits us to use just 15 denominations. These types of problems are usually optimally solved using Dynamic Programming or Memoization (A type of recursion that saves stuff along the way). I used Memoization.But before using DP or Memoization , I find it easier to first make a simple recursive function and then changing it to a DP or Memoization solution.
def nways( squares , jumps , target ):
if target == 0:return 0
if squares < 0:return 0
elif squares == 0:return 1
else:
if squares == jumps[0]:return 1
count = 0
for jump in jumps:
count += nways( squares - jump , jumps , target - 1)
return count
The function nways(squares,jumps,target) is a basic recursive python function that takes the size of the grid squares which in our case is 5 0 − 1 = 4 9 . jumps is a list of the possible denominations or the types of jumps you can do in the grid which here is [ 1 , 2 , 3 , 4 , 5 ] and target which is the limit on the number of jumps which in our case is 1 5 .
The idea behind the function is that nways(squares,jumps,target)==sum of nways(squares-k,jumps,target) where k is each value in jumps . But since this recursive function is too slow to find nways(50-1,[1,2,3,4,5],15) ,we memoize it to make it faster. What we are essentially doing is storing the values of the function so that it doesn't have to call iteslf tons of times.This greatly improves the performance of the function. so the final memoization solution is:
Memoize = {}
def nways( squares , jumps , target ):
Key = (squares,target)
if Key in Memoize:
return Memoize[Key]
if target == 0:
Memoize[Key] = 0
return 0
if squares < 0:
Memoize[Key] = 0
return 0
elif squares == 0:
Memoize[Key] = 1
return 1
else:
if squares == jumps[0]:
Memoize[Key] = 1
return 1
count = 0
for jump in jumps:
count += nways( squares - jump , jumps , target - 1)
if target == 1 and squares in jumps:count+=1
Memoize[Key] = count
return count
def Nways(squares,jumps,target):return nways(squares-1,jumps,target)
print Nways(50,[1,2,3,4,5],15) % 1000
function gameOfStones(moves) {
var total = 0;
for (e = 0; e <= moves; e++) {
for (d = 0; d <= moves; d++) {
for (c = 0; c <= moves; c++) {
for (b = 0; b <= moves; b++) {
for (a = 0; a <= moves; a++) {
if ((a + b + c + d + e <= moves) && (a + (2 * b) + (3 * c) + (4 * d) + (5 * e) == 49)) {
total++;
}
}
}
}
}
}
return total;
}
Please note that this solution is based more on mathematics than on computer science. However, this is how I solved it, and since nobody else has written a solution, I wanted to start discussion. I would be grateful if someone provides a solution based on algorithms.
Note that the stone has to go through 4 9 squares, the possible steps being 1 , 2 , 3 , 4 , 5 . Let's add another step to it of size 0 . If the stone has reached the rightmost square before the fifteenth move, the next steps it will take will be of size 0 . Using generating functions, the number of ways of doing this is simply the coefficient of x 4 9 in f ( x ) = ( 1 + x + x 2 + x 3 + x 4 + x 5 ) 1 5 Note that for all ∣ x ∣ < 1 , f ( x ) = = = ( x − 1 x 6 − 1 ) 1 5 − ( x 6 − 1 ) 1 5 ( 1 − x ) − 1 5 ( k = 0 ∑ 1 5 ( k 1 5 ) ( − 1 ) k x 6 k ) ( k = 0 ∑ ∞ ( k k + 1 4 ) x k )
Note that for the term x 4 9 to appear in the expansion, the contributions from these polynomials must sum up to 4 9 . Also note that the powers in the first bracket are always multiples of 6 . We can write 4 9 as the sum of a multiple of 6 and another number in 9 ways: 4 9 = 0 + 4 9 = 6 + 4 3 = 1 2 + 3 7 = 1 8 + 3 1 = 2 4 + 2 5 = 3 0 + 1 9 = 3 6 + 1 3 = 4 2 + 7 = 4 8 + 1
I used Python to compute the sum now. First, let's define a function which takes two positive integers n and r as input and returns ( r n ) :
import math
def C(n,r):
f = math.factorial
return f(n) / f(r) / f(n-r)
Now, the following function computes the coefficient of x n in the first polynomial:
def firstcoefficient(n):
if n%6==0 and n<=90:
m= k+1
return (-1)**m * C(15, n/6)
else:
return 0
The following function computes the coefficient of x n in the second polynomial:
def secondcoefficient(n):
return C(14+n, n)
Now, we need to find the sum:
sum=0
for x in range(0, 9):
sum= sum+firstcoefficient(6*k)*secondcoefficient(49-6*k)
print 0-sum
This prints
6
3
9
4
2
0
6
6
9
0
. Note that the whole computation could be done more efficiently if we included a
%1000
after each of the individual operations, but I thought the whole answer would be of interest, not only its last
3
digits.
i think that there is a mistake, for example (1+x+x^2+x^3+x^4+x^5)^3 = 1+3x+...., and 3 is not the number of ways to get 1 square in at most 3 steps when. So in the problem, i think that the correct solution is summing the coefficients of 1,x,....,x^15 in (x+x^2+x^3 + x^4 + x^5)^15, that is 1911695714. Hence the answer is 714
Log in to reply
Indeed. I can't believe I made this mistake. The reason for this over-count is that we are also considering the ordering of the 0 -moves. However, I believe the correct answer should be the coefficient of x 4 9 in k = 1 0 ∑ 1 5 ( x + x 2 + x 3 + x 4 + x 5 )
Log in to reply
yes with exponent k, actually i solved with an algorithm to get the answer: dp(squares, moves) = dp(squares-1,moves-1) + dp(squares-2,moves-1) + dp(squares-3,moves-1) + dp(squares-4,moves-1) + dp(squares-5,moves-1);
Typo: The last line should read
print sum
.
Excellent and neatly written... (y)
Very cool..I have seen similar solutions involving generating functions on other partitioning problems...see the thread here Problem 31
We use the dynamic programming approach. The following code prints 1 9 1 1 6 9 5 7 1 4 .
POSITIONS = 50 # Initial position: 1. Destination: 50.
MOVES = 15 # You have 15 moves total.
JUMPS = 5 # Every move you can jump up to 5 places.
M = {} # For dynamic programming.
# No matter how many moves you have, you can reach the start position in 1 way - starting there.
for moves in range(MOVES + 1):
M[(moves, 1)] = 1
# In 0 moves, you can't reach any position that's not the start position.
for pos in range(2, POSITIONS + 1):
M[(0, pos)] = 0
# If you have <= 0 moves, you can't reach any position.
for pos in range(-JUMPS + 2, 1):
for moves in range(MOVES + 1):
M[(moves, pos)] = 0
# Filling M by the dynamic programming approach.
for moves in range(1, MOVES + 1):
for pos in range(2, POSITIONS + 1):
M[(moves, pos)] = sum([M[(moves - 1, pos - j)] for j in range(1, JUMPS + 1)])
# The result: 1911695714.
print M[(MOVES, POSITIONS)]
I documented each section, but in case it's not clear yet, the following snippet prints the 2D array M.
# Printing the table, in case that helps understand.
print ' ' * 6,
for moves in range(0, MOVES + 1):
print '%6d moves' % moves,
print
for pos in range(-JUMPS + 2, POSITIONS + 1):
print 'pos %2d' % pos,
for moves in range(0, MOVES + 1):
print '%12d' % M[(moves, pos)],
print
The result is (please copy-paste it into a wider window like notepad, to see it as a table):
0 moves 1 moves 2 moves 3 moves 4 moves 5 moves 6 moves 7 moves 8 moves 9 moves 10 moves 11 moves 12 moves 13 moves 14 moves 15 moves
pos -3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
pos -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
pos -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
pos 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
pos 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
pos 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
pos 3 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2
pos 4 0 1 3 4 4 4 4 4 4 4 4 4 4 4 4 4
pos 5 0 1 4 7 8 8 8 8 8 8 8 8 8 8 8 8
pos 6 0 1 5 11 15 16 16 16 16 16 16 16 16 16 16 16
pos 7 0 0 5 15 25 30 31 31 31 31 31 31 31 31 31 31
pos 8 0 0 4 19 39 54 60 61 61 61 61 61 61 61 61 61
pos 9 0 0 3 21 56 91 112 119 120 120 120 120 120 120 120 120
pos 10 0 0 2 21 73 143 199 227 235 236 236 236 236 236 236 236
pos 11 0 0 1 19 87 208 334 418 454 463 464 464 464 464 464 464
pos 12 0 0 0 15 95 280 526 736 856 901 911 912 912 912 912 912
pos 13 0 0 0 10 95 350 776 1231 1561 1726 1781 1792 1793 1793 1793 1793
pos 14 0 0 0 6 86 406 1072 1947 2731 3226 3446 3512 3524 3525 3525 3525
pos 15 0 0 0 3 71 436 1387 2907 4559 5837 6552 6838 6916 6929 6930 6930
pos 16 0 0 0 1 53 434 1680 4095 7239 10161 12153 13154 13518 13609 13623 13624
pos 17 0 0 0 0 35 400 1906 5441 10916 16946 21851 24843 26208 26663 26768 26783
pos 18 0 0 0 0 20 340 2026 6821 15621 27006 37896 45783 50139 51959 52519 52639
pos 19 0 0 0 0 10 265 2016 8071 21211 41066 63176 81898 94130 100305 102685 103365
pos 20 0 0 0 0 4 189 1875 9015 27335 59546 101016 141628 172516 190911 199465 202525
pos 21 0 0 0 0 1 122 1628 9503 33443 82322 154725 236092 307306 356511 383447 395060
pos 22 0 0 0 0 0 70 1316 9451 38851 108526 226886 378664 530244 650299 726349 764884
pos 23 0 0 0 0 0 35 986 8861 42861 136461 318466 583699 884065 1154335 1349985 1464465
pos 24 0 0 0 0 0 15 681 7821 44901 163701 427921 864269 1421981 1988261 2452361 2761931
pos 25 0 0 0 0 0 5 431 6486 44651 187391 550556 1229014 2204352 3316112 4340317 5111607
pos 26 0 0 0 0 0 1 247 5042 42122 204707 678401 1678554 3291738 5347948 7465518 9252459
pos 27 0 0 0 0 0 0 126 3661 37661 213386 800786 2202230 4734200 8332380 12456955 16334530
pos 28 0 0 0 0 0 0 56 2471 31871 212196 905646 2776130 6557766 12536336 20139036 28065136
pos 29 0 0 0 0 0 0 21 1541 25481 201206 981381 3363310 8750197 18210037 31521037 46854187
pos 30 0 0 0 0 0 0 6 881 19201 181786 1018886 3916770 11249238 25538253 47742813 75922863
pos 31 0 0 0 0 0 0 1 456 13596 156336 1013281 4385100 13936994 34583139 69964954 119325359
pos 32 0 0 0 0 0 0 0 210 9010 127810 964910 4719980 16643540 45228395 99200145 181824795
pos 33 0 0 0 0 0 0 0 84 5559 99159 879334 4884104 19161290 57137735 136096160 268567985
pos 34 0 0 0 0 0 0 0 28 3172 72847 766297 4857792 21269264 69741259 180697559 384525109
pos 35 0 0 0 0 0 0 0 7 1659 50538 637938 4642708 22763746 82260326 232228781 533701631
pos 36 0 0 0 0 0 0 0 1 785 32996 506690 4261760 23489684 93774834 288950854 718187599
pos 37 0 0 0 0 0 0 0 0 330 20185 383350 3755169 23366344 103327524 348142549 937173499
pos 38 0 0 0 0 0 0 0 0 120 11505 275725 3173609 22401533 110050328 406241678 1186115903
pos 39 0 0 0 0 0 0 0 0 36 6066 188071 2570000 20691038 113290571 459154271 1456261421
pos 40 0 0 0 0 0 0 0 0 8 2930 121290 1991774 18403246 112712345 502703583 1734718133
pos 41 0 0 0 0 0 0 0 0 1 1279 73682 1475126 15752312 108351845 533155602 2005192935
pos 42 0 0 0 0 0 0 0 0 0 495 41965 1042118 12965678 100614473 547732613 2249397683
pos 43 0 0 0 0 0 0 0 0 0 165 22275 700733 10252627 90213807 545019562 2448987747
pos 44 0 0 0 0 0 0 0 0 0 45 10935 447283 7779751 78064901 525183041 2587765631
pos 45 0 0 0 0 0 0 0 0 0 9 4914 270147 5657034 65153614 489957371 2653794401
pos 46 0 0 0 0 0 0 0 0 0 1 1993 153771 3935407 52407402 442398640 2641048189
pos 47 0 0 0 0 0 0 0 0 0 0 715 82082 2614052 40590497 386454197 2550291227
pos 48 0 0 0 0 0 0 0 0 0 0 220 40832 1654016 30238871 326430221 2389012811
pos 49 0 0 0 0 0 0 0 0 0 0 55 18777 994115 21640260 266455285 2170423470
pos 50 0 0 0 0 0 0 0 0 0 0 10 7897 565609 14854624 210030644 1911695714
This can be solved with a naive dfs-based solution. It terminates in roughly 1.5 minutes.
Stoked to dig into these other solutions as they seem much more efficient.
#include <iostream>
using namespace std;
void go(int& M, int pos, int moves) {
if (moves > 15) return;
int remaining_moves = 15 - moves;
if ((pos + (remaining_moves*5)) < 50) return;
if (pos == 50) {
M++;
return;
}
for (int next_pos = pos+1; (next_pos <= pos+5) && (next_pos <= 50); next_pos++) {
go(M, next_pos, moves+1);
}
}
int main() {
int M = 0;
go(M, 1, 0);
cout << M << endl;
return 0;
}
using PD:
m[a][b] stores the number of ways you can move up to the square number "a" with EXACTLY "b" moves. If "a" is bigger than 5, you have 5 ways to reach it: from a-1, from a-2.... or from a-5. So, to reach "a" with "b" moves, you first have to get to a-1, a-2...or a-5 with b-1 moves, and then make one last move to "a".
So, we have:
m[a][1] = {0 for a = 1 and 7<= a <= 50, and 1 for 2 <=a <= 6}
m[a][b] = {sum of all m[c][b], with a-5 <= c < a, c>0}
And then the answer is m[50][1] + m[50][2] +...+m[50][15], because you can reach the 50th square with any number of moves below 16.
#include <stdio.h>
int m[51][16];
void find(int sqr, int movnum){
int numbways = 0;
int pred = sqr - 1;
while (pred >= 1 && sqr - pred <= 5){
numbways += m[pred][movnum - 1];
pred--;
}
m[sqr][movnum] = numbways % 1000;
}
int main(){
int i, j;
m[1][1] = 0;
for (i = 2; i <= 6; i++)
m[i][1] = 1;
for (i = 8; i <= 50; i++)
m[i][1] = 0;
for (i = 2; i <= 15; i++)
{
for (j = 1; j <= 50; j++)
{
find(j, i);
}
}
int sum = 0;
for (i = 1; i <= 15; i++)
{
sum += m[50][i];
}
printf("%d", sum % 1000);
return 0;
}
i mean: m[a][b] = {sum of all m[c][b-1], with a-5 <= c < a, c>0}
NOT m[a][b] = {sum of all m[c][b], with a-5 <= c < a, c>0}
Simple recursive solution with keeping track of what was already calculated, in order to eliminate redundant calculations.
C++ code:
int stor[55][25];
int partitions(int n, int k)
{
if (n == 0) return 1;
if (n < 0) return 0;
if (k == 0) return 0;
if (stor[n][k] != 0) return stor[n][k];
int ret = 0;
for (int i=1;i<=5;i++)
{
ret += partitions(n-i, k-1);
ret %= MOD;
}
stor[n][k] = ret;
return ret;
}
Calling partitions(49, 15) gives 714 as the answer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
|
Step 1
: Find the proper
sets
of <= 15 numbers that sum up to 49
Step 2
: Add up the numbers of permutations of those sets
Ex: No. of permutations of [5,5,5,4,3,3] is
(
3
6
)
(
1
3
)
(
2
2
)
=
6
0
My code
This C++ solution uses dynamic programming to build a matrix of board positions by number of moves to get there.
For example, matrix[23][5] would be the number of ways (paths) to get to board position 23 in 5 moves. To get the total number of ways to get to position 23, you would add up all matrix[23] entries.
#include <iostream>
const int N = 50;
unsigned __int64 positions[N + 1][15 + 1] = { 0 };
for (int i = 2; i <= N; i++) { // positions
for (int j = 1; j <= 5; j++) { // moves
if (i - j > 0) { // previous move
for (int k = 1; k <= 14; k++) { // grab all paths from previous move
positions[i][k + 1] += positions[i - j][k];
}
if (i - 1 == j) { // add 1 if direct jump from start
positions[i][1] += 1;
}
}
}
}
for (int i = 1; i <= N; i++) {
unsigned __int64 total = 0;
for (int j = 1; j <= 15; j++) {
total += positions[i][j];
}
cout << "Paths for " << i << ": " << total << endl;
}
Straightforward recursion.
import qualified Data.MemoCombinators as Memo
-- ways m n = # of ways to move n squares with exactly m moves
ways = Memo.memo2 Memo.integral Memo.integral w
where
w 0 0 = 1
w _ 0 = 0
w m n
| n < 0 = 0
| otherwise = sum [ways (m-1) nn | nn <- [n-5..n-1]]
-- there are only two hard problems in computer science;
-- cache invalidation, naming things, and off-by-one errors
-- note that 50 squares = 49 steps
main = print $ sum [ways moves 49 | moves <- [0..15]]
Very nice problem. Here's my Python code (explanations are in the comments):