## DEV Community is a community of 662,780 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #134 - Rice and Chessboard Problem dev.to staff
The hardworking team behind dev.to ❤️

I'm not sure how many of you are familiar with the ancient rice and chessboard problem (Wikipedia calls it wheat for some reason) but here's a quick recap for you: a young person asks, as compensation, only 1 grain of rice for the first square, 2 grains for the second, 4 for the third, 8 for the fourth and so on, always doubling the previous.

Your task is pretty straightforward: Write a function that, given an amount of grain, calculates to which square one needs to land on to reach at least that amount of grain.

As usual, a few examples might be way better than thousands of words from me:
`squaresNeeded(grain) === chessboard square`
`squaresNeeded(0) === 0`
`squaresNeeded(1) === 1`
`squaresNeeded(2) === 2`
`squaresNeeded(3) === 2`
`squaresNeeded(31) === 5`

Input is always going to be valid/reasonable: a non negative number.

Test Cases:
`squaresNeeded(128) === ?`
`squaresNeeded(4000000) === ?`
`squaresNeeded(32768) === ?`

Good luck, happy coding!

This challenge comes from GiacomoSorbi on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (10) Nick Holmes

No loop is needed, just some basic maths knowledge. Total grains at square n is

x = 2n -1

solve that back for n

n = log2(x+1)

In F#:

``````let squaresNeeded x = int (Math.Log(float (x+1), 2.) |> Math.Ceiling)
``````

There's a lot of noise there dealing with floats and ints, so if we only use floats, it becomes a lot cleaner.

``````let squaresNeeded x = Math.Log(x+1., 2.) |> Math.Ceiling
`````` Andreas Jakof • Edited

this reminds me of my goal to learn more F#. I can express the same in C#, but still.

Nevertheless ... A chessboard has 64 tiles and even with a `double`, there are not enough bits to fully represent the complete number if you are coming closer to the 64 bit necessary for the last tile (double has 15-17 digits precision, UInt64.MaxValue will need 20 digits).

Although the approach is very elegant, there is (sadly) no `Math.Log` for `Decimal` types in .NET., which would have had enough bits. Hence a simple shift loop (or tail recursion in F#) would be more feasable? Nick Holmes

Here is an F# tail recursive bit shifting version;

``````let squaresNeeded (x:uint64) =
let rec inner (grains:uint64) tile =
match grains with
| 0UL -> tile
| _ -> inner (grains >>> 1) (tile + 1)

inner x 0
``````

In order to check it was doing tail recursion (F# doesn't tell you), I made this version using BigIntegers, which is no longer limited to a tiny 8x8 chess board;

``````let squaresNeededBig (x:bigint) =
let rec inner (grains:bigint) square =
match grains with
| z when z.IsZero -> square
| _ -> inner (grains >>> 1) (square + 1)

inner x 0
``````

So, lets make a chess board with sides of 210, and therefore area of 220 (that's just the number of squares!). Then we can fill that, which is 2220 -1 grains of sand.

``````let squares = 1 <<< 20;
let grains =  (bigint.Pow((bigint 2), squares)-bigint.One)
printfn "Squares needed is %d" (squaresNeededBig grains)
``````

And after a few seconds, it gives the correct answer, and confirms tail recursion. Not sure what the point of all that was, but I had a bit of fun with it! Nick Holmes

Indeed.

There is a BigInteger in .Net (bigint in F#), and this does have a Log function. However, the log function (needs to) return a Double. Bottom line, log(263) and log(263 +210) both return exactly 63. There is only a difference from 211 upwards. Notice that the sum of powers of two up to n is equal to the (n+1)th power of two, less one.

So, we can just add one and take the logarithm base2:

``````const squaresNeeded = n => Math.ceil(Math.log2(n + 1))
`````` Andreas Jakof • Edited

like Nick Holmes' approach, very elegant, but Log or Log2 uses `double` as input type, which has not enough bits, when we stick to the chess board.

Since a chessboard has 64 tiles, we would need an unsigned long (64 bit) to capture the complete number space. `double` has also 64 bit, but reserves some for the exponent, introducing a small, but not negligible error when coming closer to the last tiles. double precision is 15-17 digits, but we need up to 20 digits to represent such big numbers.
E.g. if you are just a few (lets say 90, to be safe - we are already in the quadrillions to give some relation) grains over the 63th tile the error would result in giving you 63 instead of 64. Andreas Jakof • Edited

inspired by Diego Hdez' Python solution, but with a for-loop instead of a recursion and in C#

``````public static int Squaresneeded(ulong grains)
{
int tile = 0;
for(;grains > 0;++tile)
grains = grains >> 1;

return tile;
}
``````

My original solution shifted the other way round building a potential and comparing that with the number of grains.

``````public static int Squaresneeded(ulong grains)
{
int tile = 1;
ulong potential = 1;
for (;potential < grains;++tile)
{
potential = (potential << 1) + 1;
}
return tile;
}
`````` Diego Hdez

Using bit shifting in Python:

``````def calculate_squares(x):
if x == 0:
return 0
return 1 + calculate_squares(x >> 1)
`````` In JavaScript.

``````function squaresNeeded(grains) {
let s = 0;

while(2 ** s - 1 < grains) {
s++;
}

return s;
}
`````` Simon Landry

Ruby:

``````def squaresNeeded(grain)
return 0 if grain.zero?
square = 0
sum = 0
loop do
sum += 2 ** square
square += 1
break if sum >= grain
end

square
end
``````