def linear_search(data, target):
    # Check every element one by one
    for index, value in enumerate(data):
        if value == target:
            return index    # found — return position
    return -1             # -1 means not found

# ── Example usage ─────────────────────────────
scores = [45, 72, 13, 88, 56, 34]
pos = linear_search(scores, 88)

if pos != -1:
    print(f"Found at index {pos}")   # Found at index 3
else:
    print("Not found")

# ── Iterative version (preferred in exams) ─────
def binary_search(data, target):
    low  = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2          # integer division

        if   data[mid] == target: return mid
        elif data[mid] <  target: low  = mid + 1   # go right
        else:                      high = mid - 1   # go left
    return -1

# ── Recursive version ──────────────────────────
def binary_search_rec(data, target, low, high):
    if low > high: return -1           # base case: not found
    mid = (low + high) // 2
    if   data[mid] == target: return mid
    elif data[mid] <  target:
        return binary_search_rec(data, target, mid+1, high)
    else:
        return binary_search_rec(data, target, low, mid-1)

# ── Usage ──────────────────────────────────────
nums = [10, 23, 35, 42, 55, 67, 80, 91]
print(binary_search(nums, 55))  # 4
print(binary_search(nums, 99))  # -1 (not found)

def bubble_sort(data):
    n = len(data)
    for pass_num in range(n - 1):
        swapped = False                   # early-exit flag

        for i in range(n - 1 - pass_num): # window shrinks each pass
            if data[i] > data[i + 1]:
                # Python tuple swap — no temp variable needed
                data[i], data[i + 1] = data[i + 1], data[i]
                swapped = True

        if not swapped:                   # no swaps = already sorted
            break
    return data

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]     # element to place correctly
        j   = i - 1       # look backwards into sorted part

        # Shift elements right while they're larger than key
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1

        data[j + 1] = key  # drop key into the gap
    return data

# Trace for [5, 3, 8, 1, 2]:
# i=1 key=3: [3, 5, 8, 1, 2]
# i=2 key=8: [3, 5, 8, 1, 2]  (no shift needed)
# i=3 key=1: [1, 3, 5, 8, 2]
# i=4 key=2: [1, 2, 3, 5, 8]  ✓

class Stack:
    def __init__(self, max_size=10):
        self._items    = []
        self._max_size = max_size

    def push(self, item):
        if self.is_full():
            raise OverflowError("Stack is full")
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()     # removes AND returns top

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]      # view top without removing

    def is_empty(self): return len(self._items) == 0
    def is_full(self):  return len(self._items) == self._max_size
    def size(self):     return len(self._items)

    def __str__(self):
        return f"Stack(top→{self._items[::-1]})"

def rpn_evaluate(expression):
    """Evaluate Reverse Polish Notation using a stack"""
    s = Stack()
    for token in expression.split():
        if token.lstrip('-').isdigit():
            s.push(int(token))
        else:
            b, a = s.pop(), s.pop()
            if   token == '+': s.push(a + b)
            elif token == '-': s.push(a - b)
            elif token == '*': s.push(a * b)
            elif token == '/': s.push(a // b)
    return s.pop()

print(rpn_evaluate("3 4 + 5 *"))   # (3+4)*5 = 35

from collections import deque   # O(1) front removal vs list's O(n)

class Queue:
    def __init__(self, max_size=10):
        self._items    = deque()
        self._max_size = max_size

    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("Queue is full")
        self._items.append(item)       # add to rear

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._items.popleft()   # remove from front — O(1)

    def peek(self):     return self._items[0]
    def is_empty(self): return len(self._items) == 0
    def is_full(self):  return len(self._items) == self._max_size
    def size(self):     return len(self._items)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None    # pointer to next node

class LinkedList:
    def __init__(self):
        self.head = None

    # Append to end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node; return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    # Insert at front — O(1)
    def insert_at_head(self, data):
        node      = Node(data)
        node.next = self.head
        self.head = node

    # Delete first match
    def delete(self, target):
        if not self.head: return
        if self.head.data == target:
            self.head = self.head.next; return
        curr = self.head
        while curr.next:
            if curr.next.data == target:
                curr.next = curr.next.next  # bypass the node
                return
            curr = curr.next

    # Search — returns True/False
    def find(self, target):
        curr = self.head
        while curr:
            if curr.data == target: return True
            curr = curr.next
        return False

    # Convert to Python list for printing
    def to_list(self):
        res, curr = [], self.head
        while curr:
            res.append(curr.data)
            curr = curr.next
        return res

class TreeNode:
    def __init__(self, data):
        self.data  = data
        self.left  = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    # ── Insert ────────────────────────────────────
    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if not node:
            return TreeNode(data)              # base case: empty spot
        if data < node.data:
            node.left  = self._insert(node.left,  data)
        elif data > node.data:
            node.right = self._insert(node.right, data)
        return node

    # ── Search ────────────────────────────────────
    def search(self, data):
        return self._search(self.root, data)

    def _search(self, node, data):
        if not node:           return False
        if data == node.data:  return True
        if data <  node.data:  return self._search(node.left,  data)
        return self._search(node.right, data)

    # ── In-order: Left → Node → Right (sorted output)
    def inorder(self, node=None):
        if node is None: node = self.root
        if not node: return []
        return self.inorder(node.left) + [node.data] + self.inorder(node.right)

    # ── Pre-order: Node → Left → Right (copy/serialise)
    def preorder(self, node=None):
        if node is None: node = self.root
        if not node: return []
        return [node.data] + self.preorder(node.left) + self.preorder(node.right)

# ── Usage ─────────────────────────────────────
tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)

