Intermediate Exercism • rust

Grains

Challenge Overview

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

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

pow

`pow`

pub fn square(s: u32) -> u64 {
    if (s < 1) | (s > 64) {
        panic!("Square must be between 1 and 64");
    }
    2u64.pow(s - 1)
}

pub fn total() -> u64 {
    (2_u128.pow(64) - 1) as u64
}

Other languages may have an exponential operator such as ** or ^ to raise a number by a specified power. Rust does not have an exponential operator, but uses the pow method.

pow 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 2u64.pow(0), 2 grains is 2u64.pow(1), 4 is 2u64.pow(2), and so on.

Note that the type of a binding can be defined by appending it to the binding name.
It can optionally be appended using one or more `_` separators between the value and the type.
More info can be found in the [Literals](https://doc.rust-lang.org/rust-by-example/types/literals.html) section of
[Rust by Example](https://doc.rust-lang.org/rust-by-example/index.html)

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

The easiest way to get total is to use u128::pow 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 might like to call 2u64.pow(64) to get the number of grains on the imaginary 65th square. However, that won’t work, because the resulting number is too large for a u64. So, you can use 2u128.pow(64), and when it is subtracted by 1 it will then fit in the u64 value which is returned.

Bit-shifting

pub fn square(s: u32) -> u64 {
    if (s < 1) | (s > 64) {
        panic!("Square must be between 1 and 64");
    }
    1 << (s - 1)
}

pub fn total() -> u64 {
    ((1_u128 << 64) - 1) as u64
}

Instead of using math to calculate the number of grains on a square, you can simply set a bit in the correct position of a u64 or u128 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 1 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 n is 1 for square One, you subtract n 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 n is 2 for square Two, you subtract n 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. However, we can’t do this with a u64 which has only 64 bits, so we need to use a u128. To go back to our two-square example, if we can grow to three squares, then we can shift 1_u128 two positions to the left for binary 100, which is decimal 4.

Note that the type of a binding can be defined by appending it to the binding name.
It can optionally be appended using one or more `_` separators between the value and the type.
More info can be found in the [Literals](https://doc.rust-lang.org/rust-by-example/types/literals.html) section of
[Rust by Example](https://doc.rust-lang.org/rust-by-example/index.html)

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

Max value

`u64::MAX` for total

pub fn total() -> u64 {
    u64::MAX
}

The maximum value for an unsigned integer gives the total number of grains on all sixty-four squares. It is essentially getting all of the bits of a 64-bit number set to 1.

This might seem like a “cheat”. To understand how it works, consider just two squares that are represented in bits as 00.

If there is a grain on square One, then the first bit (on the right) is set to binary 01, which is the decimal value of 1.
If there are two grains on square Two, then the second bit (from the right) is set to binary 10, which is the decimal value of 2.
If there are is one grain on Square One and two grains on square Two, then both bits are set to binary 11, which is the decimal value of 3.
So, with all of the two bits set you get 3, which is the number of all grains on both squares.

Getting the value of u64::MAX is getting 64 bits set to 1, which is just what we need to get the total number of grains on sixty-four squares, given that the grains double on each square, starting with one grain on the first square.

Source: Exercism rust/grains