<gh_stars>1-10
def make_fib():
    """Returns a function that returns the next Fibonacci number
    every time it is called.

    >>> fib = make_fib()
    >>> fib()
    0
    >>> fib()
    1
    >>> fib()
    1
    >>> fib()
    2
    >>> fib()
    3
    >>> fib2 = make_fib()
    >>> fib() + sum([fib2() for _ in range(5)])
    12
    """
    from itertools import accumulate, chain, repeat
    return map(lambda x_y: x_y[0], accumulate(chain(((0, 1),), repeat(None)), lambda x_y, _: (x_y[1], x_y[0] + x_y[1]))).__next__

def make_withdraw(balance, password):
    """Return a password-protected withdraw function.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> error = w(90, 'hax0r')
    >>> error
    'Insufficient funds'
    >>> error = w(25, 'hwat')
    >>> error
    'Incorrect password'
    >>> new_bal = w(25, 'hax0r')
    >>> new_bal
    50
    >>> w(75, 'a')
    'Incorrect password'
    >>> w(10, 'hax0r')
    40
    >>> w(20, 'n00b')
    'Incorrect password'
    >>> w(10, 'hax0r')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> w(10, 'l33t')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> type(w(10, 'l33t')) == str
    True
    """
    return (lambda f: lambda x, y: f(x)(y))((lambda f: (lambda x: x(x))(lambda x: f(lambda n: x(x)(n))))(lambda f: lambda amount: lambda attempt_password: (None if hasattr(f, 'new_balance') else setattr(f, 'new_balance', balance)) or (None if hasattr(f, 'fail_count') else setattr(f, 'fail_count', 0)) or (None if hasattr(f, 'attempts') else setattr(f, 'attempts', [])) or (('Your account is locked. Attempts: ' + str(f.attempts)) if f.fail_count == 3 else setattr(f, 'attempts', f.attempts + [attempt_password]) or setattr(f, 'fail_count', f.fail_count + 1) or 'Incorrect password' if attempt_password != password else 'Insufficient funds' if amount > f.new_balance else setattr(f, 'new_balance', f.new_balance - amount) or f.new_balance)))
    """Explanation:

    def withdraw(f):
        def inner(amount, attempt_password):
            None if hasattr(f, 'new_balance') else setattr(f, 'new_balance', balance)
            None if hasattr(f, 'fail_count') else setattr(f, 'fail_count', 0)
            None if hasattr(f, 'attempts') else setattr(f, 'attempts', [])

            if f.fail_count == 3:
                return 'Your account is locked. Attempts: ' + str(f.attempts)
            elif attempt_password != password:
                setattr(f, 'attempts', f.attempts + [attempt_password])
                setattr(f, 'fail_count', f.fail_count + 1)
                return 'Incorrect password'
            elif amount > f.new_balance:
                return 'Insufficient funds'
            else:
                setattr(f, 'new_balance', f.new_balance - amount)
                return f.new_balance
        return inner
    return withdraw(withdraw)
    """

class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.current_year.

    >>> mint = Mint()
    >>> mint.year
    2019
    >>> dime = mint.create(Dime)
    >>> dime.year
    2019
    >>> Mint.current_year = 2100  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2019
    >>> nickel.worth()  # 5 cents + (81 - 50 years)
    36
    >>> mint.update()   # The mint's year is updated to 2100
    >>> Mint.current_year = 2175     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (106 - 50 years)
    116
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (106 - 50 years)
    126
    """
    current_year = 2019

    def __init__(self):
        self.update()

    def create(self, kind):
        return kind(self.year)

    def update(self):
        self.year = self.current_year

class Coin:
    def __init__(self, year):
        self.year = year

    def worth(self):
        return self.cents + (0 if Mint.current_year - self.year <= 50 else Mint.current_year - self.year - 50)

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Machine is out of stock.'
    >>> v.deposit(15)
    'Machine is out of stock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'You must deposit $10 more.'
    >>> v.deposit(7)
    'Current balance: $7'
    >>> v.vend()
    'You must deposit $3 more.'
    >>> v.deposit(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.deposit(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.deposit(15)
    'Machine is out of stock. Here is your $15.'

    >>> w = VendingMachine('soda', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.deposit(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    """
    def __init__(self, product, price):
        self.product = product
        self.price = price
        self.balance = 0
        self.stock = 0

    def vend(self):
        if self.stock == 0:
            return 'Machine is out of stock.'
        elif self.price > self.balance:
            return f'You must deposit ${self.price - self.balance} more.'
        elif self.price == self.balance:
            self.stock -= 1
            return f'Here is your {self.product}.'
        else:  # self.price < self.balance
            self.stock -= 1
            change = self.balance - self.price
            self.balance = 0
            return f'Here is your {self.product} and ${change} change.'

    def restock(self, count):
        self.stock += count
        return f'Current {self.product} stock: {self.stock}'

    def deposit(self, amount):
        if self.stock == 0:
            return f'Machine is out of stock. Here is your ${amount}.'
        else:
            self.balance += amount
            return f'Current balance: ${self.balance}'

