Skip to content

Sujet

Le projet est à réaliser individuellement et devra être rendu d'ici la fin du semestre.

Objectifs

Les deux objectifs du projet sont les suivants :

  • calculer une valeur approximative de π à l'aide d'une simulation de Monte-Carlo ;
  • générer une image animée représentant la simulation comme ci-dessous.

Image animée

Pour calculer une approximation de π à l'aide d'une simulation de Monte-Carlo en tirant n points aléatoires (comme au casino), un algorithme simple est le suivant :

  • initialiser un compteur à 0 ;
  • pour i allant de 1 à n :
    • générer un point aléatoire (x,y) dans un carré de longueur 2 et de centre (0,0). Pour cela il suffit de générer x dans [-1,1] et y dans [-1,1] ;
    • si le point est dans le cercle de centre (0,0) et de rayon 1, ajouter 1 au compteur ;
  • l'estimation de π/4 est la valeur du compteur divisée par le nombre n.

Pour en savoir plus sur le sujet, nous nous référerons au très clair billet de Bruno Tuffin sur le site interstices.info.

Pour la création de l'image animée, nous générerons des images au format PPM puis nous les agrégerons comme expliqué dans la prochaine section.

Travail à réaliser

Le travail à réaliser se décompose en deux parties.

Première partie : simulation

La première partie du projet consiste à écrire un module Python simulator.py qui sera le coeur de notre simulation. Autrement dit, ce module se charge uniquement du travail en lien avec le calcul d'une approximation de π sans se préoccuper des questions de visualisation sous forme d'image.

Il est demandé que le module simulator.py soit également un programme exécutable permettant de donner une approximation de π en utilisant un nombre de points donné sur la ligne de commande tel qu'illustré ci-dessous :

[selvama@ensipc215 projet_bpi]$ ./simulator.py 100000000
3.14152532

Deuxième partie : génération d'images PPM

Nous allons maintenant utiliser simulator.py comme un module pour passer aux choses sérieuses, c'est à dire à la génération de notre image animée représentant une simulation. Le travail demandé consiste à écrire un programme Python approximate_pi.py qui :

  • reçoit 3 arguments dans l'ordre suivant depuis la ligne de commande :
    • la taille de l'image en pixels (qui est carrée, donc un seul entier) ;
    • le nombre de point n à utiliser dans la simulation ;
    • le nombre de chiffres après la virgule à utiliser dans l'affichage de la valeur approximative de π.
  • implémente une fonction generate_ppm_file(...) qui génère une image au format PPM. L'image doit montrer les points qui sont à l'intérieur du cercle d'une certaine couleur, les points qui sont à l'extérieur du cercle d'une autre couleur et la valeur approchée de π comme l'illustre l'image animée ci-dessus. Le nom de l'image doit être au format img0_3-13776.ppm : 0 indique le numéro de l'image dans la simulation totale (0 en l'occurrence, donc la première image) et 3-13776 correspond à l'approximation courante de π en utilisant le nombre de chiffres après la virgule spécifié sur la ligne de commande (5 en l'occurrence). La signature de la fonction n'est volontairement pas donnée pour que chacun puisse réaliser sa propre solution ;
  • génère une image PPM, en utilisant la fonction generate_ppm_file, représentant l'état courant de la simulation à chaque fois qu'un dixième du nombre total de points a été tiré. Dix images seront donc générées ;
  • utilise le programme convert pour créer une image animée au format GIF à partir des dix images PPM.

Évaluation

Critères d'évaluation

L'évaluation du projet se fera sur la base des critères suivants :

  • justesse du code : le programme réalise bien ce qui est demandé ;
  • qualité du code : utilisation d'au moins deux modules tel que demandé ci-dessus et utilisation de pylint. Le fichier de configuration pour pylint est disponible ici. Ce fichier doit être placé à la racine de votre répertoire personnel et doit être nommé .pylintrc;
  • performance du programme en fonction des entrées ;
  • utilisation mémoire du programme en fonction des entrées ;
  • le poids des images PPM générées (c'est à dire le nombre d'octets sur le disque dur) ;
  • respect des consignes ci-dessous.

À titre d'information, le programme qui a généré l'image animée ci-dessus correspondant a une simulation avec un million de point a pris environ 9 secondes (sur un ordinateur portable récent assez haut de gamme) et a utilisé un maximum de 205 mégaoctets de mémoire à un instant donné. Les dix images PPM générées, d'une taille de 800 x 800, pèsent 1,9 mégaoctets chacune.

