import math

class Rational:
    """
    Represents a rational number its (integer) numerator and denominator, reduced.
    """
    num: int
    den: int
    
    def __init__(self, num: int, den: int) -> None:
        gcd = math.gcd(num, den)
        self.num = num // gcd
        self.den = den // gcd
        
    def __repr__(self) -> str:
        return f"{self.num}/{self.den}"
    
    def __add__(self, y):
        new_den = self.den * y.den
        new_num = self.num*y.den + y.num*self.den
        return Rational(new_num, new_den)
    
    def __sub__(self, y):
        return self + Rational(-y.num, y.den)
    
    def __mul__(self, y):
        return Rational(self.num*y.num, self.den*y.den)
    
    def __truediv__(self, y):
        #return Rational(self.num*y.den, self.den*y.num)
        return self * Rational(y.den, y.num)
    
print(Rational(1, 2) + Rational(1, 3))
print(Rational(1, 2) - Rational(1, 3))
print(Rational(1, 2) * Rational(1, 3))
print(Rational(1, 2) / Rational(1, 3))

5/6
1/6
1/6
3/2

def silly(x: int) -> int:
    return silly(x-1)

print(silly(42))

def factorial(n: int) -> int:
    """
    Returns n!
    """
    #print(f"factorial started ({n})")
    if n <= 1:
        #print(f"base case {n}")
        return 1
    else:
        #print(f"recursive case {n} started")
        s = factorial(n-1)
        r = n * s
        print(f"recursive case {n} finished, returned {s}")
        return r
    
print(factorial(5))

recursive case 2 finished, returned 1
recursive case 3 finished, returned 2
recursive case 4 finished, returned 6
recursive case 5 finished, returned 24
120

import typing

def sortedSearch(lst: list, needle: typing.Any) -> bool:
    """
    Returns True if needle is in lst. lst must be sorted.
    """
    print(f"Searching for {needle} in {lst}")
    if len(lst) == 0: # lst == []
        print("Base case 1: Empty list")
        return False
    midpoint = len(lst) // 2
    print(f"Comparing against midpoint ({midpoint}) == {lst[midpoint]}")
    if lst[midpoint] == needle:
        print("Base case 2: Midpoint is equal")
        return True
    elif lst[midpoint] < needle:
        print("Recursive case 1: Search right")
        return sortedSearch(lst[midpoint+1:], needle)
    else: # lst[midpoint] > needle
        print("Recursive case 2: Search left")
        return sortedSearch(lst[:midpoint], needle)
    
x = sorted([2, 4, 6, 0, 1, 8, 6, 5, 3, 0, 9])
print(x)
print(sortedSearch(x, 7))

[0, 0, 1, 2, 3, 4, 5, 6, 6, 8, 9]
Searching for 7 in [0, 0, 1, 2, 3, 4, 5, 6, 6, 8, 9]
Comparing against midpoint (5) == 4
Recursive case 1: Search right
Searching for 7 in [5, 6, 6, 8, 9]
Comparing against midpoint (2) == 6
Recursive case 1: Search right
Searching for 7 in [8, 9]
Comparing against midpoint (1) == 9
Recursive case 2: Search left
Searching for 7 in [8]
Comparing against midpoint (0) == 8
Recursive case 2: Search left
Searching for 7 in []
Base case 1: Empty list
False

def insertSortedPrime(lst: list, val: typing.Any, lb: int, ub: int) -> int:
    """
    Insert val into lst, sorted, between lb and ub. Returns index where val was inserted.
    """
    if ub == lb:
        lst.insert(lb, val)
        return lb
    midpoint = (ub - lb) // 2 + lb
    mid = lst[midpoint]
    if val < mid:
        return insertSortedPrime(lst, val, lb, midpoint)
    else:
        return insertSortedPrime(lst, val, midpoint+1, ub)

def insertSorted(lst: list, val: typing.Any) -> int:
    """
    Insert val into sorted list lst, keeping the list sorted.
    Returns the index where val was inserted.
    """
    return insertSortedPrime(lst, val, 0, len(lst))

x: list[int] = []
insertSorted(x, 2)
insertSorted(x, 4)
insertSorted(x, 6)
insertSorted(x, 0)
insertSorted(x, 1)
insertSorted(x, 8)
insertSorted(x, 6)
insertSorted(x, 7)
insertSorted(x, 5)
insertSorted(x, 3)
insertSorted(x, 0)
insertSorted(x, 9)
print(x)

[0, 0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9]