#------------------------TDdivideandconquer1------------------------#


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

def computeHonestPerson(A, isHonest):
    n = len(A)
    
    if n != 4: 
        return
    
    if isHonest(A[0], A[1]):
        return A[1]
    else:
        return A[2]



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

def binarySearch_ITERATIVE(A, x):
    start, end = 0, len(A)-1

    while end >= start:
        mid = (start+end)//2
        if x == A[mid]:
            return mid
        if x > A[mid]:
            start = mid+1
        if x < A[mid]:
            end = mid-1
    return None

import random
A = sorted( [ random.randint(0,20) for _ in range(0,10) ] )
print(A)

x = 4
print(f"Is {x} in A: ", binarySearch_ITERATIVE(A, x))



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

def binarySearch_RECURSIVE(A, start, end, x):
    if end < start:
        return None

    mid = (start+end) // 2
    if x == A[mid]:
        return mid
    if x < A[mid]:
        return binarySearch_RECURSIVE(A, start, mid-1, x)
    else:
        return binarySearch_RECURSIVE(A, mid+1, end, x)

import random
A = sorted( [ random.randint(0,20) for _ in range(0,10) ] )
print(A)

x = 4
print(f"Is {x} in A: ", binarySearch_RECURSIVE(A, 0, len(A)-1, x))



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

def findFirstTrue_ITERATIVE(A, start, end):
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == True:
            if mid == start or A[mid - 1] == False:
                return mid
            else:
                end = mid - 1
        else:
            start = mid + 1
    return None

def findFirstTrue_RECURSIVE(A, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if A[mid] == True:
        if mid == start or A[mid - 1] == False:
            return mid
        else:
            return findFirstTrue_RECURSIVE(A, start, mid - 1)
    else: 
        return findFirstTrue_RECURSIVE(A, mid + 1, end)

A1 = [False, False, False, True, True]
print(findFirstTrue_ITERATIVE(A1, 0, len(A1)-1))  # 3
print(findFirstTrue_RECURSIVE(A1, 0, len(A1)-1))  # 3

A2 = [True, True, True]
print(findFirstTrue_ITERATIVE(A2, 0, len(A2)-1))  # 0
print(findFirstTrue_RECURSIVE(A2, 0, len(A2)-1))  # 0

A3 = [False, False, False]
print(findFirstTrue_ITERATIVE(A3, 0, len(A3)-1))  # None
print(findFirstTrue_RECURSIVE(A3, 0, len(A3)-1))  # None



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

def findIncreasing_ITERATIVE(A):
    start = 0
    end = len(A)-1

    while (end-start+1) > 2:
        mid = (start + end) // 2

        if A[mid] < A[end]:
            start = mid
        else:
            end = mid
            
    return start

print(findIncreasing_ITERATIVE([60, 50, 40, 23, 28, 70]))



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

def findIncreasing_RECURSIVE(A, start, end):
    if (end-start+1) == 2:
        return start

    mid = (start + end) // 2

    if A[mid] < A[end]:
        return findIncreasing_RECURSIVE(A, mid, end)
    else:
        return findIncreasing_RECURSIVE(A, start, mid)

A1 = [60, 50, 40, 23, 28, 70]
print(findIncreasing_RECURSIVE(A1, 0, len(A1)-1))

A2 = [1, 3, 2, 4, 5]
print(findIncreasing_RECURSIVE(A2, 0, len(A2)-1))



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

def findMax_ITERATIVE(A):
    start, end = 0, len(A) - 1

    while start < end:
        mid = (start + end) // 2

        if A[mid] < A[mid + 1]:
            start = mid + 1
        else:
            end = mid

    return A[start]

import random
n = 10
A=(sorted([ random.randint(0,100) for _ in range(0, n//2) ]) +
   sorted([ random.randint(0,100) for _ in range(0, n//2) ],reverse=True))

print("A: ", A)
print("maximum: ", findMax_ITERATIVE(A))



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

poison = 11

def afterOneMonth(A):
    OUT = []
    for B in A:
        OUT.append( (B, poison in B) )
    return OUT

def assignTesters(n):
    A = []
    s = 1
    while s < n:
        P1 = []
        P2 = []
        i = 0
        while i < n:
            P1 = P1 + list(range(i,i+s))
            P2 = P2 + list(range(i+s,i+2*s))
            i = i + 2*s
        A.append( P1 )
        A.append( P2 )
        s = 2*s

    return A

def findPoison(B, n):
    T = set(range(0, n))
    for (S, V) in B:
        if V == False:
            T = T - set(S)
    print("The poisonous glass is: ", T)

A = assignTesters(16)
print(A)

B = afterOneMonth(A)
print(B)

findPoison(B, 16)



#####################[Code 9]##########################

def afterOneMonth(A, poison):
    OUT = []
    for B in A:
        OUT.append( (B, poison in B) )
    return OUT

def assignTesters(n):
    A = []
    s = 1
    while s < n:
        P = []
        i = 0
        while i < n:
            P = P + list(range(i,i+s))
            i = i + 2*s
        A.append( P )
        s = 2*s

    return A

def findPoison(B, n):
    s, e = 0, n-1
    for i in reversed(range(0,len(B))):
        print("l: ", B[i])
        if B[i][1] == True: e = (s+e)//2
        else: s = (s+e)//2 + 1
        print(s,e)

    print("The poisonous glass is: ", s, e)



n = 16
A = assignTesters(n)
for i in range(0, 4):
    poison = int(input("Enter poisonous glass:"))
    if poison > n-1: continue
    B = afterOneMonth(A, poison)
    findPoison(B, n)