# Principled Programming / Tim Teitelbaum / Chapter 7.

def e7_1_1() -> None:
        """Primality Testing: Given p≥2, output whether p is prime or composite."""
        p: int = 15

    # Search. Let d≥2 be the smallest divisor of p.
        d: int = 2
        while (p % d) != 0: d += 1
    # Discriminate based on search result.
        if d == p:
            print(p, "is prime")
        else:
            print(p, "is composite")

def e7_2_1() -> None:
        """Search in an Unordered Array."""
        A: list[int] = [10, 20, 30]
        n: int = len(A)
        v: int = 40

    # Given array A[0..n-1], n≥0, and value v, let k be the smallest non-negative integer s.t. A[k]==v,
    # or let k==n if there are no occurrences of v in A.
        k: int = 0
        while k < n and A[k] != v: k += 1

    # Output location of v in A.
        if k == n: print(v, "does not occur in", A)
        else: print(v, "occurs at index", k, "in", A)

def e7_2_2() -> None:
    """Let k be the smallest index in A[0..n-1] s.t. A[k] is even, or n if all A[0..n-1] are odd."""
    A: list[int] = [1, 3, 5, 7, 2, 4, 6, 8]
    n: int = len(A)

    k: int = 0
    while k < n and (A[k] % 2) != 0: k += 1

    if k == n: print("No value in", A, "is even")
    else: print("The first index at which an even int occurs in", A, "is", k, "and it's value is", A[k])

def e7_3_1() -> None:
        """Array Equality: Given arrays A[0..n-1] and B[0..n-1], set e to true if A equals B, else set e to false."""
        A: list[int] = [1,3,5,7,2,4,6,8]
        B: list[int] = [1,3,5,7,2,44,6,8]
        n: int = len(A)
        e: bool

    # Let k≥0 be smallest s.t. A[k]!=B[k], or n if A equals B.
        k: int = 0
        while k<n and A[k]==B[k]: k += 1
        if k == n: e = True
        else: e = False
            
        print("It is", e, "that", A, "and", B, "are equal.")

def e7_4_1() -> None:
    """
    Sentinel Search: Let k be an index in A[0..n-1] containing v, or n if no v in A.
    Assume an A[n] DOES exist, and you are free to destroy it.
    """
    A: list[int] = [10, 20, 30, -100]
    n: int  = 3
    v: int  = 40

    A[n] = v
    k = 0
    while A[k] != v: k += 1

    if k == n:
       print(v, "does not occur in", A[0:n])
    else:
       print(v, "occurs at index", k, "in", A[0:n])

def e7_4_2() -> None:
    """
    Sentinel Search:Let k be an index in A[0..n-1] containing v, or n if no v in A.
    Assume A[n] does NOT exist, i.e., the value in A[n] must be preserved.
    """
    A: list[int] = [10, 20, 30]
    n: int  = 3
    v: int  = 40
      
    temp: int  = A[n-1]
    A[n-1] = v                       # Save A[n-1]. Replace it with v.
    k: int  = 0
    while A[k]!=v: k += 1
    A[n-1] = temp                    # Restore A[n-1].
    if k==n-1 and A[n-1]!=v : k = n; # Test A[n-1] when sentinel found.
     
    if k == n:
       print(v, "does not occur in", A[0:n])
    else:
       print(v, "occurs at index", k, "in", A[0:n])

def e7_4_3() -> None:
    """Given A[0..n-1], set j so that A[j+1..n-1] is the longest descending suffix of A[0..n-1]."""
    A: list[int] = [30, 40, 50, 20, 10]
    n: int = len(A)

    print("The longest descending suffix of", A, "begins at index", end='')
    j = n - 2
    while (j >= 0) and (A[j] >= A[j+1]): j -= 1
    print(j+1)


def e7_5_1() -> None:
    """Find Minimal: Given A[0..n-1], find k s.t. A[k] is minimal in A[0..n-1]. Assume n>0."""
    A: list[int] = [10, 20, 30, 5, 15, 25]
    n: int = len(A)

    k: int = 0
    for j in range(1, n):
        if A[j] < A[k]: k = j

    print("The smallest value in", A, "is", A[k], "and occurs at index", k)

def e7_5_2() -> None:
    """
    Given A[0..n-1], find k s.t. A[k] is minimal in A[0..n-1].
    Do NOT assume n>0. Rather, set k to -1 if n=0.
    """
    A: list[int]= [10, 20, 30, 5, 15, 25]
    n: int = len(A)

    k: int = -1
    if n != 0:
        k = 0
        for j in range(1, n):
            if A[j] < A[k]: k = j

    if k == -1: print("The array is empty, and therefore has no minimal element")
    else: print("The smallest value in", A, "is", A[k], "and occurs at index", k)

def e7_5_3() -> None:
    """
    Function minimalization: Given int-valued function s(j) defined on non-empty int domain
    first through last, let k in that domain be s.t. S(k) is minimal.
    """
    def s(m: int) -> int: return -m * m
    first: int = -2
    last: int = +3

    k: int = first
    minS: int = s(first)
    for j in range(first + 1, last + 1):
        v: int = s(j)
        if v < minS: minS = v; k = j

    print("A value in the domain of s at which s is minimal is", k, "at which s is", s(k))

# Uncomment to run.
#e7_1_1()
#e7_2_1()
#e7_2_2()
#e7_3_1()
#e7_4_1()
#e7_4_2()
#e7_4_3()
#e7_5_1()
#e7_5_2()
#e7_5_3()