Exercism - Collatz Conjecture

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.

ArgumentError and Exception Handling

ArgumentError is thrown when a function receives an invalid argument. You can throw it to indicate that the input doesn’t meet the function’s requirements.

void main() {
  int calculate(int n) {
    if (n <= 0) {
      throw ArgumentError('Only positive integers are allowed');
    }
    // Calculation logic...
    return 0;
  }
  
  try {
    calculate(-5); // Throws ArgumentError
  } catch (e) {
    print(e); // ArgumentError: Only positive integers are allowed
  }
}

While Loops

While loops repeatedly execute a block of code as long as a condition is true. They’re perfect for processes that continue until a specific condition is met.

void main() {
  int n = 12;
  int count = 0;
  
  // Continue until n becomes 1
  while (n != 1) {
    // Process n
    if (n.isEven) {
      n = n ~/ 2;
    } else {
      n = 3 * n + 1;
    }
    count++;
  }
  
  print(count); // Number of steps taken
}

isEven Property

The isEven property returns true if a number is even (divisible by 2), and false if it’s odd. It’s a convenient way to check parity.

void main() {
  int num1 = 12;
  int num2 = 13;
  
  // Check if even
  print(num1.isEven); // true
  print(num2.isEven); // false
  
  // Use in conditional
  if (num1.isEven) {
    print('Even number');
  } else {
    print('Odd number');
  }
  
  // Use with ternary operator
  int result = num1.isEven ? num1 ~/ 2 : 3 * num1 + 1;
  print(result); // 6
}

Integer Division

The integer division operator (~/) divides two numbers and returns an integer result, truncating any decimal part. It’s used when dividing even numbers by 2.

void main() {
  int n = 12;
  
  // Integer division by 2
  int result = n ~/ 2;
  print(result); // 6
  
  // Regular division returns double
  double regular = n / 2;
  print(regular); // 6.0
  
  // For Collatz: if even, divide by 2
  if (n.isEven) {
    n = n ~/ 2; // 12 ~/ 2 = 6
  }
  print(n); // 6
}

Conditional (Ternary) Operator

The ternary operator (? :) provides a concise way to write if-else statements. It’s useful for simple conditional assignments.

void main() {
  int n = 12;
  
  // Ternary operator: condition ? value_if_true : value_if_false
  int result = n.isEven ? n ~/ 2 : 3 * n + 1;
  print(result); // 6 (because 12 is even)
  
  int n2 = 13;
  int result2 = n2.isEven ? n2 ~/ 2 : 3 * n2 + 1;
  print(result2); // 40 (because 13 is odd: 3 * 13 + 1 = 40)
  
  // Equivalent to:
  if (n.isEven) {
    result = n ~/ 2;
  } else {
    result = 3 * n + 1;
  }
}

Counter Variables

Counter variables track the number of iterations or steps in a loop. They’re incremented each time through the loop.

void main() {
  int n = 12;
  int count = 0; // Initialize counter
  
  while (n != 1) {
    // Process n
    n = n.isEven ? n ~/ 2 : 3 * n + 1;
    count++; // Increment counter
  }
  
  print(count); // Total number of steps
}

Comparison Operators

Comparison operators (==, !=, <, >, <=, >=) compare values and return boolean results. They’re used in loop conditions and if statements.

void main() {
  int n = 12;
  
  // Equality check
  print(n == 1); // false
  print(n != 1); // true
  
  // Use in loop condition
  while (n != 1) {
    // Continue until n equals 1
    n = n ~/ 2;
  }
  
  // Comparison operators
  print(5 > 3); // true
  print(5 <= 3); // false
}

Introduction

One evening, you stumbled upon an old notebook filled with cryptic scribbles, as though someone had been obsessively chasing an idea. On one page, a single question stood out: Can every number find its way to 1? It was tied to something called the Collatz Conjecture, a puzzle that has baffled thinkers for decades.

