# Examen 2025

--- 
_**201.1 Algorithmes et Structures de données**_

![unit tests workflow](https://git.kb28.ch/HEL/AlgoDS-Examen2025/actions/workflows/tests.yaml/badge.svg)

Voici mes réponses pour l'examen 2025 d'_Algorithmes et Structures de données_ ainsi que les tests unitaires fournis.

## Exercice 1

<table>
<tr>
<td><strong>But</strong></td>
<td>Compter le nombre de valeurs positives différentes ayant leur opposé dans une liste</td>
</tr>
<tr>
<td><strong>Input</strong></td>
<td>La liste des demi-touches (entiers relatifs non-nuls)</td>
</tr>
<tr>
<td><strong>Output</strong></td>
<td>Le nombre de touches distinctes dont les valeurs positives et négatives sont dans la liste</td>
</tr>
<tr>
<td><strong>Signature</strong></td>
<td>

```python
def countKey(
    pieces: list[int]
) -> int:
```

</td>
</tr>
</table>

[Source](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/src/Ex1.py)
/
[Tests](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/tests/test_ex1.py)


## Exercice 2

<table>
<tr>
<td><strong>But</strong></td>
<td>Trouver le chemin le plus court entre deux points, en considérant que certaines routes ne sont praticables que de nuit/jour</td>
</tr>
<tr>
<td><strong>Input</strong></td>
<td>Nœud de départ (index), nœud d'arrivée (index) et liste des routes / arêtes (nœud 1, nœud 2, restriction)</td>
</tr>
<tr>
<td><strong>Output</strong></td>
<td>Liste des nœuds (index) à parcourir</td>
</tr>
<tr>
<td><strong>Signature</strong></td>
<td>

```python
def findSafestPath(
    start: int,
    end: int,
    intersections: list[tuple[int, int, int]]
) -> list[int]:
```

</td>
</tr>
</table>

[Source](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/src/Ex2.py)
/
[Tests](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/tests/test_ex2.py)


## Exercice 3

<table>
<tr>
<td><strong>But</strong></td>
<td>Trouver dans un réseau de console un sous-graphe connexe de taille donnée</td>
</tr>
<tr>
<td><strong>Input</strong></td>
<td>Taille n du sous-graphe recherché, liste des connexions</td>
</tr>
<tr>
<td><strong>Output</strong></td>
<td>Liste de n consoles toutes interconnectées</td>
</tr>
<tr>
<td><strong>Signature</strong></td>
<td>

```python
def findTightlyLinkedConsoles(
    n: int,
    consoles: list[tuple[int, int]]
) -> list[int]:
```

</td>
</tr>
</table>

[Source](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/src/Ex3.py)
/
[Tests](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/tests/test_ex3.py)


## Exercice 4

<table>
<tr>
<td><strong>But</strong></td>
<td>Compter le nombre de séquences de N coups infligeant un total de H dégâts</td>
</tr>
<tr>
<td><strong>Input</strong></td>
<td>Nombre N de coups dans la séquence, nombre C de coups possibles (dégâts 1 à C inclus), total H de dégâts</td>
</tr>
<tr>
<td><strong>Output</strong></td>
<td>Nombre de séquences possibles</td>
</tr>
<tr>
<td><strong>Signature</strong></td>
<td>

```python
def computeNbrOfDifferentSequences(
    N: int,
    C: int,
    H: int
) -> int:
```

</td>
</tr>
</table>

[Source](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/src/Ex4.py)
/
[Tests](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/tests/test_ex4.py)


## Exercice 5

<table>
<tr>
<td><strong>But</strong></td>
<td>Trouver les placements de pièces Minitris formant un rectangle plein</td>
</tr>
<tr>
<td><strong>Input</strong></td>
<td>Largeur de la grille, longueur de la grille, liste des pièces à poser</td>
</tr>
<tr>
<td><strong>Output</strong></td>
<td>Liste des positions des pièces</td>
</tr>
<tr>
<td><strong>Signature</strong></td>
<td>

```python
def playMinitrisFastAndWell(
    board_width: int,
    board_height: int,
    pieces: list[tuple[tuple[int,int], tuple[int,int]]]
) -> list[list[int, int]]:
```

</td>
</tr>
</table>

[Source](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/src/Ex5.py)
/
[Tests](https://git.kb28.ch/HEL/AlgoDS-Examen2025/src/branch/main/tests/test_ex5.py)