Exercism - All Your Base

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.

Classes

Classes define blueprints for objects. They can contain methods that work together to solve a problem.

class AllYourBase {
  // Methods for base conversion
  List<int> rebase(int inputBase, List<int> digits, int outputBase) {
    // Conversion logic
    return [];
  }
}

void main() {
  AllYourBase converter = AllYourBase();
  List<int> result = converter.rebase(2, [1, 0, 1, 0], 10);
  print(result); // [1, 0]
}

Recursion

Recursion is when a function calls itself. It’s perfect for problems that can be broken down into smaller versions of the same problem, like base conversion.

// Recursive function to calculate factorial
int factorial(int n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

// Recursive function to convert from base
int fromBase(List<int> digits, int base, [int acc = 0]) {
  if (digits.isEmpty) return acc; // Base case
  // Recursive case: process first digit, recurse on rest
  return fromBase(
    digits.sublist(1), 
    base, 
    acc * base + digits.first
  );
}

void main() {
  print(factorial(5)); // 120
  print(fromBase([1, 0, 1, 0], 2)); // 10 (binary to decimal)
}

List `any()` Method

The any() method checks if any element in a list satisfies a condition. It returns true if at least one element matches.

void main() {
  List<int> digits = [0, 1, 2, 3];
  
  // Check if any digit is negative
  bool hasNegative = digits.any((x) => x < 0);
  print(hasNegative); // false
  
  // Check if any digit is >= 10
  bool hasInvalid = digits.any((x) => x >= 10);
  print(hasInvalid); // false
  
  // Use for validation
  List<int> invalid = [0, 1, 5, 10]; // 10 is invalid for base 2
  if (invalid.any((x) => x >= 2)) {
    throw ArgumentError('Invalid digits for base 2');
  }
}

List `every()` Method

The every() method checks if all elements in a list satisfy a condition. It returns true only if every element matches.

void main() {
  List<int> digits = [0, 0, 0, 0];
  
  // Check if all digits are zero
  bool allZero = digits.every((x) => x == 0);
  print(allZero); // true
  
  // Check if all digits are positive
  List<int> positive = [1, 2, 3];
  bool allPositive = positive.every((x) => x > 0);
  print(allPositive); // true
  
  // Use for validation
  if (digits.every((x) => x == 0)) {
    return [0]; // All zeros case
  }
}

List `isEmpty` Property

The isEmpty property checks if a list has no elements. It’s useful for base cases in recursion.

void main() {
  List<int> empty = [];
  List<int> notEmpty = [1, 2, 3];
  
  // Check if empty
  if (empty.isEmpty) {
    print('List is empty');
  }
  
  // Use in recursion base case
  int sum(List<int> list, [int acc = 0]) {
    if (list.isEmpty) return acc; // Base case
    return sum(list.sublist(1), acc + list.first);
  }
  
  print(sum([1, 2, 3])); // 6
}

List `sublist()` Method

The sublist() method creates a new list containing elements from a specified range. It’s perfect for recursive processing where you process the first element and recurse on the rest.

void main() {
  List<int> digits = [1, 2, 3, 4, 5];
  
  // Get sublist from index 1 to end
  List<int> rest = digits.sublist(1);
  print(rest); // [2, 3, 4, 5]
  
  // Get sublist with start and end
  List<int> middle = digits.sublist(1, 4);
  print(middle); // [2, 3, 4]
  
  // Use in recursion
  int process(List<int> list) {
    if (list.isEmpty) return 0;
    int first = list.first;
    List<int> rest = list.sublist(1);
    return first + process(rest);
  }
}

List `first` Property

The first property returns the first element of a list. It’s useful for processing elements one at a time in recursion.

void main() {
  List<int> digits = [1, 2, 3];
  
  // Get first element
  int first = digits.first;
  print(first); // 1
  
  // Use in recursion
  int sum(List<int> list) {
    if (list.isEmpty) return 0;
    return list.first + sum(list.sublist(1));
  }
  
  print(sum([1, 2, 3])); // 6
}

ArgumentError

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() {
  void validateBase(int base) {
    if (base < 2) {
      throw ArgumentError('Base must be >= 2');
    }
  }
  
  void validateDigits(List<int> digits, int base) {
    if (digits.any((x) => x < 0 || x >= base)) {
      throw ArgumentError('Invalid digits for base $base');
    }
  }
  
  try {
    validateBase(1); // Throws ArgumentError
  } catch (e) {
    print(e); // ArgumentError: Base must be >= 2
  }
}

Optional Parameters with Default Values

Optional parameters allow you to provide default values. They’re useful for accumulator parameters in recursive functions.

void main() {
  // Optional parameter with default value
  int sum(List<int> list, [int acc = 0]) {
    if (list.isEmpty) return acc;
    return sum(list.sublist(1), acc + list.first);
  }
  
  // Called without optional parameter
  print(sum([1, 2, 3])); // 6 (acc defaults to 0)
  
  // Called with optional parameter
  print(sum([1, 2, 3], 10)); // 16 (acc starts at 10)
  
  // Optional nullable parameter
  List<int> buildList(int n, [List<int>? acc]) {
    acc ??= []; // Use default if null
    if (n <= 0) return acc;
    return buildList(n - 1, [n, ...acc]);
  }
  
  print(buildList(3)); // [3, 2, 1]
}

Spread Operator (`...`)

The spread operator (...) expands a list into individual elements. It’s useful for prepending elements to a list in recursion.

void main() {
  List<int> list1 = [1, 2, 3];
  List<int> list2 = [4, 5, 6];
  
  // Combine lists
  List<int> combined = [...list1, ...list2];
  print(combined); // [1, 2, 3, 4, 5, 6]
  
  // Prepend element
  int element = 0;
  List<int> withElement = [element, ...list1];
  print(withElement); // [0, 1, 2, 3]
  
  // Use in recursion
  List<int> build(int n) {
    if (n <= 0) return [];
    return [n % 10, ...build(n ~/ 10)];
  }
  
  print(build(123)); // [3, 2, 1]
}

Integer Division (`~/`) and Modulo (`%`)

Integer division (~/) divides two numbers and returns an integer, discarding the remainder. Modulo (%) returns the remainder. They’re essential for base conversion.

void main() {
  int number = 42;
  int base = 10;
  
  // Integer division
  int quotient = number ~/ base;
  print(quotient); // 4
  
  // Modulo (remainder)
  int remainder = number % base;
  print(remainder); // 2
  
  // Use in base conversion
  // To convert 42 to base 10:
  // 42 % 10 = 2 (last digit)
  // 42 ~/ 10 = 4 (remaining number)
  // 4 % 10 = 4 (next digit)
  // 4 ~/ 10 = 0 (done)
  // Result: [4, 2]
  
  List<int> toBase(int n, int b) {
    if (n == 0) return [];
    return [...toBase(n ~/ b, b), n % b];
  }
  
  print(toBase(42, 10)); // [4, 2]
}

Null-Aware Operator (`??`)

The null-aware operator (??) provides a default value if the left side is null. It’s useful for optional parameters.

void main() {
  // Null-aware operator
  int? value = null;
  int result = value ?? 0;
  print(result); // 0 (uses default)
  
  int? value2 = 5;
  int result2 = value2 ?? 0;
  print(result2); // 5 (uses actual value)
  
  // Use with optional parameters
  List<int> build(int n, [List<int>? acc]) {
    acc ??= []; // Use empty list if null
    if (n <= 0) return acc;
    return build(n - 1, [n, ...acc]);
  }
  
  print(build(3)); // [3, 2, 1]
}

Expression-Bodied Methods

Expression-bodied methods use => to return a value directly. They’re perfect for concise recursive functions.

class AllYourBase {
  // Expression-bodied recursive method
  int fromBase(List<int> digits, int base, [int acc = 0]) =>
      digits.isEmpty 
        ? acc 
        : fromBase(digits.sublist(1), base, acc * base + digits.first);
}

// Equivalent to:
int fromBase(List<int> digits, int base, [int acc = 0]) {
  if (digits.isEmpty) return acc;
  return fromBase(digits.sublist(1), base, acc * base + digits.first);
}

Base Conversion Concepts

In positional notation, a number in base b is a linear combination of powers of b. Understanding this is key to base conversion.

void main() {
  // Example: 42 in base 10
  // = (4 × 10¹) + (2 × 10⁰)
  // = 40 + 2 = 42
  
  // Example: 101010 in base 2 (binary)
  // = (1 × 2⁵) + (0 × 2⁴) + (1 × 2³) + (0 × 2²) + (1 × 2¹) + (0 × 2⁰)
  // = 32 + 0 + 8 + 0 + 2 + 0 = 42
  
  // Example: 1120 in base 3
  // = (1 × 3³) + (1 × 3²) + (2 × 3¹) + (0 × 3⁰)
  // = 27 + 9 + 6 + 0 = 42
  
  // All three represent the same number: 42
}

Introduction

You’ve just been hired as professor of mathematics. Your first week went well, but something is off in your second week. The problem is that every answer given by your students is wrong! Luckily, your math skills have allowed you to identify the problem: the student answers are correct, but they’re all in base 2 (binary)! Amazingly, it turns out that each week, the students use a different base. To help you quickly verify the student answers, you’ll be building a tool to translate between bases.

Instructions

Convert a sequence of digits in one base, representing a number, into a sequence of digits in another base, representing the same number.

Note

Try to implement the conversion yourself. Do not use something else to perform the conversion for you.

About Positional Notation

In positional notation, a number in base b can be understood as a linear combination of powers of b.

The number 42, in base 10, means:

(4 × 10¹) + (2 × 10⁰)

The number 101010, in base 2, means:

(1 × 2⁵) + (0 × 2⁴) + (1 × 2³) + (0 × 2²) + (1 × 2¹) + (0 × 2⁰)

The number 1120, in base 3, means:

(1 × 3³) + (1 × 3²) + (2 × 3¹) + (0 × 3⁰)

Yes. Those three numbers above are exactly the same. Congratulations!

How does base conversion work?

To convert between bases:

Validate inputs: Check that bases are >= 2 and digits are valid for the input base
Handle edge cases: Empty list or all zeros returns [0]
Convert to decimal: Use _fromBase to convert from input base to decimal (base 10)
- Process digits left to right
- Multiply accumulator by base and add current digit
Convert from decimal: Use _toBase to convert from decimal to output base
- Repeatedly divide by base and collect remainders
- Build result list from right to left

The key insight is using decimal (base 10) as an intermediate representation: convert from input base → decimal → output base.

For example, converting [1, 0, 1, 0] from base 2 to base 10:

Start: acc = 0
Process 1: acc = 0 × 2 + 1 = 1
Process 0: acc = 1 × 2 + 0 = 2
Process 1: acc = 2 × 2 + 1 = 5
Process 0: acc = 5 × 2 + 0 = 10
Result: 10 (decimal)

Then convert 10 from decimal to base 3:

10 ÷ 3 = 3 remainder 1 → [1]
3 ÷ 3 = 1 remainder 0 → [0, 1]
1 ÷ 3 = 0 remainder 1 → [1, 0, 1]
Result: [1, 0, 1] (base 3)

Solution

class AllYourBase {
  List<int> rebase(int ib, List<int> d, int ob) {
    if (ib < 2 || ob < 2) throw ArgumentError('Bases must be >= 2');

    if (d.any((x) => x < 0 || x >= ib)) throw ArgumentError('Invalid digits');

    if (d.isEmpty || d.every((x) => x == 0)) return [0];
    

    return _toBase(_fromBase(d, ib), ob);
  }

  int _fromBase(List<int> d, int b, [int acc = 0]) =>
      d.isEmpty ? acc : _fromBase(d.sublist(1), b, acc * b + d.first);

  List<int> _toBase(int n, int b, [List<int>? acc]) {
    acc ??= [];
    return n == 0 ? (acc.isEmpty ? [0] : acc) : _toBase(n ~/ b, b, [n % b, ...acc]);
  }
}

Let’s break down the solution:

class AllYourBase - Main class:
- Encapsulates base conversion logic
- Contains public rebase method and private helper methods
List<int> rebase(int ib, List<int> d, int ob) - Public conversion method:
- Takes input base (ib), digits (d), and output base (ob)
- Returns digits in output base
- Validates inputs and handles edge cases
if (ib < 2 || ob < 2) - Validate bases:
- Checks that both bases are at least 2
- Base 1 doesn’t make sense, base 0 is invalid
- Throws ArgumentError if invalid
throw ArgumentError('Bases must be >= 2') - Error for invalid bases:
- Provides descriptive error message
- Indicates what went wrong
if (d.any((x) => x < 0 || x >= ib)) - Validate digits:
- Checks if any digit is negative or >= input base
- In base 2, digits must be 0 or 1
- In base 10, digits must be 0-9
- Throws ArgumentError if invalid
throw ArgumentError('Invalid digits') - Error for invalid digits:
- Indicates digits don’t match the input base
- Example: digit 5 in base 2 is invalid
if (d.isEmpty || d.every((x) => x == 0)) - Handle edge cases:
- Empty list represents 0
- All zeros also represents 0
- Returns [0] immediately
return [0] - Return zero:
- Zero in any base is represented as [0]
- Handles both empty and all-zero cases
return _toBase(_fromBase(d, ib), ob) - Convert via decimal:
- First converts from input base to decimal
- Then converts from decimal to output base
- Uses decimal as intermediate representation
int _fromBase(List<int> d, int b, [int acc = 0]) - Convert to decimal:
- Private recursive method
- Takes digits, base, and optional accumulator
- Returns decimal (base 10) value
d.isEmpty ? acc : ... - Base case:
- If digits list is empty, return accumulator
- Accumulator contains the final decimal value
_fromBase(d.sublist(1), b, acc * b + d.first) - Recursive case:
- Process first digit: acc * b + d.first
- Recurse on remaining digits: d.sublist(1)
- Example: base 2, digits [1, 0, 1]
  - First call: acc=0, process 1 → acc=0×2+1=1, recurse on [0,1]
  - Second call: acc=1, process 0 → acc=1×2+0=2, recurse on [1]
  - Third call: acc=2, process 1 → acc=2×2+1=5, recurse on []
  - Base case: return 5
List<int> _toBase(int n, int b, [List<int>? acc]) - Convert from decimal:
- Private recursive method
- Takes decimal number, base, and optional accumulator list
- Returns list of digits in target base
acc ??= [] - Initialize accumulator:
- Uses null-aware operator to set default empty list
- Only sets if acc is null
n == 0 ? (acc.isEmpty ? [0] : acc) : ... - Base case:
- If number is 0, check if accumulator is empty
- If empty, return [0] (number was 0)
- If not empty, return accumulator (conversion complete)
_toBase(n ~/ b, b, [n % b, ...acc]) - Recursive case:
- Calculate remainder: n % b (current digit)
- Calculate quotient: n ~/ b (remaining number)
- Prepend digit to accumulator: [n % b, ...acc]
- Recurse with quotient
- Example: convert 10 to base 3
  - First call: n=10, 10%3=1, 10~/3=3, acc=[1], recurse with n=3
  - Second call: n=3, 3%3=0, 3~/3=1, acc=[0,1], recurse with n=1
  - Third call: n=1, 1%3=1, 1~/3=0, acc=[1,0,1], recurse with n=0
  - Base case: return [1,0,1]
[n % b, ...acc] - Prepend digit:
- Spread operator expands accumulator
- New digit goes at the front
- Builds result from right to left (least significant first)

The solution efficiently converts between bases using recursion to process digits and build results. The two-step approach (input base → decimal → output base) simplifies the conversion logic and works for any base combination.

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