File size: 7,126 Bytes
f8a39f0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 | 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]
} |