Des tests automatiques seront utilisés sur votre code afin d'évaluer ces critères.

Rendu

À la fin du projet, vous devez rendre :

  • votre code, c'est à dire uniquement vos fichiers Python ;
  • un rapport de deux pages maximum.

Dans le rapport vous présenterez, en argumentant, l'état de votre programme vis à vis des critères ci-dessus. Comme le rapport est limité à deux pages, il ne faut surtout pas reprendre le sujet mais présenter directement vos arguments.

Consignes à respecter

Il est demandé de respecter les consignes suivantes dans votre code :

  • lancer une exception sans l'attraper si une ou plusieurs entrées incorrectes sont données par l'utilisateur sur la ligne de commande. Autrement dit, si l'utilisateur lance le programme avec ./approximate_pi.py tutu 10000 4 ou avec ./approximate_pi.py -800 100000 4 il doit voir dans son terminal une erreur indiquant l'exception qui a été lancée ainsi que la pile d'appels. L'interpréteur se charge de tout cet affichage pour nous quand on lance une exception et que celle-ci n'est jamais attrapée et donc remonte jusqu'au sommet de la pile d'appels ;
  • utiliser des f-string quand cela est pertinent ;
  • utiliser le module subprocess pour générer l'image animée GIF à partir des images PPM ;

