"""
Pattern 75: Tree-of-Thought Pattern

Explores multiple reasoning paths in parallel, evaluates them, and
selects the best solution. Enables deliberate decision making through
search over thought trees.
"""

from typing import Dict, Any, List, Optional
from dataclasses import dataclass, field
from datetime import datetime
import uuid
from langchain_core.prompts import ChatPromptTemplate
from langchain_openai import ChatOpenAI


@dataclass
class ThoughtNode:
    """Node in the thought tree."""
    id: str
    content: str
    parent_id: Optional[str]
    children_ids: List[str] = field(default_factory=list)
    score: float = 0.0
    depth: int = 0
    is_terminal: bool = False
    evaluation: Optional[str] = None


class TreeOfThoughtPattern:
    """
    Tree-of-Thought Pattern - Explores multiple reasoning branches.
    
    Generates multiple thought paths, evaluates them, and searches
    for the best solution through tree exploration.
    """
    
    def __init__(self, model_name: str = "gpt-4", max_depth: int = 3, branches_per_node: int = 3):
        self.llm = ChatOpenAI(model=model_name, temperature=0.9)
        self.evaluator_llm = ChatOpenAI(model=model_name, temperature=0.3)
        self.max_depth = max_depth
        self.branches_per_node = branches_per_node
        self.nodes: Dict[str, ThoughtNode] = {}
        self.root_id: Optional[str] = None
    
    def generate_thoughts(self, problem: str, parent_thought: Optional[str] = None, depth: int = 0) -> List[str]:
        """Generate multiple thought branches."""
        if depth >= self.max_depth:
            return []
        
        prompt = ChatPromptTemplate.from_messages([
            ("system", "You are a creative problem solver. Generate diverse approaches to solve the problem. "
                      "Each approach should be distinct and explore different angles."),
            ("human", f"Problem: {problem}\n"
                     f"{'Current thought: ' + parent_thought if parent_thought else ''}\n\n"
                     f"Generate {self.branches_per_node} different next steps or approaches. "
                     f"Provide them as a numbered list (1. ... 2. ... 3. ...)")
        ])
        
        chain = prompt | self.llm
        response = chain.invoke({})
        content = str(response.content)
        
        # Parse thoughts from response
        thoughts = []
        for line in content.split('\n'):
            line = line.strip()
            if line and (line[0].isdigit() or line.startswith('-') or line.startswith('•')):
                # Remove numbering/bullets
                thought = line.lstrip('0123456789.-•) ').strip()
                if thought:
                    thoughts.append(thought)
        
        return thoughts[:self.branches_per_node]
    
    def evaluate_thought(self, problem: str, thought: str) -> float:
        """Evaluate quality of a thought."""
        prompt = ChatPromptTemplate.from_messages([
            ("system", "You are an expert evaluator. Rate how promising this thought/approach is "
                      "for solving the problem. Consider feasibility, creativity, and likelihood of success."),
            ("human", f"Problem: {problem}\n"
                     f"Thought/Approach: {thought}\n\n"
                     f"Rate this approach from 0.0 (terrible) to 10.0 (excellent). "
                     f"Provide only the numeric rating.")
        ])
        
        chain = prompt | self.evaluator_llm
        response = chain.invoke({})
        content = str(response.content).strip()
        
        # Extract numeric rating
        try:
            # Find first number in response
            import re
            match = re.search(r'(\d+\.?\d*)', content)
            if match:
                score = float(match.group(1))
                return min(10.0, max(0.0, score))
        except:
            pass
        
        return 5.0  # Default middle score
    
    def build_tree(self, problem: str):
        """Build tree of thoughts."""
        # Create root node
        root_id = str(uuid.uuid4())
        self.root_id = root_id
        
        root_node = ThoughtNode(
            id=root_id,
            content=f"Problem: {problem}",
            parent_id=None,
            depth=0
        )
        self.nodes[root_id] = root_node
        
        # Build tree level by level
        nodes_to_expand = [root_node]
        
        while nodes_to_expand:
            current_node = nodes_to_expand.pop(0)
            
            if current_node.depth >= self.max_depth:
                current_node.is_terminal = True
                continue
            
            # Generate child thoughts
            thoughts = self.generate_thoughts(
                problem,
                current_node.content if current_node.depth > 0 else None,
                current_node.depth
            )
            
            for thought in thoughts:
                # Create child node
                child_id = str(uuid.uuid4())
                child_node = ThoughtNode(
                    id=child_id,
                    content=thought,
                    parent_id=current_node.id,
                    depth=current_node.depth + 1
                )
                
                # Evaluate thought
                score = self.evaluate_thought(problem, thought)
                child_node.score = score
                child_node.evaluation = f"Score: {score:.1f}/10.0"
                
                self.nodes[child_id] = child_node
                current_node.children_ids.append(child_id)
                
                # Add to expansion queue if not at max depth
                if child_node.depth  List[ThoughtNode]:
        """Get highest-scoring path from root to leaf."""
        if not self.root_id:
            return []
        
        def find_best_path_recursive(node_id: str) -> tuple[List[ThoughtNode], float]:
            """Recursively find best path."""
            node = self.nodes[node_id]
            
            if not node.children_ids or node.is_terminal:
                return ([node], node.score)
            
            best_path = [node]
            best_score = node.score
            
            for child_id in node.children_ids:
                child_path, child_score = find_best_path_recursive(child_id)
                total_score = node.score + child_score
                
                if total_score > best_score:
                    best_score = total_score
                    best_path = [node] + child_path
            
            return (best_path, best_score)
        
        path, _ = find_best_path_recursive(self.root_id)
        return path
    
    def run(self, problem: str) -> Dict[str, Any]:
        """Execute tree-of-thought reasoning."""
        print(f"   Building thought tree (depth={self.max_depth}, branches={self.branches_per_node})...")
        
        # Build tree
        self.build_tree(problem)
        
        # Find best solution path
        best_path = self.get_best_path()
        
        # Analyze tree
        total_nodes = len(self.nodes)
        terminal_nodes = sum(1 for n in self.nodes.values() if n.is_terminal)
        avg_score = sum(n.score for n in self.nodes.values()) / total_nodes if total_nodes > 0 else 0
        
        return {
            "pattern": "TreeOfThought",
            "problem": problem,
            "total_thoughts": total_nodes,
            "terminal_thoughts": terminal_nodes,
            "average_score": avg_score,
            "best_path_length": len(best_path),
            "best_path": [{"depth": n.depth, "thought": n.content, "score": n.score} for n in best_path],
            "best_solution": best_path[-1].content if best_path else None
        }


