Effective Riceboard

Effective Completion of the Riceboard

The Riceboard is a theoretical problem which is detailed as the following:

A checker board of N×N tiles is filled with rice. The first tile has 1 grain of rice. The second tile has R grains of rice. The third tile has R×R grains of rice and so on. Then, all the rice on the board is placed into bags of size M. How much rice is left over following any number of bags being filled completely?

The problem has quite an obvious solution once abstracted from the physical concept down to mathematical operations. The first tile has R0 grains of rice, since no matter the value of R, R to the zero will be 1. The second tile has R1. The third tile has R2, fourth has R3 and so on. Therefore, our total for the grains of rice is

$\sum _{x=0}^{{N}^{2}-1}{R}^{x}=T$

This can be fairly easily implemented in Python using the following logic, where rice_gain is the R value:

total_rice = sum([rice_gain**n for n in range(grid_length**2)])

Unfortunately, this is fairly slow when dealing with large numbers. The number of operations increases rapidly as the grid size increases. However, using some knowledge of sequences and series, it is possible to reduce this to a nicer relationship.
Our series we have above is:

${U}_{n+1}={U}_{n}+{R}^{n}$

This sequence is a linear recurrence relation, which isn't useful for calculating a single desired value. However, we can convert this into a function in terms of n, through which we can then calculate a term independently of any previous terms besides an initial condition. To do this we must 'solve' the linear recurrence relationship.

So, all of that boils down to a fairly general function for calculating the sum of some powers of a number. This is a function that can be implemented in programming languages without the need for any recursive patterns or iterative statements- surely this is much better than our previous summing method..? I briefly benchmarked both's performance on some randomly produced sets of numbers (using Python), and I found the results fairly impressive. The code I used is as below:

def sum1(r, n):
return sum([r**x for x in range(n)])

def sum2(r, n):
# our double slash '//' is an integer division- identical to normal division but remove the decimal
return ((r ** n) // (r - 1)) - (1 // (r - 1))

def run():
from time import time as t
from random import randint as rand

data = [(rand(2, 2500), rand(1, 1200)) for _ in range(32000)]

start = t()
x = [sum1(*x) for x in data]
print(t() - start)

start = t()
y = [sum2(*x) for x in data]
print(t() - start)

# this line finds any items that appear only in one of the result sets (XOR of 2 sets). this is to identify any potential issues with the output of the functions
print(set(x) ^ set(y))

Using the summation method, evaluation took around 100 seconds on my machine. Using the mathematical function, evaluation took 0.4 seconds, over 200 times faster.
You may see however that there's a couple of slight differences between the mathematical definition and the definition I've coded above. There's a reason for this. Python doesn't allow for floating points past a certain size, so therefore we are forced to deal purely with integers. It's alright to truncate the decimals down to an integer during the division process however, since the fractions that are taken away are purely to turn the decimal back into an integer anyway. The only place where this is different is in the summation of powers of 2, since R - 1 would be just 1, causing an integer sequence.

Now we know this, how can it work to solve the Riceboard? Knowing the grid size and 'rice gain', we can incredibly quickly sum the total grains of rice on the board:

def sum_powers(r, n):

return ((r ** n) // (r - 1)) - (1 // (r - 1))

total_squares = GRID_LENGTH ** 2

total_grains = sum_powers(RICE_GAIN, total_squares)

And now all that's left to do is figure out the left-overs when it's crammed into the bags. This is a simple use case of the modulo operator. The modulo operator just calculates the positive or zero remainder between two numbers. Therefore, it will also tell us how much rice is left after filling as many bags as possible.

def sum_powers(r, n):

return ((r ** n) // (r - 1)) - (1 // (r - 1))

total_squares = GRID_LENGTH ** 2

total_grains = sum_powers(RICE_GAIN, total_squares)

# our percent symbol '%' is the symbol for modulo in Python and many other languages
leftover = total_grains % BAG_SIZE