Menengah Exercism • java

Grains

Ringkasan Tantangan

Calculate the number of grains of wheat on a chessboard given that the number on each square doubles.

Visit the grains exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

Pow

`BigInteger.pow()`

import java.math.BigInteger;

class Grains {

    BigInteger grainsOnSquare(final int square) {
        if ((square <= 0) || (square >= 65)) {
            throw new IllegalArgumentException("square must be between 1 and 64");
        }
        return BigInteger.valueOf(2).pow(square - 1);
    }

    BigInteger grainsOnBoard() {
        return BigInteger.valueOf(2).pow(64).subtract(BigInteger.ONE);
    }
}

Other languages may have an exponential operator such as ** or ^ to raise a number by a specified power. Java does not have an exponential operator, but can use the BigInteger.pow() method.

The pow method 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 BigIntger.valueOf(2).pow(0), 2 grains is BigIntger.valueOf(2).pow(1), 4 grains is BigIntger.valueOf(2).pow(2), and so on. So, to get the right exponent, we subtract 1 from the square number. The valueOf method is used to get 2 as a BigInteger.

For grainsOnBoard, the easiest way to get the total grains on all 64 squares 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 (i.e. BigInteger.ONE) 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 BigIntger.valueOf(2).pow(64) to get the number of grains on the imaginary 65th square. Subtracting that value by 1 gives the values on all 64 squares.

Bit-shifting

import java.math.BigInteger;

class Grains {

    BigInteger grainsOnSquare(final int square) {
        if (square < 1 || square > 64) {
            throw new IllegalArgumentException("square must be between 1 and 64");
        }
        return BigInteger.ONE.shiftLeft(square - 1);
    }

    BigInteger grainsOnBoard() {
        return BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE);
    }
}

To calculate the grains on a square you can set a bit in the correct position of a BigInteger value.

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

You use the BigInteger.shiftLeft() method to set 1 (i.e. BigInteger.ONE) at the position needed to make the correct decimal value.

To set the one grain on Square One you shift 1 for 0 positions to the left. So, if square is 1 for square One, you subtract square 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 1 for 1 position to the left. So, if square is 2 for square Two, you subtract square 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 grainsOnBoard 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 BigInteger.ONE 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

Source: Exercism java/grains