Dictionnaires - Exercices

1 Exercice 1

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(stock):
  return stock.get("quantity") * stock.get("price")
# default_end
# test_start
print(mystere(Dict({"ref": 0, "name": "Boulon", "quantity": 10, "price": 1.99})))
print("C683AKRMaR")
print(mystere(Dict({"ref": 1, "name": "Ecrou", "quantity": 5, "price": 0.99})))
print("C683AKRMaR")
print(mystere(Dict({"ref": 2, "name": "Vis", "quantity": 20, "price": 0.10})))
# test_end

# exercice: show
# default_start
def mystere(stock):                                  # stock = Dict({"ref": 0, "name": "Boulon", "quantity": 10, "price": 1.99})
  return stock.get("quantity") * stock.get("price")  # 10 * 1.99 = 19.9

print(mystere(Dict({"ref": 0, "name": "Boulon", "quantity": 10, "price": 1.99})))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# exercice: show 
# default_start
def mystere(stock):
  return stock.get("quantity") * stock.get("price")  # 1 retour + 1 multiplication
# T(n) = 2
#      => O(1)
# default_end

Concevoir

Écrire une fonction \(computeDistance(pointA, pointB)\) qui prend en paramètres deux points \(pointA\) et \(pointB\) sous forme de dictionnaires avec les clés “x” et “y”, et qui retourne la distance euclidienne entre ces deux points.

Exemple d’utilisation :

• \(computeDistance(Dict(\{\q{x}: 7, \q{y}: 2\}), Dict(\{\q{x}: -5, \q{y}: 9\}))\) retourne \(13.89\)
• \(computeDistance(Dict(\{\q{x}: -14, \q{y}: 15\}), Dict(\{\q{x}: 4,\q{y}: 0\}))\) retourne \(23.43\)

Note

La distance euclidienne \(d\) entre deux points \(a\) et \(b\) dans un espace à deux dimensions (2D) est définie par la formule suivante: \[d(a, b) = \sqrt{{(x_a - x_b)}^2 + {(y_a - y_b)}^2}\] où \(x_a\) et \(y_a\) sont les coordonnées du point \(a\), et \(x_b\) et \(y_b\) sont les coordonnées du point \(b\).

Votre réponse

# exercice: design
# default_start
def computeDistance(pointA,  pointB):
    return None
# default_end
# test_start
print(computeDistance(Dict({"x": 7, "y": 2}), Dict({"x": -5, "y": 9})))
print("C683AKRMaR")
print(computeDistance(Dict({"x": -14, "y": 15}), Dict({"x": 4, "y": 0})))
print("C683AKRMaR")
print(computeDistance(Dict({"x": 3, "y": -7}), Dict({"x": -8, "y": 4})))
# test_end
# solution_start
def computeDistance(pointA,  pointB):
    x_diff = pointA.get("x") - pointB.get("x")
    y_diff = pointA.get("y") - pointB.get("y")
    return (x_diff * x_diff + y_diff * y_diff) ** 0.5
# T(n) = 7
#      => O(1)
# solution_end

2 Exercice 2

Difficulté :

Comprendre

# exercice: guess
# default_start
def mystere(arr):
    result = 0
    i = 0
    while i < arr.size():
      if arr[i].get("birthyear") < 1960:
        result = result + 1
      i = i + 1
    return result
# default_end
# test_start
print(mystere(Array([
  Dict({"firstname": "Nicolas", "lastname": "Sarkozy", "birthyear": 1955}), 
  Dict({"firstname": "Francois", "lastname": "Hollande", "birthyear": 1954}),
  Dict({"firstname": "Emmanuel", "lastname": "Macron", "birthyear": 1977})
])))
print("C683AKRMaR")
print(mystere(Array([
  Dict({"firstname": "Jacques", "lastname": "Chirac", "birthyear": 1932}), 
  Dict({"firstname": "Georges", "lastname": "Pompidou", "birthyear": 1911}),
  Dict({"firstname": "Valery", "lastname": "Giscard", "birthyear": 1926}),
  Dict({"firstname": "Emmanuel", "lastname": "Macron", "birthyear": 1977})
])))
print("C683AKRMaR")
print(mystere(Array([
  Dict({"firstname": "Charles", "lastname": "De Gaulle", "birthyear": 1890}), 
  Dict({"firstname": "Albert", "lastname": "Lebrun", "birthyear": 1871}),
  Dict({"firstname": "Paul", "lastname": "Dupont", "birthyear": 1960}),
  Dict({"firstname": "Emmanuel", "lastname": "Macron", "birthyear": 1977})
])))
# test_end

