loading...

Daily Challenge #134 - Rice and Chessboard Problem

thepracticaldev profile image dev.to staff ・1 min read

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

pic
Editor guide
Collapse
nickholmesde profile image
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)

Then just round up n to get your answer.

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
Collapse
andreasjakof profile image
Andreas Jakof

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?

Collapse
nickholmesde profile image
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!

Collapse
nickholmesde profile image
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.

Collapse
benchislett profile image
Benjamin Chislett

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))
Collapse
andreasjakof profile image
Andreas Jakof

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.

Collapse
andreasjakof profile image
Andreas Jakof

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;
}
Collapse
diegoehg profile image
Diego Hdez

Using bit shifting in Python:

def calculate_squares(x):
    if x == 0:
        return 0
    return 1 + calculate_squares(x >> 1)
Collapse
vaibhavyadav1998 profile image
Vaibhav Yadav

In JavaScript.

function squaresNeeded(grains) {
  let s = 0;

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

  return s;
}
Collapse
hyftar profile image
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