def remove_all(link, value):
    """Remove all the nodes containing value in link. Assume that the
    first element is never removed.

    >>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
    >>> print(l1)
    <0 2 2 3 1 2 3>
    >>> remove_all(l1, 2)
    >>> print(l1)
    <0 3 1 3>
    >>> remove_all(l1, 3)
    >>> print(l1)
    <0 1>
    >>> remove_all(l1, 3)
    >>> print(l1)
    <0 1>
    """
    from functools import partial, reduce
    from itertools import accumulate, chain, repeat, takewhile
    from operator import ne
    link.rest = reduce(lambda acc, x: Link(x, acc), reversed(tuple(filter(partial(ne, value), (() if link.rest is Link.empty else map(lambda x_y: x_y[1], takewhile(lambda x: x is not None, accumulate(chain(((link.rest.rest, link.rest.first),), repeat(None)), lambda x_y, _: None if x_y[0] is Link.empty else (x_y[0].rest, x_y[0].first)))))))), Link.empty)

def generate_paths(t, x):
    """Yields all possible paths from the root of t to a node with the label x
    as a list.

    >>> t1 = Tree(1, [Tree(2, [Tree(3), Tree(4, [Tree(6)]), Tree(5)]), Tree(5)])
    >>> print(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(generate_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = generate_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = Tree(0, [Tree(2, [t1])])
    >>> print(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = generate_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    from itertools import chain
    return chain(() if t.label != x else ([x],), ([t.label] + r for b in t.branches for r in generate_paths(b, x)))
    '''Explanation:

    "*** YOUR CODE HERE ***"
    if t.label == x:
        yield [x]

    for b in t.branches:
        for r in generate_paths(b, x):

            "*** YOUR CODE HERE ***"
            yield [t.label] + r

    Explanation 2:

    data Tree a = Tree a [Tree a] deriving (Show, Eq, Ord, Functor)

    paths :: Eq a => Tree a -> a -> [[a]]
    paths (Tree a ts) v = (if a == v then ([v] :) else id) [ a : r | t <- ts, r <- paths t v ]
    '''

## Link Class ##

class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.first = 5
    >>> s.rest.first = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    <5 7 <8 9>>
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

## Tree Class ##

class Tree:
    """
    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

    def map(self, fn):
        """
        Apply a function `fn` to each node in the tree and mutate the tree.

        >>> t1 = Tree(1)
        >>> t1.map(lambda x: x + 2)
        >>> t1.map(lambda x : x * 4)
        >>> t1.label
        12
        >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
        >>> t2.map(lambda x: x * x)
        >>> t2
        Tree(9, [Tree(4, [Tree(25)]), Tree(16)])
        """
        self.label = fn(self.label)
        for b in self.branches:
            b.map(fn)

    def __contains__(self, e):
        """
        Determine whether an element exists in the tree.

        >>> t1 = Tree(1)
        >>> 1 in t1
        True
        >>> 8 in t1
        False
        >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
        >>> 6 in t2
        False
        >>> 5 in t2
        True
        """
        if self.label == e:
            return True
        for b in self.branches:
            if e in b:
                return True
        return False

    def __repr__(self):
        if self.branches:
            branch_str = ', ' + repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(self.label, branch_str)

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.label) + "\n"
            for b in t.branches:
                tree_str += print_tree(b, indent + 1)
            return tree_str
        return print_tree(self).rstrip()
