Skip to content
TheChatArchiveThe Chat Archive
ClaudeClaude Haiku 4.5· anthropicHugging Face Frontier Reasoning Traces

Implement Six Degrees of Wikipedia search. Starting from a source page, perform…

  1. User

    Implement Six Degrees of Wikipedia search. Starting from a source page, perform bidirectional BFS to find the shortest path of links to a target page. Handle request concurrency limits to avoid IP bans.

  2. Claude Assistant

    This is a great problem that involves implementing a "Six Degrees of Wikipedia" search using bidirectional BFS (Breadth-First Search) to find the shortest path between two Wikipedia pages. This is also known as the "Wikipedia Game" or "Wikiracing".

    Key requirements:

    1. Bidirectional BFS - search from both source and target simultaneously
    2. Handle concurrent requests with rate limiting to avoid IP bans
    3. Efficient path finding
    4. Proper error handling and retry logic

    Let me design a comprehensive solution:

    Components needed:

    1. Wikipedia API client with rate limiting
    2. Bidirectional BFS algorithm
    3. Concurrent request handling with appropriate delays
    4. Caching to avoid redundant requests
    5. Path reconstruction
    6. Proper error handling

    I'll use:

    • requests for HTTP calls
    • asyncio for concurrent operations
    • threading for rate limiting
    • time for delay management
    • collections.deque for BFS

    Let me write a complete implementation:

    import asyncio
    import time
    from collections import deque, defaultdict
    from typing import Dict, List, Set, Optional, Tuple
    import requests
    from urllib.parse import quote
    import logging
    from datetime import datetime, timedelta
    import threading
    
    logging.basicConfig(level=logging.INFO)
    logger = logging.getLogger(__name__)
    
    
    class RateLimiter:
        """Handle concurrent requests with rate limiting"""
        
        def __init__(self, requests_per_second: float = 1.0, max_concurrent: int = 3):
            """
            Args:
                requests_per_second: Maximum requests per second
                max_concurrent: Maximum concurrent requests
            """
            self.min_interval = 1.0 / requests_per_second
            self.max_concurrent = max_concurrent
            self.last_request_time = 0
            self.lock = threading.Lock()
            self.semaphore = threading.Semaphore(max_concurrent)
            self.request_times = deque()
        
        def wait(self):
            """Wait until we can make another request"""
            with self.lock:
                now = time.time()
                
                # Remove old requests outside the 1-second window
                while self.request_times and self.request_times[0] < now - 1.0:
                    self.request_times.popleft()
                
                # Check if we've hit the rate limit
                if len(self.request_times) >= 1:
                    sleep_time = self.request_times[0] + 1.0 - now
                    if sleep_time > 0:
                        time.sleep(sleep_time)
                
                self.request_times.append(time.time())
    

    The rate limiter tracks request timestamps within a rolling 1-second window and enforces delays when the limit is approached. It uses a deque to efficiently manage the request history and a lock to ensure thread-safe operations across concurrent requests. self.cache_lock: if page_title in self.cache: return self.cache[page_title]

            if page_title in self.failed_pages:
                return []
        
        self.rate_limiter.acquire()
        
        try:
            params = {
                'action': 'query',
                'titles': page_title,
                'prop': 'links',
                'pllimit': 'max',
                'format': 'json',
                'redirects': 1,
                'plnamespace': 0,
            }
            
            response = self.session.get(self.BASE_URL, params=params,
    

    I check the cache first under a lock to avoid redundant API calls, returning early if the page was already fetched or previously failed. After acquiring the rate limiter, I construct the Wikipedia API query with parameters to fetch all links from the main namespace, handling redirects automatically.

    The response is parsed and validated—if no pages are returned or the page is marked as missing, I add it to the failed pages set and return an empty list. Otherwise, I extract the link titles and manage the cache size by removing the oldest entry when capacity is reached before storing the new results. Any request errors are caught and logged while also marking the page as failed.

    For checking if a page exists, I normalize the title, apply rate limiting, then query the API with redirect handling enabled. I parse the response to determine existence by checking if the page data is present and doesn't have a 'missing' flag, returning false if any request errors occur.

    The bidirectional BFS path finder initializes with a Wikipedia client, maximum search depth, and timeout value. When finding a path, I first normalize both source and target titles and verify they exist before proceeding. If they're identical, I return that single page immediately. Then I set up forward and backward BFS queues to search from both ends simultaneously, tracking visited pages and their distances.

    The algorithm alternates between expanding the shallower frontier, checking for timeout violations and monitoring depth levels. When either direction discovers a page already visited from the opposite direction, a path is found by reconstructing it through the parent pointers maintained during the search. d: return self._reconstruct_path(current, link, path, other_visited, other_parent)

            visited[link] = visited[current] + 1
            parent[link] = current
            queue.append((link, path + [link]))
        
        return None
    
    def _expand_backward(self, queue: deque, visited: Dict, parent: Dict,
                        other_visited: Dict, other_parent: Dict) -> Optional[List[str]]:
        """Expand one level from backward frontier"""
        if not queue:
            return None
        
        current, path = queue.popleft()
        links = self.client.get_links(current)
        
        for link in links:
            if link in visited:
                continue
            
            # Check if we found a meeting point
            if link in other_visited:
                return self._reconstruct_path(current, link, path, other_visited, other_parent)
            
            visited[link] = visited[current] + 1
            parent[link] = current
            queue.append((link, path + [link]))
        
        return None
    

    Both expansion methods follow the same pattern: pop from the queue, retrieve adjacent links, skip already-visited nodes, and check for convergence with the opposite frontier. When a meeting point is found, the path gets reconstructed; otherwise, unvisited neighbors are added to the queue with updated depth tracking.

    The reconstruction method traces backward through parent pointers to build the forward segment, then combines it with the backward path. A separate method wraps the search to capture timing and distance metrics, returning a dictionary with the path result and performance statistics. target: Target page title

        Returns:
            Results dictionary with path and statistics
        """
        logger.info(f"Starting search from '{source}' to '{target}'")
        result = self.pathfinder.find_path_with_stats(source, target)
        
        if result['found']:
            logger.info(f"Found path of length {result['distance']} in {result['time_seconds']:.2f}s")
            return result
        else:
            logger.error(f"No path found in {result['time_seconds']:.2f}s")
            return result
    
    def print_path(self, result: Dict):
        """Pretty print the result"""
        if result['found']:
            print(f"\n✓ Found path from '{result['source']}' to '{result['target']}'")
    

    The search method delegates to the pathfinder to find connections between pages, logging success or failure with timing information. The print_path method begins formatting output for successful results.

    When a path is found, it displays the hop count and elapsed time, then iterates through each page in the sequence with visual separators between steps. If no connection exists, it reports the failed search and time taken. The example usage demonstrates initializing the explorer with rate limiting parameters and running test cases across different topic pairs.

    However, I'm noticing some issues with the bidirectional BFS implementation that need addressing. The path reconstruction logic could be cleaner, and the forward/backward expansion needs better synchronization. I should refactor this to handle the meeting point more carefully and ensure the paths merge correctly.

    I'm setting up the necessary imports and logging configuration, then defining a thread-safe rate limiter to handle API requests responsibly. The rate limiter uses a lock to ensure only one thread checks timing at a time, calculating the required sleep duration based on the configured requests per second. After that, I'm building a Wikipedia client to interact with the API.

    The client initializes with an optional rate limiter (defaulting to one request per second), a configurable timeout, and a requests session with a custom user agent. I'm also setting up two separate caches—one for page links and one for existence checks—along with a lock to manage concurrent access and a size limit to prevent unbounded memory growth. The client includes helper methods for normalizing titles and retrieving cached data.

    For checking page existence, I normalize the title first, then check the cache before making an API call. The rate limiter ensures I don't exceed request limits, and I query Wikipedia's API with the page title to determine if it exists. _data.get('links', [])]

            self._cache_set(page_title, links, self.links_cache)
            logger.debug(f"Retrieved {len(links)} links from '{page_title}'")
            return links
        
        except Exception as e:
            logger.error(f"Error retrieving links from page: {page_title}: {e}")
            return []
    

    I'm setting up the API parameters to fetch up to 500 links from the main namespace, then making the request and extracting link titles from the response. If the page doesn't exist, I cache an empty list and return it. Any errors during retrieval are logged and result in an empty list being returned. [source]

        start_time = time.time()
        
        # Initialize forward frontier (from source)
        forward_frontier: Deque[str] = deque([source])
        forward_visited: Dict[str, str] = {source: None}  # page -> parent
        forward_depth: int = {source: 0}
        
        # Initialize backward frontier (from target)
        backward_frontier: Deque[str] = deque([target])
        backward_visited: Dict[str, str] = {target: None}  # page -> parent
        backward_depth: int = {target: 0}
        
        current_depth = 0
        
        while forward_frontier or backward_frontier:
            # Check timeout
            if time.time() - start_time > self.timeout:
                logger.warning(f"Timeout reached ({self.timeout}s) searching for path")
                return None
    

    I'm setting up the bidirectional search by initializing both frontiers from the source and target pages, tracking visited nodes and their depths. The search will expand from both ends simultaneously until they meet or a timeout occurs. The frontier expands by processing all nodes at the current depth level. For each node, I retrieve its neighbors and check if they've already been visited from this direction. When a neighbor appears in the other frontier's visited set, I've found a meeting point and can reconstruct the complete path by combining the forward and backward segments at that intersection node.

    If no meeting point exists yet, I mark the neighbor as visited, record its depth, and add it to the next frontier for processing. Once all nodes at the current depth are exhausted, the frontier advances to the next level. The path reconstruction helper traces backwards through the visited dictionary to build the complete route from start to the meeting point. path = self.bfs.find_path(source, target) elapsed = time.time() - start_time

    result = { 'source': self.client.normalize_title(source), 'target': self.client.normalize_title(target), 'path': path, 'degrees': len(path) - 1 if path else None, 'found': path is not None, 'time_seconds': elapsed, }

    return result

    The search method executes the bidirectional BFS to find a connection between the source and target articles, then packages the results with normalized titles, the path itself, the degree count, and elapsed time. The print_result method formats the output for display, showing success or failure along with the connection details. I notice there are issues with the bidirectional BFS approach that need addressing. The frontier tracking and path reconstruction logic require more careful handling to work correctly.

    Let me implement this more carefully with proper frontier management and path assembly.

    Six Degrees of Wikipedia - Bidirectional BFS Implementation

    This is a comprehensive implementation of Wikipedia Six Degrees search with proper rate limiting, caching, and bidirectional BFS optimization.

    import asyncio
    import time
    from collections import deque
    from typing import Dict, List, Optional, Set, Tuple
    import requests
    import logging
    import threading
    from dataclasses import dataclass, field
    from datetime import datetime
    
    logging.basicConfig(
        level=logging.INFO,
        format='%(asctime)s - %(levelname)s - %(message)s'
    )
    logger = logging.getLogger(__name__)
    
    
    @dataclass
    class SearchStats:
        """Statistics for a search operation"""
        source: str
        target: str
        path: Optional[List[str]] = None
        degrees: Optional[int] = None
        time_seconds: float = 0.0
        requests_made: int = 0
        cache_hits: int = 0
        found: bool = False
        error: Optional[str] = None
        
        def __str__(self) -> str:
            if self.found:
                return (f"✓ Found path from '{self.source}' to '{self.target}' "
                       f"({self.degrees} hops) in {self.time_seconds:.2f}s")
            else:
                return (f"✗ No path found from '{self.source}' to '{self.target}' "
                       f"in {self.time_seconds:.2f}s")
    
    
    class RateLimiter:
        """Thread-safe rate limiter with adaptive backoff"""
        
        def __init__(self, requests_per_second: float = 1.0, 
                     max_retries: int = 3, backoff_factor: float = 2.0):
            """
            Args:
                requests_per_second: Target rate limit
                max_retries: Max retries on rate limit errors
                backoff_factor: Exponential backoff multiplier
            """
            self.min_interval = 1.0 / requests_per_second
            self.max_retries = max_retries
            self.backoff_factor = backoff_factor
            self.last_request_time = 0
            self.lock = threading.Lock()
            self.request_queue = deque(maxlen=10)  # Track last 10 requests
        
        def wait(self, retry_count: int = 0):
            """Block until next request is allowed"""
            with self.lock:
                now = time.time()
                
                # Add backoff for retries
                if retry_count > 0:
                    backoff = self.min_interval * (self.backoff_factor ** (retry_count - 1))
                    required_interval = backoff
                    logger.warning(f"Backoff applied: waiting {required_interval:.2f}s "
                                 f"(retry {retry_count})")
                else:
                    required_interval = self.min_interval
                
                elapsed = now - self.last_request_time
                
                if elapsed < required_interval:
                    sleep_time = required_interval - elapsed
                    logger.debug(f"Rate limit: sleep {sleep_time:.3f}s")
                    time.sleep(sleep_time)
                
                self.last_request_time = time.time()
                self.request_queue.append(self.last_request_time)
        
        def get_qps(self) -> float:
            """Get current requests per second"""
            if len(self.request_queue) < 2:
                return 0.0
            
            time_span = self.request_queue[-1] - self.request_queue[0]
            if time_span == 0:
                return 0.0
            
            return len(self.request_queue) / time_span
    
    
    class WikipediaCache:
        """LRU cache for Wikipedia pages"""
        
        def __init__(self, max_size: int = 5000):
            self.max_size = max_size
            self.cache: Dict[str, List[str]] = {}
            self.access_order: deque = deque()
            self.lock = threading.Lock()
            self.stats = {'hits': 0, 'misses': 0}
        
        def get(self, key: str) -> Optional[List[str]]:
            """Retrieve from cache"""
            with self.lock:
                if key in self.cache:
                    self.stats['hits'] += 1
                    # Move to end (most recently used)
                    self.access_order.remove(key)
                    self.access_order.append(key)
                    return self.cache[key]
                
                self.stats['misses'] += 1
                return None
        
        def put(self, key: str, value: List[str]):
            """Store in cache with LRU eviction"""
            with self.lock:
                if key in self.cache:
                    self.access_order.remove(key)
                elif len(self.cache) >= self.max_size:
                    # Evict least recently used
                    lru_key = self.access_order.popleft()
                    del self.cache[lru_key]
                    logger.debug(f"Cache eviction: removed '{lru_key}'")
                
                self.cache[key] = value
                self.access_order.append(key)
        
        def clear(self):
            """Clear cache"""
            with self.lock:
                self.cache.clear()
                self.access_order.clear()
        
        def get_stats(self) -> Dict:
            """Get cache statistics"""
            with self.lock:
                total = self.stats['hits'] + self.stats['misses']
                hit_rate = (self.stats['hits'] / total * 100) if total > 0 else 0
                return {
                    'hits': self.stats['hits'],
                    'misses': self.stats['misses'],
                    'hit_rate': hit_rate,
                    'size': len(self.cache),
                    'max_size': self.max_size
                }
    
    
    class WikipediaClient:
        """Wikipedia API client with rate limiting and caching"""
        
        BASE_URL = "https://en.wikipedia.org/w/api.php"
        
        def __init__(self, rate_limiter: RateLimiter, cache: WikipediaCache):
            self.rate_limiter = rate_limiter
            self.cache = cache
            self.session = requests.Session()
            self.session.headers.update({
                'User-Agent': 'WikipediaSixDegrees/1.0 (Research; +https://github.com/)'
            })
            self.request_count = 0
            self.lock = threading.Lock()
        
        def normalize_title(self, title: str) -> str:
            """Normalize Wikipedia page title"""
            return title.strip()
        
        def _get_with_retry(self, url: str, params: Dict, max_retries: int = 3) -> Dict:
            """Make HTTP request with retry logic"""
            for attempt in range(max_retries):
                try:
                    self.rate_limiter.wait(retry_count=attempt)
                    
                    response = self.session.get(url, params=params, timeout=10)
                    
                    if response.status_code == 429:  # Too Many Requests
                        logger.warning(f"Rate limited, attempt {attempt + 1}/{max_retries}")
                        if attempt < max_retries - 1:
                            time.sleep(2 ** attempt)  # Exponential backoff
                        continue
                    
                    response.raise_for_status()
                    
                    with self.lock:
                        self.request_count += 1
                    
                    return response.json()
                
                except requests.RequestException as e:
                    logger.error(f"Request failed (attempt {attempt + 1}): {e}")
                    if attempt == max_retries - 1:
                        raise
                    time.sleep(1)
            
            return {}
        
        def page_exists(self, title: str) -> bool:
            """Check if a Wikipedia page exists"""
            title = self.normalize_title(title)
            
            try:
                params = {
                    'action': 'query',
                    'titles': title,
                    'format': 'json',
                }
                
                data = self._get_with_retry(self.BASE_URL, params)
                pages = data.get('query', {}).get('pages', {})
                page = next(iter(pages.values()), {})
                
                exists = 'missing' not in page and 'invalid' not in page
                logger.debug(f"Page '{title}' exists: {exists}")
                return exists
            
            except Exception as e:
                logger.error(f"Error checking page '{title}': {e}")
                return False
        
        def get_links(self, title: str) -> List[str]:
            """Get all links from a Wikipedia page"""
            title = self.normalize_title(title)
            
            # Check cache first
            cached = self.cache.get(title)
            if cached is not None:
                logger.debug(f"Cache hit: '{title}' ({len(cached)} links)")
                return cached
            
            try:
                params = {
                    'action': 'query',
                    'titles': title,
                    'prop': 'links',
                    'pllimit': 500,  # Maximum per request
                    'plnamespace': '0',  # Main namespace only
                    'format': 'json',
                }
                
                data = self._get_with_retry(self.BASE_URL, params)
                pages = data.get('query', {}).get('pages', {})
                page = next(iter(pages.values()), {})
                
                if 'missing' in page or 'invalid' in page:
                    logger.warning(f"Page not found: '{title}'")
                    self.cache.put(title, [])
                    return []
                
                links = [link['title'] for link in page.get('links', [])]
                
                logger.info(f"Retrieved {len(links)} links from '{title}'")
                
                # Cache the result
                self.cache.put(title, links)
                
                return links
            
            except Exception as e:
                logger.error(f"Error fetching links from '{title}': {e}")
                return []
    
    
    class BidirectionalBFS:
        """Bidirectional BFS for shortest path finding"""
        
        def __init__(self, client: WikipediaClient, max_depth: int = 6, timeout: int = 300):
            self.client = client
            self.max_depth = max_depth
            self.timeout = timeout
        
        def find_path(self, source: str, target: str) -> Optional[List[str]]:
            """
            Find shortest path using bidirectional BFS
            
            Returns:
                List of page titles from source to target, or None
            """
            source = self.client.normalize_title(source)
            target = self.client.normalize_title(target)
            
            logger.info(f"Starting bidirectional BFS: '{source}' → '{target}'")
            
            # Validate pages
            if not self.client.page_exists(source):
                logger.error(f"Source page not found: '{source}'")
                return None
            
            if not self.client.page_exists(target):
                logger.error(f"Target page not found: '{target}'")
                return None
            
            if source == target:
                return [source]
            
            start_time = time.time()
            
            # Forward search from source
            forward_frontier = deque([source])
            forward_visited = {source: None}
            forward_depth = {source: 0}
            
            # Backward search from target
            backward_frontier = deque([target])
            backward_visited = {target: None}
            backward_depth = {target: 0}
            
            while forward_frontier or backward_frontier:
                # Check timeout
                if time.time() - start_time > self.timeout:
                    logger.warning("Timeout reached")
                    return None
                
                # Expand forward frontier if shallower or backward is empty
                if forward_frontier and (not backward_frontier or 
                                        min(forward_depth.values()) <= min(backward_depth.values())):
                    path = self._expand_level(
                        forward_frontier, forward_visited, forward_depth,
                        backward_visited
                    )
                    if path:
                        logger.info(f"Path found: {len(path) - 1} hops")
                        return path
                
                # Expand backward frontier
                elif backward_frontier:
                    path = self._expand_level(
                        backward_frontier, backward_visited, backward_depth,
                        forward_visited
                    )
                    if path:
                        logger.info(f"Path found: {len(path) - 1} hops")
                        return path
                
                # Check depth limit
                if (forward_depth and min(forward_depth.values()) > self.max_depth and
                    backward_depth and min(backward_depth.values()) > self.max_depth):
                    logger.warning(f"Max depth {self.max_depth} exceeded")
                    return None
            
            logger.warning("No path found")
            return None
        
        def _expand_level(self, frontier: deque, visited: Dict, depth: Dict,
                         other_visited: Dict) -> Optional[List[str]]:
            """Expand one level of frontier"""
            
            # Get current level
            current_depth = min(depth.values())
            
            # Process all nodes at this depth
            level_size = len(frontier)
            
            for _ in range(level_size):
                current = frontier.popleft()
                
                # Get neighbors
                neighbors = self.client.get_links(current)
                
                for neighbor in neighbors:
                    # Skip if already visited from this direction
                    if neighbor in visited:
                        continue
                    
                    # Check if we found a meeting point
                    if neighbor in other_visited:
                        # Reconstruct path
                        path_a = self._reconstruct_path(current, visited)
                        path_b = self._reconstruct_path(neighbor, other_visited)
                        
                        path_b.reverse()
                        complete_path = path_a + path_b
                        
                        return complete_path
                    
                    # Add to frontier
                    visited[neighbor] = current
                    depth[neighbor] = current_depth + 1
                    frontier.append(neighbor)
                    
                    logger.debug(f"Discovered: '{neighbor}' at depth {current_depth + 1}")
            
            return None
        
        def _reconstruct_path(self, node: str, visited: Dict) -> List[str]:
            """Reconstruct path from start to node"""
            path = []
            current = node
            
            while current is not None:
                path.append(current)
                current = visited.get(current)
            
            path.reverse()
            return path
    
    
    class WikipediaDegreesSearch:
        """High-level search interface"""
        
        def __init__(self, rate_limit: float = 1.0, max_depth: int = 6, 
                     timeout: int = 300, cache_size: int = 5000):
            """
            Args:
                rate_limit: Requests per second (to avoid ban)
                max_depth: Maximum search depth
                timeout: Search timeout in seconds
                cache_size: Link cache size
            """
            self.rate_limiter = RateLimiter(requests_per_second=rate_limit)
            self.cache = WikipediaCache(max_size=cache_size)
            self.client = WikipediaClient(self.rate_limiter, self.cache)
            self.bfs = BidirectionalBFS(self.client, max_depth=max_depth, timeout=timeout)
            self.start_time = datetime.now()
        
        def search(self, source: str, target: str) -> SearchStats:
            """Execute search and return statistics"""
            search_start = time.time()
            initial_requests = self.client.request_count
            
            try:
                path = self.bfs.find_path(source, target)
                
                stats = SearchStats(
                    source=self.client.normalize_title(source),
                    target=self.client.normalize_title(target),
                    path=path,
                    degrees=len(path) - 1 if path else None,
                    time_seconds=time.time() - search_start,
                    requests_made=self.client.request_count - initial_requests,
                    found=path is not None
                )
            
            except Exception as e:
                stats = SearchStats(
                    source=self.client.normalize_title(source),
                    target=self.client.normalize_title(target),
                    error=str(e),
                    time_seconds=time.time() - search_start,
                    found=False
                )
                logger.error(f"Search failed: {e}")
            
            return stats
        
        def print_result(self, stats: SearchStats):
            """Pretty print search results"""
            print("\n" + "=" * 70)
            print(str(stats))
            
            if stats.found and stats.path:
                print(f"\nPath ({len(stats.path)} pages):")
                for i, page in enumerate(stats.path, 1):
                    if i < len(stats.path):
                        print(f"  {i:2}. {page}")
                        print(f"      ↓")
                    else:
                        print(f"  {i:2}. {page}")
            
            cache_stats = self.cache.get_stats()
            print(f"\nStats:")
            print(f"  Requests: {stats.requests_made}")
            print(f"  Cache Hit Rate: {cache_stats['hit_rate']:.1f}%")
            print(f"  Cache Size: {cache_stats['size']}/{cache_stats['max_size']}")
            print(f"  Rate: {self.rate_limiter.get_qps():.2f} req/s")
            print("=" * 70 + "\n")
        
        def batch_search(self, queries: List[Tuple[str, str]]) -> List[SearchStats]:
            """Execute multiple searches"""
            results = []
            
            for source, target in queries:
                result = self.search(source, target)
                results.append(result)
                self.print_result(result)
                time.sleep(0.5)  # Brief pause between searches
            
            return results
        
        def get_statistics(self) -> Dict:
            """Get overall statistics"""
            cache_stats = self.cache.get_stats()
            
            return {
                'uptime_seconds': (datetime.now() - self.start_time).total_seconds(),
                'total_requests': self.client.request_count,
                'cache': cache_stats,
                'rate_limiter_qps': self.rate_limiter.get_qps(),
            }
    
    
    # ============================================================================
    # Example Usage
    # ============================================================================
    
    def main():
        """Demonstration of Six Degrees of Wikipedia search"""
        
        # Initialize search with rate limiting
        search = WikipediaDegreesSearch(
            rate_limit=1.0,      # 1 request per second (safe limit)
            max_depth=6,         # Maximum 6 degrees
            timeout=300,         # 5 minute timeout
            cache_size=5000      # Cache up to 5000 pages
        )
        
        # Test cases
        queries = [
            ("Python (programming language)", "Artificial intelligence"),
            ("Eiffel Tower", "Internet"),
            ("Pizza", "Quantum mechanics"),
            ("Albert Einstein", "Tennis"),
        ]
        
        print("\n" + "=" * 70)
        print("WIKIPEDIA SIX DEGREES SEARCH")
        print("=" * 70)
        
        # Run searches
        results = search.batch_search(queries)
        
        # Print summary
        print("\nSUMMARY")
        print("-" * 70)
        stats = search.get_statistics()
        
        successful = sum(1 for r in results if r.found)
        total_time = sum(r.time_seconds for r in results)
        avg_degrees = sum(r.degrees for r in results if r.degrees) / successful if successful > 0 else 0
        
        print(f"Successful searches: {successful}/{len(results)}")
        print(f"Total time: {total_time:.2f}s")
        print(f"Average degrees: {avg_degrees:.1f}")
        print(f"Total API requests: {stats['total_requests']}")
        print(f"Cache hit rate: {stats['cache']['hit_rate']:.1f}%")
        print(f"Average rate: {stats['cache']['hits'] / total_time if total_time > 0 else 0:.2f} req/s")
    
    
    if __name__ == "__main__":
        main()
    

    Key Features

    1. Rate Limiting

    • Thread-safe rate limiter with adaptive backoff
    • Exponential backoff on 429 errors
    • QPS monitoring

    2. Caching

    • LRU cache for Wikipedia links
    • Cache statistics and hit rates
    • Configurable cache size

    3. Bidirectional BFS

    • Searches from both ends simultaneously
    • Reduces search space significantly
    • Optimal shortest path finding

    4. Error Handling

    • Validates page existence before search
    • Retry logic with exponential backoff
    • Timeout protection
    • Graceful degradation

    5. Monitoring

    • Request counting
    • Cache statistics
    • Search statistics (time, requests, degrees)
    • Rate limiting metrics

    Usage Examples

    # Simple search
    search = WikipediaDegreesSearch(rate_limit=1.0)
    stats = search.search("Python", "Artificial Intelligence")
    search.print_result(stats)
    
    # Batch searches
    queries = [
        ("Eiffel Tower", "Internet"),
        ("Pizza", "Quantum mechanics"),
    ]
    results = search.batch_search(queries)
    
    # Get statistics
    stats = search.get_statistics()
    print(f"Cache hit rate: {stats['cache']['hit_rate']:.1f}%")
    

    This implementation handles IP bans by respecting rate limits and provides optimal pathfinding through bidirectional BFS!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.