"""CS 61A HW 05
Name:
Login:
TA:
Section:
"""


from irlist import *
from idict import *
from functools import reduce


def is_tuple(x):
    return type(x) is tuple


#### Q1
def to_irlist(items):
    """The sequence of values in 'items', converted into a corresponding
    irlist.

    >>> irlist_str(to_irlist((1, (0, 2), (), 3)))
    '<1, <0, 2>, <>, 3>'
    """
    "*** YOUR CODE HERE ***"


#### Q2
def to_tuple(L):
    """Assuming L is an irlist, returns a tuple containing the same
    sequence of values.

    >>> x = to_irlist((1, (0, 2), (), 3))
    >>> to_tuple(x)
    (1, (0, 2), (), 3)
    """
    "*** YOUR CODE HERE ***"


#### Q3
def count_words(words):
    """Returns an idict mapping each unique word to the
    number of times it occurred in the tuple of words.
    >>> counts = count_words(('the', 'best', 'the', 'best', 'the', 'worst'))
    >>> idict_select(counts, 'the')
    3
    >>> idict_select(counts, 'worst')
    1
    >>> idict_select(counts, 'best')
    2
    """
    "*** YOUR CODE HERE ***"


#### Q4
def inserted_into_all(item, list_list):
    """Assuming that 'list_list' is an irlist of irlists, return the
    irlist consisting of the irlists in 'list_list', but with
    'item' prepended as the first item in each.

    >>> L0 = to_irlist(((), (1, 2), (3,)))
    >>> L1 = inserted_into_all(0, L0)
    >>> to_tuple(L1)
    ((0,), (0, 1, 2), (0, 3))
    """
    "*** YOUR CODE HERE ***"


def subseqs(S):
    """Assuming that S is an irlist, return an irlist of all subsequences
    of S (an irlist of irlists).  The order in which the subsequences
    appear is unspecified.

    >>> seqs = subseqs(to_irlist((1, 2, 3)))
    >>> tuple(sorted(to_tuple(seqs)))
    ((), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,))
    """
    "*** YOUR CODE HERE ***"


#### Q5
def inserted_into_all_tuples(item, tuple_tuple):
    """Assuming that 'tuple_tuple' is a tuple of tuples, return the
    tuple consisting of the tuples in 'tuple_tuple', but with
    'item' prepended as the first item in each.
    >>> inserted_into_all_tuples(0, ((), (1, 2), (3, )))
    ((0,), (0, 1, 2), (0, 3))
    """
    "*** YOUR CODE HERE ***"


def subseqs_tuples(S):
    """Assuming that S is a tuple, return tuple of all subsequences
    of S (a tuple of tuples).  The order in which the subsequences
    appear is unspecified.
    >>> seqs = subseqs_tuples((1, 2, 3))
    >>> tuple(sorted(seqs))
    ((), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,))
    """
    "*** YOUR CODE HERE ***"


#### Q6
def count_palindromes(L):
    """The number of palindromic words in the sequence of strings
    L (ignoring case).
    >>> count_palindromes(("acme", "madam", "pivot", "pip"))
    2
    """
    return _____________________________


#### Q7
def alt_filter(pred, L):
    """The tuple containing all elements, x, of L such that pred(x).
    >>> alt_filter(lambda x: x%2 == 0, (0, 1, 3, 8, 4, 12, 13))
    (0, 8, 4, 12)
    """
    return _____________________________


#### Q8
def capitalize_sentences(S):
    """The sequence of words (strings) S, with all initial words in
    sentences capitalized, and all others unchanged.  A word begins a
    sentence if it is either the first word in S, or the preceding word
    in S ends in a period.
    >>> capitalize_sentences(("see", "spot", "run.", "run", "spot", "run."))
    ('See', 'spot', 'run.', 'Run', 'spot', 'run.')
    """
    return _____________________________


#### Q9
def repeat(f, x, n):
    """Apply f to x n times.  When n is 0, the result is x; when n is
    1, the result is f(x); when n is 2, f(f(x)), etc.
    >>> repeat(lambda x: x+1, 1, 5)
    6
    """
    return _____________________________


#### Extra for Experts
#### Q10
def sortit(S):
    """The sequence of strings S sorted into lexicographic order (the <
    operator).

    >>> sortit((4, 2, 3, 5, 1))
    (1, 2, 3, 4, 5)
    """
    "*** YOUR CODE HERE ***"