Bracket Sequence Completion Test Manifold¶

Overview¶

The Bracket Sequence Completion test manifold assesses a model's ability to correctly complete bracket sequences by generating the appropriate closing brackets in the correct order. This task tests understanding of nested data structures, stack-based processing, and the Last-In-First-Out (LIFO) principle fundamental to many programming and mathematical contexts.

Task Description¶

Models are presented with sequences of opening and closing brackets of various types, and must generate the correct sequence of closing brackets to properly balance the expression. The task requires understanding bracket matching rules, proper nesting order, and stack-based evaluation principles.

Key Features:

Multiple bracket types: Support for round (), square [], curly {}, and pointy <> brackets
Configurable bracket sets: Bitwise selection allows enabling specific bracket type combinations
Variable nesting depth: Expressions can have shallow or deeply nested bracket structures
Weighted generation: Configurable probability weighting for opening vs closing bracket placement
Stack-based validation: Proper LIFO ordering ensures syntactically valid bracket sequences

Difficulty Progression and Complexity Factors¶

Sequence Length (length):

3-5 pairs: Basic bracket matching with minimal nesting
6-10 pairs: Moderate complexity requiring sustained attention to bracket order
10+ pairs: Extended sequences testing working memory and systematic processing

Nesting Depth (max_depth):

Depth 1: Simple linear sequences with minimal nesting
Depth 2-3: Moderate nesting requiring careful bracket tracking
Depth 4+: Deep nesting structures challenging working memory limits

Bracket Type Combinations (bracket_types):

Single type (1, 2, 4, 8): Focus on nesting without type confusion
Two types (3, 5, 6, 9, 10, 12): Moderate complexity with type differentiation
Three types (7, 11, 13, 14): High complexity requiring careful type tracking
All types (15): Maximum complexity with full bracket type diversity

Bracket Types Encoding:

Bit 1 (value 1): Round brackets ()
Bit 2 (value 2): Square brackets []
Bit 3 (value 4): Curly brackets {}
Bit 4 (value 8): Pointy brackets <>

Close Weight Multiplier (close_weight_multiplier):

Values < 1.0: Favor opening brackets, creating more nested structures
Value = 1.0: Equal probability of opening/closing brackets
Values > 1.0: Favor closing brackets, creating more balanced sequences
Higher values (2.0+): Generate sequences that close brackets more frequently

Test Case Generation¶

Algorithm Overview¶

The generator uses a guided random walk approach with stack-based validation:

Weighted Random Selection: At each step, probabilistically choose between opening and closing brackets based on current state
Stack Tracking: Maintain a stack of open brackets to ensure valid closing sequences
Depth Limiting: Enforce maximum nesting depth to control complexity
Type Validation: Ensure closing brackets match the most recent opening bracket of the same type
Completion Generation: After generating the input sequence, compute the required closing sequence using stack unwinding

Bracket Matching Rules¶

Opening Brackets:

Can be added when current depth < max_depth
Push onto stack for later matching
Increase current nesting depth

Closing Brackets:

Can only be added when matching opening bracket exists on stack
Must match the most recent opening bracket of the same type
Pop matching opening bracket from stack
Decrease current nesting depth

Target Generation:

Process input sequence to build stack of unmatched opening brackets
Generate closing sequence by popping stack in LIFO order
Each opening bracket maps to its corresponding closing bracket

Configuration Parameters¶

Generation Schema (`BracketGenerationParams`)¶

class BracketGenerationParams(BaseModel):
    count: int                           # Number of test cases to generate (> 0)
    length: int                          # Number of bracket pairs in sequence (≥ 1)
    max_depth: int                       # Maximum bracket nesting depth (≥ 1)
    bracket_types: int                   # Bitwise enum for bracket types (1-15, default: 15)
    close_weight_multiplier: float       # Multiplier for closing bracket probability (≥ 0, default: 2.0)

Bracket Types Bitwise Encoding:

1 (0001): Round brackets only ()
2 (0010): Square brackets only []
4 (0100): Curly brackets only {}
8 (1000): Pointy brackets only <>
15 (1111): All bracket types enabled

Result Schema (`BracketTestCaseResult`)¶

class BracketTestCaseResult(BaseModel):
    input: str                          # The bracket sequence to complete
    target: str                         # The correct closing sequence

Example Test Cases¶

