# Compte rendu étape 1 : morning_sunshine

## Analyse du contexte

Nous devons réalise un script dans le langage choisi (python) afin d'analyser et calculer le bénéfices réalisé par le promoteur immobilier en augmentant de 5% le loyer des appartements ayant une vue sur le lever du soleil pour l'année à venir.

Le format des données en entrée et en sortie sont au format JSON.

Nous possédons un exemple avec deux bâtiments et pour chaque bâtiment, on dispose des informations suivantes :
- Sa hauteur (en nombre d'étages)
- L'agencement d'un étage, sous forme de liste d'appartements, avec pour chacun :
- Le loyer mensuel de l'année précédente
- Les directions vers lesquelles il est orienté

## Résumé de l'approche

Après réflexion, un des moyens de réaliser cet alogrithme serait d'inverser la liste des batiments.
En effet, nous avons une liste des batiments d'Ouest en Est. Le soleil se levant à l'Est, et les appartements pouvant bloquer les étages suivants, il nous faut donc inverser cette liste d'Est en Ouest.

Cela nous évite de regarder et analyser chaque batiment dont on cherche à déterminer le prix pour voir combien d'étages seront bloqués, en regardant cette fois-ci dans une variable stockée.

## Solution

Tout d'abord, nous indiquons que nous allons ouvrir et lire le fichier json mis en paramètre avec :

    json_array = json.loads(sys.argv[1]);

Ensuite nous définisson la variable de résultat : `result` et `previous_height` à 0.
La variable `previous_height` contiendra la hauteur du plus grand immeuble dans ceux déjà parcouru.

Puis nous avons inversé la liste JSON via la fonction reverse():

json_array.reverse();

Une fois cela fait, nous pouvons commencer à parcourir chaque batiment:

- Pour chaque appartement dans la disposition du batiment, si l'appartement est orienté vers l'Est et que le nombre d'étages du batiment est plus grand que `previous_height`:

- On attribue à la variable `monthly_rent` la valeur de l'augmentation (5% de la valeur du loyer soit * 0,05)

 monthly_rent = ceil(flat['monthly_rent'] * 0.05)

- On ajoute à notre résulat `result` la variable `monthly_rent` * 12 (pour les 1 an de loyer) * (taille du batiment - previous_height)
Pour rappel : On prend seulement les étages supérieurs, qui ne seront pas bloqués par le plus haut batiment dans les précédents de la liste.

  result += monthly_rent * 12 * (building['height'] - previous_height)

Enfin si le batiment est plus grand que previous_height, celle-ci prend la valeur du batiment.

Pour finir, nous faison un print du résultat `result`, qui a été arrondi au supérieur, donnant ainsi le bénéfices réalisé en augmentant de 5% le loyer des appartements ayant une vue sur le lever du soleil sur une année de loyer.

## Compléxité

La solution comporte une compléxité de 0(n^2) car nous avons 2 boucles `for` imbriqués.

---

# Compte rendu étape 2 : money_for_nothing

## Analyse du contexte

Nous devons réalisé un script dans le langage choisi (python) afin de planifier la meilleure stratégie d'achat et de vente pour faire le maximum de profits sur la période de la prédiction.

Le format des données en entrée et en sortie sont au format JSON.

## Résumé de l'approche

Pour réaliser cette algorithme nous avons pris les cours des actions des jours donnés pour représenter graphiquement les prix par rapport au cours de l'action du jour adjacent.

Le tableau stock la comparaisons du prix du jour actuel avec le prix du jour suivant. Si le prix augmente le lendemain, il sera négatif, s'il diminue, il sera positif.

Le tableau doit stocker le jour d'achat et de vente des actions, nous mettrons à jour la variable d'achat avec le jour actuel si aucun achat n'a été effectué et que le prix du lendemain est supérieur à celui d'aujourd'hui, c'est-à-dire que nous achèterions des actions ce jour-là, de la même manière si le prix le lendemain est inférieur à celui d'aujourd'hui et qu'un achat a été effectué, nous devrons vendre ce stock aujourd'hui.

## Solution

On defini une premiere boucle qui vas comparer l'élément présent a l'élément suivant dans le tableau donné pour trouver le minimum local soit le prix d'achat le plus bas, on stop quand on atteint la fin puis on rentre le prix dans notre tableau.

while index < n - 1 and json_array[index] >= json_array[index + 1]:
            index += 1
        if index == n - 1:
            break
        result.append(index)
        index += 1

Ensuite, nous créons une seconde boucle qui va definir le prix de vente, soit le maximum local en comparant a l'élément précedent. Les deux boucles fonctionnent de la même maniere en verifiant que nous ne somme pas a la fin du tableau et que le nombre actuel est superieur (en cas de recherche de vente) ou inferieur (en cas de recherche d'achat )au nombre precedant.
Une fois la boucle arretée, si nous ne somme pas a la fin du tableau ce nombre est ajouté a notre tableau et les étapes se répetent.

    while index < n and json_array[index] >= json_array[index - 1]:
        index += 1
    sell = index - 1
    result.append(sell)
    index = sell + 1

