"""Functions to test for presence of certain recursively-defined structure in
strings"""
# MCS 275 Spring 2021 Project 2 Solutions
# Emily Dumas

def is_egg(s):
    """Is s a string of length 3 with the last two
    characters equal?"""
    return len(s)==3 and s[1]==s[2]


def is_superegg_recursive(s):
    """Use recursion to determine whether s is a string
    of the form A+B+B where A is a single character and B
    is a single character, or another string of this form."""
    if len(s) < 3:
        return False
    if len(s) == 3:
        return is_egg(s)
    if s[-1] != s[-2]:
        return False
    return is_superegg_recursive(s[:-2])


def is_superegg_iterative(s):
    """Check whether s is a string that ends with
    a sequence of repeated pairs of characters.  This
    is equal to the return value of is_superegg_recursive"""
    n = len(s)
    # supereggs have >=3 characters and odd length
    if n < 3 or n%2 == 0:
        return False
    # Loop to check that s[1:] consists of pairs of characters.
    # Rare appropriate use for range(...len(...)...)!
    # (but see below for another way to do it)
    for i in range(1,len(s),2):
        # Note: The length is odd, so s[i+1] exists!
        if s[i]!=s[i+1]:
            return False
    return True


def is_superegg_codegolf_edition(s):
    """Short iterative version of is_superegg."""
    # Bonus question 1: Why does this work?
    # Bonus question 2: Can you write a version that works
    # and has fewer characters than this?
    return len(s)>1 and len(s)%2 and s[1::2]==s[2::2]


def is_hyperegg(s):
    """Check whether s is a string of the form A+B+B
    where A and B are either single characters or other
    strings that have this form."""
    n = len(s)
    # hypereggs have >=3 characters and odd length
    if n < 3 or n%2 == 0:
        return False
    # Now we look for pattern A+B+B
    # But we don't know the length of A or B, so we need to try every
    # possibility.  Of course, the length of B determines that of A, so we just
    # loop over possible lengths of B.
    # Rare appropriate use for range(...len(...)...)!
    for lenB in range(1, n//2+1):
        B = s[-lenB:]         # Last `lenB` chars
        B2 = s[-2*lenB:-lenB] # The `lenB` chars before those
        if B != B2:
            continue
        A = s[:-2*lenB] # Everything before the two Bs
        if (len(A)==1 or is_hyperegg(A)) and (len(B)==1 or is_hyperegg(B)):
            return True
        # If we make it here, this splitting doesn't work so we just let the for
        # loop continue to the next iteration
    
    # The for loop finished, so no splitting worked.
    return False


# Bonus question 3: Why did I assign A *after* checking whether B==B2? Are there
# other statements in the loop body that could be similarly delayed for the same
# benefit?