Implementing Delta Debugging for Jest Test Failures

This challenge focuses on implementing a simplified version of Delta Debugging, a powerful technique for automatically finding the smallest input that causes a program to fail. In the context of software testing, this means pinpointing the exact code change or input variation that triggers a specific Jest test failure, significantly speeding up debugging.

Problem Description

Your task is to implement a core component of a Delta Debugging algorithm specifically designed to work with Jest test failures. Given a failing Jest test scenario, represented by a set of "parts" that can be individually removed or kept, you need to find the minimal subset of these parts that still causes the test to fail.

What needs to be achieved: You will create a function findMinimalFailingSubset that takes an initial set of failing "parts" and a function to test if a given subset of parts causes the test to fail. The function should return the smallest possible subset of the original parts that still triggers the failure.

Key requirements:

• The function must explore different combinations of removing parts.
• It should iteratively reduce the failing subset until no smaller subset fails.
• The algorithm should be efficient enough for practical use.

Expected behavior: The function should return an array of the minimal set of "parts" that, when passed to the testFailingCondition function, results in true (indicating a failure). If the initial set doesn't fail, or if no subset fails, it should return an empty array.

Important edge cases to consider:

• The initial input might not actually fail.
• The input might consist of only one part, and that part alone causes the failure.
• All parts might be necessary for the failure.

Examples

Example 1:

Input:
parts = ['a', 'b', 'c', 'd']
testFailingCondition = (subset: string[]) => {
  // Simulate failure if 'a' and 'c' are present
  return subset.includes('a') && subset.includes('c');
};

Output: ['a', 'c']
Explanation:
1. Start with all parts: ['a', 'b', 'c', 'd'] - fails.
2. Try removing 'd': ['a', 'b', 'c'] - fails.
3. Try removing 'c': ['a', 'b'] - does not fail. Backtrack.
4. With ['a', 'b', 'c'], try removing 'b': ['a', 'c'] - fails.
5. With ['a', 'b', 'c'], try removing 'a': ['b', 'c'] - does not fail. Backtrack.
6. With ['a', 'c'] (from step 4), try removing 'c': ['a'] - does not fail.
7. With ['a', 'c'] (from step 4), try removing 'a': ['c'] - does not fail.
The minimal failing subset found is ['a', 'c'].

Example 2:

Input:
parts = ['x', 'y', 'z']
testFailingCondition = (subset: string[]) => {
  // Simulate failure if 'x' is present
  return subset.includes('x');
};

Output: ['x']
Explanation:
1. Start with all parts: ['x', 'y', 'z'] - fails.
2. Try removing 'z': ['x', 'y'] - fails.
3. Try removing 'y': ['x'] - fails.
4. Try removing 'x': [] - does not fail. Backtrack.
The minimal failing subset found is ['x'].

Example 3: (Edge Case)

Input:
parts = ['p', 'q']
testFailingCondition = (subset: string[]) => {
  // Simulate failure only if both 'p' and 'q' are present
  return subset.includes('p') && subset.includes('q');
};

Output: ['p', 'q']
Explanation:
1. Start with all parts: ['p', 'q'] - fails.
2. Try removing 'q': ['p'] - does not fail. Backtrack.
3. Try removing 'p': ['q'] - does not fail. Backtrack.
Since removing any single part stops the failure, and the initial set fails, the minimal failing subset is the original set itself.

Constraints

• The parts array will contain strings.
• The testFailingCondition function will always return a boolean.
• The number of parts will be between 0 and 20 (inclusive). This constraint is to keep the computational complexity manageable for this exercise.
• The implementation should aim for a reasonable time complexity, avoiding brute-force checking of all 2^N subsets directly.

Notes

This challenge is a simplified implementation of Delta Debugging. Real-world Delta Debugging algorithms can be more complex and deal with various forms of "parts" (e.g., lines of code, configuration options).

Consider a strategy where you divide the current failing set into roughly equal halves and test whether each half is responsible for the failure. If a half fails, recursively apply the process to that half. If neither half fails on its own, then the combination of parts from both halves (i.e., the original failing set) is still minimal with respect to the current division strategy. You'll need to manage the subsets carefully to ensure you're always working with a set that is known to fail.