# CP Python: Séances 13 et 14

## 0) Ressources de la séance 12
* [Guide de séance](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/HkWCjS7Tv)
* [Correctif de la QBF](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/r1cwBFOTv)

## 1) A préparer: Listes chaînées
### A.Théorie
- [ ] Lire les [slides *Semaine 12 - Restructuration*](https://drive.google.com/file/d/1FJWRw4MxG5i0cysI8G0w5MUocGG19Kl9/view?usp=sharing)
- [ ] Lire la section [6 - Linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/linked_lists)
- [ ] Essayer et comprendre le code développé dans le syllabus et qui se trouve aussi dans l'annexe [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list)
- [ ] *Optionnel*: Je vous fournis également [ma synthèse](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/SyE9Kf6aE)

| Liste chaînée | Parcours |
| -------- | -------- |
| | |
| **Points importants** | **Dessiner aide beaucoup!** NB. Attention à l'ordre des opérations. |
| | 

### B. Exercices: 1ere partie -> *Utiliser ce [REPL](https://repl.it/join/cwpsfrzn-guillaumegst)*
Dans les [exercices du cours](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-exercises/PART_III/MISSION_11/preparation):
- [ ] **Répondez aux *Questions à choix multiples* (via Inginious)**
- [ ] **Résoudre *3. Imprimer une liste chaînée (généralisation)***
> Dans le code donné dans l'annexe [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list) la méthode `print()` de la classe LinkedList imprime les éléments d'une liste chaînée, séparés par une espace. Par exemple:
>
> ```
> >>> l = LinkedList()
> >>> l.add(3)
> >>> l.add(2)
> >>> l.add(1)
> >>> l.print()
> [ 1 2 3 ]
> ```
> Or, normalement la convention est de séparer les éléments d'une liste par des virgules. Ajoutez une nouvelle méthode print_avec_virgule() dans la classe LinkedList qui imprime la liste comme suite:
>
> ```
> >>> l.print_avec_virgule()
> [ 1, 2, 3 ]
> ```
> Attention: il n'y a pas de virgule après le dernier élément ou si on imprime une liste vide.
>
> ```
> >>> l = LinkedList()
> >>> l.print_avec_virgule()
> [ ]
> ```
> ---
> Généralisez la méthode print_avec_virgule de l'exercice précédente par une méthode print_avec_separateur qui peut prendre n'importe quelle séparateur. Par exemple:
>
> ```
> >>> l.print_avec_separateur(", ")
> [ 1, 2, 3 ]
> >>> l.print_avec_separateur(" ")
> [ 1 2 3 ]
> >>> l.print_avec_separateur(" - ")
> [ 1 - 2 - 3 ]
> ```
- [ ] **Résoudre *9. Insérer un élément***
> *Considérez qu'on désire utiliser la classe LinkedList pour stocker une liste de strings. On souhaite qu'elle soit en permanence en ordre alphabétique croissant.*
1. Pour la première partie utilisez [ce Jamboard](https://jamboard.google.com/d/1QX0XZxUC9dhaLTlD5lIlofqHg0_HKq0dOjSMHS7zO8k/edit?usp=sharing) pour les illustrations.
> --> 1. Dessinez complètement une telle liste chainée contenant les trois strings "abc", "def" et "xyz".

> --> 2. Expliquez en français et dessinez les opérations à effectuer pour ajouter un Node contenant "aaa" dans cette liste ? Idem avec "ghi" ? "def" ? "zzz" ?
>
2. Implémentez `insert` dans `LinkedList`. Repartez du *[REPL](https://repl.it/join/cwpsfrzn-guillaumegst)*, qui inclut déjà le code fourni en [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list).

- [ ] **Réfléchissez déjà à la résolution de la QBF, dont l'énoncé est disponible [ici](https://www.docdroid.net/q5Oa6TW/mission-11-qbf-pdf). Nous terminerons l'exercice ensemble en séance.**

:::info
Correction ici avec énoncé: [DEEPNOTE](https://deepnote.com/project/2b95be22-c40d-4807-b3ec-acc946a0e44d) :rocket:
- Alternative: [Version lecture](https://deepnote.com/publish/2b95be22-c40d-4807-b3ec-acc946a0e44d)
- Alternative 2 (sans énoncé): [REPL](https://repl.it/@GuillaumeGst/CP-Python-Tuteur-S13)
:::

------
### C. Examen blanc -> *Utiliser ce [REPL](https://repl.it/join/hpbiumco-guillaumegst)*
Dans ce 2e REPL, résolvez tout l'examen blanc qu'on vous a fourni :-)

:::success
<div style="text-align:center;font-size:20px;font-weight:bolde;">
Bon travail 💪
</div>
:::

---
### Annexe: 2D-to-1D mapping :wink:

Given x and y, and 2D array sizes `width` (for x-direction) and `height` (for y-direction), you can calculate the according index `i` in 1D space (zero-based) by

i = x + width*y;

and the reverse operation is

x = i % width;    
# % is the "modulo operator", the remainder of i // width;
y = i // width;    
# where "//" is an integer division