6 exercices algorithmiques en Python (Master 1, ETNA — module IDV-ALG4).
Chaque programme lit des données JSON en entrée et écrit le résultat sur la sortie standard.
Un promoteur veut savoir quel profit il peut dégager en augmentant de 5% les loyers des appartements exposés à l'Est. Les bâtiments plus hauts font de l'ombre à leurs voisins côté Ouest.
Approche : parcours des bâtiments de droite à gauche (Est→Ouest), en gardant la hauteur maximale rencontrée pour déterminer les étages exposés de chaque bâtiment.
Complexité : O(n × m) — n bâtiments, m appartements par étage
python morning_sunshine/morning_sunshine.py '[{"height": 15, "floor_layout": [{"monthly_rent": 1200, "orientations": ["E","N"]}]}]'Trouver la séquence optimale d'achats/ventes sur une série de prix pour maximiser le profit. On doit vendre avant de racheter.
Approche : parcours unique — on identifie les creux locaux (achat) et les pics locaux (vente) successifs.
Complexité : O(n)
python money_for_nothing/money_for_nothing.py '[108, 45, 216, 215, 213, 96, 167, 245]' # → [1, 2, 5, 7]
Calculer le nombre minimum de salles pour accueillir un planning de sessions qui se chevauchent.
Approche : on génère deux événements par session (+1 à l'ouverture, -1 à la fermeture), on trie par heure, et le pic du compteur donne la réponse. Les fins et débuts simultanés se traitent correctement grâce au tri secondaire sur le delta.
Complexité : O(n log n)
python schools_out/schools_out.py schools_out/data.json
Identifier les hashtags Twitter dont la fréquence dépasse un seuil (en % du nombre total de hashtags).
Approche : Counter sur l'ensemble des hashtags collectés, filtre sur le seuil calculé.
Complexité : O(n) — n = nombre total de hashtags
python tweety_one_pilots/tweety_one_pilots.py tweety_one_pilots/data/data.json
Exécuter un graphe de tâches : les primitives retournent le hash MD5 de leur input, les workflows enchaînent des sous-tâches et hashent la concaténation de leurs résultats.
Approche : résolution récursive avec mémoïsation par (task_id, input) pour éviter les recalculs à l'intérieur d'une même exécution. Le graphe est acyclique par construction (garanti par le sujet).
Complexité : O(w × t) — w exécutions, t tâches uniques
python flowrent_pagny/flowrent_pagny.py "$(cat flowrent_pagny/tasks_1.json)" "$(cat flowrent_pagny/workflow_1.json)"
Chercher des chaînes de caractères dans des fichiers texte et retourner leur position (offset).
Approche : re.finditer pour chaque motif sur le contenu de chaque fichier. Résultat trié par fichier puis par motif.
Complexité : O(F × M × N) — F fichiers, M motifs, N taille du fichier
python pattern_particulier/pattern_particulier.py -e dolor -e volupta pattern_particulier/lipsum.txt
Python 3.7+, aucune dépendance externe.