Skip to content

Grains

Count the grains of wheat on a chessboard square, doubling from one grain on the first, and on the whole board.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: grains.nomi
//# Grains of wheat on a chessboard, doubling from one grain on the first
//# square. The 64th square holds 2^63 grains and the board 2^64 - 1, which an
//# `Int` holds exactly, as it holds a whole number of any size.

/// The grains on `square`, numbered from 1 to 64.
pub fn square(square: Int) -> Result<Int, String>
    if not square in 1..=64 then return Err("square must be between 1 and 64")

    Ok(grains_on(square))
end

/// The grains on the whole board.
pub fn total() -> Int
    1..=64 |> Iter.map(grains_on) |> Iter.sum()
end

fn grains_on(square: Int) -> Int
    // Squares are numbered from 1, so the exponent is never negative.
    Int.pow(2, NonNegativeInt.try_from(square - 1)!)
end

// FILE: grains_test.nomi
import grains

group "returns the number of grains on the square"
    test "counts the grains"
        [
            ("grains on square 1",  1,  1),
            ("grains on square 2",  2,  2),
            ("grains on square 3",  3,  4),
            ("grains on square 4",  4,  8),
            ("grains on square 16", 16, 32768),
            ("grains on square 32", 32, 2147483648),
            ("grains on square 64", 64, 9223372036854775808),
        ]
        |> subtests (description, square, expected), description
            assert grains.square(square) == Ok(expected)
        end
    end

    test "rejects squares off the board"
        [
            ("square 0 is invalid",               0),
            ("negative square is invalid",        -1),
            ("square greater than 64 is invalid", 65),
        ]
        |> subtests (description, square), description
            assert grains.square(square) == Err("square must be between 1 and 64")
        end
    end
end

test "returns the total number of grains on the board"
    assert grains.total() == 18446744073709551615
end
  • The counts are Ints. The 64th square holds 2^63 grains and the board 2^64 - 1, past 64 bits, and an Int is exact at any size.
  • A square’s grains are Int.pow(2, square - 1) (style §33), which says what the count is. 1 <<< (square - 1) is the same number.
  • total sums every square rather than using 2^64 - 1, so it says what the board holds.
  • A square off the board is Err with the canonical message, a String, as collatz-conjecture does. There is one error, so an Error enum would add a type for one variant.
  • The seven counts are one subtests table and the three bad squares another, since they assert different shapes; both sit in the canonical group.