exercism

Exercism - Sublist

This post shows you how to get Sublist exercise of Exercism.

Stevinator Stevinator
• 9 min read
SHARE
exercism dart flutter sublist

Preparation

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

Sublist Exercise

So we need to use the following concepts.

Enums

Enums are a way to define a set of named constants. They’re perfect for representing a fixed set of possible values or states.

enum Classification {
  equal,
  sublist,
  superlist,
  unequal
}

void main() {
  Classification result = Classification.equal;
  print(result); // Classification.equal
  
  // Switch on enum
  switch (result) {
    case Classification.equal:
      print('Lists are equal');
      break;
    case Classification.sublist:
      print('A is a sublist of B');
      break;
    case Classification.superlist:
      print('A is a superlist of B');
      break;
    case Classification.unequal:
      print('Lists are unequal');
      break;
  }
}

List Methods: skip and take

The skip method returns an iterable that skips the first n elements, and take returns an iterable with the first n elements. These are useful for extracting sublists.

void main() {
  List<int> numbers = [1, 2, 3, 4, 5];
  
  // Skip first 2 elements
  Iterable<int> skipped = numbers.skip(2);
  print(skipped.toList()); // [3, 4, 5]
  
  // Take first 3 elements
  Iterable<int> taken = numbers.take(3);
  print(taken.toList()); // [1, 2, 3]
  
  // Combine skip and take
  Iterable<int> sublist = numbers.skip(1).take(3);
  print(sublist.toList()); // [2, 3, 4]
}

List toString

The toString() method converts a list to its string representation. This can be used for comparing lists by their string representation.

void main() {
  List<int> list1 = [1, 2, 3];
  List<int> list2 = [1, 2, 3];
  
  // Convert to string
  String str1 = list1.toString();
  String str2 = list2.toString();
  
  print(str1); // [1, 2, 3]
  print(str2); // [1, 2, 3]
  
  // Compare string representations
  bool equal = str1 == str2;
  print(equal); // true
}

List Length and Indexing

You can get the length of a list and access elements by index. This is essential for iterating through possible sublist positions.

void main() {
  List<int> list = [1, 2, 3, 4, 5];
  
  // Get length
  int len = list.length;
  print(len); // 5
  
  // Access by index
  print(list[0]); // 1
  print(list[2]); // 3
  
  // Calculate valid range for sublist search
  int sublistLen = 3;
  int maxStart = len - sublistLen;
  print(maxStart); // 2 (can start at index 0, 1, or 2)
  
  // Iterate through possible positions
  for (int i = 0; i <= maxStart; i++) {
    print('Position $i: ${list.skip(i).take(sublistLen).toList()}');
  }
}

String Comparison

Strings can be compared using the == operator. When comparing list string representations, this checks if the lists have the same elements in the same order.

void main() {
  List<int> a = [1, 2, 3];
  List<int> b = [1, 2, 3];
  List<int> c = [1, 2, 4];
  
  // Compare string representations
  bool equal1 = a.toString() == b.toString();
  bool equal2 = a.toString() == c.toString();
  
  print(equal1); // true
  print(equal2); // false
}

Helper Methods

Helper methods are private methods that encapsulate reusable logic. They make code more readable and maintainable.

class Example {
  // Public method
  bool check(List<int> a, List<int> b) {
    return _contains(a, b);
  }
  
  // Private helper method
  bool _contains(List<int> small, List<int> large) {
    // Implementation
    return true;
  }
}

Conditional Logic

You can use if statements and logical operators to determine relationships between lists based on their lengths and contents.

void main() {
  List<int> a = [1, 2, 3];
  List<int> b = [1, 2, 3];
  
  // Check if equal length and contain same elements
  if (a.length == b.length && contains(a, b)) {
    print('Equal');
  } else if (contains(a, b)) {
    print('A is sublist of B');
  } else if (contains(b, a)) {
    print('A is superlist of B');
  } else {
    print('Unequal');
  }
}

Empty List Handling

Empty lists are special cases. An empty list is considered a sublist of any list, and any list is a superlist of an empty list.

void main() {
  List<int> empty = [];
  List<int> nonEmpty = [1, 2, 3];
  
  // Empty list is sublist of any list
  bool isEmptySublist = contains(empty, nonEmpty);
  print(isEmptySublist); // true
  
  // Any list is superlist of empty list
  bool isSuperlist = contains(nonEmpty, empty);
  print(isSuperlist); // true (if we check the reverse)
}

Introduction

