Seminar 3: Python Basics II — Data Structures

# --- List creation ---
empty_list = []
numbers = [4, 2, 7, 1, 9, 3, 6]
mixed = [1, "hello", 3.14, True, None]   # heterogeneous (avoid in practice)
from_range = range(1, 8)

print(f"numbers: {numbers}")
print(f"from_range: {from_range}")

# --- Indexing ---
print(f"\nnumbers[0]  = {numbers[0]}"    )  # first element
print(f"numbers[-1] = {numbers[-1]}")     # last element  (negative indexing)
print(f"numbers[-2] = {numbers[-2]}")     # second-to-last

# --- Slicing: lst[start:stop:step] ---
print(f"\nnumbers[2:5]   = {numbers[2:5]}"   )  # indices 2,3,4
print(f"numbers[:3]    = {numbers[:3]}"    )  # first 3
print(f"numbers[4:]    = {numbers[4:]}"    )  # from index 4 to end
print(f"numbers[::2]   = {numbers[::2]}"   )  # every 2nd element
print(f"numbers[::-1]  = {numbers[::-1]}"  )  # reversed!

# --- Mutating methods ---
lst = [3, 1, 4, 1, 5, 9, 2, 6]
print(f"\nOriginal: {lst}")

lst.append(7)         # add to end
print(f"After append(7):       {lst}")

lst.insert(0, 0)      # insert 0 at index 0
print(f"After insert(0, 0):    {lst}")

removed = lst.pop()   # removes and returns the last element
print(f"After pop():           {lst}  (removed: {removed})")

lst.remove(1)         # removes first occurrence of 1
print(f"After remove(1):       {lst}")

lst.sort()            # in-place sort (modifies lst)
print(f"After sort():          {lst}")

sorted_copy = sorted(numbers)  # sorted() returns a NEW list
print(f"sorted(numbers):       {sorted_copy}   (original unchanged: {numbers})")

lst.reverse()         # in-place reverse
print(f"After reverse():       {lst}")

# --- Useful functions ---
print(f"\nlen(numbers) = {len(numbers)}")
print(f"sum(numbers) = {sum(numbers)}")
print(f"min(numbers) = {min(numbers)}")
print(f"max(numbers) = {max(numbers)}")
print(f"9 in numbers: {9 in numbers}")
print(f"numbers.index(9): {numbers.index(9)}")  # first index of value 9
print(f"numbers.count(9): {numbers.count(9)}")   # how many times 9 appears

# --- Tuple creation ---
empty_tuple = ()          # or: tuple()
single = (42,)            # ONE-element tuple needs a trailing comma!
point_2d = (3.0, 7.5)
rgb = (255, 128, 0)       # orange colour
record = ("Alice", 21, "CS")  # student record

print(f"point_2d: {point_2d}")
print(f"rgb:      {rgb}")
print(f"record:   {record}")

# Single element gotcha:
not_a_tuple = (42)     # This is just the integer 42 in parentheses
is_a_tuple  = (42,)    # This is a tuple with one element
print(f"\n(42)  → type: {type(not_a_tuple)}")
print(f"(42,) → type: {type(is_a_tuple)}")

# --- Indexing (same as lists) ---
print(f"\npoint_2d[0] = {point_2d[0]}")
print(f"point_2d[1] = {point_2d[1]}")
print(f"record[-1]  = {record[-1]}")  # last element

# --- Immutability ---
try:
    point_2d[0] = 99   # TypeError!
except TypeError as e:
    print(f"\nTypeError: {e}")

# --- Unpacking ---
x, y = point_2d
print(f"\nUnpacked point: x={x}, y={y}")

name, age, major = record
print(f"Unpacked record: name={name}, age={age}, major={major}")

# Extended unpacking with *
first, *rest = [1, 2, 3, 4, 5]
print(f"\nfirst={first}, rest={rest}")

*beginning, last = [1, 2, 3, 4, 5]
print(f"beginning={beginning}, last={last}")

