#!/usr/bin/env python
# coding: utf-8

# <div class="alert alert-block alert-info">
# <center><font size=5><b>TP n°14 (représentation des nombres) : Éléments de correction</b></font></center></div>

# $\require{color}$
# $\require{xcolor}$
# $\require{cancel}$
# $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$
# $\require{stmaryrd}$
# $\newcommand{\ient}{[\![}$
# $\newcommand{\rrbracket}{]\!]}$
# $\newcommand{\llbracket}{[\![}$
# $\newcommand{\fient}{]\!]}$
# $\newcommand{\R}{\mathbb R}$
# $\newcommand{\K}{\mathbb K}$
# $\newcommand{\N}{\mathbb N}$
# $\newcommand{\C}{\mathbb C}$
# $\newcommand{\P}{\mathbb P}$
# $\newcommand{\E}{\mathbb E}$
# $\newcommand{\V}{\mathbb V}$
# $\newcommand{\Z}{\mathbb Z}$
# $\newcommand{\dt}{\mathrm d}$
# $\newcommand{\sh}{\operatorname{sh}}$
# $\newcommand{\ch}{\operatorname{ch}}$
# $\newcommand{\id}{\operatorname{Id}}$
# $\newcommand{\mat}{\operatorname{mat}}$
# $\newcommand{\sp}{\operatorname{Sp}}$
# $\newcommand{\In}{\operatorname{I}}$
# $\newcommand{\vect}{\operatorname{Vect}\ }$
# $\newcommand{\rg}{\operatorname{rg}}$
# $\newcommand{\tr}{\operatorname{Tr}}$
# $\newcommand{\dis}{\displaystyle}$
# $\renewcommand{\Im}{\operatorname{Im}}$
# $\newcommand{\im}{\operatorname{Im}}$
# $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\  #3  & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$
# $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$
# $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$
# $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$
# $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$

# In[65]:


import matplotlib.pyplot as plt
import numpy as np


# ## I. <u>Représentation binaire, addition et complément à deux</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 1 (conversion en binaire)</b></font>
# </div>

# In[66]:


def conv_binaire(n):
    """
    Entrée : un entier naturel n
    Sortie : la chaîne de caractères correspondant à sa décomposition binaire    
    """
    if n == 0:
        return "0"
    else:
        binaire = ""
        while n > 0:
            binaire = str(n % 2) + binaire
            n = n // 2
        return binaire


# In[42]:


conv_binaire(6)


# Pour la conversion "réciproque", on peut utiliser la méthode de Hörner, qui minimise le nombre de multiplications à faire :

# In[47]:


def conv_decimal(L):
    """
    Entrée : une chaîne de caractères de 0 et de 1
    Sortie : l’entier en base 10 correspondant.
    """
    s = len(L)
    n = int(L[0])
    for i in range(1,s):
        n = n * 2 + int(L[i])
    return n


# In[4]:


def conv_decimal(L):
    """
    Entrée : une chaîne de caractères de 0 et de 1
    Sortie : l’entier en base 10 correspondant.
    """
    s = int(L[0])
    for l in L[1:]:
        s = s * 2 + int(l)
    return s


# In[5]:


conv_decimal("100")


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 2 (représentation des entiers relatifs)</b></font>
# </div>

# In[6]:


def inverse(S):
    R = ""
    for s in S:
        if s == "1":
            R = R + "0"
        else:
            R = R + "1"
    return R


# In[7]:


inverse("10011")


# Pour obtenir la représentation de $-n$ (avec complément à $2$) :
# - on convertit $n$ en binaire sur $b$ bits
# - on inverse tous les bits
# - on ajoute $1$ au résultat (avec propagation de la retenue)
# - on tronque à $b$ bits

# In[8]:


def oppose(n, b):
    assert n > 0 and n <= 2**(b - 1)
    S = conv_binaire(n) # on convertit n en binaire sur b bits
    S = "0" * (b - len(S)) + S # on utilise exactement b bits
    S = inverse(S) # on inverse les bits
    R = "" # le résultat à renvoyer
    k = 1
    while S[-k] == "1":
        R = "0" + R
        k +=1
    R = "1" + R
    R = S[0:b-k] + R
    return R


# In[9]:


oppose(120,8)


# In[10]:


np.binary_repr(-120, width=8)


# In[11]:


for k in range(1,128):
    if oppose(k,8) != np.binary_repr(-k, width=8):
        print(k)


# In[12]:


def conv_binaire_r(n, b):
    assert n >= -2**(b - 1) and n <= 2**(b - 1) - 1
    if n >= 0:
        S = conv_binaire(n)
        return "0" * (b - len(S)) + S
    else:
        return oppose(-n,b)


# In[13]:


conv_binaire_r(-1, 8)


# In[14]:


conv_binaire_r(1, 8)


# In[15]:


for k in range(-128,127):
    if conv_binaire_r(k, 8) != np.binary_repr(k, width=8):
        print(k)


# In[16]:


def conv_decimal_r(S, b):
    if S[0] == "0":
        return conv_decimal(S)
    else:
        return conv_decimal(S[1:]) - 2**(b - 1)


# In[17]:


conv_decimal_r('00000101', 8)


# In[18]:


conv_decimal_r('11111111', 8)


# ## II. <u>Stéganographie</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 3</b></font>
# </div>

# In[48]:


def stegano(S1, S2):
    return S1[:4] + S2[:4]


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 4</b></font>
# </div>

# In[49]:


