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)
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#:
There's a lot of noise there dealing with floats and ints, so if we only use floats, it becomes a lot cleaner.
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
forDecimal
types in .NET., which would have had enough bits. Hence a simple shift loop (or tail recursion in F#) would be more feasable?Here is an F# tail recursive bit shifting version;
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;
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.
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!
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:
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.
inspired by Diego Hdez' Python solution, but with a for-loop instead of a recursion and in C#
My original solution shifted the other way round building a potential and comparing that with the number of grains.
Using bit shifting in Python:
Ruby:
In JavaScript.