• ⚙️ QUEST OF EFFICIENCY

⚙️ QUEST OF EFFICIENCY

The notebook cell only runs if all challenges work.

The demonic challenge remains hidden unless optimized.

List the Run-Time Complexity and Memory/Space Complexity of each function/activity.

import heapq
import unicodedata
import time

# -----------------------
# EASY CHALLENGES (5)
# -----------------------

def easy_1_sum_list(nums):
    """Compute the sum of a list (inefficiently)."""
    # Hint: Why climb the same stairs again to count how many you took?
    total = 0
    for i in range(len(nums)):
        total += nums[i]
    return total

# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n^2) — nested accumulation: sum_{i=0}^{n-1}(i+1).
# Space Complexity: O(1) — a few scalars only.

def easy_2_is_palindrome(s):
    """Check if a string is a palindrome."""
    # Hint: A mirror need not reflect twice.
    s = ''.join(ch.lower() for ch in s if ch.isalnum())
    for i in range(len(s)):
        if s[i] != s[len(s) - 1 - i]:
            return False
    return True
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n) — one pass to filter/lower + one pass to compare.
# Space Complexity: O(n) — builds a cleaned copy of the string.


def easy_3_reverse_string(s):
    """Return reversed string inefficiently."""
    # Hint: Adding one stone at a time builds a wall slowly.
    rev = ""
    for ch in s:
        rev = ch + rev
    return rev
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n^2) — repeated string concatenation copies prefixes.
# Space Complexity: O(n) — stores the reversed string (peak still linear).


def easy_4_factorial(n):
    """Compute factorial inefficiently."""
    # Hint: Counting up is fine, but why recount every time?
    if n == 0:
        return 1
    vals = [1]
    for i in range(1, n + 1):
        prod = 1
        for j in range(1, i + 1):
            prod *= j
        vals.append(prod)
    return vals[-1]
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n^2) — inner product recomputed for each i up to n.
# Space Complexity: O(n) — stores all intermediate factorials in 'vals'.


def easy_5_find_max(lst):
    """Find the maximum number (inefficient)."""
    # Hint: True greatness does not need to be checked against everyone each time.
    for i in range(len(lst)):
        is_max = True
        for j in range(len(lst)):
            if lst[j] > lst[i]:
                is_max = False
        if is_max:
            return lst[i]
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n^2) worst, O(n) best — compares each i to all j.
# Space Complexity: O(1) — constant extra variables.


# -----------------------
# MEDIUM CHALLENGES (3)
# -----------------------

def medium_1_fibonacci(n):
    """Return first n Fibonacci numbers (inefficient recursion)."""
    # Hint: Memory forgotten must always be rediscovered.
    def fib(k):
        if k <= 1:
            return k
        return fib(k - 1) + fib(k - 2)
    return [fib(i) for i in range(n)]
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(φ^n) (~O(2^n)) — naive recursion per term dominates.
# Space Complexity: O(n) — recursion depth + output list of length n.


def medium_2_sort_unique(nums):
    """Sort numbers and remove duplicates."""
    # Hint: Sorting once is order. Sorting twice is obsession.
    result = []
    for x in sorted(nums):
        if x not in result:
            result.append(x)
            result = sorted(result)
    return result
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n log n + m^2 log m) → worst O(n^2 log n)
#   (initial sort O(n log n); then m inserts, each does 'x in result' O(k) + re-sort O(k log k)).
# Space Complexity: O(m) — 'result' holds uniques; sorting overhead is linear extra.


def medium_3_balanced_parentheses(s):
    """Check for balanced parentheses (inefficient)."""
    # Hint: You can be thorough or you can be efficient—rarely both.
    pairs = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in pairs:
            stack.append(ch)
        elif ch in pairs.values():
            if not stack or pairs[stack.pop()] != ch:
                return False
    return not stack

# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(n^2) — checks balance on every prefix (1..n), each O(i).
# Space Complexity: O(n) — stack can grow to length n in worst case.


# -----------------------
# HARD CHALLENGE (1)
# -----------------------

def hard_1_shortest_path(graph, start):
    """Dijkstra’s algorithm — works, but wastes time."""
    # Hint: The patient traveler rechecks every road too often.
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    visited = set()
    while pq:
        smallest = min(pq, key=lambda x: x[0])  # O(n)
        pq.remove(smallest)
        d, node = smallest
        if node in visited:
            continue
        visited.add(node)
        for nei, w in graph[node]:
            if dist[node] + w < dist[nei]:
                dist[nei] = dist[node] + w
                pq.append((dist[nei], nei))
    return dist
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(E^2) worst — each iteration scans/removes min in O(|pq|),
#   and |pq| can grow to O(E) due to repeated relaxations; edge scans add O(E).
# Space Complexity: O(V + E) — 'dist' and 'visited' are O(V); 'pq' can hold O(E) entries.


# -----------------------
# DEMONIC (HIDDEN)
# -----------------------

def _demonic_unicode_equal(a, b):
    """Hidden: looks fine, but scales poorly."""
    # No hints for demons.
    for _ in range(5000):
        if a == b:
            continue
    return unicodedata.normalize('NFC', a) == unicodedata.normalize('NFC', b)
# Add Run-time Complexity and Memory/Space Complexity here:
# Run-time Complexity: O(L) — 5000 equality checks add a large constant; normalization is O(L).
# Space Complexity: O(L) — two normalized strings allocated.



# ============================================================
# ✅ GATEKEEPER EXECUTION LOGIC
# ============================================================

# Each challenge must succeed for this cell to complete.
# If one fails or throws, execution will halt.
# The demonic test runs silently and only reveals itself when solved.

def _assert_eq(value, expected, name):
    if value != expected:
        raise AssertionError(f"❌ Challenge failed: {name}\nExpected {expected}, got {value}")

# Run all visible challenges
_assert_eq(easy_1_sum_list([1,2,3,4,5]), 15, "easy_1_sum_list")
_assert_eq(easy_2_is_palindrome("Racecar"), True, "easy_2_is_palindrome")
_assert_eq(easy_3_reverse_string("stressed"), "desserts", "easy_3_reverse_string")
_assert_eq(easy_4_factorial(5), 120, "easy_4_factorial")
_assert_eq(easy_5_find_max([3,1,4,1,5,9]), 9, "easy_5_find_max")

_assert_eq(medium_1_fibonacci(10), [0,1,1,2,3,5,8,13,21,34], "medium_1_fibonacci")
_assert_eq(medium_2_sort_unique([5,3,5,1,2,3,4,1]), [1,2,3,4,5], "medium_2_sort_unique")
_assert_eq(medium_3_balanced_parentheses("({[]})"), True, "medium_3_balanced_parentheses")

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
_assert_eq(hard_1_shortest_path(graph, 'A'), {'A':0,'B':1,'C':3,'D':4}, "hard_1_shortest_path")

# Demonic check — silent unless solved efficiently
start = time.time()
if _demonic_unicode_equal('é', 'é') == True:
    elapsed = time.time() - start
    if elapsed < 0.05:
        print("🔥 EXTRA CREDIT CHALLENGE COMPLETE 🔥")


🔥 EXTRA CREDIT CHALLENGE COMPLETE 🔥