# exercice: show
# default_start
def mystere(arr): 
# arr=Array([
#  Dict({"firstname": "Nicolas", "lastname": "Sarkozy", "birthyear": 1955}), 
#  Dict({"firstname": "Francois", "lastname": "Hollande", "birthyear": 1954}),
#  Dict({"firstname": "Emmanuel", "lastname": "Macron", "birthyear": 1977})
# ])
    result = 0                            # result = 0
    i = 0                                 # i = 0
    while i < arr.size():                 # 0 < 3                     1 < 3                     2 < 3                     3 < 3
      if arr[i].get("birthyear") < 1960:  # arr[0].birthyear < 1960   arr[1].birthyear < 1960   arr[2].birthyear < 1960   
                                          # 1955 < 1960               1954 < 1960               1977 < 1960     
        result = result + 1               # result = 1                result = 2    
      i = i + 1                           # i = 1                     i = 2                     i = 3
    return result                         #                                                                               2

print(mystere(Array([
  Dict({"firstname": "Nicolas", "lastname": "Sarkozy", "birthyear": 1955}), 
  Dict({"firstname": "Francois", "lastname": "Hollande", "birthyear": 1954}),
  Dict({"firstname": "Emmanuel", "lastname": "Macron", "birthyear": 1977})
])))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# exercice: show
# default_start
def mystere(arr):                    
    result = 0                      # 1 affectation
    i = 0                           # 1 affectation
    # Boucle:
    #   de i=0 jusqu'à i>=arr.size() par pas de 1 
    #   => (arr.size() - 0)/ 1 
    #   => arr.size() iterations 
    while i < arr.size():                 # 1 comparaison
      if arr[i].get("birthyear") < 1960:  # 1 comparaison
        result = result + 1               # 1 affectation + 1 addition
      i = i + 1                           # 1 affectation + 1 addition
    return result                   # 1 retour
# n = arr.size()
# T(n) = 1 + 1 + n * (1 + 1 + 2 + 2) + 1 
#      = 6n + 3 
#      => O(n)
# default_end

Concevoir

Écrire une fonction \(computeDistancePath(points)\) qui prend en paramètre un tableau de points \(points\) sous forme de dictionnaires avec les clés “x” et “y”, et qui retourne la distance totale de la suite de points.

Exemple d’utilisation :

• \(computeDistancePath(Array([Dict(\{\q{x}: 8, \q{y}: 2\}), Dict(\{\q{x}: -8, \q{y}: 14\}), Dict(\{\q{x}: 32, \q{y}: -1\})]))\) retourne \(62.72\)
• \(computeDistancePath(Array([Dict(\{\q{x}: 7, \q{y}: 2\}), Dict(\{\q{x}: -5, \q{y}: 9\}), Dict(\{\q{x}: -14, \q{y}: 15\}), Dict(\{\q{x}: -10, \q{y}: 5\})]))\) retourne \(35.47\)
• \(computeDistancePath(Array([Dict(\{\q{x}: -17, \q{y}: -25\}), Dict(\{\q{x}: -45, \q{y}: 90\}), Dict(\{\q{x}: 14, \q{y}: -15\}), Dict(\{\q{x}: 10, \q{y}: 50\}), Dict(\{\q{x}: -100, \q{y}: -50\})]))\) retourne \(452.58\)

Votre réponse

# exercice: design
# default_start
def computeDistancePath(points):
    return None
