dev.to staff

Posted on Dec 10, 2019

Daily Challenge #134 - Rice and Chessboard Problem

#challenge

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!

Top comments (10)

Nick Holmes • Dec 10 '19

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

x = 2ⁿ -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

Andreas Jakof • Dec 11 '19 • 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 • Dec 11 '19

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 2^10, and therefore area of 2²⁰ (that's just the number of squares!). Then we can fill that, which is 2^2²⁰ -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 • Dec 11 '19

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(2⁶³⁾ and log(2⁶³ +2¹⁰⁾ both return exactly 63. There is only a difference from 2¹¹ upwards.

Benjamin Chislett • Dec 10 '19

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 • Dec 11 '19 • 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 • Dec 11 '19 • 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 • Dec 10 '19

Using bit shifting in Python:

def calculate_squares(x):
    if x == 0:
        return 0
    return 1 + calculate_squares(x >> 1)

Simon Landry • Dec 13 '19

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

Vaibhav Yadav • Dec 10 '19

In JavaScript.

function squaresNeeded(grains) {
  let s = 0;

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

  return s;
}

DEV Community

Daily Challenge #134 - Rice and Chessboard Problem

Top comments (10)

Read next

Introduction to Clock IC

Security iOS Apps with OWASP Best Practices for Data Protection

Don't expose primary id's with Rails' dom_id

jQuery - Simplifying JavaScript for your convenience