# --- Pythonic swap ---
a, b = 10, 20
print(f"\nBefore swap: a={a}, b={b}")
a, b = b, a   # tuple packing/unpacking under the hood
print(f"After swap:  a={a}, b={b}")

# --- Functions returning multiple values (tuples) ---
def min_and_max(lst):
    """Return (minimum, maximum) of a list."""
    return min(lst), max(lst)   # returns a tuple


data = [4, 2, 9, 1, 7]
lo, hi = min_and_max(data)    # unpack the returned tuple
print(f"\nData: {data}")
print(f"min={lo}, max={hi}")

from collections import Counter

# --- Creating dicts ---
empty_dict = {}
student = {"name": "Alice", "age": 21, "major": "CS", "gpa": 3.8}
from_pairs = dict([("a", 1), ("b", 2), ("c", 3)])  # from list of tuples
using_dict = dict(x=10, y=20)  # keyword arguments

print(f"student:     {student}")
print(f"from_pairs:  {from_pairs}")

# --- Access ---
print(f"\nstudent['name'] = {student['name']}")

# .get() is safer: returns None (or a default) if key doesn't exist
print(f"student.get('gpa')        = {student.get('gpa')}")
print(f"student.get('phone')      = {student.get('phone')}")
print(f"student.get('phone', 'N/A') = {student.get('phone', 'N/A')}")

# --- Modify / add / delete ---
student["age"] = 22           # modify existing key
student["email"] = "a@unige.ch" # add new key
del student["major"]          # delete a key
print(f"\nModified student: {student}")

popped = student.pop("email")  # remove and return a value
print(f"Popped email: {popped}")

# --- Iteration ---
print("\nIterating:")
for key in student.keys():         # or just: for key in student
    print(f"  key: {key}")

for value in student.values():
    print(f"  value: {value}")

for key, value in student.items():  # most common — unpack both
    print(f"  {key}: {value}")

# --- Nested dicts ---
course_db = {
    "CS101": {"name": "Algorithmics", "students": 45, "instructor": "Prof. Smith"},
    "CS201": {"name": "Databases",    "students": 38, "instructor": "Prof. Jones"},
}
print(f"\nCS101 instructor: {course_db['CS101']['instructor']}")

# --- dict comprehension ---
word_lengths = {word: len(word) for word in ["hello", "world", "python"]}
print(f"Word lengths: {word_lengths}")

# --- Frequency counter (important pattern!) ---
sentence = "the quick brown fox jumps over the lazy dog"
word_freq = {}
for word in sentence.split():
    word_freq[word] = word_freq.get(word, 0) + 1

print(f"\nWord frequencies: {word_freq}")

# Tip: Python's collections.Counter does this automatically:
counter = Counter(sentence.split())
print(f"Most common 3: {counter.most_common(3)}")

# --- Creating sets ---
from_list = set([1, 2, 2, 3, 3, 3])   # duplicates removed!
print(f"from_list: {from_list}  (duplicates removed)")

# --- Uniqueness ---
words = ["apple", "banana", "apple", "cherry", "banana", "date"]
unique_words = set(words)
print(f"\nOriginal list: {words}")
print(f"Unique set:    {unique_words}")

# --- Add / remove ---
s = {1, 2, 3}
s.add(4)        # add one element
s.add(2)        # adding an existing element is a no-op
s.discard(10)   # discard: no error if element not present
print(f"\nAfter add(4) and add(2): {s}")

# --- Set operations ---
a = {1, 2, 3, 4, 5}
b = {4, 5, 6, 7, 8}

print(f"\na = {a}")
print(f"b = {b}")
print(f"a | b  (union):              {a | b}")
print(f"a & b  (intersection):       {a & b}")
print(f"a - b  (difference A\\B):     {a - b}")
print(f"b - a  (difference B\\A):     {b - a}")
print(f"a ^ b  (symmetric diff):     {a ^ b}")

