"""
Pattern Algorithms Module
Python Number Pattern Generator
Author: Molla Samser (Founder, RSK World)
Designer & Tester: Rima Khatun
Website: https://rskworld.in
Email: hello@rskworld.in, support@rskworld.in
Phone: +91 93305 39277
Address: Nutanhat, Mongolkote, Purba Burdwan, West Bengal, India - 713147
Year: 2026
Description: Core pattern generation algorithms
"""

import math
from typing import List, Dict, Any, Optional


class PatternAlgorithms:
    """Collection of pattern generation algorithms"""

    @staticmethod
    def pyramid(size: int, start_num: int = 1) -> str:
        """Generate pyramid pattern

        Args:
            size: The height of the pyramid (number of rows)
            start_num: The starting number for the pattern

        Returns:
            String representation of the pyramid pattern
        """
        pattern: List[str] = []
        for i in range(1, size + 1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1} "
            pattern.append(spaces + numbers.rstrip())
        return "\n".join(pattern)
    
    @staticmethod
    def reverse_pyramid(size, start_num=1):
        """Generate reverse pyramid pattern"""
        pattern = []
        for i in range(size, 0, -1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1} "
            pattern.append(spaces + numbers.rstrip())
        return "\n".join(pattern)
    
    @staticmethod
    def triangle(size, start_num=1):
        """Generate number triangle"""
        pattern = []
        for i in range(1, size + 1):
            row = ""
            for j in range(1, i + 1):
                row += f"{start_num + j - 1} "
            pattern.append(row)
        return "\n".join(pattern)
    
    @staticmethod
    def pascal_triangle(size: int) -> str:
        """Generate Pascal's triangle

        Args:
            size: The number of rows in Pascal's triangle

        Returns:
            String representation of Pascal's triangle
        """
        pattern: List[str] = []
        triangle: List[List[int]] = [[1] * (i + 1) for i in range(size)]

        for i in range(2, size):
            for j in range(1, i):
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

        for row in triangle:
            pattern.append(" " * (size - len(row)) + " ".join(map(str, row)))

        return "\n".join(pattern)
    
    @staticmethod
    def floyd_triangle(size):
        """Generate Floyd's triangle"""
        pattern = []
        num = 1
        for i in range(1, size + 1):
            row = ""
            for j in range(i):
                row += f"{num:3d}"
                num += 1
            pattern.append(row)
        return "\n".join(pattern)
    
    @staticmethod
    def square(size, start_num=1):
        """Generate number square"""
        pattern = []
        for i in range(size):
            row = ""
            for j in range(size):
                row += f"{start_num + i * size + j:3d}"
            pattern.append(row)
        return "\n".join(pattern)
    
    @staticmethod
    def diamond(size, start_num=1):
        """Generate diamond pattern"""
        pattern = []
        # Upper half
        for i in range(1, size + 1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1}"
            for j in range(i - 1, 0, -1):
                numbers += f"{start_num + j - 1}"
            pattern.append(spaces + numbers)

        # Lower half
        for i in range(size - 1, 0, -1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1}"
            for j in range(i - 1, 0, -1):
                numbers += f"{start_num + j - 1}"
            pattern.append(spaces + numbers)

        return "\n".join(pattern)
    
    @staticmethod
    def hourglass(size, start_num=1):
        """Generate hourglass pattern"""
        pattern = []
        # Upper half (reverse pyramid)
        for i in range(size, 0, -1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1} "
            pattern.append(spaces + numbers.rstrip())

        # Lower half (pyramid)
        for i in range(2, size + 1):
            spaces = " " * (size - i)
            numbers = ""
            for j in range(1, i + 1):
                numbers += f"{start_num + j - 1} "
            pattern.append(spaces + numbers.rstrip())

        return "\n".join(pattern)
    
    @staticmethod
    def spiral(size):
        """Generate number spiral"""
        matrix = [[0] * size for _ in range(size)]
        num = 1
        top, bottom = 0, size - 1
        left, right = 0, size - 1
        
        while top <= bottom and left <= right:
            # Top row
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1
            
            # Right column
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            
            # Bottom row
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    matrix[bottom][i] = num
                    num += 1
                bottom -= 1
            
            # Left column
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    matrix[i][left] = num
                    num += 1
                left += 1
        
        pattern = []
        for row in matrix:
            pattern.append(" ".join(f"{num:3d}" for num in row))
        
        return "\n".join(pattern)
    
    @staticmethod
    def prime_numbers(size):
        """Generate prime numbers pattern"""
        def is_prime(n):
            if n < 2:
                return False
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    return False
            return True

        primes = []
        num = 2
        while len(primes) < size * size:
            if is_prime(num):
                primes.append(num)
            num += 1

        pattern = []
        for i in range(size):
            row = ""
            for j in range(size):
                idx = i * size + j
                if idx < len(primes):
                    row += f"{primes[idx]:4d} "
                else:
                    row += "     "
            pattern.append(row.rstrip())

        return "\n".join(pattern)
    
    @staticmethod
    def fibonacci_triangle(size):
        """Generate Fibonacci triangle (bonus pattern)"""
        def fibonacci(n):
            if n <= 0:
                return 0
            elif n == 1:
                return 1
            a, b = 0, 1
            for _ in range(2, n + 1):
                a, b = b, a + b
            return b
        
        pattern = []
        for i in range(1, size + 1):
            row = ""
            for j in range(1, i + 1):
                row += f"{fibonacci(j):3d}"
            pattern.append(row)
        return "\n".join(pattern)
    
    @staticmethod
    def multiplication_table(size):
        """Generate multiplication table (bonus pattern)"""
        pattern = []
        for i in range(1, size + 1):
            row = ""
            for j in range(1, size + 1):
                row += f"{i * j:4d}"
            pattern.append(row)
        return "\n".join(pattern)
    
    @staticmethod
    def magic_square(size):
        """Generate magic square (bonus pattern for odd sizes)"""
        if size % 2 == 0:
            return "Magic square generation only supported for odd sizes"
        
        magic_square = [[0] * size for _ in range(size)]
        
        # Siamese method for odd order magic squares
        n, i, j = size, 0, size // 2
        
        for num in range(1, size * size + 1):
            magic_square[i][j] = num
            next_i, next_j = (i - 1) % size, (j + 1) % size
            
            if magic_square[next_i][next_j]:
                i = (i + 1) % size
            else:
                i, j = next_i, next_j
        
        pattern = []
        for row in magic_square:
            pattern.append(" ".join(f"{num:4d}" for num in row))
        
        return "\n".join(pattern)

    @staticmethod
    def sierpinski_triangle(size: int) -> str:
        """Generate Sierpinski triangle fractal pattern

        Args:
            size: The depth/level of the fractal (recommended 1-6)

        Returns:
            String representation of Sierpinski triangle
        """
        if size <= 0:
            return ""

        # Create base triangle
        height = 2 ** size
        pattern = [[" " for _ in range(height * 2)] for _ in range(height)]

        def draw_triangle(x: int, y: int, size: int):
            if size == 1:
                pattern[y][x] = "1"
                return

            half = size // 2
            draw_triangle(x, y, half)
            draw_triangle(x + half, y, half)
            draw_triangle(x + half // 2, y + half, half)

        draw_triangle(0, 0, height)

        return "\n".join("".join(row).rstrip() for row in pattern)

    @staticmethod
    def mandelbrot_set(size: int, max_iter: int = 50) -> str:
        """Generate Mandelbrot set visualization

        Args:
            size: The size of the grid (recommended 10-20)
            max_iter: Maximum iterations for convergence

        Returns:
            String representation of Mandelbrot set
        """
        pattern = []
        for y in range(-size, size):
            row = ""
            for x in range(-size * 2, size * 2):
                # Map to complex plane
                c = complex(x / size, y / size)
                z = 0j
                iter_count = 0

                while abs(z) <= 2 and iter_count < max_iter:
                    z = z*z + c
                    iter_count += 1

                # Map iteration count to characters
                if iter_count == max_iter:
                    char = "█"
                elif iter_count > max_iter * 0.8:
                    char = "▓"
                elif iter_count > max_iter * 0.6:
                    char = "▒"
                elif iter_count > max_iter * 0.4:
                    char = "░"
                else:
                    char = " "

                row += char
            pattern.append(row.rstrip())

        return "\n".join(pattern)

    @staticmethod
    def hilbert_curve(size: int) -> str:
        """Generate Hilbert curve pattern

        Args:
            size: The order of the curve (recommended 1-4)

        Returns:
            String representation of Hilbert curve
        """
        def rotate(n: int, x: int, y: int, rx: int, ry: int) -> tuple[int, int]:
            if ry == 0:
                if rx == 1:
                    x = n - 1 - x
                    y = n - 1 - y
                x, y = y, x
            return x, y

        def hilbert_curve_points(n: int) -> List[tuple[int, int]]:
            points = []
            for d in range(n * n):
                x, y = 0, 0
                s = 1
                while s < n:
                    rx = (d // (s * 2)) % 2
                    ry = (d // s) % 2
                    x, y = rotate(s, x, y, rx, ry)
                    x += s * rx
                    y += s * ry
                    s *= 2
                points.append((x, y))
            return points

        n = 2 ** size
        points = hilbert_curve_points(n)
        grid = [[" " for _ in range(n)] for _ in range(n)]

        for i, (x, y) in enumerate(points):
            if 0 <= x < n and 0 <= y < n:
                grid[y][x] = str(i % 10)

        return "\n".join("".join(row) for row in grid)

    @staticmethod
    def dragon_curve(size: int) -> str:
        """Generate dragon curve pattern

        Args:
            size: The number of iterations (recommended 1-10)

        Returns:
            String representation of dragon curve
        """
        # Generate dragon curve using L-system
        sequence = "FX"

        for _ in range(size):
            new_sequence = ""
            for char in sequence:
                if char == "X":
                    new_sequence += "X+YF+"
                elif char == "Y":
                    new_sequence += "-FX-Y"
                else:
                    new_sequence += char
            sequence = new_sequence

        # Convert to grid pattern (simplified visualization)
        x, y = 0, 0
        direction = 0  # 0: right, 1: up, 2: left, 3: down
        grid_size = 2 ** (size + 2)
        grid = [[" " for _ in range(grid_size)] for _ in range(grid_size)]
        min_x, min_y = grid_size // 2, grid_size // 2
        max_x, max_y = grid_size // 2, grid_size // 2

        for char in sequence:
            if char in "F-":
                if char == "F":
                    grid[y][x] = "█"
                elif char == "-":
                    direction = (direction - 1) % 4
                elif char == "+":
                    direction = (direction + 1) % 4

                # Move in current direction
                if direction == 0:  # right
                    x += 1
                elif direction == 1:  # up
                    y -= 1
                elif direction == 2:  # left
                    x -= 1
                elif direction == 3:  # down
                    y += 1

                min_x = min(min_x, x)
                max_x = max(max_x, x)
                min_y = min(min_y, y)
                max_y = max(max_y, y)

        # Extract relevant part of grid
        result = []
        for y in range(min_y, max_y + 1):
            row = ""
            for x in range(min_x, max_x + 1):
                if 0 <= x < grid_size and 0 <= y < grid_size:
                    row += grid[y][x]
                else:
                    row += " "
            result.append(row.rstrip())

        return "\n".join(result)

    @staticmethod
    def koch_snowflake(size: int) -> str:
        """Generate Koch snowflake pattern

        Args:
            size: The number of iterations (recommended 1-4)

        Returns:
            String representation of Koch snowflake
        """
        def koch_curve(iterations: int) -> str:
            curve = "F"
            for _ in range(iterations):
                new_curve = ""
                for char in curve:
                    if char == "F":
                        new_curve += "F+F-F-F+F"
                    else:
                        new_curve += char
                curve = new_curve
            return curve

        # Generate three sides of the snowflake
        side = koch_curve(size)
        snowflake = side + "+F+" + side + "+F+" + side

        # Convert to grid (simplified visualization)
        x, y = 0, 0
        direction = 0  # 0: right, 1: up, 2: left, 3: down
        grid_size = 3 ** (size + 2)
        grid = [[" " for _ in range(grid_size)] for _ in range(grid_size)]

        for char in snowflake:
            if char == "F":
                grid[y][x] = "█"
                # Move forward
                if direction == 0:
                    x += 1
                elif direction == 1:
                    y -= 1
                elif direction == 2:
                    x -= 1
                elif direction == 3:
                    y += 1
            elif char == "+":
                direction = (direction + 1) % 4
            elif char == "-":
                direction = (direction - 1) % 4

        # Find bounds and extract pattern
        min_x = min(x for row in grid for x, cell in enumerate(row) if cell != " ")
        max_x = max(x for row in grid for x, cell in enumerate(row) if cell != " ")
        min_y = min(y for y, row in enumerate(grid) for x, cell in enumerate(row) if cell != " ")
        max_y = max(y for y, row in enumerate(grid) for x, cell in enumerate(row) if cell != " ")

        result = []
        for y in range(min_y, max_y + 1):
            row = ""
            for x in range(min_x, max_x + 1):
                row += grid[y][x]
            result.append(row.rstrip())

        return "\n".join(result)

    @staticmethod
    def cellular_automaton(size: int, rule: int = 30) -> str:
        """Generate cellular automaton pattern (Wolfram rule)

        Args:
            size: The number of generations (height)
            rule: The Wolfram rule number (0-255)

        Returns:
            String representation of cellular automaton
        """
        if not 0 <= rule <= 255:
            rule = 30

        # Convert rule to binary
        rule_bits = [(rule >> i) & 1 for i in range(8)]

        # Initialize first row with single 1 in center
        width = size * 2 + 1
        grid = [[0] * width for _ in range(size)]
        grid[0][width // 2] = 1

        # Generate subsequent rows
        for row in range(1, size):
            for col in range(1, width - 1):
                # Get neighborhood (3 bits)
                left = grid[row-1][col-1]
                center = grid[row-1][col]
                right = grid[row-1][col+1]

                # Convert to rule index
                neighborhood = (left << 2) | (center << 1) | right
                grid[row][col] = rule_bits[neighborhood]

        # Convert to string representation
        pattern = []
        for row in grid:
            pattern.append("".join("█" if cell else " " for cell in row).rstrip())

        return "\n".join(pattern)

    @staticmethod
    def binary_tree(size: int) -> str:
        """Generate binary tree pattern

        Args:
            size: The depth of the tree (recommended 1-6)

        Returns:
            String representation of binary tree
        """
        if size <= 0:
            return ""

        height = 2 ** size
        width = 2 ** (size + 1) - 1
        grid = [[" " for _ in range(width)] for _ in range(height)]

        def draw_node(x: int, y: int, depth: int):
            if depth <= 0:
                return

            # Draw current node
            grid[y][x] = "O"

            # Draw connections and children
            if depth > 1:
                left_child_x = x - 2 ** (depth - 2)
                right_child_x = x + 2 ** (depth - 2)
                child_y = y + 2 ** (depth - 2)

                if child_y < height:
                    # Draw left connection
                    for i in range(1, 2 ** (depth - 2)):
                        grid[y + i][x - i] = "/"
                    # Draw right connection
                    for i in range(1, 2 ** (depth - 2)):
                        grid[y + i][x + i] = "\\"

                    # Draw children
                    draw_node(left_child_x, child_y, depth - 1)
                    draw_node(right_child_x, child_y, depth - 1)

        draw_node(width // 2, 0, size)
        return "\n".join("".join(row) for row in grid)


# Utility functions for pattern analysis
class PatternUtils:
    """Utility functions for pattern analysis and validation"""

    @staticmethod
    def validate_size(size: Any) -> tuple[bool, int]:
        """Validate pattern size

        Args:
            size: The size value to validate

        Returns:
            Tuple of (is_valid, validated_size)
        """
        try:
            size = int(size)
            return 1 <= size <= 50, size
        except ValueError:
            return False, 0

    @staticmethod
    def validate_start_number(start_num: Any) -> tuple[bool, int]:
        """Validate starting number

        Args:
            start_num: The start number value to validate

        Returns:
            Tuple of (is_valid, validated_start_num)
        """
        try:
            start_num = int(start_num)
            return 0 <= start_num <= 1000, start_num
        except ValueError:
            return False, 0

    @staticmethod
    def count_pattern_lines(pattern: Optional[str]) -> int:
        """Count number of lines in pattern

        Args:
            pattern: The pattern string to analyze

        Returns:
            Number of lines in the pattern
        """
        return len(pattern.split('\n')) if pattern else 0

    @staticmethod
    def get_pattern_stats(pattern: Optional[str]) -> Dict[str, int]:
        """Get statistics about the pattern

        Args:
            pattern: The pattern string to analyze

        Returns:
            Dictionary with pattern statistics
        """
        if not pattern:
            return {"lines": 0, "characters": 0, "numbers": 0}

        lines = pattern.split('\n')
        characters = len(pattern)
        numbers = sum(line.count(str(i)) for i in range(10) for line in lines)

        return {
            "lines": len(lines),
            "characters": characters,
            "numbers": numbers
        }


if __name__ == "__main__":
    # Test all patterns
    algorithms = PatternAlgorithms()
    
    print("Testing Pattern Algorithms")
    print("=" * 40)
    
    patterns_to_test = [
        ("Pyramid", algorithms.pyramid, 5),
        ("Reverse Pyramid", algorithms.reverse_pyramid, 5),
        ("Triangle", algorithms.triangle, 5),
        ("Pascal's Triangle", algorithms.pascal_triangle, 5),
        ("Floyd's Triangle", algorithms.floyd_triangle, 4),
        ("Square", algorithms.square, 3),
        ("Diamond", algorithms.diamond, 3),
        ("Hourglass", algorithms.hourglass, 4),
        ("Spiral", algorithms.spiral, 3),
        ("Prime Numbers", algorithms.prime_numbers, 3),
        ("Fibonacci Triangle", algorithms.fibonacci_triangle, 5),
        ("Multiplication Table", algorithms.multiplication_table, 5),
        ("Magic Square", algorithms.magic_square, 3),
        ("Sierpinski Triangle", algorithms.sierpinski_triangle, 3),
        ("Mandelbrot Set", algorithms.mandelbrot_set, 8),
        ("Hilbert Curve", algorithms.hilbert_curve, 2),
        ("Dragon Curve", algorithms.dragon_curve, 4),
        ("Koch Snowflake", algorithms.koch_snowflake, 2),
        ("Cellular Automaton", algorithms.cellular_automaton, 8),
        ("Binary Tree", algorithms.binary_tree, 3),
    ]
    
    for name, func, size in patterns_to_test:
        print(f"\n{name}:")
        print("-" * 20)
        if name in ["Pascal's Triangle", "Prime Numbers", "Fibonacci Triangle", "Multiplication Table", "Magic Square", "Sierpinski Triangle", "Mandelbrot Set", "Hilbert Curve", "Dragon Curve", "Koch Snowflake", "Cellular Automaton", "Binary Tree"]:
            print(func(size))
        else:
            print(func(size, 1))