Given any two lists A and B, determine if:

  • List A is equal to list B; or
  • List A contains list B (A is a superlist of B); or
  • List A is contained by list B (A is a sublist of B); or
  • None of the above is true, thus lists A and B are unequal

Specifically, list A is equal to list B if both lists have the same values in the same order. List A is a superlist of B if A contains a contiguous sub-sequence of values equal to B. List A is a sublist of B if B contains a contiguous sub-sequence of values equal to A.

Examples

  • If A = [] and B = [] (both lists are empty), then A and B are equal
  • If A = [1, 2, 3] and B = [], then A is a superlist of B
  • If A = [] and B = [1, 2, 3], then A is a sublist of B
  • If A = [1, 2, 3] and B = [1, 2, 3, 4, 5], then A is a sublist of B
  • If A = [3, 4, 5] and B = [1, 2, 3, 4, 5], then A is a sublist of B
  • If A = [3, 4] and B = [1, 2, 3, 4, 5], then A is a sublist of B
  • If A = [1, 2, 3] and B = [1, 2, 3], then A and B are equal
  • If A = [1, 2, 3, 4, 5] and B = [2, 3, 4], then A is a superlist of B
  • If A = [1, 2, 4] and B = [1, 2, 3, 4, 5], then A and B are unequal
  • If A = [1, 2, 3] and B = [1, 3, 2], then A and B are unequal

What is a sublist?

A sublist is a contiguous sequence of elements from a larger list. For example, [2, 3, 4] is a sublist of [1, 2, 3, 4, 5] because it appears as a consecutive sequence within the larger list.

The relationship between lists can be:

  • Equal: Both lists have the same elements in the same order
  • Sublist: One list appears as a contiguous sequence in the other
  • Superlist: One list contains the other as a contiguous sequence
  • Unequal: None of the above relationships hold

— Computer Science

How can we determine the relationship?

To determine the relationship between two lists:

  1. Check if equal: If both lists have the same length and contain the same elements in the same order
  2. Check if sublist: If the smaller list appears as a contiguous sequence in the larger list
  3. Check if superlist: If the larger list contains the smaller list as a contiguous sequence (reverse of sublist check)
  4. Otherwise: The lists are unequal

The key is to check all possible starting positions in the larger list to see if the smaller list appears as a contiguous sequence.

Solution

enum Classification { equal, sublist, superlist, unequal }

class Sublist {
  Classification sublist(List<int> a, List<int> b) {
    if (a.length == b.length && _contains(a, b)) return Classification.equal;
    if (_contains(a, b)) return Classification.sublist;
    if (_contains(b, a)) return Classification.superlist;
    return Classification.unequal;
  }
  
  bool _contains(List<int> small, List<int> large) {
    if (small.isEmpty) return true;
    
    for (int i = 0; i <= large.length - small.length; i++) {
      if (large.skip(i).take(small.length).toList().toString() == small.toString()) {
        return true;
      }
    }
    return false;
  }
}

Let’s break down the solution:

  1. enum Classification - Defines the four possible relationships:

    • equal: Lists are identical
    • sublist: A is a sublist of B
    • superlist: A is a superlist of B
    • unequal: Lists have no relationship

  2. sublist(List<int> a, List<int> b) - Main method that determines the relationship:

    • Equal check: First checks if lists have the same length AND _contains(a, b) returns true
      • This ensures both lists are identical
    • Sublist check: If A is contained in B (A is smaller or equal, and appears in B)
    • Superlist check: If B is contained in A (reverse check - A contains B)
    • Unequal: If none of the above conditions are met

  3. _contains(List<int> small, List<int> large) - Helper method that checks if small appears as a contiguous sequence in large:

    • Empty list handling: If small is empty, returns true (empty list is a sublist of any list)
    • Iteration: Loops through all possible starting positions in large:
      • i ranges from 0 to large.length - small.length (inclusive)
      • This ensures we don’t go out of bounds when extracting a sublist of small.length
    • Comparison: For each position:
      • Uses skip(i) to skip to position i
      • Uses take(small.length) to get exactly small.length elements
      • Converts to list and compares string representations
      • If they match, small is found in large at position i
    • Returns false if no match is found

The solution efficiently checks all possible positions where the smaller list could appear in the larger list, using string comparison for simplicity. The order of checks in sublist() ensures that equal lists are detected first, then sublist/superlist relationships, and finally unequal lists.

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
Stevinator

Stevinator

Stevinator is a software engineer passionate about clean code and best practices. Loves sharing knowledge with the developer community.