import numpy as np

# Q1
"""
Il y a 256 possibilités par composante,
donc 256 * 256 * 256 possibilités en tout,
soit 16777216 valeurs possibles.
"""

# Q2
pixel_blanc = np.array([255, 255, 255], np.uint8)

# Q3
"""
Les calculs entiers se font modulo 256. Ainsi:
a = 24
b = 240
a + b = 8
a - b = 40
a // b = 1
a / b = 1.15666...
"""

# Q4
def gris(p):
    m = p.mean()
    return np.uint8(m)

# Q5
"""
L'image source a 3000 lignes, 4000 colonnes, et chaque case source[i, j]
est constituée de trois composantes (r, g, b).
Le pixel en haut à gauche, de coordonnées (0, 0), est constitué de
144/255 de rouge, 191/255 de vert, 221/255 de bleu. Il sera assez clair
et un peu bleuté.
"""

# Q6
def conversion(a):
    n, m, k = a.shape
    b = np.zeros((n, m), np.uint8)
    for i in range(n):
        for j in range(m):
            b[i, j] = gris(a[i, j])
    return b

# Q7
"""
Chaque photomosaïque fait 2 mètres de large,
à raison de 10 pixels par millimètre, soit 20000 pixels de large.
De même, chacune fera 15000 pixels de hauteur.
Au total, l'image contiendra 3x10^8 pixels.
Puisqu'il y a 40 vignettes sur la largeur, chaque vignette
doit faire 20000/40 = 500 pixels de large, et de même
elle doit faire 375 pixels de hauteur, soit 187500 pixels au total.
"""

# Q8
def procheVoisin(A, w, h):
    H, W, k = A.shape
    a = np.zeros((h, w), np.uint8)
    for i in range(h):
        for j in range(w):
            a[i, j] = A[i*H // h, j*W // w]
    return a

# Q9
"""
La complexité est en O(hw) (création de a, parcours de a)
"""

# Q10
"""
Dans cette fonction, l'image A est divisée en h * w blocs rectangulaires
de dimensions H/h par W/w. I et J sont des indices marquant les
pixels en haut à gauche de chacun de ces blocs. Ainsi, (I, J)
est le pixel en haut à gauche du bloc numéro (Ih/H, Jw/W). Chaque
bloc est alors remplacé par la moyenne de ses valeurs.
"""

# Q11
"""
Il y a H/ph = h tours de la boucle sur I.
De même, il y a w tours de la boucle sur J.
Il y a donc h*w tours de boucle, mais chaque
tour doit calculer la moyenne d'un sous-tableau
de taille ph*pw.
Au total, le coût est donc
O(h*w * ph * pw) = O(H*W) = O(N)
"""

# Q12
"""
np.uint32 stocke des entiers jusqu'à 2^32, soit
un peu plus de 4 milliards.

Si l'image comporte 50 millions de pixels, la case S[H,W]
pourra contenir le résultat d'une somme de 50 millions de termes,
chacun pouvant valoir 255 au pire.

50 * 10^6 * 255 =12.75 * 10^9: le type uint32 ne suffit pas !
"""

# Q13
"""
On remarque (en faisant un schéma) que:
S[i+1, j+1] = S[i+1, j] + S[i, j+1] - S[i, j] + A[i, j]
De plus, S[i, 0] = S[0, j] = 0 pour tout i, j
"""


def table_sommation(A):
    H, W = A.shape
    # créer la table, l'initialiser à 0
    S = np.zeros((H+1, W+1), np.uint64)
    # la remplir avec la formule de récurrence
    for i in range(H+1):
        for j in range(W+1):
            S[i+1, j+1] = S[i+1, j] + S[i, j+1] - S[i, j] + A[i, j]
    return S


# Q14
"""
Cette fonction calcule la même image réduit que la fonction
moyenneLocale, en utilisant la table des sommations.
Pour calculer la couleur du pixel (i, j) de l'image réduite,
il faut calculer la moyenne des pixels dans l'image de base,
dans le rectangle entre (I, J) et (I+ph, J+pw) (exclus), avec
I = i*ph et J = j*pw.
Il suffit donc de calculer la somme de cette zone rectangulaire,
et de la diviser par ph*pw.
Suivant la même logique que la question précédente, la somme
s'obtient en considérant une bonne combinaison de cases de S.
La quantité X du code est précisément cette somme.
"""

# Q15
"""
La complexité temporelle asymptotique est O(h*w) = O(n),
car chaque passage de boucle est en O(1).
"""

# Q16
"""
sred contient les cases de S dont l'indice de ligne
est multiple de ph, et dont l'indice de colonne est
indice de pw.

L'opération sred[:, 1:] - sred[:, :-1]
permet de soustraire à chaque case celle de gauche.
Ainsi, dc[i, j] contient sred[i, j+1] - sred[i, j]
= S[I, J+pw] - S[I, J] avec I = i*ph et J = j*pw

De même, l'opération dc[1:, :] - dc[:-1, :] permet de soustraire
à chaque case celle du dessus.
Ainsi, dl[i, j] = dc[i+1, j] - dc[i, j]
= S[I+ph, J+pw] - S[I+ph, J] - (S[I, J+pw] - S[I, J])

ce qui est exactement la valeur de X au tour de boucle (I, J)
dans la fonction reductionSommation !
"""

# Q17
"""
Les deux complexités asymptotiques en temps sont les même,
O(n), car dans la 2ème version, les opérations case à case
effectuées sont en réalité des boucles.

De même la complexité en mémoire est O(n): on crée la nouvelle
matrice a dans les deux cas, et les autres matrices crées
dans reductionSommation2 sont aussi de taille n.

Un avantage de la deuxième version peut être que les boucles
ne sont pas gérées par l'utilisateur mais directement par numpy,
ce qui peut être plus rapide.
"""