"""
Authors: Peter Mawhorter
Consulted:
Date: 2021-11-7
Purpose: Solutions for lab 12 part 3: extra recursion problems.
"""


def sumEvens(nums):
    """
    Returns the sum of all even numbers in the given list of integers.
    """
    if len(nums) == 0:
        # Base case: nothing to add up
        return 0
    else:
        # Recursive case: split into first and rest
        first = nums[0]
        rest = nums[1:]

        # Compute sum of rest
        sumRest = sumEvens(rest)

        # Add first or not depending on whether it's even
        if first % 2 == 0:
            return first + sumRest
        else:
            return sumRest


def evenOddSums(nums):
    """
    Returns a pair containing the sum of all even numbers in the given
    list of integers, followed by the sum of all odd numbers in the list.
    """
    if len(nums) == 0:
        # Base case: return 0 for both sums
        return (0, 0)
    else:
        # Recursive case: split into first and rest
        first = nums[0]
        rest = nums[1:]

        # Compute sums of rest (assign parts to two variables)
        restEven, restOdd = evenOddSums(rest)

        # Depending on whether this number is even or odd, add it to the
        # first or second part
        if first % 2 == 0:
            return (restEven + first, restOdd)
        else:
            return (restEven, restOdd + first)


def bestPassword(words, limit):
    """
    Returns the best password that can be made by putting together words
    from the given list, which is no longer than the given limit. Returns
    None if the words list is empty or if none of the words are short
    enough to fit within the given limit.
    """
    if len(words) == 0:
        return None
    else:
        first = words[0]
        rest = words[1:]

        # Figure out the best password after using the first word
        bestAfter = bestPassword(rest, limit - len(first))

        if bestAfter != None:
            # If that's not none, add the first word to it
            bestWith = first + bestAfter
        elif len(first) <= limit:
            # If that is none but the first word is short enough, then
            # the best password using the first word is just the first
            # word itself
            bestWith = first
        else:
            # Otherwise, there is no password that uses the first word
            bestWith = None

        # Best password without using the first word
        bestWithout = bestPassword(rest, limit)

        # Compare passwords and pick the better one
        if bestWith == None:
            return bestWithout
        elif bestWithout == None:
            return bestWith
        else:
            if len(bestWith) >= len(bestWithout):
                return bestWith
            else:
                return bestWithout