def generate_explanation(analysis_result: dict) -> dict: """ Generates structured explanations. Priority Order: 1. Final resolved pattern (highest authority) 2. Strong structural feature patterns 3. Generic structural fallback """ features = analysis_result.get("features", {}) pattern = analysis_result.get("analysis", {}).get("pattern") explanation = "" # ============================================================ # 1️⃣ PATTERN-DRIVEN EXPLANATIONS (HIGHEST PRIORITY) # ============================================================ if pattern == "Quick Sort": explanation = ( "|Quick Sort Pattern| A pivot element partitions the array into " "smaller subarrays which are recursively sorted." ) elif pattern == "Merge Sort": explanation = ( "|Merge Sort Pattern| The array is recursively divided into halves, " "sorted independently, and merged back together." ) elif pattern == "Bubble Sort": explanation = ( "|Bubble Sort Pattern| Adjacent elements are repeatedly compared " "and swapped if out of order. Larger elements 'bubble' to the end " "with each pass." ) elif pattern == "Insertion Sort": explanation = ( "|Insertion Sort Pattern| Elements are inserted into their correct " "position within the sorted portion of the list by shifting larger elements." ) elif pattern == "Heap-Based Algorithm" or pattern == "Heap Sort": explanation = ( "|Heap / Priority Queue Pattern| The algorithm uses a heap data " "structure to maintain ordered elements efficiently, typically " "enabling O(log n) insertions and removals." ) elif pattern == "Breadth-First Search": explanation = ( "|Breadth-first search Pattern| The algorithm explores nodes " "level by level using a queue." ) elif pattern == "Depth-First Search": explanation = ( "|Depth-first traversal Pattern| The algorithm explores as far " "as possible along each branch before backtracking." ) elif pattern == "Binary Search": explanation = ( "|Binary search Pattern| The algorithm repeatedly halves the " "search space, resulting in logarithmic time complexity." ) elif pattern == "Memoization": explanation = ( "|Memoization Pattern| Previously computed results are stored " "to avoid redundant recursive calls." ) elif pattern == "Tabulation": explanation = ( "|Tabulation Dynamic Programming Pattern| A table is built " "iteratively using previously computed subproblem results." ) elif pattern == "Sliding Window": explanation = ( "|Sliding Window Pattern| A window expands and contracts across " "the data structure while maintaining a running condition." ) elif pattern == "Two-Pointer Technique": explanation = ( "|Two-pointer technique Pattern| Two indices move toward each other " "in a controlled manner during a single traversal." ) # ============================================================ # 2️⃣ STRUCTURAL FEATURE FALLBACK (ONLY IF NO PATTERN MATCH) # ============================================================ elif features.get("heap_pattern"): explanation = ( "|Heap Pattern| The algorithm relies on a heap data structure " "for ordered extraction or insertion." ) elif features.get("memoization_pattern"): explanation = ( "|Memoization Pattern| Previously computed results are reused " "to reduce redundant computation." ) elif features.get("tabulation_pattern"): explanation = ( "|Tabulation Pattern| A dynamic programming table is constructed " "iteratively to build the final solution." ) elif features.get("bfs_pattern"): explanation = ( "|Breadth-first search Pattern| The algorithm processes elements " "level by level using a queue." ) elif features.get("binary_search_pattern"): explanation = ( "|Binary search Pattern| The search space is repeatedly divided in half." ) elif features.get("sliding_window_pattern"): explanation = ( "|Sliding Window Pattern| A dynamic window adjusts across input " "to maintain a condition efficiently." ) elif features.get("pointer_updates", 0) >= 2: explanation = ( "|Two-pointer Pattern| Two pointers are adjusted during traversal " "to control search or comparison." ) elif features.get("dfs_pattern"): explanation = ( "|Depth-first traversal Pattern| The algorithm explores branches " "deeply before backtracking." ) elif features.get("merge_sort_pattern"): explanation = ( "|Merge Sort Pattern| Recursive division and merging strategy detected." ) elif features.get("quick_sort_pattern"): explanation = ( "|Quick Sort Pattern| Partition-based recursive sorting detected." ) elif features.get("divide_and_conquer"): explanation = ( "|Divide-and-conquer Pattern| The problem is split into smaller " "subproblems and their results are combined." ) elif features.get("recursion") and features.get("recursive_call_count", 0) > 1: explanation = ( "Multiple recursive calls per invocation detected, suggesting " "exponential growth." ) elif features.get("recursion"): explanation = ( "Single recursive call per invocation detected, suggesting " "linear recursion depth." ) elif features.get("bubble_sort_pattern"): explanation = ( "|Bubble Sort Pattern| Repeated adjacent swaps detected." ) elif features.get("insertion_sort_pattern"): explanation = ( "|Insertion Sort Pattern| Element shifting within a sorted subarray detected." ) elif features.get("max_loop_depth", 0) > 1: explanation = ( "Nested loop structures detected, indicating polynomial behavior." ) elif features.get("max_loop_depth", 0) == 1: explanation = ( "Single loop traversal detected, indicating linear iteration." ) else: explanation = ( "No significant structural patterns were detected." ) return { "summary": explanation, "details": [explanation] }