---
# System prepended metadata

title: E3aV-S05-INFO-ALGO - Algorithmique et structure de données

---

# E3aV-S05-INFO-ALGO - Algorithmique et structure de données

## EVAL
### Questions
https://hackmd.io/V5aMWRABRN6MUw6t5558Hg

### Réponses
https://docs.google.com/forms/d/e/1FAIpQLScy2Ia_oTBEW-giDYS34mi0zgMbl5aVvtcsyhcDqeoGAKMTvw/viewform

### Dépot projet

https://docs.google.com/forms/d/e/1FAIpQLScxXj9GF-ICvrkCEVWRxTsYrTF2L5QxxQKVmDyTEuUQ0dQf8w/viewform?usp=publish-editor



##  Généralités
### Algorithmique et programmation structurée


### Séance 1 et 2


Cours introduction -> [cours 1](https://drive.google.com/file/d/1J6o984hpf4hU937SWKUwxUTfmaEmmMXc/view?usp=drive_link)

Cours structures avancées ->[cours 2](https://drive.google.com/file/d/13JUAuEGG2b6-NyfWN95PUjch2w3pQG5t/view?usp=drive_link)

Le document ci-dessus présente le contenu du cours structures de données avancées: Liste, Pile, File et Arbre.

La bible du python-> [ici](https://drive.google.com/file/d/0B9fj93mCrxamVXRGazBMMXEzS28/view?usp=drive_link&resourcekey=0-nXcNw7dniYcYjPZPecPShQ)

En English -> [ici](https://github.com/manish-old/ebooks-2/blob/master/O'Reilly%20-%20Learning%20Python%204th%20Edition.pdf)

Pour analyser vos codes  -> pythontutor.com

## Tri à bulle

{%youtube h00xRb-L8Zs%}

Tri par selection
<iframe width="1535" height="835" src="https://www.youtube.com/embed/qpeeRU_K90k" title="Tri par sélection" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

Tri par insertion
<iframe width="1535" height="835" src="https://www.youtube.com/embed/pzxSlJVprkc" title="Tri par insertion" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>


RECAP

https://github.com/MachineLearnia/Python-Machine-Learning/

### Seance 3

TP : -> [TP Algorithmes de base  ](https://drive.google.com/file/d/1WvI3sXN1nBexem7atRsyae02iM2wd3Z9/view?usp=drive_link)

TP : -> [Pour les trop rapide -- (turtle+takuzu)](https://drive.google.com/file/d/1mojIr24v9cAouHOR5vQ3kdUbgpOPQl0F/view?usp=drive_link)

Code triangle imbriqué
```python
from turtle import *

width(5)
up()
goto(-100,-100)
down()
for i in range(3):
    color("blue")
    forward(256)
    left(120)
    for j in range(3):
        color("red")
        forward(128)
        left(120)
        for k in range(3):
            color("green")
            forward(64)
            left(120)  
            # for i in range(3):
            #     color("orange")
            #     forward(32)
            #     left(120)                            

```

Code Takuzu
```python
# le titre suffit a  comprendre ce que fait la fonction :-)
def initTakuzuCorrect () :
    matrice = list ([[0, 1, 1, 0], 
                     [1, 0, 0, 1],
                     [0, 0, 1, 1],
                     [1, 1, 0, 0]] )
    
    return matrice

# le titre suffit a  comprendre ce que fait la fonction :-)
def initTakuzuNonCorrect () :
    matrice = list ([[0, 1, 1, 1], 
                     [1, 0, 0, 1],
                     [0, 0, 1, 1],
                     [1, 1, 0, 0]] )
    return matrice

matrice=initTakuzuCorrect ()
print (matrice)


```

TP : -> [Pour les plus fort -- (Pong)](https://drive.google.com/file/d/1sZ6Q4KkHF-lsLrg1zZs77236YGe1y6Q9/view?usp=drive_link)

```python
def effaceEcran ():
    for i in range (1,100) :
        print("\n")


# Initialise la grille de facon a ce qu'elle contienne ce qui se trouve 
# a la figure de droite 

def initGrille (grille, pos_balle_x, pos_balle_y) :
    .........
   

    
    
# Affiche le rectangle d'etoiles et la balle (tout ceci en meme
# temps et non pas le rectangle puis la balle...) 

def afficheGrille (grille) : 
    .........
    
    

    
# Calcule la nouvelle position de la balle en fonction de 
# l'ancienne position de la balle (old_pos_balle_x, old_pos_balle_y) 
#  et du vecteur de deplacement (deplacement_x, deplacement_y).
# supprime l'ancienne position de la balle et place cette dernière 
# a la nouvelle position

def modifiePositionBalle (grille, pos_balle_x, pos_balle_y, deplacement_x, deplacement_y) :

    theo_pos_x=0
    theo_pos_y=0;

	# On efface l'ancienne balle
    grille[pos_balle_x][pos_balle_y]=' '

    print ("Position actuelle : (",str(pos_balle_x)," , ",str(pos_balle_y),")")
    print ("Deplacement actuel : (",str(deplacement_x)," , ",str(deplacement_y),")")

	# On calcule la future position theorique de la balle
    theo_pos_x = pos_balle_x + deplacement_x 
    theo_pos_y = pos_balle_y + deplacement_y

	# En fonction de la position theorique de la balle
    # si elle tape sur la bordure, 
    # on modifie le vecteur de deplacement
    if (grille[theo_pos_x][theo_pos_y]=='*') :
		# Si on tape sur l'axe vertical
        if (( theo_pos_x == 0 ) or ( theo_pos_x == 9 )) :
            deplacement_x = - deplacement_x

        # Si on tape sur l'axe horizontal
        if (( theo_pos_y == 0 ) or ( theo_pos_y == 9 )) :
            deplacement_y = - deplacement_y

    # On calcule la nouvelle position de la balle
    pos_balle_x = .........
    pos_balle_y = .........

    print ("Nouvelle position : (",str(pos_balle_x)," , ",str(pos_balle_y),")")
	
    # On met la balle dans la grille a sa nouvelle position
    grille[pos_balle_x][pos_balle_y]=.........
    
    return grille, pos_balle_x, pos_balle_y, deplacement_x, deplacement_y


##################################
# programme principal :
##################################
    
    
grille= [[' ' for i in range(10)] for j in range(10)] 	# grille qui pourra contenir
                # 3 sortes de caractères : '*' ou 'O' ou le caractere espace ' '

    
pos_balle_x=3   # position  balle au depart
pos_balle_y=4     


deplacement_x=1
deplacement_y=1;  # vecteur de deplacement de la balle

initGrille (grille, pos_balle_x, pos_balle_y) ;

s='*'
while (s!='s') :
    effaceEcran ()
    afficheGrille(grille);
    grille, pos_balle_x, pos_balle_y, deplacement_x, deplacement_y = modifiePositionBalle (grille, pos_balle_x, pos_balle_y, deplacement_x, deplacement_y)
	
    s=input("Appuyez sur la touche entrée ou 's' pour sortir... ")
```
Ce qui donne
![pong](https://hackmd.io/_uploads/S1-YALSzZg.gif)



# Exercices 1
> [color=#d1a823]
:information_source: 
> Exercice 1:
> Écrire une fonction qui supprime les doublons d'une liste.
>  Exercice 2 :
> Écrire un programme qui affiche un petit calendrier de la semaine lorsqu'on lui fournit
> en argument la date du dimanche. Si on entre 29,4,18 (29 avril 2018), ce programme
> doit nous afficher Lundi 30 avril 2018, Mardi 1 mai 2018, ..., Dimanche 6 mai 2018.
>  Exercice 3 :
> Écrire un programme qui renvoie une main de N cartes prises au hasard dans un jeu de
> 32 cartes.
> Par exemple, avec N=2, on devrait pouvoir obtenir [As de Trèfle, Dix de Pique].






| Critères de notation | |
| -------- | -------- | 
| -> Document à rendre au format ipynb (notebook - jupyter) avec le nom des participants (max 3) |   | 
| -> Respect des consignes| | 
| ->  Code commenté, clair et concis | | 
| -> Nom des variables compréhenibles et en lien avec la donnée traitée| | 
| -> Présentation de plusieurs solutions possibles avec explication des différences.| | 



# Exercices 2

> [color=#d1a823]
:information_source: 
> Exercice 1:
> Finir l'exercice sur le takuzu

| Critères de notation | |
| -------- | -------- | 
| -> Document à rendre au format ipynb (notebook - jupyter) |   | 
| -> Respect des consignes| | 
| ->  Code commenté, clair et concis | | 
| -> Nom des variables compréhenibles et en lien avec la donnée traitée| | 
| -> Présentation de plusieurs solutions possibles avec explication des différences.| |


# Les classes

[Classe python](/4dvs1NgWQVKUz-GE9MRLfw)

# Exercices 3

> [color=#d1a823]
:information_source: 
> Exercice 1:
> Refaire l'exercice du pong en utilisant les classes
> Exercice 2:
> Rajouter 1 balle au jeu
> Exercice 3:
> Rajouter encore 1 balle au jeu
> Exercice 4:
> Comment traiter le cas de colision entre les balles
# Projet
----
> [color=#d1a823]
:information_source: 
>[Mini projet Blokus](https://drive.google.com/file/d/1KObUlAKy7vzNDswVuHgBcblEGAhqZVeU/view?usp=drive_link)
[Règle du jeu](https://drive.google.com/file/d/1vLCwUUriw4-CUdqEZPY1Rx2VyhbebtqV/view?usp=drive_link)
[une these sur le sujet](https://teaching.bb-ai.net/Student-Projects/project-reports/Games/Sharon-Mathew-Blokus-project-report.pdf)
[Consigne de rendu (document à rendre)](https://hackmd.io/@YSaVczpYQySlUnehD8yxvw/BykA9KjVp)



<div style="padding:56.25% 0 0 0;position:relative;"><iframe src="https://player.vimeo.com/video/139794342?badge=0&amp;autopause=0&amp;player_id=0&amp;app_id=58479" frameborder="0" allow="autoplay; fullscreen; picture-in-picture; clipboard-write" style="position:absolute;top:0;left:0;width:100%;height:100%;" title="Blokus, la règle du jeu en 5 mn"></iframe></div><script src="https://player.vimeo.com/api/player.js"></script>



Pour la gestion des couleurs
-----
```python
class colors:



    reset = '\033[0m'
    bold = '\033[01m'
    disable = '\033[02m'
    underline = '\033[04m'
    reverse = '\033[07m'
    strikethrough = '\033[09m'
    invisible = '\033[08m'

    class fg:
            black = '\033[30m'
            red = '\033[31m'
            green = '\033[32m'
            orange = '\033[33m'
            blue = '\033[34m'
            purple = '\033[35m'
            cyan = '\033[36m'
            lightgrey = '\033[37m'
            darkgrey = '\033[90m'
            lightred = '\033[91m'
            lightgreen = '\033[92m'
            yellow = '\033[93m'
            lightblue = '\033[94m'
            pink = '\033[95m'
            lightcyan = '\033[96m'

    class bg:
        black = '\033[40m'
        red = '\033[41m'
        green = '\033[42m'
        orange = '\033[43m'
        blue = '\033[44m'
        purple = '\033[45m'
        cyan = '\033[46m'
        lightgrey = '\033[47m'

#print(colors.bg.green, "SKk", colors.fg.red, "Amartya")
#print(colors.bg.lightgrey, "SKk", colors.fg.red, "Amartya")

print( colors.fg.red, "Amartya")
```




Client
------

```python
import asyncio
import json
grille_tetris = [[0] * 10 for _ in range(20)]


def placerPiece(posX,posY,pieces,grille):
    bloc_L = [
    [1, 0, 0],
    [1, 1, 1]
    ]
    x, y = posX, posY
    for i in range(len(bloc_L)):
        for j in range(len(bloc_L[0])):
            grille[y + i][x + j] = bloc_L[i][j]
    return grille

def afficheGrille () : 
    for ligne in grille_tetris:
        ligne_formattee = ["#" if cellule == 1 else "." for cellule in ligne]
        print("".join(ligne_formattee))

def convert(x):
    if x=='A':return 10
    elif x=='B':return 11
    elif x=='C':return 12
    elif x=='D':return 13
    elif x=='E':return 14
    elif x=='F':return 15
    elif x=='G':return 16
    elif x=='H':return 17
    elif x=='I':return 18
    elif x=='J':return 19
    else : return int(x)
s='*'
piece='line'
async def send_receive_matrix(reader, writer):
    round=1
    while True:
        s=input("Appuyez sur la touche entrée ou 's' pour sortir... ")
        if round==1:
        # Modifier la matrice (ajout d'une valeur)
            #matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
            matrix = grille_tetris
        else :
            x=convert(s[0:1])
            y=convert(s[2:3])
            matrix=placerPiece(x,y,piece,matrix)
            #matrix= matrix

        matrix_json = json.dumps(matrix)
        writer.write(matrix_json.encode())
        print("Matrice envoyée au serveur")
        for row in matrix:
            print(row)
        await writer.drain()


        data = await reader.read(1024)
        matrix_json = data.decode()
        matrix = json.loads(matrix_json)
        print("Matrice reçue du serveur :")
        for row in matrix:
            print(row)
        round +=1
async def main():
    reader, writer = await asyncio.open_connection('127.0.0.1', 8888)

    await send_receive_matrix(reader, writer)

    writer.close()
    await writer.wait_closed()

asyncio.run(main())

```

Sever
------

```python
import asyncio
import json

grille_tetris = [[0] * 10 for _ in range(20)]


def placerPiece(posX,posY,pieces,grille):
    bloc_L = [
    [1, 0, 0],
    [1, 1, 1]
    ]
    x, y = posX, posY
    for i in range(len(bloc_L)):
        for j in range(len(bloc_L[0])):
            grille[y + i][x + j] = bloc_L[i][j]
    return grille

def afficheGrille () : 
    for ligne in grille_tetris:
        ligne_formattee = ["#" if cellule == 1 else "." for cellule in ligne]
        print("".join(ligne_formattee))

def convert(x):
    if x=='A':return 10
    elif x=='B':return 11
    elif x=='C':return 12
    elif x=='D':return 13
    elif x=='E':return 14
    elif x=='F':return 15
    elif x=='G':return 16
    elif x=='H':return 17
    elif x=='I':return 18
    elif x=='J':return 19
    else : return int(x)

s='*'
piece='line'
async def handle_client(reader, writer):
    round=1
    while True:
        data = await reader.read(1024)
        if not data:
            break
        matrix_json = data.decode()
        matrix = json.loads(matrix_json)
        print("Matrice reçue du client :")
        for row in matrix:
            print(row)
        s=input("Appuyez sur la touche entrée ou 's' pour sortir... ")
        # Modifier la matrice (ajout d'une valeur)
        x=convert(s[0:1])
        y=convert(s[2:3])
        matrix=placerPiece(x,y,piece,matrix)
        #matrix[1][1] +=round
        matrix_json = json.dumps(matrix)
        writer.write(matrix_json.encode())
        await writer.drain()
        print("Matrice modifiée renvoyée au client")
        for row in matrix:
   ![blokus-server](https://hackmd.io/_uploads/B1sBkOEX1x.gif)
         print(row)
        round +=1
    writer.close()

async def main():
    server = await asyncio.start_server(
        handle_client, '127.0.0.1', 8888)

    addr = server.sockets[0].getsockname()
    print(f'Serveur en attente de connexions sur {addr}')

    async with server:
        await server.serve_forever()

asyncio.run(main())

```


![blokus-server](https://hackmd.io/_uploads/HkkP1O4Xke.gif)