# Example usage
if __name__ == "__main__":
    print("=== Tree-of-Thought Pattern Demo ===\n")
    
    # Create pattern
    pattern = TreeOfThoughtPattern(max_depth=2, branches_per_node=3)
    
    # Solve problem
    print("1. Solving problem with tree-of-thought reasoning...")
    problem = "How can we reduce carbon emissions in urban transportation?"
    
    result = pattern.run(problem)
    
    print(f"\n2. Tree Statistics:")
    print(f"   Total Thoughts Explored: {result['total_thoughts']}")
    print(f"   Terminal Thoughts: {result['terminal_thoughts']}")
    print(f"   Average Score: {result['average_score']:.2f}/10.0")
    
    print(f"\n3. Best Reasoning Path:")
    for step in result['best_path']:
        indent = "   " * step['depth']
        print(f"{indent}└─ [{step['score']:.1f}] {step['thought'][:80]}...")
    
    print(f"\n4. Best Solution:")
    print(f"   {result['best_solution']}")
    
    print("\n✓ Tree-of-thought pattern explored multiple reasoning paths!")

    

Agentic Architecture Pattern: Tree Of Thought

Pattern 75: 75 Tree Of Thought – Line-by-Line Explanation

Overview

Pattern 75: Tree-of-Thought Pattern

Explores multiple reasoning paths in parallel, evaluates them, and selects the best solution. Enables deliberate decision making through search over thought trees.