## Compléxité

La boucle `while` externe s’exécute jusqu’à ce que ma variable `index` devienne n-1.
De plus les deux boucles internes incrémentent la valeur de mon index à chaque itération.
La fonction `append()` est de compléxité O(1).
La solution comporte donc une compléxité de O(n).

---

# Compte rendu étape 3 : schools_out

## Analyse du contexte

Nous devons réalisé un script dans le langage choisi (python) afin de déterminer le nombre minimum de salles nécessaires au déroulement de sessions d'activités prévues sur une journée.

Le format des données en entrée et en sortie sont au format JSON.

## Résumé de l'approche

Afin de réaliser cette algorithme, nous avons défini que les sessions commencaient à 8h00 et se terminer à 18h00. De plus nous avons repris l'exemple et avons définis qu'une sessions représenté 1h soit 60 minutes.

Par la suite nous avons penser à créer une liste contenant chaque session d'activités possible et prévues sur une journée.

On parcourera ensuite chaque session et on augmentera le nombre de salles nécéssaires à cette heure-ci ce qui nous donnera le nombre de salles total.

## Solution

Tout d'abord, nous indiquons que nous allons ouvrir et lire le fichier json mis en paramètre avec :

input_file = open(sys.argv[1])
json_array = json.load(input_file)

Ensuite nous déclarons une liste `openings`, puis nous parcourons chaque session de notre input en regardant les horaires :

- Si l'heure de début est compris entre l'horaire de début (inclus) et de fin de la session, on augmente le nombre salles requises.
- Sinon on le passe pour arriver au niveau des créneaux : `openings` correspondants.

Notre boucle `for` imbriqués dans une autre boucle `for` nous permet de nous assurer du bon nombre de salles nécessaire pour chacun des créneaux.

    for item in json_array:
        session = {'start': datetime.strptime(item['start'], '%H:%M'),
                'end': datetime.strptime(item['end'], '%H:%M')}

        for opening in openings:
            if session['start'] <= opening['hour'] < session['end']:
                opening['classes_required'] += 1

Enfin nous faisont un print de notre variable `classes_required` qui contient le nombre maximum de salles requis sur la liste de créneaux afin d'obtenir le nombre de salles nécessaires.

        classes_required = max(
        opening['classes_required'] for opening in openings)

    print(classes_required)

## Compléxité

Malgrès que j'ai 2 boucles `for` imbriqués cela me fait une compléxité O(1) car ma boucle `for` parcours juste le nombre de `openings` qui est constant :

        for opening in openings:
            if session['start'] <= opening['hour'] < session['end']:
                opening['classes_required'] += 1

Cependant la boucle `for` principal doit repasser sur tout les élément donné. Ce qui fera une complexité de O(n)

La solution comporte donc une compléxité de O(n)

---

# Compte rendu étape 4 : tweety_one_pilots

## Analyse du contexte

Nous devons réalisé un script dans le langage choisi (python) afin de mener une étude sur le contenu posté sur Twitter sur une période de temps donnée.
Pour ce faire il s'agit donc d'analyser les tweets postés durant cette période, et de les traiter afin d'extraire les hashtags qui reviennent le plus fréquemment.

De plus il ne faut pas oublier que un tweet peux contenir de multiples hashtags.

Le format des données en entrée et en sortie sont au format JSON.

## Résumé de l'approche

Pour réaliser cette algorithme nous allons commencer par récupere le pourcentage requis afin de retenir un hashtag.
Ensuite nous récuprons une liste avec tous les hashtags que nous allons trier pour pour en extraire des hashtags unique.
Pour finir nous allons compter le nombre de fois que les hashtags apparaissent pour chacun d'eux.

## Solution

Tout d'abord, nous créons une liste `tweet_list` qui grâce a notre première boucle `for` récupera et regroupera tous les hashtags avec la fonction `extend()`.

    for item in json_array['tweets']:
        tweet_list.extend(item['hashtags'])

Ensuite nous avons créer une autre liste `sorted_tweet_list` qui contiendra les hashtags de `tweet_list`, ce qui nous permettra par la suite de compter le nombre de fois qu'il aura apparu.

