Exercism - Pascal's Triangle

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.

Lists and List.generate

The List.generate() method creates a list of a specified length by calling a function for each index. It’s useful for creating lists dynamically based on calculations.

void main() {
  // Generate list of numbers
  List<int> numbers = List.generate(5, (i) => i);
  print(numbers); // [0, 1, 2, 3, 4]
  
  // Generate list with calculations
  List<int> squares = List.generate(5, (i) => (i + 1) * (i + 1));
  print(squares); // [1, 4, 9, 16, 25]
  
  // Generate nested lists
  List<List<int>> triangle = List.generate(3, (i) => List.generate(i + 1, (j) => j + 1));
  print(triangle); // [[1], [1, 2], [1, 2, 3]]
}

Nested Lists

Nested lists (lists of lists) allow you to represent two-dimensional structures like matrices or triangles.

void main() {
  // Create a list of lists
  List<List<int>> triangle = [
    [1],
    [1, 1],
    [1, 2, 1]
  ];
  
  // Access elements
  print(triangle[0]); // [1]
  print(triangle[1][0]); // 1
  print(triangle[2][1]); // 2
  
  // Build dynamically
  List<List<int>> result = [];
  for (int i = 0; i < 3; i++) {
    result.add(List.generate(i + 1, (j) => j + 1));
  }
  print(result); // [[1], [1, 2], [1, 2, 3]]
}

Recursion

Recursion is when a function calls itself. It’s useful for problems that can be broken down into smaller, similar subproblems. Recursive functions need a base case to stop the recursion.

void main() {
  // Recursive factorial function
  int factorial(int n) {
    // Base case: stop recursion
    if (n == 0 || n == 1) {
      return 1;
    }
    // Recursive case: call itself with smaller value
    return n * factorial(n - 1);
  }
  
  print(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
  print(factorial(0)); // 1
  print(factorial(1)); // 1
}

Factorial

The factorial of a number n (written as n!) is the product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.

void main() {
  int factorial(int n) {
    if (n == 0 || n == 1) {
      return 1;
    }
    return n * factorial(n - 1);
  }
  
  // Examples
  print(factorial(0)); // 1 (by definition)
  print(factorial(1)); // 1
  print(factorial(3)); // 6 (3 * 2 * 1)
  print(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
}

Integer Division

The integer division operator (~/) divides two numbers and returns an integer result, truncating any decimal part. This is different from regular division (/) which returns a double.

void main() {
  // Regular division (returns double)
  double result1 = 10 / 3;
  print(result1); // 3.3333333333333335
  
  // Integer division (returns int)
  int result2 = 10 ~/ 3;
  print(result2); // 3
  
  // Useful for calculations that must be integers
  int n = 5;
  int k = 2;
  int combination = factorial(n) ~/ (factorial(k) * factorial(n - k));
  print(combination); // 10
}

Conditional Logic

Conditional statements allow you to execute different code based on conditions. This is essential for handling edge cases and base cases in recursive functions.

void main() {
  int calculate(int n) {
    // Handle base case
    if (n == 0 || n == 1) {
      return 1;
    }
    // Handle normal case
    return n * calculate(n - 1);
  }
  
  // Check for empty input
  List<List<int>> buildTriangle(int rows) {
    if (rows == 0) {
      return [];
    }
    // Build triangle...
    return [];
  }
}

Pascal’s Formula

Pascal’s triangle can be calculated using the binomial coefficient formula: C(n, k) = n! / (k! × (n-k)!). This formula gives the value at row n, position k in Pascal’s triangle.

void main() {
  int factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n - 1);
  }
  
  // Pascal's formula: C(n, k) = n! / (k! * (n-k)!)
  int pascalValue(int n, int k) {
    return factorial(n) ~/ (factorial(k) * factorial(n - k));
  }
  
  // Row 4, position 2 (0-indexed: row 3, position 1)
  print(pascalValue(3, 1)); // 3
  // Row 5, position 2 (0-indexed: row 4, position 2)
  print(pascalValue(4, 2)); // 6
}

Introduction

With the weather being great, you’re not looking forward to spending an hour in a classroom. Annoyed, you enter the class room, where you notice a strangely satisfying triangle shape on the blackboard. Whilst waiting for your math teacher to arrive, you can’t help but notice some patterns in the triangle: the outer values are all ones, each subsequent row has one more value than its previous row and the triangle is symmetrical. Weird!

Not long after you sit down, your teacher enters the room and explains that this triangle is the famous Pascal’s triangle.

Over the next hour, your teacher reveals some amazing things hidden in this triangle:

It can be used to compute how many ways you can pick K elements from N values.
It contains the Fibonacci sequence.
If you color odd and even numbers differently, you get a beautiful pattern called the Sierpiński triangle.

