synth/games/tasks/dyck_language

Dyck Language (Bracket Closing) Game

Task Description

This is a game about bracket closing, requiring the model to complete an incomplete bracket sequence to make it a valid bracket sequence.

Game Rules

1. The game uses 4 types of bracket pairs:

   • ()
   • []
   • {}
   • <>

2. Generation rules:

   • Randomly generate a sequence containing n_types of brackets
   • If total_length is greater than 0, the total length must equal total_length
   • If total_length is 0, the total length is randomly between 5×n_types and 10×n_types
   • If to_fill_length is greater than 0, remove the last to_fill_length characters
   • If to_fill_length is 0, remove the last random 20%~50% length of characters
   • The removed portion must be less than or equal to half of the total length

3. Bracket matching rules:

   • Each left bracket must have a corresponding right bracket
   • Brackets must be closed in the correct order
   • The supplemented part needs to meet the minimum requirement, i.e., cannot add extra bracket pairs

Example

Input:

{[[[{[]}]]

Output:

{[[[{[]}]]]}

Usage

1. Use run.sh to generate multiple parameter groups of data in batch:

# Generate 3 different parameter groups of data, 1000 entries each
./games/tasks/dyck_language/run.sh

2. Manually specify parameters to generate data:

python -m games.tasks.dyck_language.scripts.dyck_language --num_of_data 100 --n_types 3 --total_length 20 --to_fill_length 4

Parameter Description

• num_of_data: Number of samples to generate
• max_attempts: Maximum number of attempts per sample
• n_types: Number of bracket types to use (1-6)
• total_length: Total length of the complete sequence, if 0 then randomly generated
• to_fill_length: Length to be filled, if 0 then randomly generated
• nesting_depth: Nesting depth, if 0 then no limit

Output Format

The model needs to directly output the completed full bracket sequence, without including other text or code block formats. For example:

Input sequence: ((()[ Model should answer: ((()[]))

Implementation Details

1. Generation algorithm:

   • Use a stack to generate valid bracket sequences
   • Use backtracking algorithm to ensure non-repetitive sequences
   • Generate sequences by randomly choosing left or right brackets

2. Validation algorithm:

   • Use a stack to verify the validity of bracket sequences
   • Check if each left bracket has a corresponding right bracket
   • Ensure brackets are closed in the correct order

3. Answer extraction:

   • Prioritize directly extracting valid bracket sequences from the text
   • Support answer extraction in various Chinese and English formats
   • Handle various special characters and formats
   • Backward compatible with Python code block format answers

Test Cases

1. Generation tests:

   • Test basic generation functionality
   • Test generation with different parameter combinations
   • Test sequence validity
   • Test sequence non-repetitiveness

2. Validation tests:

   • Test validation of correct answers
   • Test validation of incorrect answers
   • Test different answer formats
   • Test edge cases

3. Answer extraction tests:

   • Test extraction of Chinese format
   • Test extraction of English format
   • Test handling of special characters
   • Test handling of multi-line text

Batch Data Generation Description

The run.sh script has been updated to generate multiple parameter groups of data in batch. By default, it will generate data for the following three parameter groups, 1000 entries each:

1. n_types=2, total_length=10, to_fill_length=1
2. n_types=3, total_length=15, to_fill_length=3
3. n_types=4, total_length=20, to_fill_length=5