Simple Single Type (length=3, max_depth=2, bracket_types=1)¶

Input: "( ( ("
Target: ") ) )"

Analysis: Three nested opening round brackets require three closing brackets in reverse order (LIFO).

Mixed Types Shallow (length=4, max_depth=2, bracket_types=3)¶

Input: "( [ ] ("
Target: ")"

Analysis: The square bracket pair is properly closed, leaving only the outer round bracket to close.

Deep Nesting (length=5, max_depth=4, bracket_types=1)¶

Input: "( ( ( ( ("
Target: ") ) ) ) )"

Analysis: Maximum depth nesting with single bracket type requires systematic LIFO unwinding.

Complex Mixed Types (length=6, max_depth=3, bracket_types=15)¶

Input: "{ [ < > ] ("
Target: ") }"

Analysis: Multiple bracket types with partial closing: {[<>]( leaves the round and curly brackets unmatched, requiring ) } to close.

Balanced Sequence (length=4, max_depth=2, bracket_types=6)¶

Input: "[ { } ]"
Target: ""

Analysis: Fully balanced sequence requires no additional closing brackets.

Interleaved Types (length=5, max_depth=3, bracket_types=7)¶

Input: "( { } [ ("
Target: ") ]"

Analysis: Proper bracket ordering: ({}[( - the curly bracket pair is closed, leaving ([ which requires ) ] to close in LIFO order.

High Close Weight (length=4, max_depth=2, close_weight_multiplier=5.0)¶

Input: "( ) [ ]"
Target: ""

Analysis: High closing weight creates more balanced sequences with fewer unclosed brackets.

Low Close Weight (length=4, max_depth=3, close_weight_multiplier=0.5)¶

Input: "( [ { <"
Target: "> } ] )"

Analysis: Low closing weight favors opening brackets, creating deeply nested structures.

Cognitive Skills Tested¶

Core Competencies¶

Stack Processing: Understanding Last-In-First-Out (LIFO) data structure principles
Pattern Matching: Recognizing corresponding opening and closing bracket pairs
Sequential Tracking: Maintaining awareness of bracket order throughout processing
Nesting Recognition: Understanding hierarchical bracket structure relationships
Symbol Differentiation: Distinguishing between different bracket types and their pairing rules

Advanced Skills¶

Working Memory: Tracking multiple open brackets across extended sequences
Systematic Processing: Methodically unwinding nested structures in correct order
Error Detection: Identifying malformed or unbalanced bracket sequences
Structural Visualization: Mental modeling of nested bracket hierarchies

Special Implementation Notes¶

Stack-Based Processing¶

The bracket completion task directly mirrors stack data structure operations:

Push Operation: Adding opening brackets to the stack
Pop Operation: Matching closing brackets remove from stack
Stack Unwinding: Target generation pops remaining brackets in LIFO order
Validation: Ensures only valid bracket sequences are generated

Bracket Type Validation¶

The generator enforces strict bracket type matching:

Type Consistency: Closing brackets must match opening bracket type
Stack Ordering: Only the most recent unmatched opening bracket can be closed
Invalid Sequences: Generator prevents creation of syntactically invalid bracket combinations

Weighted Generation Strategy¶

The close weight multiplier affects sequence characteristics:

Structural Bias: Higher weights create more balanced, less nested sequences
Complexity Control: Lower weights generate more challenging deeply nested structures
Realistic Modeling: Mimics natural bracket usage patterns in programming contexts

Applications¶

This test manifold evaluates capabilities essential for:

Programming Languages: Understanding nested code structures, function calls, and data structures
Mathematical Notation: Parsing complex mathematical expressions with multiple grouping levels
Data Serialization: Processing nested JSON, XML, and other structured data formats
Compiler Design: Lexical analysis and syntax parsing of programming languages
Text Processing: Handling nested markup languages and structured document formats
Algorithm Design: Stack-based algorithm implementation and recursive data structure processing
Code Validation: Detecting syntax errors in bracket-heavy programming constructs

Relationship to Other Manifolds¶

The bracket completion task shares cognitive elements with:

Boolean Expressions: Both require understanding of operator precedence and grouping
Arithmetic Expressions: Similar parenthetical grouping and order of operations
Sequence Tasks: Pattern recognition and systematic processing requirements
Nested Structures: Hierarchical thinking and recursive processing skills