Exercism - Grains | Stevinator

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

BigInt

BigInt is used to represent arbitrarily large integers. This is essential when dealing with numbers that exceed the maximum value of a regular int (which is 64-bit in Dart).

void main() {
  // Create BigInt from integer
  BigInt number = BigInt.from(2);
  print(number); // 2
  
  // BigInt constants
  BigInt zero = BigInt.zero;
  BigInt one = BigInt.one;
  print(zero); // 0
  print(one); // 1
  
  // Large numbers
  BigInt large = BigInt.parse('18446744073709551615');
  print(large);
}

Power Operations with BigInt

The pow method raises a BigInt to a given power. This is crucial for exponential calculations.

import 'dart:math';

void main() {
  // Power with BigInt
  BigInt base = BigInt.from(2);
  BigInt result = base.pow(10);
  print(result); // 1024
  
  // Large powers
  BigInt large = BigInt.from(2).pow(64);
  print(large); // 18446744073709551616
  
  // Square calculation: 2^(n-1)
  int square = 5;
  BigInt grains = BigInt.from(2).pow(square - 1);
  print(grains); // 16
}

ArgumentError

ArgumentError is used to signal that an argument passed to a function is invalid. It’s part of Dart’s exception system.

void main() {
  // Throwing ArgumentError
  void validateSquare(int n) {
    if (n < 1 || n > 64) {
      throw ArgumentError('square must be between 1 and 64');
    }
  }
  
  // Using it
  try {
    validateSquare(65);
  } catch (e) {
    print(e); // ArgumentError: square must be between 1 and 64
  }
}

Conditional Logic

You can use if statements to validate inputs and handle edge cases before performing calculations.

void main() {
  int square = 5;
  
  // Validate range
  if (square < 1 || square > 64) {
    throw ArgumentError('Invalid square');
  }
  
  // Proceed with calculation
  print('Square $square is valid');
}

Mathematical Operations with BigInt

BigInt supports standard arithmetic operations like addition, subtraction, and multiplication.

void main() {
  BigInt a = BigInt.from(10);
  BigInt b = BigInt.from(5);
  
  // Addition
  BigInt sum = a + b;
  print(sum); // 15
  
  // Subtraction
  BigInt diff = a - b;
  print(diff); // 5
  
  // Multiplication
  BigInt product = a * b;
  print(product); // 50
  
  // Using constants
  BigInt result = BigInt.from(2).pow(64) - BigInt.one;
  print(result);
}

Exponential Growth

Understanding exponential growth is key to this problem. Each square doubles the previous value: 1, 2, 4, 8, 16, 32, 64, …

void main() {
  // Pattern: square n has 2^(n-1) grains
  // Square 1: 2^0 = 1
  // Square 2: 2^1 = 2
  // Square 3: 2^2 = 4
  // Square 4: 2^3 = 8
  
  for (int i = 1; i <= 5; i++) {
    BigInt grains = BigInt.from(2).pow(i - 1);
    print('Square $i: $grains grains');
  }
}

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

Examples

Square 1: 1 grain (2^0)
Square 2: 2 grains (2^1)
Square 3: 4 grains (2^2)
Square 4: 8 grains (2^3)
Square 64: 9,223,372,036,854,775,808 grains (2^63)
Total: 18,446,744,073,709,551,615 grains (2^64 - 1)

What is the wheat and chessboard problem?

The wheat and chessboard problem is a mathematical problem that demonstrates exponential growth. The problem involves placing grains of wheat on a chessboard, with the number of grains doubling on each square. By the 64th square, the number becomes astronomically large.

This problem is often used to illustrate the power of exponential growth and the importance of understanding mathematical series. The total number of grains (2^64 - 1) is so large that it exceeds the world’s annual wheat production many times over.

— Mathematics

How can we calculate the grains?

To calculate grains on a chessboard:

For a given square n: The number of grains is 2^(n-1)
- Square 1: 2^0 = 1
- Square 2: 2^1 = 2
- Square 3: 2^2 = 4
- And so on…
For the total: The sum of all grains from square 1 to 64
- This is a geometric series: 1 + 2 + 4 + 8 + … + 2^63
- The sum equals 2^64 - 1
Validation: Square numbers must be between 1 and 64 (inclusive)

The key insight is that we can use the mathematical formula 2^(n-1) for individual squares and 2^64 - 1 for the total, rather than calculating each square individually.

Solution

import 'dart:math';

BigInt square(int n) {
  if (n < 1 || n > 64) {
    throw ArgumentError('square must be between 1 and 64');
  }
  
  return BigInt.from(2).pow(n - 1);
}

BigInt total() {
  return BigInt.from(2).pow(64) - BigInt.one;
}

Let’s break down the solution:

square(int n) - Calculates the number of grains on a given square:
- Validation: First checks if n is between 1 and 64 (inclusive)
  - If not, throws an ArgumentError with a descriptive message
- Calculation: Returns BigInt.from(2).pow(n - 1)
  - Creates a BigInt from 2
  - Raises it to the power of n - 1
  - This gives us 2^(n-1) grains for square n
- Why BigInt?: Regular int can only hold values up to 2^63 - 1, but square 64 needs 2^63, and the total needs 2^64 - 1, which exceeds the int limit
total() - Calculates the total number of grains on all 64 squares:
- Returns BigInt.from(2).pow(64) - BigInt.one
- This calculates 2^64 and subtracts 1
- Mathematical formula: The sum of a geometric series 1 + 2 + 4 + … + 2^63 equals 2^64 - 1
- This is much more efficient than summing all 64 squares individually

The solution efficiently uses mathematical formulas to calculate the results directly, avoiding the need for loops or iterative calculations. BigInt is essential because the numbers involved exceed the maximum value of a regular integer.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel