submodules/rlp/ASCII_PARSER_IMPLEMENTATION_GUIDE_new.md

ASCII Parser Implementation Guide for Bridges Puzzles

This document provides a comprehensive guide to implementing ASCII parsers for puzzle games, using the Bridges puzzle as a reference implementation. This guide can be used to create similar parsers for other puzzles (undead, loopy, etc.).

Table of Contents

1. Overview
2. Architecture
3. Implementation Structure
4. Key Components
5. Testing Strategy
6. Gotchas and Lessons Learned
7. Integration Points
8. Step-by-Step Implementation Checklist

---

Overview

Purpose

The ASCII parser converts ASCII text representations of puzzle states into Python dictionaries that match the format produced by get_puzzle_state_<puzzle_name>() functions. This enables:

• Verification: Check if an ASCII state (from LLM or other sources) is solved
• State Loading: Load arbitrary puzzle states from ASCII text
• Round-trip Testing: Verify ASCII → state dict → load → format → ASCII works correctly
• Integration: Use ASCII states with existing load_state_dict functionality

Pipeline

The complete pipeline follows this flow:

ASCII Text → Parse (Python) → State Dict → Load (C) → Game State → Verify/Format

1. Parse ASCII (Python): Convert ASCII text to state dictionary
2. Load State Dict (C): Use existing load_state_dict_<puzzle>() function
3. Verify/Format (C): Check completed flag or format back to ASCII

---

Architecture

Three-Layer Design

1. Python Parser Layer (rlp/ascii_parser.py)

   • Pure Python implementation
   • Parses ASCII text into state dictionaries
   • No C dependencies for parsing logic

2. State Dict Format Layer (rlp/specific_api.py)

   • Must match get_puzzle_state_<puzzle>() format exactly
   • Defines the canonical state representation

3. C Loading Layer (existing load_state_dict_<puzzle>())

   • Reconstructs C game state from state dict
   • Computes derived fields (possibles, max arrays, etc.)
   • Validates and checks if solved

Key Design Principle

The parser only needs to produce the minimal canonical fields required for reconstruction. The C code will:

• Recompute derived arrays (possibles, max arrays, etc.)
• Rebuild internal structures (island adjacencies, etc.)
• Validate the state and set completed/solved flags

---

Implementation Structure

File Organization

rlp/
  ascii_parser.py          # Main parser module (puzzle-specific functions)
  specific_api.py          # State dict format definitions
  puzzle.py                # Puzzle class (load_state_dict method)
verifier.py                # Verification script using new pipeline
test_ascii_parser.py       # Parser-specific tests
test_verifier.py           # Integration tests

Parser Function Signature

def parse_ascii_<puzzle_name>(ascii_text: str) -> dict:
    """
    Parse ASCII text representation of a <puzzle_name> puzzle and return a state dict.
    
    Args:
        ascii_text: The ASCII representation of the puzzle state
        
    Returns:
        dict: State dictionary matching get_puzzle_state_<puzzle_name> format
        
    Raises:
        ValueError: If the ASCII text is invalid or empty
    """

State Dict Format

The parser must produce a dictionary that exactly matches the format from get_puzzle_state_<puzzle_name>(). For bridges, this includes:

{
    "w": int,                    # Width
    "h": int,                    # Height
    "completed": bool,           # Will be computed by C code (set to False)
    "solved": bool,              # Will be computed by C code (set to False)
    "grid": List[int],           # Grid flags array (w*h elements)
    "lines": List[int],          # Lines array (w*h elements)
    "islands": List[dict],       # Island structures
    "n_islands": int,            # Number of islands
    "n_islands_alloc": int,      # Allocation size (same as n_islands for parsed)
    "params": {                  # Minimal params (only for verification/printing)
        "w": int,
        "h": int,
        "maxb": int,             # Default: 2 for bridges
        "allowloops": bool,      # Default: True for bridges
    },
    # Derived arrays - initialized to zeros, computed by C code
    "wha": List[int],            # w*h elements
    "possv": List[int],          # w*h elements
    "possh": List[int],          # w*h elements
    "maxv": List[int],           # w*h elements
    "maxh": List[int],           # w*h elements
}

---

Key Components

1. ASCII Format Understanding

For Bridges:

• Islands: '0'-'9' (count 0-9) or 'A'-'G' (count 10-16)
• Vertical bridges: '|' (single), '"' (double)
• Horizontal bridges: '-' (single), '=' (double)
• Empty cells: '.'

Key Insight: Study the C game_text_format() function to understand the exact ASCII format. This is the inverse operation.

2. Dimension Inference

# First pass: infer dimensions
lines = ascii_text.strip().split('\n')
h = len(lines)
max_w = max(len(line.rstrip()) for line in lines)
w = max_w

Important: Handle variable line lengths gracefully. Shorter lines are treated as empty cells.

3. Grid Flags

Define constants matching the C definitions:

# Grid flags matching <puzzle>.c definitions
G_ISLAND = 0x0001
G_LINEV = 0x0002   # contains a vertical line
G_LINEH = 0x0004   # contains a horizontal line

Critical: These must match the C #define values exactly.

4. State Dict Construction

# Initialize arrays
wh = w * h
grid = [0] * wh
lines_array = [0] * wh
islands = []

# Parse each cell
for y, line in enumerate(lines):
    for x in range(w):
        c = stripped[x] if x < len(stripped) else None
        idx = y * w + x
        
        if c is island_char:
            grid[idx] |= G_ISLAND
            islands.append({"x": x, "y": y, "count": count})
        elif c is line_char:
            grid[idx] |= G_LINE_FLAG
            lines_array[idx] = line_count  # 1 or 2
        # Empty cells remain 0

5. Minimal Params

Only include params needed for verification/printing:

"params": {
    "w": w,
    "h": h,
    # Only include fields needed for load_state_dict
    # Omit generation params: islands, expansion, difficulty
}

---

Testing Strategy

1. Unit Tests (Parser-Specific)

File: test_ascii_parser.py

Test cases:

• Problem states (initial puzzle, no solution)
• Solution states (complete solution with all elements)
• Edge cases: Empty states, single cell, maximum size
• Special characters: Letter islands (A-G), double bridges
• Round-trip: ASCII → parse → load → format → ASCII (must match)

2. Integration Tests (Verifier)

File: test_verifier.py

Test cases:

• CSV predictions: Verify problems return solved=False, solutions return solved=True
• State comparison: Compare two similar ASCII states
• Large-scale testing: Test all problems/solutions from dataset

3. Round-Trip Testing

The most important test pattern:

# 1. Get ASCII from a puzzle state
ascii_original = game.text_format(state).decode('utf-8')

# 2. Parse with Python parser
state_dict = parse_ascii_bridges(ascii_original)

# 3. Load into C
loaded_state_ptr = puzzle.load_state_dict(state_dict)

# 4. Format back to ASCII
ascii_loaded = game.text_format(loaded_state_ptr).decode('utf-8')

# 5. Compare (should match exactly)
assert ascii_original.strip() == ascii_loaded.strip()

4. Structural Validity (Optional but Recommended)

For puzzles with connectivity requirements (like bridges), add a structural validity check:

def check_<puzzle>_structural_validity(ascii_text: str) -> bool:
    """
    Check structural validity before parsing.
    
    Validates:
    - Lines are contiguous (no breaks)
    - Clues haven't been modified
    - Basic sanity checks
    """

This catches common errors early (broken lines, modified clues, etc.).

---

Gotchas and Lessons Learned

1. Grid Flags Must Match C Exactly

Problem: Grid flag values must match C #define values exactly.

Solution: Copy the exact hex values from the C source file.

# From bridges.c:
#define G_ISLAND        0x0001
#define G_LINEV         0x0002
#define G_LINEH         0x0004

# In Python:
G_ISLAND = 0x0001  # Must match exactly
G_LINEV = 0x0002
G_LINEH = 0x0004

2. Derived Arrays Can Be Zeros

Problem: Don't try to compute derived arrays (possibles, max arrays) in Python.

Solution: Initialize to zeros. The C code will recompute them:

# Derived arrays - initialized to zeros, will be computed by C code
"wha": [0] * wh,
"possv": [0] * wh,
"possh": [0] * wh,
"maxv": [0] * wh,
"maxh": [0] * wh,

3. Only Include Canonical Fields

Problem: Including non-canonical fields (generation params, solver flags) causes issues.

Solution: Only include fields needed for reconstruction. Omit:

• Generation params: islands, expansion, difficulty
• Solver flags: G_SWEEP, G_WARN (these are computed by C)
• Allocation details: n_islands_alloc can be set to n_islands for parsed states

4. Handle Variable Line Lengths

Problem: ASCII text may have lines of different lengths.

Solution: Use maximum width, treat shorter lines as having empty cells:

max_w = max(len(line.rstrip()) for line in lines)
# For cells beyond line length, treat as empty (already 0)

5. Memory Management

Problem: Must free loaded states to avoid memory leaks.

Solution: Always use try/finally:

loaded_state_ptr = puzzle.load_state_dict(state_dict)
try:
    # Use the state
    is_solved = loaded_state_ptr.contents.completed
finally:
    if loaded_state_ptr:
        free_game_func(loaded_state_ptr)

6. State Dict Format Must Match Exactly

Problem: Even small differences in state dict format cause failures.

Solution:

• Copy the exact structure from get_puzzle_state_<puzzle>()
• Use the same field names and types
• Test with round-trip verification

7. Letter Islands (A-G)

Problem: Islands can have counts 10-16 represented as letters.

Solution: Handle both digits and letters:

if c >= '0' and c <= '9':
    count = ord(c) - ord('0')
elif c >= 'A' and c <= 'G':
    count = (ord(c) - ord('A')) + 10

8. Double Bridges

Problem: Double bridges use different characters (" for vertical, = for horizontal).

Solution: Check for both single and double bridge characters:

elif c == '|':
    lines_array[idx] = 1
elif c == '"':
    lines_array[idx] = 2
elif c == '-':
    lines_array[idx] = 1
elif c == '=':
    lines_array[idx] = 2

9. Empty Cells vs Missing Cells

Problem: Need to distinguish between empty cells (.) and cells beyond line length.

Solution: Both are treated the same (grid=0, lines=0), but handle bounds checking:

if x >= len(stripped):
    continue  # Beyond line length, already initialized to 0
elif c == '.':
    pass  # Empty cell, already initialized to 0

10. Testing with Real Data

Problem: Unit tests may not catch all edge cases.

Solution: Test with real dataset:

• Parse all problems and solutions from CSV
• Verify round-trip works for all
• Check that problems are unsolved and solutions are solved

---

Integration Points

1. Verifier Script

The verifier uses the parser in a complete pipeline:

def verify_ascii_state(puzzle, ascii_text: str) -> str:
    # 1. Optional: Check structural validity
    if not check_bridges_structural_validity(ascii_text):
        return "NOT SOLVED"
    
    # 2. Parse ASCII
    state_dict = parse_ascii_bridges(ascii_text)
    
    # 3. Load state dict
    loaded_state_ptr = puzzle.load_state_dict(state_dict)
    
    # 4. Check completed flag
    is_solved = loaded_state_ptr.contents.completed
    return "SOLVED" if is_solved else "NOT SOLVED"

2. Load State Dict Function

The parser output must be compatible with existing load_state_dict_<puzzle>():

# In rlp/specific_api.py
def load_state_dict_bridges(state_dict: dict, lib: c.PyDLL) -> c.POINTER(GameState):
    # Validates required fields
    # Creates C structures
    # Calls bridges_state_from_repr()

3. Puzzle Class

The Puzzle class provides the interface:

# In rlp/puzzle.py
puzzle = Puzzle('bridges', arg='5x5de', headless=True)
puzzle.new_game()
state_dict = parse_ascii_bridges(ascii_text)
loaded_state = puzzle.load_state_dict(state_dict)

---

Step-by-Step Implementation Checklist

Phase 1: Research and Understanding

• Study the C game_text_format() function to understand ASCII format
• Review get_puzzle_state_<puzzle>() to understand state dict format
• Identify all ASCII characters and their meanings
• Identify grid flags and their values from C source
• Understand the puzzle's state structure

Phase 2: Parser Implementation

• Create rlp/ascii_parser.py (or add to existing file)
• Define grid flag constants matching C
• Implement dimension inference
• Implement cell-by-cell parsing
• Build grid array with correct flags
• Build lines/connections array
• Extract puzzle-specific structures (islands, etc.)
• Construct state dict matching get_puzzle_state_<puzzle>() format
• Add error handling and validation

Phase 3: Structural Validity (Optional)

• Implement structural validity checker
• Validate connectivity (if applicable)
• Validate clues haven't been modified
• Add sanity checks

Phase 4: Testing

• Create test_ascii_parser.py
• Test problem states (unsolved)
• Test solution states (solved)
• Test edge cases (empty, single cell, max size)
• Test special characters/features
• Implement round-trip tests
• Test with real dataset (CSV)

Phase 5: Integration

• Update verifier.py to use new parser
• Create/update test_verifier.py
• Test CSV predictions (problems vs solutions)
• Verify memory management (no leaks)

Phase 6: Documentation

• Document ASCII format
• Document parser function
• Document state dict format
• Add examples and usage

---

Example: Bridges Parser Structure

# rlp/ascii_parser.py

# 1. Grid flags (must match C)
G_ISLAND = 0x0001
G_LINEV = 0x0002
G_LINEH = 0x0004

# 2. Structural validity (optional)
def check_bridges_structural_validity(ascii_text: str) -> bool:
    # Validates line continuity, clue integrity, etc.
    pass

# 3. Main parser
def parse_ascii_bridges(ascii_text: str) -> dict:
    # Dimension inference
    lines = ascii_text.strip().split('\n')
    h = len(lines)
    w = max(len(line.rstrip()) for line in lines)
    
    # Initialize arrays
    wh = w * h
    grid = [0] * wh
    lines_array = [0] * wh
    islands = []
    
    # Parse cells
    for y, line in enumerate(lines):
        for x in range(w):
            c = line[x] if x < len(line.rstrip()) else None
            idx = y * w + x
            
            if c in '0-9A-G':  # Island
                grid[idx] |= G_ISLAND
                islands.append({"x": x, "y": y, "count": ...})
            elif c in '|"':  # Vertical line
                grid[idx] |= G_LINEV
                lines_array[idx] = 2 if c == '"' else 1
            elif c in '-=':  # Horizontal line
                grid[idx] |= G_LINEH
                lines_array[idx] = 2 if c == '=' else 1
    
    # Build state dict
    return {
        "w": w,
        "h": h,
        "grid": grid,
        "lines": lines_array,
        "islands": islands,
        # ... rest of fields
    }

---

Key Takeaways

1. Study the C code first: Understand game_text_format() and state structure
2. Match formats exactly: State dict must match get_puzzle_state_<puzzle>() exactly
3. Minimal canonical fields: Only include what's needed for reconstruction
4. Let C compute derived fields: Initialize derived arrays to zeros
5. Round-trip testing is critical: ASCII → parse → load → format → ASCII must match
6. Handle edge cases: Variable line lengths, special characters, empty states
7. Memory management: Always free loaded states
8. Test with real data: Use actual problems and solutions from datasets

---

References

• Bridges parser: rlp/ascii_parser.py
• State dict format: rlp/specific_api.py (lines 2576-2585)
• C text format: puzzles/bridges.c (lines 234-266)
• C state structure: puzzles/bridges.c (lines 177-189)
• Load state dict: rlp/specific_api.py (lines 2588-2686)
• Tests: test_ascii_parser.py, test_verifier.py
• Verifier: verifier.py