M = plt.imread("eleves.png")
M = (M * 255).astype(np.uint8)

N = plt.imread("paysage.png")
N = (N * 255).astype(np.uint8)


# In[50]:


M[12][24]


# In[22]:


plt.figure(figsize=(4, 4))
plt.imshow(M)
plt.axis("off")
plt.show()


# On va «cacher» les élèves dans l'image du paysage :

# In[23]:


taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
    for j in range(taille):
        for k in range(3):
            S1 = np.binary_repr(N[i][j][k], width=8)
            S2 = np.binary_repr(M[i][j][k], width=8)
            P[i][j][k] = conv_decimal(stegano(S1, S2))

plt.figure(figsize=(4, 4))
plt.imshow(P)
plt.axis("off")
plt.title("Les élèves sont cachés dans cette image")
plt.show()


# On peut chercher à la comparer à l'image originale :

# In[24]:


plt.figure(figsize=(6, 6))
plt.subplot(1, 2, 1)  # sous-figure n°1 (1 ligne, 2 colonnes, position 1)
plt.imshow(N)
plt.axis('off')
plt.title("Image originale")
plt.subplot(1, 2, 2)  # sous-figure n°2 (1 ligne, 2 colonnes, position 2)
plt.imshow(P)
plt.axis('off')
plt.title("Image perturbée")
plt.show()


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 5</b></font>
# </div>

# On peut maintenant chercher à retrouver l'image cachée dans l'image précédente :

# In[25]:


L = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
    for j in range(taille):
        for k in range(3):
            S = np.binary_repr(P[i][j][k], width=8)
            S = S[4:] + 4 * "0"
            L[i][j][k] = conv_decimal(S)

# taille et résolution des figures
plt.rcParams['figure.figsize'] = [4, 4]

plt.imshow(L)
plt.axis("off")
plt.show()


# On peut la comparer avec l'image originale :

# In[26]:


plt.figure(figsize=(6, 6))
plt.subplot(1, 2, 1)  # sous-figure n°1 (1 ligne, 2 colonnes, position 1)
plt.imshow(M)
plt.axis('off')
plt.title("Image originale")
plt.subplot(1, 2, 2)  # sous-figure n°2 (1 ligne, 2 colonnes, position 2)
plt.imshow(L)
plt.axis('off')
plt.title("Image retrouvée")
plt.show()


# ## III. <u>Fibonacci et stéganographie</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 6</b></font>
# </div>

# In[27]:


u, v = 0, 1
L = []
for k in range(12):
    u, v = v, u + v
    L.append(v)
print(L)


# In[28]:


def zeckendorf(n):
    m = n
    S = ""
    i = len(L) - 1
    while m > 0:
        while L[i] > m:
            i -= 1
            S = S + "0"
        S = S + "1"
        m = m - L[i]
        i -= 1
    return S + "0" * (12 - len(S))


# In[29]:


zeckendorf(240)


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 7</b></font>
# </div>

# In[58]:


M = plt.imread("eleves.png")
M = (M * 255).astype(np.uint8)

N = plt.imread("paysage.png")
N = (N * 255).astype(np.uint8)


# In[59]:


def stegano_fib(S1, S2):
    return S1[:6] + S2[:6]


# In[60]:


def conv_decimal_fib(S):
    return sum(L[len(L) - i - 1] * int(S[i]) for i in range(len(L)))


# In[61]:


taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
    for j in range(taille):
        for k in range(3):
            S1 = zeckendorf(N[i][j][k])
            S2 = zeckendorf(M[i][j][k])
            P[i][j][k] = conv_decimal_fib(stegano_fib(S1, S2))

plt.figure(figsize=(4, 4))
plt.imshow(P)
plt.axis("off")
plt.show()


# Effectivement, on peut, avec cette méthode, dépasser la valeur $255$. Python tronque alors la valeur à $255$ avant d'afficher l'image... Cela peut provenir de deux problèmes :
# - en concaténant, on peut créer des représentations contenant le motif ```"11"```, qui ne sont pas des représentations de Zeckendorf valides.
# - On peut également créer des nombres qui ont une représentation valide, mais qui dépassent $255$ en écriture décimale.
# 
# Le second point se règle au moment de l'affichage, en prenant le minimum entre la valeur de chaque couleur de chaque pixel et $255$, à l'aide de la fonction ```np.minimum()``` qui s'applique composante par composante.
# 
# Le premier point est plus problématique : la conversion inverse ne redonne pas les bits initiaux. On peut régler ce problème de la manière suivante :

# In[62]:


def stegano_fib(S1, S2):
    if S1[5] == "1" and S2[0] == "1":
        return S1[:5] + "0" + S2[:6]
    else:
        return S1[:6] + S2[:6]


# In[63]:


taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
    for j in range(taille):
        for k in range(3):
            S1 = zeckendorf(N[i][j][k])
            S2 = zeckendorf(M[i][j][k])
            P[i][j][k] = conv_decimal_fib(stegano_fib(S1, S2))

plt.figure(figsize=(4, 4))
plt.imshow(np.minimum(P, 255))
plt.axis("off")
plt.show()


# On peut désormais essayer de retrouver l'image cachée :

# In[64]:


C = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
    for j in range(taille):
        for k in range(3):
            S = zeckendorf(P[i][j][k])
            S = S[6:] + 6 * "0"
            C[i][j][k] = conv_decimal_fib(S)

plt.figure(figsize=(4, 4))
plt.imshow(C)
plt.axis("off")
plt.show()