from itertools import combinations, permutations, product
from typing import List, Tuple, TypeVar

T = TypeVar('T')

def demonstrate_itertools() -> None:
    """
    Show common itertools patterns in AoC problems.
    """
    # Example 1: Finding pairs that sum to target
    def find_sum_pairs(numbers: List[int], target: int) -> List[Tuple[int, int]]:
        """Find all pairs of numbers that sum to target."""
        return [(a, b) for a, b in combinations(numbers, 2)
                if a + b == target]

    # Example 2: Generate all possible paths
    def generate_paths(points: List[str]) -> List[List[str]]:
        """Generate all possible paths through points."""
        return list(permutations(points))

    # Example 3: Grid walking
    def generate_walks(steps: int, directions: List[str]) -> List[Tuple[str, ...]]:
        """Generate all possible walks of given length."""
        return list(product(directions, repeat=steps))

    # Example 4: Finding subsets of specific size
    def find_subsets(items: List[T], k: int) -> List[Tuple[T, ...]]:
        """Find all subsets of size k."""
        return list(combinations(items, k))

    # Example usage
    numbers = [1, 2, 3, 4, 5, 6]
    print("Pairs summing to 7:", find_sum_pairs(numbers, 7))
    
    points = ['A', 'B', 'C']
    print("All possible paths:", generate_paths(points))
    
    directions = ['N', 'E', 'S', 'W']
    print("Possible 2-step walks:", generate_walks(2, directions))
    
    items = ['a', 'b', 'c', 'd']
    print("2-element subsets:", find_subsets(items, 2))

if __name__ == "__main__":
    demonstrate_itertools()

import heapq
from dataclasses import dataclass, field
from typing import Any, Dict, List, Optional, Set, Tuple
from collections import defaultdict

@dataclass(order=True)
class PrioritizedItem:
    """
    Wrapper class for items with priority.
    
    The order=True decorator automatically implements comparison methods
    based on field order, with priority being compared first.
    """
    priority: int
    # field(compare=False) ensures item isn't used in comparisons
    item: Any = field(compare=False)

class PriorityQueue:
    """
    A generic priority queue implementation using heapq.
    
    This class wraps heapq to provide a more intuitive interface
    and adds functionality commonly needed in AoC problems.
    """
    def __init__(self):
        self._queue = []
        self._entry_count = 0  # For breaking priority ties
    
    def push(self, item: Any, priority: int) -> None:
        """Add an item with given priority."""
        entry = [priority, self._entry_count, item]
        self._entry_count += 1
        heapq.heappush(self._queue, entry)
    
    def pop(self) -> Tuple[Any, int]:
        """Remove and return the lowest priority item."""
        if not self._queue:
            raise IndexError("pop from an empty queue")
        priority, _, item = heapq.heappop(self._queue)
        return item, priority
    
    def peek(self) -> Optional[Tuple[Any, int]]:
        """View the lowest priority item without removing it."""
        if not self._queue:
            return None
        priority, _, item = self._queue[0]
        return item, priority
    
    def __bool__(self) -> bool:
        """Allow direct boolean testing."""
        return bool(self._queue)
    
    def __len__(self) -> int:
        """Return number of items in queue."""
        return len(self._queue)

def demonstrate_basic_heapq() -> None:
    """
    Demonstrate fundamental heapq operations.
    """
    # Creating a min heap
    numbers = [5, 2, 8, 1, 9, 3]
    heapq.heapify(numbers)  # Convert list to heap in-place
    print("Heap from numbers:", numbers)  # Note: List remains valid heap
    
    # Adding elements
    heapq.heappush(numbers, 4)
    print("After pushing 4:", numbers)
    
    # Removing smallest element
    smallest = heapq.heappop(numbers)
    print(f"Popped {smallest}, heap is now: {numbers}")
    
    # Finding n smallest elements
    original = [5, 2, 8, 1, 9, 3]
    smallest_3 = heapq.nsmallest(3, original)
    print("3 smallest elements:", smallest_3)

def demonstrate_dijkstra() -> None:
    """
    Implement Dijkstra's algorithm using a priority queue.
    """
    def dijkstra(graph: Dict[str, Dict[str, int]], start: str) -> Dict[str, int]:
        """
        Find shortest paths from start node to all other nodes.
        
        Args:
            graph: Dictionary of dictionaries representing weighted edges
            start: Starting node
            
        Returns:
            Dictionary of shortest distances to each node
        """
        distances = {node: float('inf') for node in graph}
        distances[start] = 0
        pq = PriorityQueue()
        pq.push(start, 0)
        seen = set()
        
        while pq:
            current_node, current_distance = pq.pop()
            
            if current_node in seen:
                continue
            seen.add(current_node)
            
            # Check each neighbor
            for neighbor, weight in graph[current_node].items():
                distance = current_distance + weight
                
                # Update if we found a shorter path
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    pq.push(neighbor, distance)
        
        return distances
    
    # Example graph
    graph = {
        'A': {'B': 4, 'C': 2},
        'B': {'D': 3, 'C': 1},
        'C': {'B': 1, 'D': 5},
        'D': {}
    }
    
    distances = dijkstra(graph, 'A')
    print("Shortest distances from A:", distances)

