#############################################
######### Fonctions à étudier ###############
#############################################

def indice_minimum_depuis(t, j):
    """
    Entrées:
      - t : une liste de nombres
      - j : un indice de t
    Sortie:
      - Le premier indice de t auquel
        t contient le minimum de t[j:].
    """
    resultat = None
    for i in range(j, len(t)):
        if resultat == None or t[i] < t[resultat]:
            resultat = i
    return resultat

def indice_minimum(t):
    """
    Entrée:
      t: une liste de nombres
    Sortie:
      Le premier indice du minimum de t dans t.
    """
    return indice_minimum_depuis(t, 0)

def tri_selection(t):
    """
    Entrée:
      t: Une liste de nombres
    Sortie:
      Aucune
    Effet de bord:
      La liste t est triée en place
    """
    for i in range(len(t) - 1):
        indice_min = indice_minimum_depuis(t, i)
        if i != indice_min:
            temp = t[i]
            t[i] = t[indice_min]
            t[indice_min] = temp

def test_tri_selection():
    """Un cas de test pour la fonction tri_selection."""
    t = [1, 0, 2, 0, 8, 1, 1, 3, 3]
    tri_selection(t)
    assert(t == [0, 0, 1, 1, 1, 2, 3, 3, 8])

test_tri_selection()

#############################################################
######### Données et fonction pour l'exercice 1 #############
#############################################################

import numpy as np
import matplotlib.pyplot as plt


x_exo1 =  [50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
           64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77,
           78, 79, 80]
y_exo1 = [2343750000323, 2692232033882, 3084215107919,
          3524133419852, 4016775630299, 4567305703478,
          5181284548967, 5864692479944, 6623952503027,
          7465954454834, 8398080000383, 9428228508452,
          10564843819019, 11816941917902, 13194139533719,
          14706683672288, 16365482103587, 18182134816394,
          20168966455727, 22339059758204, 24706290000443,
          27285360475622, 30091839013319, 33142195557752,
          36453840819539, 40045166016098, 43935583715807,
          48145569801044, 52696706565227, 57611726958974,
          62914560000503]

from scipy.stats import linregress
def regression_lineaire(x, y):
    """
    Entrée
    -------
      - x : une liste d'abcisses
      - y : la liste d'ordonnées associées

    Sortie
    -------
      Aucune

    Effet de bord
    -------------
      Affiche un message d'information sur une
      régression linéaire sur les données en entrée.
    """
    regression = linregress(x, y)
    pente = round(regression.slope, 2)
    print("Si les points donnés décrivent une droite,", end=" ")
    print("alors la pente de cette droite est de ", pente)

#################################################################
################ Pour l'exercice 2 ##############################
#################################################################

from random import randint

def liste_alea(taille):
    """
    Entrée
    ------
      taille: un entier
    Sortie
    ------
      Une liste d'entier générée aléatoirement,
      de la taille donnée en entrée
    """
    return [randint(0, 50) for i in range(taille)]


from time import time

def temps_exec(f, taille):
    """
    Entrées
    -------
      - f: une fonction prennant en argument une liste d'entiers
      - taille: un entier

    Sortie
    ------
      Le temps mis par f pour s'exécuter sur une liste aléatoire
      de taille taille.
    """
    liste = liste_alea(taille)
    debut = time()
    f(liste)
    fin = time()
    return fin - debut

def taille_dixieme_seconde(f):
    """
    Entrée
    ------
      f: une fonction qui prend des listes d'entiers en entrée

    Sortie
    ------
      Une estimation de à partir de quelle taille de liste
      la fonction en entrée prend plus d'un dixième de seconde
      à s'exécuter.

    Avertissement
    -------------
      Cette fonction peut mettre longtemps à s'exécuter
      (de l'ordre de 16 secondes pour les fonctions étudiées ici)
    """
    tentative_actuelle   = 1
    tentative_precedente = 1
    while temps_exec(f,  tentative_actuelle) < 0.1:
        tentative_precedente = tentative_actuelle
        tentative_actuelle = 10 *  tentative_actuelle
    majorant = tentative_actuelle
    minorant = tentative_precedente
    while minorant < majorant:
        milieu = (minorant + majorant)//2
        temps_milieu = temps_exec(f,  milieu)
        if temps_milieu < 0.1 and minorant != milieu:
            minorant = milieu
        elif temps_milieu > 0.1 and majorant != milieu:
            majorant = milieu
        else:
            minorant = milieu
            majorant = milieu
    return majorant

###############################################################
################## Pour l'exercice 4 ##########################
###############################################################

def random_letter():
    return chr(randint(97, 122))

def grille_carree_alea(n):
    return [[random_letter() for i in range(n)] 
            for j in range(n)]

def grille_info():
    """
    Une grille de mots mélés contenant les mots
    'info', 'algo' et 'ordi'.
    """
    base = grille_carree_alea(5)
    base[0][4] = 'i'
    base[1][4] = 'n'
    base[2][4] = 'f'
    base[3][4] = 'o'
    base[3][3] = 'g'
    base[3][2] = 'l'
    base[3][1] = 'a'
    base[4][0] = 'i'
    base[3][0] = 'd'
    base[2][0] = 'r'
    base[1][0] = 'o'
    return base