Code Structure Analysis

File Information

• Pattern Number: 75
• Pattern Name: 75 Tree Of Thought
• File Path: patterns\execution_control\75_tree_of_thought.py
• Total Lines: 239

Detailed Code Explanation

Module Docstring

"""
Pattern 75: Tree-of-Thought Pattern

Explores multiple reasoning paths in parallel, evaluates them, and
selects the best solution. Enables deliberate decision making through
search over thought trees.
"""

Explanation: This module docstring describes the purpose and key features of the 75 Tree Of Thought pattern.

Imports Section

from typing import Dict, Any, List, Optional
from dataclasses import dataclass, field
from datetime import datetime
import uuid
from langchain_core.prompts import ChatPromptTemplate
from langchain_openai import ChatOpenAI
            import re  # First 20 imports shown

Explanation: The module imports necessary dependencies: – from typing import Dict, Any, List, Optional: Type hints for better code documentation – from dataclasses import dataclass, field: Data class decorators for clean data structures – from datetime import datetime: Date and time utilities – from langchain_core.prompts import ChatPromptTemplate: LangChain framework integration – from langchain_openai import ChatOpenAI: LangChain framework integration

Classes

ThoughtNode (Line 18)

Description: Node in the thought tree.

TreeOfThoughtPattern (Line 30)

Description: Tree-of-Thought Pattern – Explores multiple reasoning branches.

Generates multiple thought paths, evaluates them, and searches for the best solution through tree exploration.

Methods:

__init__ (Line 38)

def __init__(self, model_name, max_depth, branches_per_node):
    """No method docstring."""

Purpose: No method docstring.

Parameters: – self: Instance reference – model_name: LLM model to use (e.g., “gpt-4”) – max_depth: Parameter for max_depth – branches_per_node: Parameter for branches_per_node

generate_thoughts (Line 46)

def generate_thoughts(self, problem, parent_thought, depth):
    """Generate multiple thought branches."""

Purpose: Generate multiple thought branches.

Parameters: – self: Instance reference – problem: Parameter for problem – parent_thought: Parameter for parent_thought – depth: Parameter for depth

evaluate_thought (Line 76)

def evaluate_thought(self, problem, thought):
    """Evaluate quality of a thought."""

Purpose: Evaluate quality of a thought.

Parameters: – self: Instance reference – problem: Parameter for problem – thought: Parameter for thought

build_tree (Line 104)

def build_tree(self, problem):
    """Build tree of thoughts."""

Purpose: Build tree of thoughts.

Parameters: – self: Instance reference – problem: Parameter for problem

get_best_path (Line 157)

def get_best_path(self):
    """Get highest-scoring path from root to leaf."""

Purpose: Get highest-scoring path from root to leaf.

Parameters: – self: Instance reference

run (Line 185)

def run(self, problem):
    """Execute tree-of-thought reasoning."""

Purpose: Execute tree-of-thought reasoning.

Parameters: – self: Instance reference – problem: Parameter for problem

Design Patterns Used

• Strategy Pattern: Different execution strategies for various scenarios
• State Pattern: Managing different states in the workflow
• Chain of Responsibility: Sequential processing through workflow nodes
• Observer Pattern: Tracking and monitoring pattern execution
• Factory Pattern: Creating instances with proper configuration

Usage Example

# Initialize the pattern
pattern = ThoughtNode(name="example", model_name="gpt-4")

# Configure and execute
result = pattern.execute(data={"key": "value"})

# Check results
print(result)

Key Concepts

• LLM Integration: Uses LangChain/OpenAI for intelligent decision-making
• Workflow Orchestration: LangGraph manages execution flow through nodes
• State Management: TypedDict defines workflow state structure
• Error Handling: Comprehensive error handling and fallback mechanisms
• Extensibility: Designed for easy customization and extension

Extension Points

This pattern can be extended by: 1. Adding custom workflow nodes 2. Implementing additional validation logic 3. Integrating with external services 4. Customizing LLM prompts and responses 5. Adding monitoring and logging capabilities