Dixième exercice en Python, JavaScript et APL

Publié le par

Résumé en français : On vous donne une liste contenant des couleurs de moufles (donc pas de main gauche ou droite à distinguer). On vous demande le nombre de paires que vous pouvez constituer, c’est-à-dire avoir 2 moufles de la même couleur.

Avec le premier exemple donné, on peut constituer une paire de moufles rouge (red) et une paire bleue (blue) soit 2 paires.

Version classique

Relisez l’exercice 6 que j’ai proposé, vous devriez constater de nombreuses ressemblances.

Une première idée est de commencer par récupérer les différentes couleurs puis, pour chacune d’elle, de compter combien de fois cette couleur apparait. Il suffira de diviser par 2 ce nombre (sans tenir compte des virgules) pour savoir combien de paires on peut constituer avec cette couleur. Finalement, on fera la somme du nombre de paires trouvées.

python

Je reprends la structure classique vue dans l’exercice 6 :

def nb_paires(gants):
 couleurs = [ ]                   # couleurs distinctes
 for g in gants:                  # on parcourt les gants
  if g not in couleurs:           # nouvelle couleur ?
   couleurs.append(g)             # on l'ajoute à la liste
 paires = 0                       # nombre de paires possibles
 for c in couleurs:               # on parcourt à nouveau les gants
  paires += gants.count(c) // 2   # on compte puis ÷ entière par 2 
 return paires                    # on renvoie le nombre de paires

>> nb_paires(["gray","black","purple","purple","gray","black"])
3
>> nb_paires(["red","green","blue"])
0

javascript

A nouveau je reprends la structure de l’exercice 6 :

const nb_paires = gants => 
{
  couleurs = gants.reduce((a, g) => 
                   a.includes(g) ? a : a.concat(g), []);
  paires = 0;
  for (c of couleurs) 
  {
      paires += Math.floor(gants.filter(g => g == c).length / 2)
  }
    return paires
}

>> nb_paires(["gray","black","purple","purple","gray","black"])
3
>> nb_paires(["red","green","blue"])
0

Remarque : La division entière par 2 ou des puissances de 2 (c’est-à-dire 4, 8, 16, 32…) peut se faire autrement. En effet, si un nombre est écrit en binaire, diviser par 2 revient à supprimer l’unité (bit le plus à droite) :

>> (13).toString(2)      // 13 en binaire. Python : bin(13) → '0b1101'
'1101'
>> (6).toString(2)       // Diviser par 2 = supprimer l'unité 
'110'

La raison est que 13 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 = 11012. En divisant par 2, toutes les puissances vont diminuer de 1 : 6 = 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 1102

On utilise >> pour décaler un bit vers la droite en Python et JavaScript :

13 >> 1
6

De la même façon, on peut diviser par 4, multiplier par 8 etc :

13 >> 2        // Diviser par 4 (c'est-à-dire ÷ 2 fois par 2)
3
13 << 3        // Multiplier par 8 (c'est-à-dire × 3 fois par 2)
104

Version ensembliste

Comme nous l’avons également vu dans l’exercice 6, nous pouvons utiliser des ensembles (set) pour récupérer les éléments uniques. Les versions sont alors nettement plus courtes :

Python