Pour finir nous créons une dernière liste `result` qui contiendra les hashtags dont le nombre d'apparition est supérieur au pourcentage donné par rapport au nombre total d'hashtags.

Pour ce faire nous divison son nombre d'apparition par le nombre total d'hastags, ensuite nous le multiplions par 100 et enfin nous le comparons au pourcentage donné.

    for hashtag in sorted_tweet_list:        
        if (100 * tweet_list.count(hashtag)/len(tweet_list) >= json_array['percentage_threshold']):
            result.append(hashtag)

Enfin nous passont par la fonction `dumps` afin de retourner notre résulat en JSON avec les guillemets et non avec des simples cotes

    res_json = json.dumps(result)

## Compléxité

La solution comporte une compléxité de O(n) car aucunes boucles est imbriquès. Nous effectuons une boucle `for` à la fois.

---

# Compte rendu étape 5 :

## Analyse du contexte

Nous devons réalise un script dans le langage choisi (python) afin concevoir un algorithme permettant d'exécuter des traitements donnés de manière optimisée.

Pour cela, le format des données en entrée sont 2 arguments, le premier argument est un liste décrivant les différentes tâches disponibles et en second argument la liste des workflows à exécuter et leurs inputs respectifs (tous les deux au format JSON).

De plus, chaque tâche primitive retournera simplement le hash MD5 correspondant à son input.
L'output d'un workflow sera égal au hash MD5 de la concaténation des bytes des différents résultats des tâches qui composent le workflow. Dans le cas où un workflow n'est composé d'aucune tâche, on doit retourner le hash MD5 correspondant à une séquence de bytes vide.

Pour chaque tâche, on dispose des informations suivantes :

* Son ID numérique unique
* Son type :
* `primitive`, s'il s'agit d'une tâche primitive
* `workflow`, s'il s'agit d'un workflow
* La liste des IDs des différentes tâches qui la composent (uniquement dans le cas d'un workflow)

Pour chaque exécution de workflow, on dispose des informations suivantes :

* L'ID numérique du workflow
* La string à utiliser comme input

la liste des tâches ne contient pas de dépendance circulaire entre les workflows. Et la liste d'exécutions comporte toujours des IDs de workflows présents dans la liste des tâches.

Ef efin nous devons afficher une liste de strings, chacune correspondant respectivement à la représentation hexadécimale du résultat de chaque exécution au format JSON.

## Résumé de l'approche

Tout d'abord, il y a 3 points importants à ne pas négliger, le fait que la liste des tâches ne contient pas de dépendance circulaire entre les workflows, que la liste d'exécutions comporte toujours des IDs de workflows présents dans la liste des tâches et que les workflows sont des tâches qui décrivent un enchaînement de tâches qui peuvent être des ``primitives`` ou d'autres ``workflows``

Donc, après réflexion, un des moyens de réaliser cet algorithme serait d'utiliser le deuxième argument (liste d'exécution) pour parcourir la liste des tâches afin de réaliser les tâches contenues dans un workflow.

Puis de créer une fonction récursive permettant de gérer les tâches du workflows, que ce soit des tâches primitives ou d'autre workflows ou un tableau vide.

Et enfin de stoker les résultats retourner par la fonction dans un tableau au format hexadécimale et d'afficher le tout en format JSON.

## Solution

Tout d'abord, nous récupérons les arguments en entrée et nous les stockons dans les variable `task_json_array` et `execution_json_array` au format JSON.

task_json_array = json.loads(sys.argv[1])
execution_json_array = json.loads(sys.argv[2])

Puis nous parcourons la liste `execution_json_array` et pour chaque workflow, nous parcourons la liste `task_json_array` et nous vérifions si l'ID du workflow est égale à l'ID d'une tâche, si c'est le cas, nous vérifions si le workflow contient des tâches ou non, si elle sont vide on stock dans `resluts` la valeur correspondante d'un bytes vide. Sinon on utilise la fonction `workflow_tasks` pour récupérer les résultats des tâches du workflow et on stocke le résultat dans `results`.

for execution in execution_json_array:
    for task in task_json_array:
        if execution['workflow_id'] == task['id']:
            if task['tasks'] == []:
                empty_bytes = b''
                hash = hashlib.md5(empty_bytes)
                results.append(hash.hexdigest())
            else:
                concatenated_bytes = b''
                for task_id in task['tasks']:
                    concatenated_bytes += workflow_tasks(task_id, execution['input'], task_json_array)
                    results.append(hashlib.md5(concatenated_bytes).hexdigest())

la fonction `workflows_taks` prend en paramètre l'ID d'une tâche, l'input du workflow et la liste des tâches.

