Beginner Exercism • javascript

Grains

Challenge Overview

Calculate the number of grains of wheat on a chessboard.

Introduction

There once was a wise servant who saved the life of a prince. The king promised to pay whatever the servant could dream up. Knowing that the king loved chess, the servant told the king he would like to have grains of wheat. One grain on the first square of a chessboard, with the number of grains doubling on each successive square.

Instructions

Calculate the number of grains of wheat on a chessboard.

A chessboard has 64 squares. Square 1 has one grain, square 2 has two grains, square 3 has four grains, and so on, doubling each time.

Write code that calculates:

the number of grains on a given square
the total number of grains on the chessboard

Dig Deeper

exponentiation

Exponentiation

export function square(num) {
  if (num < 1 || num > 64) {
    throw new Error('square must be between 1 and 64');
  }
  return 2n ** BigInt(num - 1);
}

export function total() {
  return 2n ** 64n - 1n;
}

JavaScript uses the exponential operator to raise a number by a certain exponent. Math.pow() can also be used to raise a number by an exponent, but it does not work with a BigInt.

Exponentiation is nicely suited to the problem, since we start with one grain and keep doubling the number of grains on each successive square. 1 grain is 2n ** 0, 2 grains is 2n ** 1, 4 is 2n ** 2, and so on.

Note that a [`BigInt`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt) literal can be specified by appending `n` to the value.

So, to get the right exponent, we subtract 1 from the square number num.

The easiest way to get total is to get the value for an imaginary 65th square, and then subtract 1 from it. To understand how that works, consider a board that has only two squares. If we could grow the board to three squares, then we could get the number of grains on the imaginary third square, which would be 4. You could then subtract 4 by 1 to get 3, which is the number of grains on the first square (1) and the second square (2). Remembering that the exponent must be one less than the square you want, you can call 2n ** 64 to get the number of grains on the imaginary 65th square. Subtracting that value by 1 gives the values on all 64 squares.

Shortening

When the body of a function is a single expression, the function can be implemented as an arrow function, like so

export const total = () => 2n ** 64n - 1n;

Notice that return and the curly braces are not needed.

Bit-shifting

export function square(num) {
  if (num < 1 || num > 64) {
    throw new Error('square must be between 1 and 64');
  }
  return 1n << (BigInt(num) - 1n);
}

export function total() {
  return (1n << 64n) - 1n;
}

Instead of using math to calculate the number of grains on a square, you can set a bit in the correct position of a BigInt value.

Note that a `BigInt` literal can be specified by appending `n` to the value.

To understand how this works, consider just two squares that are represented in binary bits as 00.

You use the left-shift operator to set 1n at the position needed to make the correct decimal value.

To set the one grain on Square One you shift 1n for 0 positions to the left. So, if num is 1 for square One, you subtract num by 1 to get 0, which will not move it any positions to the left. The result is binary 01, which is decimal 1.
To set the two grains on Square Two you shift 1n for 1 position to the left. So, if num is 2 for square Two, you subtract num by 1 to get 1, which will move it 1 position to the left. The result is binary 10, which is decimal 2.

Square	Shift Left By	Binary Value	Decimal Value
1	0	0001	1
2	1	0010	2
3	2	0100	4
4	3	1000	8

For total we want all of the 64 bits set to 1 to get the sum of grains on all sixty-four squares. The easy way to do this is to set the 65th bit to 1 and then subtract 1. To go back to our two-square example, if we can grow to three squares, then we can shift 1n two positions to the left for binary 100, which is decimal 4. By subtracting 1 we get 3, which is the total amount of grains on the two squares.

Square	Binary Value	Decimal Value
3	0100	4

Square	Sum Binary Value	Sum Decimal Value
1	0001	1
2	0011	3

Shortening

When the body of a function is a single expression, the function can be implemented as an arrow function, like so

export const total = () => (1n << 64n) - 1n;

Source: Exercism javascript/grains

💡 View Solution

export const square = (n) => {
  if (n < 1 || n > 64) throw new Error('square must be between 1 and 64');
  return BigInt(2) ** BigInt(n - 1);
};
export const total = () => (BigInt(2) ** BigInt(64)) - BigInt(1);