# coding: utf-8
from math import *
from functools import reduce
HW_SOURCE_FILE = 'hw04.py'


###############
#  Questions  #
###############

def intersection(st, ave):
    """Represent an intersection using the Cantor pairing function."""
    return (st+ave)*(st+ave+1)//2 + ave

def street(inter):
    return w(inter) - avenue(inter)

def avenue(inter):
    return inter - (w(inter) ** 2 + w(inter)) // 2

w = lambda z: int(((8*z+1)**0.5-1)/2)

def taxicab(a, b):
    """Return the taxicab distance between two intersections.

    >>> times_square = intersection(46, 7)
    >>> ess_a_bagel = intersection(51, 3)
    >>> taxicab(times_square, ess_a_bagel)
    9
    >>> taxicab(ess_a_bagel, times_square)
    9
    """
    "*** YOUR CODE HERE ***"
    return street( abs(a-b) ) + avenue( abs(a-b) )

def squares(s):
    """Returns a new list containing square roots of the elements of the
    original list that are perfect squares.

    >>> seq = [8, 49, 8, 9, 2, 1, 100, 102]
    >>> squares(seq)
    [7, 3, 1, 10]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    #print({s_v:v for s_v, v in zip(map(lambda x: sqrt(x), s), s) })
    #print({s_v:v for s_v, v in zip(map(lambda x: sqrt(x), s), s) if pow(s_v, 2) == float(v)  })
    return [ int(s_v) for s_v, v in zip(map(lambda x: sqrt(x), s), s) if pow(round(s_v), 2) == v ] 


N = 102
computed = [ -1 for i in range(N) ]
def g(n): # type(computed) == List,保存以计算的值
    """Return the value of G(n), computed recursively.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'g', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    global computed
    if computed[n] != -1: return computed[n]
    elif n <= 3: 
        computed[n] = n
        return n
    else: return g(n-1) + 2*g(n-2) + 3*g(n-3)

def g_iter(n):
    """Return the value of G(n), computed iteratively.

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'g_iter', ['Recursion'])
    True
    """
    "*** YOUR CODE HERE ***"
    computed = [1, 2, 3] # type: List
    for i in range(4, n+1):
        computed.append( computed[i-2] + 2*computed[i-3] + 3*computed[i-4] )
    return computed[n-1]

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"
    def func(i, now, direction):
        """
        i 表示当前位置
        now 表示当前位置的值
        direction表示方向，上或者下
        """
        if n == i: return now
        else:
            if i%7 == 0 or has_seven(i):
                return func(i+1, now+(-1*direction), -1*direction)
            return func(i+1, now+direction, direction)
    return func(1, 1, 1)

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    if k % 10 == 7:
        return True
    elif k < 10:
        return False
    else:
        return has_seven(k // 10)

def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    #coins = [ 1, 2, 4, 8, 16 ]  错误
    #if amount < 0: return 0
    #elif amount in coins: return 1
    #else:
    #    return sum( map(count_change, (amount-i for i in coins)) )
    pass

###################
# Extra Questions #
###################

from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
    True
    """
    return lambda x: reduce(mul, [i for i in range(2,x+1)], 1)

if __name__ == "__main__":
    seq = [8, 49, 8, 9, 2, 1, 100, 102, 500, 30]
    squares(seq)
    #print(make_anonymous_factorial()(5))
