Intermediate Exercism • csharp

Grains

Challenge Overview

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

`Math.Pow`

using System;
using System.Linq;

public static class Grains
{
    public static double Square(int i)
    {
        if (i is <= 0 or > 64)
            throw new ArgumentOutOfRangeException(nameof(i));

        return Math.Pow(2, i - 1);
    }

    public static double Total()
    {
        return Enumerable.Range(1, 64).Sum(Square);
    }
}

Other languages may have an exponential operator such as ** or ^ to raise a number by a specified power. C# does not have an exponential operator, but uses the Math.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 Math.Pow(2, 0), 2 grains is Math.Pow(2, 1), 4 is Math.Pow(2, 2), and so on. So, to get the right exponent, we subtract 1 from the square number i.

For Total we can reuse Square by passing it 1 through 64 and summing the result from each call. This example uses Enumerable.Range to iterate from 1 through 64 and chains it to the Sum method.

Shortening

When the body of an if statement is a single line, both the test expression and the body could be put on the same line, like so

if (i is <= 0 or > 64) throw new ArgumentOutOfRangeException(nameof(i));

The C# Coding Conventions advise to write only one statement per line in the layout conventions section, but the conventions begin by saying you can use them or adapt them to your needs. Your team may choose to overrule them.

When the body of a function is a single expression, the function can be implemented as a expression-bodied member, like so

public static double Total() =>
    Enumerable.Range(1, 64).Sum(Square);

public static double Total() => Enumerable.Range(1, 64).Sum(Square);

Bit-shifting

using System;
using System.Numerics; // Allows using BigInteger

public static class Grains
{
    public static ulong Square(int n)
    {
        switch (n)
        {
            case int num when num > 0 && num < 65: return (ulong)1 << (num - 1);
            default: throw new ArgumentOutOfRangeException("n must be 1 through 64");
        }
    }

    public static ulong Total()
    {
        return (ulong)((BigInteger.One << 64) - 1);
    }
}

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 ulong 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 ulong which has only 64 bits, so we need to use a BigInteger. 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

Shortening

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

public static ulong Total() =>
    (ulong)((BigInteger.One << 64) - 1);

public static ulong Total() => (ulong)((BigInteger.One << 64) - 1);

Max value

`Int64.MaxValue` for Total

using System;

public static class Grains
{
    public static double Square(int i)
    {
        if (i is <= 0 or > 64)
            throw new ArgumentOutOfRangeException(nameof(i));

        return Math.Pow(2, i - 1);
    }

    public static double Total()
    {
        return UInt64.MaxValue;
    }
}

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 System.UInt64.MaxValue 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.

Shortening

When the body of a function is a single expression, the function can be implemented as a expression-bodied member, like so

public static ulong Total() =>
  System.UInt64.MaxValue;

public static ulong Total() => System.UInt64.MaxValue;

Source: Exercism csharp/grains