print(tree.inorder())    # [20, 30, 40, 50, 60, 70, 80]
print(tree.search(40))   # True
print(tree.search(99))   # False

# ── Creating ───────────────────────────────────
grades = {"Alice": 91, "Bob": 78, "Charlie": 85}
empty  = {}

# ── Insert / update ────────────────────────────
grades["Diana"] = 95         # insert new key
grades["Bob"]   = 82         # update existing key

# ── Safe lookup with .get() ────────────────────
print(grades.get("Alice", "Not found"))  # 91
print(grades.get("Zara",  "Not found"))  # Not found

# ── Membership test — use 'in' on keys ─────────
if "Alice" in grades:
    print("Alice is in the dict")

# ── Delete ─────────────────────────────────────
del grades["Bob"]

# ── Iterating ──────────────────────────────────
for name, score in grades.items():    # key-value pairs
    print(f"{name}: {score}")

for name  in grades.keys():           # just keys
    print(name)

for score in grades.values():         # just values
    print(score)

# ── Useful patterns ────────────────────────────
# Count frequency of items
text   = "hello world"
counts = {}
for ch in text:
    counts[ch] = counts.get(ch, 0) + 1

# Group items by category
students = [("Alice","A"), ("Bob","B"), ("Carol","A")]
by_grade = {}
for name, grade in students:
    by_grade.setdefault(grade, []).append(name)
# {'A': ['Alice', 'Carol'], 'B': ['Bob']}

# O(1) — single operation regardless of n
def get_first(lst): return lst[0]

# O(n) — one loop through all n items
def find_max(lst):
    m = lst[0]
    for x in lst: m = max(m, x)
    return m

# O(n²) — nested loops, both iterate over n
def has_duplicate_slow(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]: return True
    return False

# O(n) — same task, using a set instead
def has_duplicate_fast(lst):
    return len(lst) != len(set(lst))

# How to count: 3 nested loops → O(n³)
# Two independent loops → O(n + n) = O(n)
# Always drop constants: O(5n) → O(n)

def factorial(n):
    if n == 0 or n == 1:
        return 1                         # BASE CASE
    return n * factorial(n - 1)        # RECURSIVE CASE

# ── Call stack for factorial(4) ────────────────
# factorial(4) → 4 * factorial(3)   [frame 1]
#   factorial(3) → 3 * factorial(2) [frame 2]
#     factorial(2) → 2 * factorial(1) [frame 3]
#       factorial(1) → 1             [BASE CASE]
# Stack unwinds:
#   factorial(2) = 2 * 1 = 2
#   factorial(3) = 3 * 2 = 6
#   factorial(4) = 4 * 6 = 24  ✓

# Naive — O(2ⁿ), recalculates same values repeatedly
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Memoised — O(n), caches results to avoid repetition
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1:   return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Or use Python's built-in decorator:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1: return n
    return fib_cached(n-1) + fib_cached(n-2)

# ── Sum of a list ──────────────────────────────
def rec_sum(lst):
    if not lst: return 0                   # base case: empty list
    return lst[0] + rec_sum(lst[1:])       # head + sum of tail

# ── Power (x to the n) ─────────────────────────
def power(x, n):
    if n == 0: return 1                    # base: x⁰ = 1
    return x * power(x, n - 1)

# ── Flatten nested list ────────────────────────
def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse on sub-list
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4], 5], 6]))   # [1,2,3,4,5,6]

# ── Tower of Hanoi ─────────────────────────────
def hanoi(n, source, target, aux):
    if n == 1:
        print(f"Move disk 1: {source} → {target}")
        return
    hanoi(n-1, source, aux,    target)   # move n-1 to aux
    print(f"Move disk {n}: {source} → {target}")
    hanoi(n-1, aux,    target, source)   # move n-1 from aux

class BankAccount:
    interest_rate = 0.03    # class variable — shared by all instances

    def __init__(self, owner, balance=0):
        self._owner   = owner      # _ prefix = private (convention)
        self._balance = balance

    # Getter via @property — access like an attribute
    @property
    def balance(self):
        return self._balance

    # Setter with validation
    @balance.setter
    def balance(self, value):
        if value < 0: raise ValueError("Balance cannot be negative")
        self._balance = value

    def deposit(self, amount):
        if amount <= 0: raise ValueError("Amount must be positive")
        self._balance += amount

    def withdraw(self, amount):
        if amount > self._balance:
            raise ValueError("Insufficient funds")
        self._balance -= amount

    def apply_interest(self):
        self._balance *= (1 + BankAccount.interest_rate)

    def __str__(self):
        return f"{self._owner}: £{self._balance:.2f}"