# --- Subset / superset ---
small = {2, 3}
large = {1, 2, 3, 4}
print(f"\n{small} is subset of {large}: {small <= large}")
print(f"{large} is superset of {small}: {large >= small}")

# --- Membership test: O(1) vs list O(n) ---
import timeit

big_list = list(range(100_000))
big_set = set(big_list)

list_time = timeit.timeit("99_999 in big_list", globals=globals(), number=10_000)
set_time  = timeit.timeit("99_999 in big_set",  globals=globals(), number=10_000)

print(f"\nMembership test (100k elements, 10k repetitions):")
print(f"  list: {list_time:.4f}s")
print(f"  set:  {set_time:.6f}s")
print(f"  Speedup: {list_time / set_time:.0f}x")

# --- CORE: positional + default parameters ---
def greet(name, greeting="Hello"):
    """Return a greeting string."""
    return f"{greeting}, {name}!"


print(greet("Alice"))                       # uses default greeting
print(greet("Bob", "Good morning"))         # overrides default
print(greet(greeting="Hi", name="Carol"))    # keyword arguments


# --- CORE: return values + type hints ---
def add(a: int, b: int) -> int:
    """Add two integers and return the result."""
    return a + b


print(f"add(3, 4) = {add(3, 4)}")


# --- BONUS: *args and **kwargs (optional today) ---
def my_sum(*args):
    """Sum any number of arguments."""
    total = 0
    for num in args:
        total += num
    return total


def print_info(**kwargs):
    """Print key-value pairs from keyword arguments."""
    for key, value in kwargs.items():
        print(f"  {key}: {value}")


print(f"my_sum(1, 2, 3) = {my_sum(1, 2, 3)}")
print("Student info:")
print_info(name="Alice", age=21, gpa=3.8)


# Optional one-liner example used often in sorting
students = [("Alice", 3.8), ("Bob", 3.5), ("Carol", 3.9)]
students.sort(key=lambda s: s[1], reverse=True)
print(f"Sorted by GPA: {students}")

# --- A complete class example: BankAccount ---

class BankAccount:
    """A simple bank account with deposit, withdraw, and balance query."""

    bank_name = "University Bank"   # class variable (shared by all instances)
    MIN_BALANCE = 0.0                # class-level constant

    def __init__(self, owner: str, initial_balance: float = 0.0):
        """Constructor: initialise a newly created account object."""
        if initial_balance < self.MIN_BALANCE:
            raise ValueError("Initial balance cannot be negative")
        self.owner = owner               # instance attribute (specific object)
        self._balance = initial_balance
        self._transactions = []

    def deposit(self, amount: float) -> None:
        if amount <= 0:
            raise ValueError("Deposit amount must be positive")
        self._balance += amount
        self._transactions.append(("deposit", amount))

    def withdraw(self, amount: float) -> None:
        if amount <= 0:
            raise ValueError("Withdrawal amount must be positive")
        if amount > self._balance:
            raise ValueError(f"Insufficient funds (balance: {self._balance:.2f})")
        self._balance -= amount
        self._transactions.append(("withdrawal", -amount))

    @property
    def balance(self) -> float:
        return self._balance

    def get_history(self) -> list:
        return list(self._transactions)

    def label(self) -> str:
        # Access class variable from inside the class
        return f"{self.owner} @ {self.__class__.bank_name}"

    def __str__(self) -> str:
        return f"[{self.bank_name}] {self.owner}'s account — Balance: CHF {self._balance:,.2f}"


# --- Using the class ---
alice_account = BankAccount("Alice", initial_balance=1000.0)
bob_account = BankAccount("Bob", initial_balance=500.0)

print(alice_account)
print(bob_account)
print()

# Class variable access: via class and via objects
print(f"Bank name from class: {BankAccount.bank_name}")
print(f"Bank name via alice:  {alice_account.bank_name}")
print(f"Label via method:     {alice_account.label()}")

print()
alice_account.deposit(500.0)
alice_account.withdraw(200.0)