def workflow_tasks(task_id, execution_input, task_json_array):

Elle parcours la liste des tâches et vérifie si l'ID de la tâche est égale à l'ID d'une tâche, si c'est le cas, elle vérifie si la tâche est un workflow ou une tâche primitive, si c'est un `primitive`, elle retourne le hash MD5 de l'input du workflow. Si c'est un workflow, elle appelle la fonction `workflow_tasks` avec l'ID de la tâche, l'input du workflow et la liste des tâches. Sinon, elle retourne le hash MD5 de l'input du workflow. De plus via ce code, nous n'avons pas besoin de vérifier si la liste des tâches est vide ou non. Car si elle est vide la variable `concatenated_bytes` sera égale à un bytes vide.

for task in task_json_array:
    if task_id == task['id'] and task['task_type'] == "primitive":
        md5 = hashlib.md5()
        encoded_input = execution_input.encod('UTF-8')
        md5.update(encoded_input)
        return md5.digest()
    if task_id == task['id'] and task['task_type'] == "workflow":
        concatenated_bytes = b''
        for task_id in task['tasks']:
            concatenated_bytes += workflow_tasks(task_id, execution_input, task_json_array)
        return hashlib.md5(concatenated_bytes).digest()
        

Ainsi, nous avons une liste de résultats, que nous convertissons en format hexadécimale

results.append(hashlib.md5(concatenated_bytes).hexdigest())

et nous l'affichons en format JSON.

print(json.dumps(results))

## Compléxité

La solution comporte une complexité de O(n⁶). En effet, nous avons la boucles `task['tasks']` qui est imbriquées dans la boucle `task_json_array`, celui-ci est imbriqué dans la boucle `execution_json_array` et nous avons une fonction récursive de O(n³) qui est imbriquée dans une boucle `task['tasks']`. Ce qui donne une complexité de O(n⁶).

---

# Compte rendu étape 6 :

## Analyse du contexte

Nous devons réalise un script dans le langage choisi (python) afin de chercher des chaînes de caractères précises dans des fichiers, afin de connaître l'ensemble des correspondances trouvées ainsi que leur position dans le fichier.

Le format des données en entrée sont les argurments de chaîne de caractère, qui sont préciser via l'option `-e` et le reste des arguments sont les fichiers à analyser.
Puis, en sortie, le format des données sont en format JSON.

## Résumé de l'approche

Après réflexion, un des moyens de réaliser cet algorithme serait de séparer les arguments qui sont des chaînes de caractère, du reste des arguments qui correspondrait au fichier a analyser.

En stockant les fichiers dans une liste, nous pourrons alors parcourir cette liste et vérifier les chaînes de caractères dans chaque fichier afin de stocker la chaîne de caractère et sa position directement dans un variable résultat qui sera au format JSON.

## Solution

Tout d'abord, nous initialisons la variable `list_file_path` qui sera un tableau contenant les fichiers entrer en argument, une variable `extension` qui sera également un tableau qui contiendra les chaînes de caractères, une autre variable prev_arg qui nous permettra de savoir si l'argument précédent était l'option `-e` ou non, puis la variable `result` qui sera un tableau qui contiendra les chaînes de caractères et leur position dans le fichier.

Nous allons donc parcourir les arguments en entrée, et si `prev_arg` est égale à l'option `-e`, alors nous allons stocker la chaîne de caractère dans la variable `extension` sinon on stocke le chemin du fichier dans la variable `list_file_path` et `prev_arg` prendra la valeur du précedent arguments.

for arg in sys.argv[1:]:
    if prev_arg == '-e':
        extension.append(arg)
    elif arg != '-e':
        list_file_path.append(arg)
    prev_arg = arg

Ensuite nous parcourons la liste `list_file_path` et pour chaque fichier, nous ouvrons le fichier et nous parcourons chaque ligne du fichier, puis nous parcourons chaque chaîne de caractère de la variable `extension` et nous vérifions si la chaîne de caractère est dans la ligne, si c'est le cas, nous stockons la chaîne de caractère et sa position dans la variable `result`.

for file_path in list_file_path:
    with open(file_path, "r") as file:
        text = file.read()
        for string in extension:
            for data in re.finditer(string, text):
                result.append({"file": file_path, "pattern": data.group() "offset": data.start()})

Enfin pour retourner `result` au format JSON, nous utilisons la fonction `json.dumps()`

json_result = json.dumps(result)

## Compléxité

La solution comporte une compléxité de 0(n^2) car nous parcourons la liste `list_file_path` et pour chaque fichier, nous parcourons chaque chaîne de caractère de la variable `extension`.