# default_end
# test_start
print(computeDistancePath(Array([
  Dict({"x": 8, "y": 2}), 
  Dict({"x": -8, "y": 14}), 
  Dict({"x": 32, "y": -1})
])))
print("C683AKRMaR")
print(computeDistancePath(Array([
  Dict({"x": 7, "y": 2}),
  Dict({"x": -5, "y": 9}),
  Dict({"x": -14, "y": 15}),
  Dict({"x": -10, "y": 5})
])))
print("C683AKRMaR")
print(computeDistancePath(Array([
  Dict({"x": -17, "y": -25}),
  Dict({"x": -45, "y": 90}),
  Dict({"x": 14, "y": -15}),
  Dict({"x": 10, "y": 50}),
  Dict({"x": -100, "y": -50})
])))
# test_end
# solution_start
# OPTION 1
def computeDistancePath(points): # O(n)
    distance_totale = 0
    i = 0
    while i < points.size() - 1:
        pointA = points[i]
        pointB = points[i+1]
        x_diff = pointA.get("x") - pointB.get("x")
        y_diff = pointA.get("y") - pointB.get("y")
        distance = (x_diff * x_diff + y_diff * y_diff) ** 0.5
        distance_totale = distance_totale + distance
        i = i + 1
    return distance_totale

# OPTION 2 (avec la fonction computeDistance)
def computeDistance(pointA,  pointB): # O(1)
    x_diff = pointA.get("x") - pointB.get("x")
    y_diff = pointA.get("y") - pointB.get("y")
    return (x_diff * x_diff + y_diff * y_diff) ** 0.5

def computeDistancePath(points): # O(n)
    distance_totale = 0
    i = 0
    while i < points.size() - 1:
        distance = computeDistance(points[i], points[i+1])
        distance_totale = distance_totale + distance
        i = i + 1
    return distance_totale
# solution_end

3 Exercice 3

Difficulté :

Comprendre

# exercice: guess
# default_start
def mystere(arr):
    i = 0
    total = 0
    res = Dict({"total_cost": 0, "average_cost": 0.0})
    while i < arr.size():
        quantity = arr[i].get("quantity")
        price = arr[i].get("price")
        cost = quantity * price
        total = total + cost
        i = i + 1
    res.set("total_cost", total)
    avg = total / arr.size()
    res.set("average_cost", avg)
    return res
# default_end
# test_start
print(mystere(Array([
  Dict({"item": "book", "price": 3, "quantity": 2}),
  Dict({"item": "pen", "price": 1, "quantity": 5})
])))                                                    
print("C683AKRMaR")
print(mystere(Array([
  Dict({"item": "apple", "price": 1, "quantity": 3}),
  Dict({"item": "banana", "price": 1, "quantity": 1}),
  Dict({"item": "pear", "price": 1, "quantity": 2}),
  Dict({"item": "orange", "price": 2, "quantity": 1})
])))
# test_end

# exercice: show
# default_start
def mystere(arr):
    # arr = Array([
    #  Dict({"item": "book", "price": 3, "quantity": 2}),
    #  Dict({"item": "pen", "price": 1, "quantity": 5})
    # ])
    i = 0                                             # i = 0
    total = 0                                         # total = 0
    res = Dict({"total_cost": 0, "average_cost": 0.0})# res = Dict({"total_cost": 0, "average_cost": 0})
    while i < arr.size():                             # 0 < 2                     1 < 2               2 < 2
        quantity = arr[i].get("quantity")             # quantity = 2             quantity = 5         
        price = arr[i].get("price")                   # price = 3                price = 1            
        cost = quantity * price                       # cost = 2 * 3 = 6         cost = 5 * 1 = 5
        total = total + cost                          # total = 0 + 6 = 6        total = 6 + 5 = 11
        i = i + 1                                     # i = 1                 i = 2    
    res.set("total_cost", total)                      # res = Dict({"total_cost": 11, "average_cost": 0})   
    avg = total / arr.size()                          # avg = 11 / 2 = 5.5
    res.set("average_cost", avg)                      # res = Dict({"total_cost": 11, "average_cost": 5.5})
    return res                                        # Dict({"total_cost": 11, "average_cost": 5.5})