def demonstrate_k_way_merge() -> None:
    """
    Demonstrate merging k sorted sequences efficiently.
    """
    def merge_sorted(*sequences: List[int]) -> List[int]:
        """
        Merge multiple sorted sequences into a single sorted sequence.
        Uses heapq.merge for efficient k-way merging.
        """
        return list(heapq.merge(*sequences))
    
    # Example sequences
    seq1 = [1, 4, 7]
    seq2 = [2, 5, 8]
    seq3 = [3, 6, 9]
    
    merged = merge_sorted(seq1, seq2, seq3)
    print("Merged sequences:", merged)

def demonstrate_continuous_median() -> None:
    """
    Demonstrate tracking the median of a stream using two heaps.
    """
    class MedianFinder:
        def __init__(self):
            self.small = []  # max heap (-ve numbers)
            self.large = []  # min heap
        
        def add_number(self, num: int) -> None:
            # Add to appropriate heap
            if len(self.small) == len(self.large):
                heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
            else:
                heapq.heappush(self.small, -heapq.heappushpop(self.large, num))
        
        def find_median(self) -> float:
            if len(self.small) == len(self.large):
                return (-self.small[0] + self.large[0]) / 2
            return float(self.large[0])
    
    # Example usage
    finder = MedianFinder()
    numbers = [2, 3, 4, 1, 5, 6, 7]
    print("Finding running median:")
    for num in numbers:
        finder.add_number(num)
        print(f"After adding {num}, median is {finder.find_median()}")

if __name__ == "__main__":
    print("Basic heapq operations:")
    demonstrate_basic_heapq()
    print("\nDijkstra's algorithm:")
    demonstrate_dijkstra()
    print("\nK-way merge:")
    demonstrate_k_way_merge()
    print("\nContinuous median:")
    demonstrate_continuous_median()

def process_input_examples():
    """Common input processing patterns in AoC."""
    
    # Pattern 1: Quick number extraction
    def extract_numbers(line: str) -> list[int]:
        # Fast way to pull all numbers from a string
        import re
        return [int(x) for x in re.findall(r'-?\d+', line)]
    
    # Pattern 2: Grid parsing
    def parse_grid(input_text: str) -> list[list[str]]:
        return [list(line) for line in input_text.splitlines()]
    
    # Pattern 3: Chunk processing
    def process_chunks(input_text: str) -> list[str]:
        return input_text.strip().split('\n\n')
    
    # Pattern 4: Mixed data parsing
    def parse_mixed_line(line: str) -> tuple[str, int]:
        # Example: "forward 5" -> ("forward", 5)
        direction, amount = line.split()
        return direction, int(amount)

    # Examples
    examples = {
        "number_line": "Position at x=2, y=-5",
        "grid": "123\n456\n789",
        "chunks": "chunk1\n\nchunk2\n\nchunk3",
        "mixed": "forward 5"
    }
    
    print("Numbers:", extract_numbers(examples["number_line"]))
    print("Grid:", parse_grid(examples["grid"]))
    print("Chunks:", process_chunks(examples["chunks"]))
    print("Mixed:", parse_mixed_line(examples["mixed"]))

from collections import defaultdict, deque
from typing import List, Dict, Set, Tuple
import re
import heapq
import itertools

class AoCTemplate:
    def __init__(self, input_file: str):
        # Load input immediately
        with open(input_file) as f:
            self.raw_input = f.read().strip()
            self.lines = self.raw_input.splitlines()
        
        # Common data structures ready to go
        self.graph = defaultdict(list)
        self.seen = set()
        self.queue = deque()
        self.counts = defaultdict(int)
        
        # Regular expressions
        self.number_pattern = re.compile(r'-?\d+')
        
        # Directions for grid problems
        self.DIRS = [(0,1), (1,0), (0,-1), (-1,0)]  # R,D,L,U
        self.DIRS_8 = [(i,j) for i in [-1,0,1] 
                            for j in [-1,0,1] if (i,j) != (0,0)]
    
    def parse_numbers(self, line: str) -> List[int]:
        return [int(x) for x in self.number_pattern.findall(line)]
    
    def is_valid_pos(self, pos: Tuple[int, int], 
                     grid: List[List[any]]) -> bool:
        row, col = pos
        return (0 <= row < len(grid) and 
                0 <= col < len(grid[0]))
    
    def solve_part1(self) -> int:
        """Solution for part 1."""
        result = 0
        for line in self.lines:
            # Ready to start solving
            pass
        return result
    
    def solve_part2(self) -> int:
        """Solution for part 2."""
        result = 0
        # Often builds on part 1
        return result

if __name__ == "__main__":
    solver = AoCTemplate("input.txt")
    print(f"Part 1: {solver.solve_part1()}")
    print(f"Part 2: {solver.solve_part2()}")

class DebugTools:
    @staticmethod
    def visualize_grid(grid: List[List[any]]) -> None:
        """Print grid with coordinates for debugging."""
        print("  " + " ".join(str(i%10) for i in range(len(grid[0]))))
        for i, row in enumerate(grid):
            print(f"{i%10} {' '.join(str(x) for x in row)}")
    
    @staticmethod
    def trace_path(path: List[Tuple[int, int]], 
                   grid: List[List[any]]) -> None:
        """Visualize a path through a grid."""
        debug_grid = [['.'] * len(grid[0]) for _ in range(len(grid))]
        for i, (r, c) in enumerate(path):
            debug_grid[r][c] = str(i % 10)
        DebugTools.visualize_grid(debug_grid)
    
    @staticmethod
    def log_state(step: int, **kwargs) -> None:
        """Log current state of various variables."""
        print(f"\nStep {step}:")
        for name, value in kwargs.items():
            print(f"  {name}: {value}")