#------------------------TD7------------------------#


#####################[Code 1]##########################

def sommepaire(A, x):
    return any(A[i] + A[j] == x for i in range(len(A)) for j in range(i+1, len(A)))


def sommetriple(A, x):
    for i in range(0, len(A)):
        if sommepaire(A[:i] + A[i+1:], x-A[i]) == True:
            return True
    return False



print( sommetriple( [1, 2, 7, 11, 15], 18  ) )
print( sommetriple( [1, 2, 7, 11, 15], 17  ) )



#####################[Code 2]##########################

def est_puissance_de_deux(n):
    if n <= 0:
        return False

    return bin(n).count('1') == 1

print( est_puissance_de_deux(8) )
print( est_puissance_de_deux(6) )



#####################[Code 3]##########################

def computerinversions(A):
    return sum(A[i] > A[j] for i in range(len(A)) for j in range(i+1, len(A)))

def esttriee(A):
    n = len(A)
    x = computerinversions(A)
    return x == n*(n-1)/2


print( esttriee( [4,3,2,1] ) )
print( esttriee( [4,3,1,2] ) )



#####################[Code 4]##########################

from os.path import commonprefix

def min_chaines(A):
    _m = A[0]

    for i in range(1, len(A)):
        t = len( commonprefix([_m, A[i]]) )

        if len(A[i]) == t:
            _m = A[i]
        elif len(_m) > t and A[i][t] < _m[t]:
            _m = A[i]
    return _m


print( min_chaines( ["aeb", "abf", "abd", "ac"] ) )



#####################[Code 5]##########################

def findTwoContiguous(A):
    B = sorted(A)

    _min = abs(B[1]-B[0])
    for i in range(1, len(B)-1):
        _min = min( _min, abs(B[i]-B[i+1]) )

    return _min

A = [ 10, 78, 102, 20, 44, 69 ]

print( findTwoContiguous(A) )



#####################[Code 6]##########################

def findMajority(A):
    return sorted(A)[ len(A) // 2 ]


A = [1,2,6,4,2,2,2]
print( findMajority(A) )



#####################[Code 7]##########################

def findClosest(A, x, k):
    if len(A) < k: return -1

    B = [ [abs(x-A[i]), A[i]] for i in range(0, len(A)) ]
    B = sorted(B, key=lambda element: element[0])

    R = []
    for i in range(0, k):
        R.append(B[i][1])

    return R

A = [4, 1, 3, 8, 10]
print( findClosest(A, 5, 3) )



#####################[Code 8]##########################

def to_binary_string(x):
    s = ''
    while x != 0:
        if x%2 == 1:
            s = '1' + s
        else:
            s = '0' + s
        x = x // 2
    return s

def allsubsets(A):
    B = [ [] ]
    for i in range(1, 2**len(A)):
        s = to_binary_string(i)
        print(s)
        B.append([])
        for j in range(0, len(s)):
            k = len(s)-j-1
            if s[k] == '1':
                B[-1].append(A[j])
    return B


print( allsubsets( ['a', 'af', 41.34] ) )