def nb_paires(gants):
    return sum(gants.count(v) // 2 for v in set(gants))

JavaScript

const nb_paires = gants => [...new Set(gants)]
    .reduce((a,v) => a + (gants.filter(c => c == v).length >> 1), 0)

apl

Toujours dans l’exercice 6, nous avons vu l’utilisation de ⌸ (key), qui permet de synthétiser des informations. Ici, nous voulons pour chaque couleur distincte, compter combien de fois elle apparait dans la liste et diviser cette valeur par 2 (sans virgule). Ecrivons cela étape par étape :

      gants ← 'gray' 'red' 'purple' 'purple' 'gray' 'black'

      {⍺, ⍵}⌸ gants        ⍝ Positions des couleurs dans le vecteur
┌──────┬─┬─────┐
│gray  │1│5    │
├──────┼─┼─────┤
│red   │2│     │
├──────┼─┼─────┤
│purple│3│4    │
├──────┼─┼─────┤
│black │6│     │
└──────┴─┴─────┘
      {⍺, ⍴⍵}⌸ gants       ⍝ Nombre d'apparitions de chaque couleur
┌──────┬─┐
│gray  │2│
├──────┼─┤
│red   │1│
├──────┼─┤
│purple│2│
├──────┼─┤
│black │1│
└──────┴─┘
      {⍴⍵}⌸ gants            ⍝ Uniquement le nombre d'apparitions
2
1
2
1

      {.5 × ⍴⍵}⌸ gants       ⍝ Division par 2
1  
0.5
1  
0.5
      {⌊ .5 × ⍴⍵}⌸ gants     ⍝ avec partie entière
1
0
1
0
      +⌿ {⌊ .5 × ⍴⍵}⌸ gants   ⍝ Somme de la colonne
2

Le programme final APL à tester ici :

      nb_paires ← +⌿ {⌊ .5 × ⍴⍵}⌸

      nb_paires 'red' 'green' 'red' 'blue' 'blue'
2
      nb_paires 'red' 'green' 'blue'
0

Python et JavaScript : Version utilisant une seule boucle et une pile

Est-il vraiment nécessaire de récupérer les couleurs uniques ? Imaginons la situation dans la vie réelle avec ‘red’ ‘green’ ‘red’ ‘blue’ ‘blue’ :

  • Dans ma tête je pense à 0, c’est le nombre de paires que j’ai réussi à faire
  • Je prends le premier gant, il est ‘red’, je n’ai pas cette couleur donc je la garde
  • Je prends le deuxième, il est ‘green’, je n’ai pas cette couleur donc je la garde
  • Je prends le troisième, il est ‘red’. J’ai déjà cette couleur, je peux donc faire une paire. J’enlève les 2 moufles ‘red’ et j’ajoute 1 au nombre de paires
  • Je prends le quatrième, il est ‘blue’, je n’ai pas cette couleur donc je la garde
  • Je prends le cinquième, il est ‘blue’. J’ai déjà cette couleur, je peux donc faire une paire. J’enlève les 2 moufles ‘blue’ et j’ajoute 1 au nombre de paires
  • J’ai finalement réussi à constituer 2 paires.

🤖 Refaites de tête le processus avec les gants ‘red’ ‘red’ ‘red’ ‘red’ ‘red’

Prendre un gant revient à ajouter un élément dans une liste, inversement créer une paire à éliminer cette couleur de la liste. Voyons comment ajouter, enlever ou tester si un élément est dans un ensemble en utilisant les méthodes add, remove, delete :

python

>> paires = set()           # Ensemble vide
>> paires.add('red')        # on ajoute 'red' à l'ensemble
>> paires
{'red'}
>> paires.add('blue')
>> paires
{'red', 'blue'}
>> paires.remove('red')     # on enlève 'red'
>> paires
{'blue'}
>> 'red' in paires          # on teste si 'red' est dans l'ensemble
False

javascript

>> paires = new Set()       // Ensemble vide
>> paires.add('red')        // on ajoute 'red' à l'ensemble
Set(1) {'red'}
>> paires.add('blue')
Set(2) {'red', 'blue'}
>> paires.delete('red')     // on enlève 'red'
>> paires
Set(1) {'blue'}
>> paires.has('red')        // on teste si 'red' est dans l'ensemble
false

Versions finales basées sur cette idée :

Python

def nb_paires(gants):
  couleurs = set()          # les couleurs trouvées
  paires = 0                # nb de paires réalisées
  for c in gants:           # on parcourt les gants
    if c in couleurs:       # couleur déjà vue ?
      couleurs.remove(c)    # on la retire des couleurs trouvées
      paires += 1           # le nombre de paires augmente de 1
    else:                   # sinon
      couleurs.add(c)       # ajouter cette nouvelle couleur
  return paires             # nombre de paires trouvées

JavaScript

const nb_paires = gants => {
  couleurs = new Set();
  paires = 0;
  for (c of gants)
  {
    if (couleurs.has(c)) 
    {   
      couleurs.delete(c);
      paires ++
    }
    else
      couleurs.add(c)
  }
  return paires
}

🤯 Pour terminer, voici une version (difficile à lire) avec reduce du programme JavaScript précédent :

const nb_paires = gants => 
     gants.reduce((a, c) =>   // On parcourt les couleurs
       a[1].has(c) ?          // Couleur déjà vue ?
       [a[0] + a[1].delete(c), a[1]] : // +1 paire et suppr couleur
       [a[0], a[1].add(c)]   // sinon on ajoute couleur
      ,[0, new Set()])       // Initialisation paires = 0 et couleurs
     [0]                     // On récupère le nombre de paires

On utilise le fait que true + nombre donne le même résultat que 1 + nombre :

>> a = new Set()         // Ensemble vide
>> a.add('red')          // on ajoute 'red'
Set(1) {'red'}
>> 3 + a.delete('red')   // a.delete renvoie true qui correspond à 1
4                        // Cela donne bien 3 + 1 = 4

Autre version en APL

Nous avons vu le produit interne à plusieurs reprises dans les exercices. Il existe également un produit externe (noté ∘), l’exemple classique étant la table de multiplication :


      (⍳5) ∘.× ⍳3       ⍝ Multiplier chaque élément de 1 2 3 4 5
1  2  3                 ⍝ par chaque élément de 1 2 3
2  4  6
3  6  9                 ⍝ d'où une matrice 5 x 3
4  8 12
5 10 15

Voici un autre exemple :

      gants ← 'red' 'green' 'red' 'blue' 'blue'

      ∪ gants               ⍝ Eléments uniques dans le vecteur
┌───┬─────┬────┐
│red│green│blue│
└───┴─────┴────┘
      gants ∘.≡ ∪ gants     ⍝ On teste toutes les égalités
1 0 0                       ⍝ 'red' est égal au 1er élément de ∪ gants
0 1 0                       ⍝ 'vert' égal au 2e élément de ∪ gants
1 0 0                       ⍝ 'red' est égal au 1er élément de ∪ gants
0 0 1                       ⍝ 'blue' est égal au 32 élément de ∪ gants
0 0 1                       ⍝ 'blue' est égal au 32 élément de ∪ gants

On peut alors faire la somme des colonnes, diviser les totaux par 2 et prendre la partie entière :

      ⌊ .5 × +⌿ gants ∘.≡ ∪ gants
1 0 1

Et finalement réduire par la somme :

      +/ ⌊ .5 × +⌿ gants ∘.≡ ∪ gants
2

⍝ En faisant les produits puis la somme (produit interne +.×)

      +/ ⌊ .5 +.× gants ∘.≡ ∪ gants
2

Ce qui donne cette autre version finale en APL à tester ici :

      nb_paires ← {+/ ⌊ .5 +.× ⍵ ∘.≡ ∪⍵}

      nb_paires gants
2

🧐 Les plus attentifs d’entre vous auront remarqué que ⍵ ∘.≡ ∪⍵ peut s’écrire ⊢∘.≡∪ (fork). En effet, on applique l’union à ⍵, l’identité à ⍵ puis le test d’égalité aux 2 résultats. Or (f⍵)g(h⍵) peut s’écrire sous la forme (fgh)⍵ :

      (⊢∘.≡∪) 'red' 'green' 'red' 'blue' 'blue'
1 0 0
0 1 0
1 0 0
0 0 1
0 0 1

🥵 Ce qui nous amène à cette troisième version à tester ici :

      nb_paires ← +/∘⌊ .5 +.× ⊢∘.≡∪

      nb_paires 'red' 'green' 'red' 'blue' 'blue'
2
      nb_paires 'red' 'green' 'blue'
0