# default_end
# test_start
print(mystere(Array([
  Dict({"item": "book", "price": 3, "quantity": 2}),
  Dict({"item": "pen", "price": 1, "quantity": 5})
])))                                                    
print("C683AKRMaR")
print(mystere(Array([
  Dict({"item": "apple", "price": 1, "quantity": 3}),
  Dict({"item": "banana", "price": 1, "quantity": 1}),
  Dict({"item": "pear", "price": 1, "quantity": 2}),
  Dict({"item": "orange", "price": 2, "quantity": 1})
])))
# test_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# exercice: show
# default_start
def mystere(arr):
    i = 0                                              # 1 affectation
    total = 0                                          # 1 affectation
    res = Dict({"total_cost": 0, "average_cost": 0.0}) # O(n) création d'un dictionnaire => 2 clés-valeurs (n=2) => O(1)
    # Boucle:
    #   de i=0 jusqu'à i>=arr.size() par pas de 1
    #   => (arr.size() - 0)/ 1
    #  => arr.size() iterations
    while i < arr.size():                               # 1 comparaison
        quantity = arr[i].get("quantity")               # 1 affectation
        price = arr[i].get("price")                     # 1 affectation
        cost = quantity * price                         # 1 affectation + 1 multiplication
        total = total + cost                            # 1 affectation + 1 addition
        i = i + 1                                       # 1 affectation + 1 addition
    res.set("total_cost", total)                      # 1 affectation
    avg = total / arr.size()                          # 1 division
    res.set("average_cost", avg)                      # 1 affectation
    return res                                        # 1 retour
# n = arr.size()
# T(n) = 1 + 1 + 1 + n * (1 + 1 + 1 + 2 + 2) + 1 + 1 + 1 + 1
#      = 8n + 5
#      => O(n)
# default_end

Concevoir

Écrire une fonction \(computeMinimumDistance(points)\) qui prend en paramètre un tableau de points \(points\) sous forme de dictionnaires avec les clés “x” et “y”, et qui retourne la plus petite distance entre n’importe quel couple de points du tableau.

Exemple d’utilisation :

• \(computeMinimumDistance(Array([Dict(\{\q{x}: 8, \q{y}: 2\}), Dict(\{\q{x}: -8, \q{y}: 14\}), Dict(\{\q{x}: 32, \q{y}: -1\})]))\) retourne \(20.00\)
• \(computeMinimumDistance(Array([Dict(\{\q{x}: 7, \q{y}: 2\}), Dict(\{\q{x}: -5, \q{y}: 9\}), Dict(\{\q{x}: -14, \q{y}: 15\}), Dict(\{\q{x}: -10, \q{y}: 5\})]))\) retourne \(6.40\)
• \(computeMinimumDistance(Array([Dict(\{\q{x}: -17, \q{y}: -25\}), Dict(\{\q{x}: -45, \q{y}: 90\}), Dict(\{\q{x}: 14, \q{y}: -15\}), Dict(\{\q{x}: 10, \q{y}: 50\}), Dict(\{\q{x}: -100, \q{y}: -50\})]))\) retourne \(35.57\)

Votre réponse

# exercice: design
# default_start
def computeMinimumDistance(points):
    return None
# default_end
# test_start
print(computeMinimumDistance(Array([
  Dict({"x": 8, "y": 2}), 
  Dict({"x": -8, "y": 14}), 
  Dict({"x": 32, "y": -1})
])))
print("C683AKRMaR")
print(computeMinimumDistance(Array([
  Dict({"x": 7, "y": 2}),
  Dict({"x": -5, "y": 9}),
  Dict({"x": -14, "y": 15}),
  Dict({"x": -10, "y": 5})
])))
print("C683AKRMaR")
print(computeMinimumDistance(Array([
  Dict({"x": -17, "y": -25}),
  Dict({"x": -45, "y": 90}),
  Dict({"x": 14, "y": -15}),
  Dict({"x": 10, "y": 50}),
  Dict({"x": -100, "y": -50})
])))
# test_end
# solution_start
# SOLUTION 1 => O(n²)
def computeMinimumDistance(points):
    i = 0
    distance_minimale = None
    while i < points.size():
        pointA = points[i]
        j = i + 1
        while j < points.size():
            pointB = points[j]
            x_diff = pointA.get("x") - pointB.get("x")
            y_diff = pointA.get("y") - pointB.get("y")
            distance = (x_diff * x_diff + y_diff * y_diff) ** 0.5
            if distance_minimale == None or distance < distance_minimale:
                distance_minimale = distance
            j = j + 1
        i = i + 1
    return distance_minimale
# solution_end

4 Exercice 4