The rules were deceptively simple. Pick any positive integer.

If it’s even, divide it by 2.
If it’s odd, multiply it by 3 and add 1.

Then, repeat these steps with the result, continuing indefinitely.

Curious, you picked number 12 to test and began the journey:

12 ➜ 6 ➜ 3 ➜ 10 ➜ 5 ➜ 16 ➜ 8 ➜ 4 ➜ 2 ➜ 1

Counting from the second number (6), it took 9 steps to reach 1, and each time the rules repeated, the number kept changing. At first, the sequence seemed unpredictable — jumping up, down, and all over. Yet, the conjecture claims that no matter the starting number, we’ll always end at 1.

It was fascinating, but also puzzling. Why does this always seem to work? Could there be a number where the process breaks down, looping forever or escaping into infinity? The notebook suggested solving this could reveal something profound — and with it, fame, fortune, and a place in history awaits whoever could unlock its secrets.

Instructions

Given a positive integer, return the number of steps it takes to reach 1 according to the rules of the Collatz Conjecture.

What is the Collatz Conjecture?

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

— Wikipedia

How can we calculate Collatz steps?

To calculate the number of steps to reach 1:

Validate input: Ensure the number is positive (throw error if not)
Initialize counter: Start with count = 0
Loop until n == 1:
- If n is even: divide by 2 (n = n ~/ 2)
- If n is odd: multiply by 3 and add 1 (n = 3 * n + 1)
- Increment the counter
Return count: The number of steps taken

The key insight is using a while loop that continues until the number reaches 1, applying the Collatz rules at each step and counting the iterations.

For example, with n = 12:

Step 1: 12 is even → 12 ÷ 2 = 6 (count = 1)
Step 2: 6 is even → 6 ÷ 2 = 3 (count = 2)
Step 3: 3 is odd → 3 × 3 + 1 = 10 (count = 3)
Step 4: 10 is even → 10 ÷ 2 = 5 (count = 4)
Step 5: 5 is odd → 5 × 3 + 1 = 16 (count = 5)
Step 6: 16 is even → 16 ÷ 2 = 8 (count = 6)
Step 7: 8 is even → 8 ÷ 2 = 4 (count = 7)
Step 8: 4 is even → 4 ÷ 2 = 2 (count = 8)
Step 9: 2 is even → 2 ÷ 2 = 1 (count = 9)
n == 1, loop ends → return 9

Solution

class CollatzConjecture {
  int steps(int n) {
    if (n <= 0) throw ArgumentError('Only positive integers are allowed');

    int count = 0;
    while (n != 1) {
      n = n.isEven ? n ~/ 2 : 3 * n + 1;
      count++;
    }
    return count;
  }
}

Let’s break down the solution:

int steps(int n) - Main method that calculates Collatz steps:
- Takes a positive integer as input
- Returns the number of steps to reach 1
if (n <= 0) throw ArgumentError(...) - Input validation:
- Checks if the input is not positive
- Throws an ArgumentError with a descriptive message if invalid
- Ensures only positive integers are processed
int count = 0 - Initialize step counter:
- Tracks the number of steps taken
- Starts at 0 and increments with each iteration
while (n != 1) - Loop until reaching 1:
- Continues as long as n is not equal to 1
- Stops when n becomes 1 (the goal)
n = n.isEven ? n ~/ 2 : 3 * n + 1 - Apply Collatz rules:
- Uses ternary operator for concise conditional logic
- If even (n.isEven): Divide by 2 using integer division (n ~/ 2)
- If odd (else): Multiply by 3 and add 1 (3 * n + 1)
- Updates n with the new value
count++ - Increment step counter:
- Increases count by 1 after each transformation
- Tracks the total number of steps
return count - Return the result:
- Returns the number of steps taken to reach 1

The solution efficiently implements the Collatz Conjecture algorithm using a while loop and ternary operator. It validates input, applies the transformation rules, and counts steps until the number reaches 1.

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