print(f"Balance after transactions: CHF {alice_account.balance:,.2f}")
print("Transaction history:")
for txn_type, amount in alice_account.get_history():
    sign = "+" if amount > 0 else ""
    print(f"  {txn_type:<12}: {sign}CHF {amount:,.2f}")

print()
try:
    alice_account.withdraw(10_000)
except ValueError as e:
    print(f"Caught ValueError: {e}")

# Exercise 1 — Comprehension warm-up

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
words = ["hi", "hello", "hey", "algorithmics", "data", "structures", "AI"]
sentence = "the quick brown fox jumps over the lazy fox"

# TODO 1
sorted_unique = None

# TODO 2
word_lengths = None

# TODO 3
repeated_words = None

print("sorted_unique:", sorted_unique)
print("word_lengths:", word_lengths)
print("repeated_words:", repeated_words)

# Quick checks (uncomment after solving)
# assert sorted_unique == [1, 2, 3, 4, 5, 6, 9]
# assert word_lengths["hello"] == 5 and "hi" not in word_lengths
# assert repeated_words == {"the", "fox"}

# Exercise 2 — Character frequency counter

def char_frequency(text):
    # TODO: implement
    # Step 1: normalise case with text.lower()
    # Step 2: skip spaces
    # Step 3: count with a dict and .get(char, 0) + 1
    pass


sample = "Data Structures"
freq = char_frequency(sample)

# TODO: create sorted_items as list of (char, count), most common first
sorted_items = None

print("freq:", freq)
print("sorted_items:", sorted_items)

# Quick checks (uncomment after solving)
# assert freq["t"] == 3
# assert " " not in freq
# assert sorted_items[0][1] >= sorted_items[-1][1]

# Exercise 3 — Remove duplicates without set()

def remove_duplicates(lst):
    # TODO: implement
    # Keep first appearance only, preserve order
    pass


data = [3, 1, 3, 2, 1, 4, 2, 5]
result = remove_duplicates(data)
print("result:", result)

# Quick checks (uncomment after solving)
# assert result == [3, 1, 2, 4, 5]
# assert remove_duplicates([]) == []

# Exercise 4 — Merge two dictionaries

def merge_dicts_loop(d1, d2):
    # TODO: core implementation with loops
    pass


def merge_dicts_update(d1, d2):
    # TODO: core implementation with .update()
    pass


# BONUS
# def merge_dicts_unpack(d1, d2):
#     return {**d1, **d2}


a = {"x": 1, "y": 2}
b = {"y": 99, "z": 3}

print("loop:  ", merge_dicts_loop(a, b))
print("update:", merge_dicts_update(a, b))

# Quick checks (uncomment after solving)
# assert merge_dicts_loop(a, b) == {"x": 1, "y": 99, "z": 3}
# assert merge_dicts_update(a, b) == {"x": 1, "y": 99, "z": 3}

# Exercise 5 — Student class

# Step A (bridge): function first

def is_passing_average(grades_dict, threshold=50):
    # TODO: implement
    pass


# Step B (core): class
class Student:
    def __init__(self, name, student_id):
        self.name = name
        self.student_id = student_id
        self.grades = {}

    def add_grade(self, subject, score):
        # TODO: validate 0..100 and store
        pass

    def average_grade(self):
        # TODO: average of grades dict values
        pass

    def is_passing(self, threshold=50):
        # TODO: use average_grade()
        pass

    def __str__(self):
        # TODO: return readable one-line summary
        pass

    # BONUS
    # def best_subject(self):
    #     pass
    #
    # def report(self):
    #     pass
    #
    # def __repr__(self):
    #     pass


s = Student("Alice", "S123")
s.add_grade("Math", 80)
s.add_grade("Algorithms", 70)

print(s)
print("Average:", s.average_grade())
print("Passing:", s.is_passing())

# Quick checks (uncomment after solving)
# assert is_passing_average({"Math": 80, "Algo": 40}, threshold=60) is True
# assert round(s.average_grade(), 2) == 75.0
# assert s.is_passing(76) is False