# ── Usage ──────────────────────────────────────
acc = BankAccount("Alice", 1000)
acc.deposit(500)
acc.withdraw(200)
acc.apply_interest()
print(acc)              # Alice: £1339.00
print(acc.balance)      # 1339.0  (via @property)

# ── Parent class ───────────────────────────────
class Shape:
    def __init__(self, colour):
        self.colour = colour

    def area(self):
        return 0    # meant to be overridden

    def describe(self):
        return f"{self.colour} shape, area = {self.area():.2f}"

# ── Child classes ──────────────────────────────
class Circle(Shape):
    def __init__(self, colour, radius):
        super().__init__(colour)        # call parent __init__
        self.radius = radius

    def area(self):                     # override parent method
        return 3.14159 * self.radius ** 2

class Rectangle(Shape):
    def __init__(self, colour, width, height):
        super().__init__(colour)
        self.width  = width
        self.height = height

    def area(self):
        return self.width * self.height

# ── Polymorphism — same method, different result
shapes = [Circle("red", 5), Rectangle("blue", 4, 6)]
for s in shapes:
    print(s.describe())
# red shape, area = 78.54
# blue shape, area = 24.00

# isinstance — check type safely
for s in shapes:
    if isinstance(s, Circle):
        print(f"Radius: {s.radius}")

class Address:
    def __init__(self, street, city, postcode):
        self.street   = street
        self.city     = city
        self.postcode = postcode
    def __str__(self):
        return f"{self.street}, {self.city} {self.postcode}"

class Person:
    def __init__(self, name, address):
        self.name    = name
        self.address = address    # Person HAS-A Address
    def __str__(self):
        return f"{self.name} at {self.address}"

addr = Address("10 Baker St", "London", "NW1 6XE")
p    = Person("Holmes", addr)
print(p)   # Holmes at 10 Baker St, London NW1 6XE

# ── Write ──────────────────────────────────────
with open("students.txt", "w") as f:   # 'with' auto-closes file
    f.write("Alice,91\n")
    f.write("Bob,78\n")
    f.write("Charlie,85\n")

# ── Read line by line ──────────────────────────
with open("students.txt", "r") as f:
    for line in f:                        # memory-efficient
        name, score = line.strip().split(",")
        print(f"{name} scored {score}")

# ── Append ─────────────────────────────────────
with open("students.txt", "a") as f:
    f.write("Diana,95\n")

# ── Update a specific record ───────────────────
def update_score(filename, name_to_update, new_score):
    with open(filename, "r") as f:
        lines = f.readlines()          # read all into memory

    with open(filename, "w") as f:   # rewrite entire file
        for line in lines:
            name, _ = line.strip().split(",")
            if name == name_to_update:
                f.write(f"{name},{new_score}\n")
            else:
                f.write(line)

import csv

# ── Write CSV ──────────────────────────────────
with open("records.csv", "w", newline="") as f:
    writer = csv.writer(f)
    writer.writerow(["Name", "Age", "Grade"])   # header row
    writer.writerow(["Alice", 17, "A"])
    writer.writerow(["Bob",   18, "B"])

# ── Read CSV as dicts (column names as keys) ───
with open("records.csv", "r") as f:
    reader = csv.DictReader(f)
    for row in reader:
        print(row["Name"], row["Grade"])

try:
    x = int(input("Enter a number: "))
    result = 100 / x

except ValueError:
    print("That wasn't a valid integer")

except ZeroDivisionError:
    print("Cannot divide by zero")

except Exception as e:               # catch-all fallback
    print(f"Unexpected error: {e}")

else:                                 # runs ONLY if no exception was raised
    print(f"Result: {result}")

finally:                              # ALWAYS runs — use for cleanup
    print("Done.")

# ── Common exception types ─────────────────────
# ValueError        int("abc"), float("x")
# ZeroDivisionError 5 / 0
# IndexError        lst[100] when len < 100
# KeyError          d["missing_key"]
# FileNotFoundError open("no_file.txt")
# TypeError         "hi" + 5
# OverflowError     very large numbers

# ── Define a custom exception ──────────────────
class InsufficientFundsError(Exception):
    def __init__(self, amount, balance):
        self.amount  = amount
        self.balance = balance
        super().__init__(
            f"Cannot withdraw £{amount}, balance is £{balance}")

def withdraw(balance, amount):
    if amount > balance:
        raise InsufficientFundsError(amount, balance)
    return balance - amount

try:
    withdraw(100, 250)
except InsufficientFundsError as e:
    print(e)   # Cannot withdraw £250, balance is £100

# ── Validated input loop (very common in exams)
def get_positive_int(prompt):
    while True:
        try:
            n = int(input(prompt))
            if n <= 0: raise ValueError
            return n
        except ValueError:
            print("Please enter a positive integer.")

# ── Safe file read ─────────────────────────────
def safe_read(filename):
    try:
        with open(filename, "r") as f:
            return f.read()
    except FileNotFoundError:
        print(f"File '{filename}' not found")
        return None