tries = 10  # nombre d'essais / de répétitions
n = 128      # nombre de personnes dans le village


def isHonestPersonIdx(A,isHonest,j):
  # On teste si la personne A[j] est honnete (j dans [0,len(A)[)
  # retourne True or False
  n = len(A)
  L=[ i for i in range(0, n) if i!=j and isHonest(A[i], A[j]) ]
  cH=len(L) # nb de réponses "honnete"
  cM=(n-1)-cH # nb de réponses "malhonnete"
  if cH >= cM:
    return True

def isHonestPersonv1(A,isHonest,p):
  # On teste si la personne p est honnete (p dans A)
  # retourne True or False
  n = len(A)
  L=[ i for i in range(0, n) if A[i]!=p and isHonest(A[i], p) ]
  cH=len(L) # nb de réponses "honnete"
  cM=(n-1)-cH # nb de réponses "malhonnete"
  if cH >= cM:
    return True

def isHonestPerson(A,isHonest,p):
  # On teste si la personne p est honnete (p dans A)
  # retourne True or False
  n = len(A)
  cH=0 # compteur de réponses "honnete"
  for i in range(0, n):
    if A[i]!=p and isHonest(A[i], p):
      cH+=1
  cM=(n-1)-cH # nb de réponses "malhonnete"
  if cH >= cM:
    return True


#################ci-dessous: tache 3.######################
def computeHonestPerson_SLOW_ITERATIVE(A, isHonest):
  n = len(A)
  if n == 1: return A[0]
  for j in range(0, n):
    if isHonestPerson(A,isHonest,A[j]):
      return A[j]
#################ci-dessous: tache 3.######################

def computeHonestPerson_SLOW_ITERATIVEv1(A, isHonest):
  n = len(A)
  if n == 1: return A[0]
  for j in range(0, n):
    if isHonestPersonIdx(A,isHonest,j):
      return A[j]


#####################ci-dessous: tache 4.#######
def computeHonestPerson_SLOW_RECURSIVE(A, isHonest):
  n = len(A)
  if n == 1:
    return A[0]

  if isHonestPerson(A,isHonest,A[n-1]):
    return A[n-1]
  else:
    return computeHonestPerson_SLOW_RECURSIVE(A[0:n-1], isHonest)
#####################ci-dessus: tache 4.###########################









########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier lLe deuxième quiz aura lieu le 14 avril, de la manière suivante : e code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
########Il n'est pas necessaire de lire ou de modifier le code sous cette ligne.##################
import random

def generateProblem(n):
    S = [0]*n
    count = 0
    while sum(S) <= n/2.0: S[random.randint(0,n-1)] = 1

    def isHonest(i, j):
        nonlocal S, count
        count += 1
        if S[i] == 1: return bool(S[j])
        else: return random.choice([True, False])

    def giveAnswer(i):
        nonlocal S
        return bool(S[i])

    def numQuestions():
        nonlocal count
        return count

    def reset():
        nonlocal count
        count = 0

    return isHonest, giveAnswer, numQuestions, reset




print("=" * 93)
print(f"{'Algorithm':<20} {'Personne Computed':<26} {'Really Honest?':<26} {'# Questions asked':<20}")
print("-" * 93)

for _ in range(tries):
    isHonest, giveAnswer, numQuestions, reset = generateProblem(n)

    reset()
    sol1 = computeHonestPerson_SLOW_ITERATIVE([i for i in range(0, n)], isHonest)
    print(f"{'SLOW_ITERATIVE':<20} {sol1:<26} {str(giveAnswer(sol1)):<26} {numQuestions():<20}")

    reset()
    sol2 = computeHonestPerson_SLOW_RECURSIVE([i for i in range(0, n)], isHonest)
    print(f"{'SLOW_RECURSIVE':<20} {sol2:<26} {str(giveAnswer(sol2)):<26} {numQuestions():<20}")

    print()

print("=" * 93)