The teacher implores you and your classmates to look up other uses, and assures you that there are lots more! At that moment, the school bell rings. You realize that for the past hour, you were completely absorbed in learning about Pascal’s triangle. You quickly grab your laptop from your bag and go outside, ready to enjoy both the sunshine and the wonders of Pascal’s triangle.

Instructions

Your task is to output the first N rows of Pascal’s triangle.

Pascal’s triangle is a triangular array of positive integers.

In Pascal’s triangle, the number of values in a row is equal to its row number (which starts at one). Therefore, the first row has one value, the second row has two values, and so on.

The first (topmost) row has a single value: 1. Subsequent rows’ values are computed by adding the numbers directly to the right and left of the current position in the previous row.

If the previous row does not have a value to the left or right of the current position (which only happens for the leftmost and rightmost positions), treat that position’s value as zero (effectively “ignoring” it in the summation).

Example

Let’s look at the first 5 rows of Pascal’s Triangle:

The topmost row has one value, which is 1.

The leftmost and rightmost values have only one preceding position to consider, which is the position to its right respectively to its left. With the topmost value being 1, it follows from this that all the leftmost and rightmost values are also 1.

The other values all have two positions to consider. For example, the fifth row’s (1 4 6 4 1) middle value is 6, as the values to its left and right in the preceding row are 3 and 3.

What is Pascal’s Triangle?

Pascal’s triangle is a triangular array of the binomial coefficients. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in India, Persia, China, Germany, and Italy. Each number in the triangle is the sum of the two numbers directly above it. The triangle has many interesting properties and applications in combinatorics, probability, and algebra.

— Wikipedia

How can we calculate Pascal’s Triangle?

To calculate Pascal’s Triangle:

Use Pascal’s formula: Each value at row n, position k can be calculated using the binomial coefficient: C(n, k) = n! / (k! × (n-k)!)
Handle edge cases: Return an empty list if numberOfRows is 0
Build each row: For each row from 1 to numberOfRows, generate the values using Pascal’s formula
Use recursion: Calculate factorials recursively (with base cases for 0 and 1)

The key insight is that Pascal’s triangle values can be computed directly using the binomial coefficient formula, which is more efficient than building row by row using addition.

For example, to get the value at row 5, position 3 (0-indexed: row 4, position 2):

C(4, 2) = 4! / (2! × (4-2)!) = 24 / (2 × 2) = 24 / 4 = 6

Solution

class PascalsTriangle {
  List<List<int>> rows(int numberOfRows) {
    if (numberOfRows == 0) return <List<int>>[];
    List<List<int>> result = List.generate(0, (i) => []);

    for (var i = 1; i <= numberOfRows; i++) {
      result.add(List.generate(i, (index) => pascalsFormula(i - 1, index)));
    }
    return result;
  }

  int findFactorial(int no) {
    if (no == 1 || no == 0) {
      return 1;
    }
    return no * findFactorial(no - 1);
  }

  int pascalsFormula(int n, int k) {
    return findFactorial(n) ~/ (findFactorial(k) * findFactorial(n - k));
  }
}

Let’s break down the solution:

int findFactorial(int no) - Recursive function to calculate factorial:
- Base cases: Returns 1 if no is 0 or 1 (by definition, 0! = 1 and 1! = 1)
- Recursive case: Returns no * findFactorial(no - 1) to calculate the factorial
- Example: findFactorial(5) = 5 × 4 × 3 × 2 × 1 = 120
int pascalsFormula(int n, int k) - Calculates the value at row n, position k using the binomial coefficient:
- Uses Pascal’s formula: C(n, k) = n! / (k! × (n-k)!)
- findFactorial(n) - Calculates n!
- findFactorial(k) - Calculates k!
- findFactorial(n - k) - Calculates (n-k)!
- Uses integer division (~/) to get an integer result
- Example: pascalsFormula(4, 2) = 4! / (2! × 2!) = 24 / 4 = 6
List<List<int>> rows(int numberOfRows) - Main method that builds Pascal’s triangle:
- Edge case: Returns an empty list if numberOfRows == 0
- Initialize result: Creates an empty list of lists using List.generate(0, (i) => [])
- Build each row: Loops from 1 to numberOfRows:
  - For each row i, generates i values using List.generate(i, ...)
  - Each value at position index in row i is calculated using pascalsFormula(i - 1, index)
  - Note: Row numbers are 1-indexed in the problem, but we use 0-indexed for the formula (hence i - 1)
- Add to result: Adds each generated row to the result list
- Returns the complete triangle as a list of lists

The solution efficiently calculates each value in Pascal’s triangle using the binomial coefficient formula, which is mathematically elegant and avoids the need to build rows incrementally.

You can watch this tutorial on YouTube. So don’t forget to like and subscribe. 😉

Watch on YouTube