Résumé des consignes et précisions apportées au fil du projet sur le salon général BPI

  • ne pas mettre son nom ni dans le rapport ni dans les fichiers Python (c'est pour corriger de façon anonyme) ;
  • des valeurs raisonnables, disons entre 1 et 7, seront utilisées pour le paramètre nombre de décimales ;
  • l'archive ne doit contenir que vos fichiers Python et votre rapport, rien d'autre ;
  • vous pouvez utiliser des modules externes comme numpy, même si ce n'est pas du tout nécessaire ;
  • vous pouvez utiliser PIL ou autre chose pour rajouter le texte de π par dessus votre image, même si l'objectif premier était de le coder à la main en pensant à l'afficheur 7 segments de votre gadget électronique préféré ;
  • le temps d'exécution absolu de votre programme sur des entrées particulières n'est pas très important. Ce qui compte surtout, c'est l'évolution du temps en fonction des entrées, c'est à dire la complexité ;
  • idem pour l'utilisation mémoire ;
  • le module simulator.py doit fournir à minima les points aléatoires au programme approximate_pi.py ainsi que la fonction indiquant si un point est dans le cercle unitaire ou non ;
  • idéalement, la taille du texte de π par dessus votre image s'adapte à la taille de l'image ;
  • aucun problème si votre programme est capable de prendre des arguments optionnels en plus des 3 arguments obligatoires ;
  • respecter scrupuleusement les noms des fichiers Python et image indiqués sur cette page un peu plus haut ;

Cliquez ici pour révéler la correction.

Correction

Voici ci-dessous deux propositions de correction. D'autres solutions faisant des choix différents impliquant éventuellement des complexité mémoire et temps de calcul différentes, néanmoins toutes aussi raisonnables sont possibles. On peut notamment citer une autre solution consistant à stocker toute l'image en mémoire via une list ou un bytearray et "écrire les pixels" directement au bon endroit dans cette list ou ce bytearray. N'hésitez pas à contacter vos enseignants si vous voulez discuter d'une solution particulière.

simulator.py

Les points clés sont les suivants :

  • la fonction génératrice simulate_iterator(nb_point) renvoie un itérateur permettant de tirer aléatoirement nb_point points (x, y) avec x dans [-1, 1] et y dans [-1, 1]. En plus du point courant, l'itérateur renvoie un booléen indiquant si le point courant est dans le cercle ou non ainsi que le nombre de points déjà tirés appartenant au cercle ;

  • lorsque simulator.py est utilisé comme programme principal, on crée simplement un itérateur avec la fonction génératrice simulate_iterator(nb_point) puis on le parcours entièrement sans rien faire juste pour récupérer le nombre total de points dans le cercle. Avec cette valeur on calcul l'approximation de π. La complexité mémoire du programme est donc constante et la complexité en temps de calcul est une fonction linéaire du nombre de points.

#!/usr/bin/env python3


"""Heart of the simulation.

This module provides:

- a Point type made of two integers called x and y
- a function to fix the randomness of point generation
- a function to generate a random point
- a function to approximate the value of PI from points
"""

import math

import random
import collections
import sys

# A point in a square of size 2.
# Hence point.x ∈ [-1, 1] and point.y ∈ [-1, 1]
Point = collections.namedtuple("Point", ["x", "y"])

def fix_random_from(number):
    """Fix the random number generation for reproductibility

    The generated sequence of points must be same every time
    this function is called with the same number before the
    first call to create_random_point.
    """
    random.seed(number)

def create_random_point():
    """Return a new random point between (0, 0) and (max_val, max_val)"""
    x_coord = random.uniform(-1, 1)
    y_coord = random.uniform(-1, 1)
    return Point(x_coord, y_coord)

def simulate_iterator(nb_points):
    """Generator for the simulation"""
    nb_points_in_circle = 0
    for _ in range(nb_points):
        point = create_random_point()
        in_circle = is_in_circle(point)
        nb_points_in_circle += int(in_circle)
        yield point, in_circle, nb_points_in_circle

def simulate_quadratic_with_list(nb_points):
    """Simulation using a list.

    For testing auto tests only.
    Linear in memory, quadratic in time
    """
    nb_points_in_circle = 0
    points = []
    for _ in range(nb_points):
        for i, _ in enumerate(range(nb_points)):
            if i == 0:
                point = create_random_point()
                points.append(points)
                in_circle = is_in_circle(point)
                nb_points_in_circle += int(in_circle)
    return (points, in_circle, nb_points_in_circle)

def is_in_circle(point):
    """Return True if the point is in the unit circle and False otherwise"""
    dist_from_center = math.sqrt((point.x - 0.0)**2 + (point.y - 0.0)**2)
    return dist_from_center <= 1

def main():
    """Program's entry point"""

    # Program's inputs is given on the command line
    if len(sys.argv) != 2:
        print("utilisation ./simulator.py nb_points")
    nb_points = int(sys.argv[1])
    if nb_points <= 0:
        raise ValueError("all parameters must be integers "
                         "strictly greater than 0")

    # Fix random in the simulator
    fix_random_from(42)

    # Main simulation loop using generator function
    for last in simulate_iterator(nb_points):
        pass
    # pylint: disable=undefined-loop-variable
    _, _, nb_points_in_circle = last

    # Main simulation loop using list
    # For testing the automatic test only
    # i.e to have LINEAR memory complexity
    # instead of CONSTANT and quadratic
    # in time instead of linear
    # _, _, nb_points_in_circle = simulate_quadratic_with_list(nb_points)

    # Approximate the value of PI from the points
    # Nous on sait que nb_points > 0, donc on le dit à pylint
    pi_approx = 4 * nb_points_in_circle / nb_points
    print(pi_approx)

if __name__ == "__main__":
    main()

approximate_pi.py

Les points clés sont les suivants :

  • comme indiqué ci-dessous, simulator.py ne stocke jamais les points tirés aléatoirement dans une liste mais fourni un itérateur sur ces points ;
  • on ne stocke jamais toute l'image en mémoire mais seulement les pixels correspondant aux points déjà tirés aléatoirement par simulator.py ;
  • dans l'algorithme 1, le fait de ne jamais stocker toute l'image en mémoire implique la nécessité de trier ces pixels avant de dessiner une image PPM pour avoir une complexité en temps de calcul raisonnable ;
  • dans l'algorithme 2, on utilise le fait que la recherche d'appartenance à un set se fait en temps constant.
#!/usr/bin/env python3


"""Monte Carlo simulation to approximate π."""

# Imports from standard library
import collections
import subprocess
import sys

# Then, imports from our own modules
import simulator

# Stuff to represent the 3 different PPM formats
PPM_ASCII_255 = 0
PPM_ASCII_1 = 1
PPM_BINARY_1 = 2
PPM_FILE_TYPE = PPM_BINARY_1
PPMHeaderInfos = collections.namedtuple("PPMHeaderInfos",
                                        ["magic_number",
                                         "max_color_val"])
PPM_HEADER_INFOS = {
    PPM_ASCII_255 : PPMHeaderInfos("P3", 255),
    PPM_ASCII_1 : PPMHeaderInfos("P3", 1),
    PPM_BINARY_1 : PPMHeaderInfos("P6", 1)
}

# Type for digit bars used to draw the "text"
# of the π approximation.
# A digit bar is a rectangle inside a slot,
# hence its coordinate are defined considering (0,0)
# is the top left of the slot.
DigitBar = collections.namedtuple("DigitBar", ["top_left",
                                               "width",
                                               "height"])

# Type for representing a pixel
Pixel = collections.namedtuple("Pixel", ["line",
                                         "col",
                                         "in_circle"])

def is_in_bar(line, col, barr):
    """Return True if (line, col) is in bar else False."""
    if barr.top_left.col <= col <= barr.top_left.col + barr.width and \
       barr.top_left.line <= line <= barr.top_left.line + barr.height:
        return True
    return False

def is_in_bars(line, col, bars):
    """Return True if (line, col) is in one of the bar in bars else False."""
    for barr in bars:
        if is_in_bar(line, col, barr):
            return True
    return False

def get_pi_rectangle(image_size):
    """"Return the rectangle in the image where to draw PI text."""

    # The PI rectangle depends on image's size
    # The height is height_prop of the image size
    # The width is width_prop of the image size
    pi_rect_height_prop = 1 / 12
    pi_rect_width_prop = 1 / 6
    pi_rect_top_left = Pixel(int(image_size *
                                 (1 - pi_rect_height_prop) / 2), # line
                             int(image_size *
                                 (1 - pi_rect_width_prop) / 2), # col
                             False)
    pi_rect_width = int(image_size * pi_rect_width_prop)
    pi_rect_height = int(image_size * pi_rect_height_prop)
    return pi_rect_top_left, pi_rect_width, pi_rect_height

def get_pi_pixels_it(pi_approx_s, image_size):
    """Return an iterator over the pixels to draw in black for PI text.

    The pixels are returned sorted by line first and then by column.
    pi_approx_s is the string representation of the pi approximation.
    The given rectangle is the location where to draw the text.
    The text is made of a number of digits plus a dot such as :
        d1.d2d3d4d5 ...
    """

    top_left, width, height = get_pi_rectangle(image_size)

    line_stroke_p = 5
    line_stroke = int(height * line_stroke_p / 100)
    margin_between_slots = line_stroke
    point_slot_width = line_stroke * 2
    slot_width = width // (len(pi_approx_s) - 1) - margin_between_slots
    slot_height = height

    # First two slots are always present. They correspond
    # to "3." in the pi_approx string
    slots = [(0,
              slot_width),
             (1 * slot_width + 1 * margin_between_slots,
              1 * slot_width + 1 * margin_between_slots + point_slot_width)]

    # Then comes "pi_precision" digits after the dot
    precision_digits_slots = [(i * slot_width + (i + 1) *
                               margin_between_slots + point_slot_width,
                               (i + 1) * slot_width + (i + 1) *
                               margin_between_slots + point_slot_width)
                              for i in range(1, len(pi_approx_s) - 1)]
    slots.extend(precision_digits_slots)

    # Define the bars of the digital numbers :)
    h_top_bar = DigitBar(Pixel(0, 0, False),
                         slot_width, line_stroke)
    h_middle_bar = DigitBar(Pixel(slot_height // 2 - line_stroke // 2,
                                  0, False),
                            slot_width, line_stroke)
    h_bottom_bar = DigitBar(Pixel(slot_height - line_stroke,
                                  0, False),
                            slot_width, line_stroke)
    v_top_left_bar = DigitBar(Pixel(0, 0, False),
                              line_stroke, slot_height // 2)
    v_top_right_bar = DigitBar(Pixel(0, slot_width - line_stroke,
                                     False),
                               line_stroke, slot_height // 2)
    v_bottom_left_bar = DigitBar(Pixel(slot_height // 2, 0, False),
                                 line_stroke, slot_height // 2)
    v_bottom_right_bar = DigitBar(Pixel(slot_height // 2,
                                        slot_width - line_stroke,
                                        False),
                                  line_stroke, slot_height // 2)

    # Define the bars for all numbers between 0 and 9
    zero_bars = (h_top_bar, h_bottom_bar,
                 v_top_left_bar, v_top_right_bar,
                 v_bottom_left_bar, v_bottom_right_bar)
    one_bars = (v_top_right_bar, v_bottom_right_bar)
    two_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                v_top_right_bar, v_bottom_left_bar)
    three_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                  v_top_right_bar, v_bottom_right_bar)
    four_bars = (h_middle_bar,
                 v_top_right_bar, v_bottom_right_bar,
                 v_top_left_bar)
    five_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                 v_top_left_bar, v_bottom_right_bar)
    six_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                v_bottom_right_bar,
                v_top_left_bar, v_bottom_left_bar)
    seven_bars = (v_top_right_bar, v_bottom_right_bar,
                  h_top_bar)
    eight_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                  v_top_right_bar, v_bottom_right_bar,
                  v_top_left_bar, v_bottom_left_bar)
    nine_bars = (h_top_bar, h_bottom_bar, h_middle_bar,
                 v_top_right_bar, v_bottom_right_bar,
                 v_top_left_bar)

    # Map caracters to bars
    car_to_bars = {"0" : zero_bars,
                   "1" : one_bars,
                   "2" : two_bars,
                   "3" : three_bars,
                   "4" : four_bars,
                   "5" : five_bars,
                   "6" : six_bars,
                   "7" : seven_bars,
                   "8" : eight_bars,
                   "9" : nine_bars}

    # Yield pixels line by line
    slot = 0
    for line in range(height):
        for slot_idx, slot in enumerate(slots):
            for col in range(slot[0], slot[1]):
                current_car = pi_approx_s[slot_idx]
                if current_car in car_to_bars:
                    if is_in_bars(line,
                                  col - slot[0],
                                  car_to_bars[current_car]):
                        yield Pixel(line + top_left.line,
                                    col + top_left.col,
                                    False)
                elif current_car == ".":
                    if line > height - point_slot_width:
                        yield Pixel(line + top_left.line,
                                    col + top_left.col,
                                    False)
                else:
                    assert False, "Should not be here !"

def create_ppm_file(image_size, pi_approx_s, image_count):
    """Create and return the PPM file whit its header.

    Return also the max color value to be used when
    drawing in the file.
    The file MUST be closed by the caller.
    """

    # Create the PPM file
    ppm_file = open(f"img{image_count}_{pi_approx_s.replace('.', '-')}.ppm",
                    "wb" if PPM_FILE_TYPE == PPM_BINARY_1 else "w")

    # Header
    max_color_val = PPM_HEADER_INFOS[PPM_FILE_TYPE].max_color_val
    magic_number = PPM_HEADER_INFOS[PPM_FILE_TYPE].magic_number
    if PPM_FILE_TYPE == PPM_BINARY_1:
        # Magic number
        ppm_file.write(f"{magic_number}\n".encode("ascii"))
        # Image's size
        ppm_file.write(f"{image_size} {image_size}\n".encode("ascii"))
        # Image's max color value
        ppm_file.write(f"{max_color_val}\n".encode("ascii"))
    else:
        # Magic number
        print(magic_number, file=ppm_file)
        # Image's width and height
        print(f"{image_size} {image_size}", file=ppm_file)
        # Image's max color value
        print(max_color_val, file=ppm_file)

    return ppm_file, max_color_val

def write_pixel(ppm_file,
                pixelc_red, pixelc_green, pixelc_blue):
    """Write the given pixel value in the PPM file."""
    if PPM_FILE_TYPE == PPM_BINARY_1:
        ppm_file.write(bytes((pixelc_red,
                              pixelc_green,
                              pixelc_blue)))
    elif PPM_FILE_TYPE == PPM_ASCII_255:
        ppm_file.write(f'{pixelc_red:3d} '
                       f'{pixelc_green:3d} '
                       f'{pixelc_blue:3d}\n')
    else:
        ppm_file.write(f'{pixelc_red} '
                       f'{pixelc_green} '
                       f'{pixelc_blue}\n')

def generate_ppm_file_algo_1(pixels_list,
                             image_size,
                             pi_approx_s,
                             image_count):
    """Generate the PPM image in the given file."""

    ppm_file, max_color_val = create_ppm_file(image_size, pi_approx_s, image_count)

    # Sort the list of pixels by line first and then by column.
    # This works because by default tuples are sorted field by
    # field. Try `(1, 2) > (42, 3)` in an interactive interpreter
    # to convince yourself.
    #
    # The worst case cost of this is O(nlogn) where n is
    # the length of the pixels_list, hence the number of
    # points in our case if all points maps to different
    # pixels of the image.
    pixels_list.sort()

    # Get the first pixel corresponding to a point
    pixels_it = iter(pixels_list)
    pixel = next(pixels_it, None)

    # Get the first pixel corresponding to the PI text
    pi_pixels_it = get_pi_pixels_it(pi_approx_s,
                                    image_size)
    pi_pixel = next(pi_pixels_it, None)

    # Draw pixels line by line
    for line in range(image_size):
        for col in range(image_size):

            # The current pixel correspond to a point that is in
            # the point list. Then, draw it with color depending
            # if it's in the unit circle or not
            if pixel and \
               pixel.line == line and \
               pixel.col == col:

                # Get the color of the pixel
                if pixel.in_circle:
                    pixelc_red = 0
                    pixelc_green = 0
                    pixelc_blue = max_color_val
                else:
                    pixelc_red = max_color_val
                    pixelc_green = 0
                    pixelc_blue = max_color_val

                # Move to the next different pixel corresponding to
                # a point in the list of pixels
                pixel = next(pixels_it, None)

            # The point is not in the point list
            # draw it white
            else:
                pixelc_red = max_color_val
                pixelc_green = max_color_val
                pixelc_blue = max_color_val

            # The current pixel is in the PI points,
            # override it with black.
            # This must be done IN ADDITION to the first test
            # because both pixel_point and pi_pixel must be
            # changed to next if they have the same value equal
            # to the current pixel.
            if pi_pixel and \
               pi_pixel.line == line and \
               pi_pixel.col == col:
                pixelc_red = 0
                pixelc_green = 0
                pixelc_blue = 0
                pi_pixel = next(pi_pixels_it, None)

            # write the pixel value in the PPM file
            write_pixel(ppm_file, pixelc_red, pixelc_green, pixelc_blue)

    # Don't forget to close the file
    ppm_file.close()

def generate_ppm_file_algo_2(pixels_in_circle_set,
                             pixels_not_in_circle_set,
                             image_size,
                             pi_approx_s,
                             image_count):
    """Generate the PPM image in the given file."""

    ppm_file, max_color_val = create_ppm_file(image_size, pi_approx_s, image_count)

    # Get the first pixel corresponding to the PI text
    pi_pixels_it = get_pi_pixels_it(pi_approx_s,
                                    image_size)
    pi_pixel = next(pi_pixels_it, None)

    # Draw pixels line by line
    for line in range(image_size):
        for col in range(image_size):

            # The current pixel correspond to a point that is in
            # the point list and in the unit circle
            pixel = (line, col)
            if pixel in pixels_in_circle_set:
                pixelc_red = 0
                pixelc_green = 0
                pixelc_blue = max_color_val

            # The current pixel correspond to a point that is in
            # the point list and not in the unit circle
            elif pixel in pixels_not_in_circle_set:
                pixelc_red = max_color_val
                pixelc_green = 0
                pixelc_blue = max_color_val

            # The point is not in the point list
            # draw it white
            else:
                pixelc_red = max_color_val
                pixelc_green = max_color_val
                pixelc_blue = max_color_val

            # The current pixel is in the PI points,
            # override it with black.
            if pi_pixel and \
                 pi_pixel.line == line and \
                 pi_pixel.col == col:
                pixelc_red = 0
                pixelc_green = 0
                pixelc_blue = 0
                pi_pixel = next(pi_pixels_it, None)

            # write the pixel value in the PPM file
            write_pixel(ppm_file, pixelc_red, pixelc_green, pixelc_blue)

    # Don't forget to close the file
    ppm_file.close()

def generate_ppm_files_algo_1(image_size, nb_points, pi_precision):
    """Algorithm that saves choosen pixels in a list."""

    # Where are we in the simulation ?
    ten_percent = nb_points // 10
    image_count = 0

    # Set containing all the pixels of the image that have been
    # randomly choosed by the simulator module up to now
    pixels_set = set()

    # List containing exactly the same pixels as the set above.
    # Used by the image drawing function to get pixels in drawing
    # order, that is by line first and then by column.
    pixels_list = []

    # Main simulation loop
    for i, simulator_state in enumerate(simulator.simulate_iterator(nb_points)):

        # Add the current point to the set and to the list of choosen
        # pixels if it is not already present.
        # The mapping of points to pixel is done here since
        # the simulator must not deal with any "drawing" stuff,
        # hence it does not know the image size.
        point, in_circle, nb_in_circle = simulator_state
        pixel_line = int(point.y * image_size // 2 + image_size // 2)
        pixel_col = int(point.x * image_size // 2 + image_size // 2)
        pixel_pos = (pixel_line, pixel_col)
        if not pixel_pos in pixels_set:
            pixels_set.add(pixel_pos)
            pixel = Pixel(pixel_pos[0],
                          pixel_pos[1],
                          in_circle)
            pixels_list.append(pixel)

        # Every 10 percents of the simulation
        # generate an image
        if (i + 1) % ten_percent == 0:

            # Approximate the value of PI from the points
            pi_approx = 4 * nb_in_circle / (i + 1)
            pi_approx_s = f"{pi_approx:.{pi_precision}f}"
            print(pi_approx_s)

            # Draw the image
            generate_ppm_file_algo_1(pixels_list,
                                     image_size,
                                     f"{pi_approx_s}",
                                     image_count)
            image_count += 1

def generate_ppm_files_algo_2(image_size, nb_points, pi_precision):
    """Algorithm that saves choosen pixels in sets."""

    # Where are we in the simulation ?
    ten_percent = nb_points // 10
    image_count = 0

    # Set containing all the pixels of the image that have been
    # randomly choosed by the simulator module up to now and
    # that are in the circle
    pixels_in_circle_set = set()

    # Set containing all the pixels of the image that have been
    # randomly choosed by the simulator module up to now and
    # that are not in the circle
    pixels_not_in_circle_set = set()

    # Main simulation loop
    for i, simulator_state in enumerate(simulator.simulate_iterator(nb_points)):

        # Add the current point to the set and to the list of choosen
        # pixels if it is not already present.
        # The mapping of points to pixel is done here since
        # the simulator must not deal with any "drawing" stuff,
        # hence it does not know the image size.
        point, in_circle, nb_in_circle = simulator_state
        pixel_line = int(point.y * image_size // 2 + image_size // 2)
        pixel_col = int(point.x * image_size // 2 + image_size // 2)
        pixel_pos = (pixel_line, pixel_col)
        if in_circle and not pixel_pos in pixels_in_circle_set:
            pixels_in_circle_set.add(pixel_pos)
        elif not in_circle and not pixel_pos in pixels_not_in_circle_set:
            pixels_not_in_circle_set.add(pixel_pos)

        # Every 10 percents of the simulation
        # generate an image
        if (i + 1) % ten_percent == 0:

            # Approximate the value of PI from the points
            pi_approx = 4 * nb_in_circle / (i + 1)
            pi_approx_s = f"{pi_approx:.{pi_precision}f}"
            print(pi_approx_s)

            # Draw the image
            generate_ppm_file_algo_2(pixels_in_circle_set,
                                     pixels_not_in_circle_set,
                                     image_size,
                                     f"{pi_approx_s}",
                                     image_count)
            image_count += 1

def main():
    """Program's entry point"""

    # Program's inputs are given on the command line
    # and we must have 3 arguments
    if len(sys.argv) < 4:
        print("utilisation ./approximate_pi.py "
              "image_size nb_points pi_precision")
        return

    # Convert the 3 arguments to integers.
    # If any of the 3 conversion fails because
    # argument is not a valid integer, the `int`
    # function will throw a ValueError for us.
    # We don't catch it, so that it flows up to
    # the top of the execution stack as specified
    # in the project's requirements.
    image_size = int(sys.argv[1])
    nb_points = int(sys.argv[2])
    pi_precision = int(sys.argv[3])

    # We must also raise an exception if any of
    # the 3 argument is not stricly positive.
    if not all(param > 0 for param in (image_size,
                                       nb_points,
                                       pi_precision)):
        raise ValueError("all parameters must be "
                         "integers strictly greater than 0")

    # Fix random in the simulator
    # Uncomment the following line for debug.
    simulator.fix_random_from(42)

    # Generate the PPMs
    algos = [None,
             generate_ppm_files_algo_1,
             generate_ppm_files_algo_2]
    if len(sys.argv) >= 5:
        algo = int(sys.argv[4])
    else:
        algo = 1
    print(f"Utilisation de l'algorithme {algo}")
    algos[algo](image_size, nb_points, pi_precision)

    # # Generate the GIF
    # cmd = ["convert", "-delay", "100",
    #        "-loop", "0", "img*.ppm", "pi.gif"]
    # process = subprocess.Popen(cmd)
    # process.wait()

if __name__ == "__main__":
    main()