Écrire une fonction \(generateSquareAsArrayOfPoints(side)\) qui prend en paramètres un entier positif \(side\) et retourne un tableau contenant des dictionnaires représentant des points avec les clés “x” et “y”. Le premier point dans le tableau correspond au sommet en bas à gauche du carré, suivi des autres points dans le sens horaire.

Exemple d’utilisation :

• \(generateSquareAsArrayOfPoints(2)\) retourne \(Array([Dict(\{\q{x}: 0, \q{y}: 0\}), Dict(\{\q{x}: 0, \q{y}: 2\}), Dict(\{\q{x}: 2, \q{y}: 2\}), Dict(\{\q{x}: 2, \q{y}: 0\})])\)
• \(generateSquareAsArrayOfPoints(4)\) retourne \(Array([Dict(\{\q{x}: 0, \q{y}: 0\}), Dict(\{\q{x}: 0, \q{y}: 4\}), Dict(\{\q{x}: 4, \q{y}: 4\}), Dict(\{\q{x}: 4, \q{y}: 0\})])\)
• \(generateSquareAsArrayOfPoints(7)\) retourne \(Array([Dict(\{\q{x}: 0, \q{y}: 0\}), Dict(\{\q{x}: 0, \q{y}: 7\}), Dict(\{\q{x}: 7, \q{y}: 7\}), Dict(\{\q{x}: 7, \q{y}: 0\})])\)

# exercice: design
# default_start
def generateSquareAsArrayOfPoints(side):
    return None
# default_end
# test_start
print(generateSquareAsArrayOfPoints(4))
print("C683AKRMaR")
print(generateSquareAsArrayOfPoints(7))
print("C683AKRMaR")
print(generateSquareAsArrayOfPoints(15))
print("C683AKRMaR")
print(generateSquareAsArrayOfPoints(37))
# test_end
# solution_start
def generateSquareAsArrayOfPoints(side):
    res = Array([Dict({"x": 0, "y": 0})] * 4)
    res[1].set("y", side)
    res[2].set("x", side)
    res[2].set("y", side)
    res[3].set("x", side)
    return res
# solution_end

5 Bonus

Écrire une fonction \(generatePointsFromArrays(xValues, yValues)\) qui prend en paramètres deux tableaux d’entiers \(xValues\) et \(yValues\) de même taille. La fonction retourne un tableau contenant des dictionnaires représentant des points avec les clés “x” et “y” correspondant à chaque couple de valeurs \((xValues_i,\; yValues_i)\).

Exemple d’utilisation :

• \(generatePointsFromArrays(Array([1, 2]), Array([3, 4]))\) retourne \(Array([Dict(\{\q{x}: 1, \q{y}: 3\}), Dict(\{\q{x}: 2, \q{y}: 4\})])\)
• \(generatePointsFromArrays(Array([-15, 35, -14]), Array([14, -34, 15]))\) retourne \(Array([Dict(\{\q{x}: -15, \q{y}: 14\}), Dict(\{\q{x}: 35, \q{y}: -34\}), Dict(\{\q{x}: -14, \q{y}: 15\})])\)
• \(generatePointsFromArrays(Array([13, 24, 35, 46]), Array([-14, -25, -36, -47]))\) retourne \(Array([Dict(\{\q{x}: 13, \q{y}: -14\}), Dict(\{\q{x}: 24, \q{y}: -25\}), Dict(\{\q{x}: 35, \q{y}: -36\}), Dict(\{\q{x}: 46, \q{y}: -47\})])\)

# exercice: design
# default_start
def generatePointsFromArrays(xValues, yValues):
    return None
# default_end
# test_start
print(generatePointsFromArrays(
  Array([1, 2]), 
  Array([3, 4]
)))
print("C683AKRMaR")
print(generatePointsFromArrays(
  Array([-15, 35, -14]),
  Array([14, -34, 15])
))
print("C683AKRMaR")
print(generatePointsFromArrays(
  Array([13, 24, 35, 46]), 
  Array([-14, -25, -36, -47])
))
# test_end
# solution_start
def generatePointsFromArrays(xValues, yValues):
    res = Array([Dict({"x":0, "y":0})] * xValues.size())
    i = 0
    while i < res.size():
        res[i].set("x", xValues[i])
        res[i].set("y", yValues[i])
        i = i + 1
    return res 
# solution_end

# default_start
print("Hello World!")

# default_end