# CSCI 121: Computer Science Fundamentals
# SPRING 2026
#
# solutions to the practice final exam

#P1

def maxDigitHelper(number):
    # Recursive, just because.
    if number < 10:
        return number
    else:
        return max(number%10, maxDigitHelper(number//10))

def maxDigit(numbers):
    max_digit = None
    for number in numbers:
        digit = maxDigitHelper(number)
        if max_digit is None or digit > max_digit:
            max_digit = digit
    return max_digit

#P2

def unzipDict(d):
    ks = []
    vs = []
    for k in d:
        v = d[k]
        ks.append(k)
        vs.append(v)
    return [ks, vs]

#P3

seconds = int(input("Enter a time period in seconds: "))
minutes = seconds // 60
seconds = seconds % 60
hours = minutes // 60
minutes = minutes % 60

report = str(hours) + " hour"
if hours != 1:
    report += "s"
report += " " + str(minutes) + " minute"
if minutes != 1:
    report += "s"
report += " " + str(seconds) + " second"
if seconds != 1:
    report += "s"
    
print(report)

#P4

class Node:
    
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    
    def __init__(self):
        self.first = None
        
    def prepend(self, value):
        newNode = Node(value)
        newNode.next = self.first
        self.first = newNode

    def output(self):
        current = self.first
        while current is not None:
            print(current.value)
            current = current.next
  
    def appendSum(self):
        sum = 0
        previous = None
        current = self.first
        while current is not None:
            sum += current.value
            previous = current
            current = current.next
        if previous is None:
            self.first = Node(sum)
        else:
            previous.next = Node(sum)

#P5

def makeStringFormatter(text):
    def formatter(width):
        if len(text) > width:
            return text[:width]
        else:
            return text + (width - len(text)) * " "
    return formatter

#P6

class Socialite:
    def __init__(self, name, email):
        self.name = name
        self.email = email
        self.known = {}
        
    def meet(self, other):
        self.known[other.email] = other.name
        other.known[self.email] = self.name

    def contacts(self):
        for em in self.known:
            print(em, self.known[em])

#P7

class Animal:
    
    def __init__(self, id, species):
        self.id = id
        self.species = species
        self.hunger = 0
        self.energy = 100
        self.asleep = False
        
    def update(self):
        if self.asleep:
            self.energy += 1
            if self.energy >= 100:
                self.asleep = False
        else:
            self.energy -= 1
            if self.energy <= 0:
                self.asleep = True

    def eat(self, amount):
        if self.asleep:
            self.asleep = False
        self.hunger = max(0,self.hunger - amount)

class Elephant(Animal):
    
    def __init__(self, id):
        super().__init__(id, 'elephant')

    def eat(self, amount):
        if not self.asleep:
            super().eat(amount)

#P8

#a Theta(n)

#b Theta(n^2)

#c Theta(n^3)

# There was supposed to be "i -= 1" instead of "i += 1".
#d Theta(n log(n))

#P9

def firstMissing(xs):
    n = len(xs)
    if xs[0] != 1:
        return 1
    if xs[n-1] == n:
        return n+1
    left = 0
    right = n-1
    while left <= right:
        print(left,right)
        middle = (left + right) // 2
        if xs[middle] == middle+1:
            left = middle + 1
        else:
            right = middle - 1
    return left+1

#P10

class BSTNode:
    
    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None
        
class BSTree:
    def __init__(self):
        self.root = None
        
    def insert(self, k):
        p = None
        n = self.root
        while n is not None:
            p = n
            if n.key == k:
                return
            elif n.key > k:
                n = n.left
            else:
                n = n.right
        e = BSTNode(k)
        if p is None:
            self.root = e
        elif p.key > k:
            p.left = e
        else:
            p.right = e
    
    def maxResult(self, f):
        
        def maxh(a,b):
            # allows b to be None
            if b is None:
                return a
            else:
                return max(a,b)
        
        def helper(n):
            if n is None:
                return None
            else:
                mx = f(n.key)
                mx = maxh(mx, helper(n.left))
                mx = maxh(mx, helper(n.right))
                return mx

        return helper(self.root)

# BONUS

def firstError(f, n):
    x = 0
    while x <= n:
        try:
            f(x)
        except:
            return x
        x += 1
    return None