Horloges mathématiques

J’ai eu l’occasion de faire plusieurs vidéos de montres originales sur ma chaine Youtube, en particulier :

Aujourd’hui nous allons nous inspirer des horloges ALBERT qui ne vous donnent l’heure qu’après avoir effectué un calcul arithmétique (additions, soustractions, multiplications ou divisions suivant le niveau choisi)

Je vous propose différentes versions web inspirées par cette idée. Une fois les fichiers récupérés, vous n’aurez besoin d’aucune connexion Internet et vous pourrez mettre les fichiers sur une tablette ou un ordinateur portable.

Installation et modifications

Par défaut les horloges s’actualisent toutes les 60 secondes. Pour modifier cet intervalle, ouvrez le fichier .html avec le bloc-note puis rechercher la ligne contenant 60000 (60 millisecondes). Remplacez cette valeur par exemple par 20000 (pour 20 secondes) et enregistrez.

Concernant les tablettes, mettre le 2 fichiers (.html et .ttf) sur votre tablette (via Bluetooth, par mail ou autre), par exemple dans le dossier download ou documents. Pour ouvrir le fichier .html avec un navigateur installé sur votre tablette (Chrome ou FireFox ou Brave), lancez le navigateur puis tapez l’adresse (avec 3 « / ») :

file:///storage/emulated/0/download/horloge.html

ou

file:///storage/emulated/0/documents/horloge.html

Si les fichiers sont sur une carte SD, l’adresse sera du type :

file:///sdcard/download/horloge.html

Une fois que vous avez réussi, mettre la page en Favori. Si vous n’y arrivez pas, vous pouvez toujours utiliser les liens démo ci-dessous, mais il vous faudra alors une connexion Internet.

Additions et soustractions

Téléchargez | Voir la démo en ligne

-21+18+18=15 et -8+10+4=6, il est 15 h 06 min

Pour créer la formule des heures, l’idée a été de choisir au hasard 2 nombres entre -24 et 24 (par exemple -21 et +18), de les additionner (-3) et de regarder si la différence entre l’heure actuelle (par exemple 15h) et cette somme est ou non entre -24 et 24. Ici 15 – (-3) = 18 convient. D’où la formule -21+18+18. Sinon, on tire à nouveau 2 entiers et on recommence, les ordinateurs étant rapides, on ne se rend pas compte s’il y a eu besoin de 1 ou 1000 essais !

Addition et multiplication

Téléchargez | Voir la démo en ligne

7 × 9 – 45 = 18 et 3 + 7 × 5 = 38, il est 18 h 38 min

Les 2 nombres à multiplier sont choisis entre 2 et 9, l’un des 2 pouvant être négatif. Le troisième nombre est calculé pour obtenir le bon résultat (la bonne heure puis même chose avec les minutes). Volontairement les 2 lignes n’ont pas le même ordre d’affichage : a×b+c pour les heures et a+b×c pour les minutes.

Version points sur des dés

Téléchargez | Voir la démo en ligne

Il y a 17 points sur le dé du haut et 35 sur le dé du bas, il est 17 h 35 min

C’est en regardant un manuel de CP cycle 2 que j’ai eu l’idée de cette version. Le programme est assez simple, on compte les dizaines et les unités (un dé existe pour tous les chiffres entre 0 et 9). Lorsque l’on a un multiple de 10, on s’arrange pour n’afficher que les dés « 10 » (qui est en fait le caractère « = »). Il n’y a qu’avec « 0 » seul que l’on affiche le dé sans point.

AFF = n => n == 0 ?     // n vaut 0 ?
                0 :     // si oui on renvoie 0
                '='.repeat(0 | n / 10)  // Nombre de dizaines
                + (n % 10 != 0 ? n % 10 : '')  // et unités si pas 0

Version aiguilles : Heures – Minutes – Secondes

Téléchargez | Voir la démo en ligne | Version tirage aléatoire de l’heure

3 horloges séparées pour lire heures, minutes et secondes. Il est 7 h 28 min 48 s

L’horloge provient de Wikipedia, elle est au format SVG (donc transformable sans perte de qualité). Modification du SVG avec Inkscape pour créer les 2 visuels (heures et minutes), il a suffit ensuite de donner les noms heures, minutes, secondes aux aiguilles et d’appliquer une rotation en JavaScript (en précisant dans Inkscape où est le centre de rotation) :

var hm = HM(new Date().toLocaleTimeString())

// h[0] contient l'heure, h[1] les minutes et h[2] les secondes
heures.setAttribute('transform','rotate('+(hm[0]*30)+')');
minutes.setAttribute('transform','rotate('+(hm[1]*6)+')');
secondes.setAttribute('transform','rotate('+(hm[2]*6)+')');

Version cercle trigonométrique

Téléchargez | Voir la démo en ligne

0° = 15h et -18° = 3 minutes après 15 soit 15 h 18 min

La formule pour les minutes n’est qu’une fonction affine : 0 min est à 90° et 60 min à -270°. On obtient la formule :

ANGLEMIN = min => -6 * min + 90

On fait ensuite un test pour savoir si le nombre est plus petit que -180 (par exemple -246), si c’est le cas on affichera plutôt -246 + 360 = 114°

La stratégie est la même pour les heures, en faisant attention aux 2 cas : heures entre 3h et 9h puis entre 9h-12h-3h. La formule utilisée est :

ANGLEH = h => -30 * (h % 12) + 90   // le % correspond à 'modulo'

Système d’équations

Téléchargez | Voir la démo en ligne

Il faut résoudre le système pour trouver H=16 et M=37, il est donc 16 h 37 min

Pour ne pas avoir de nombres trop grands, les coefficients devant les heures sont choisis aléatoirement entre -4 et 4 (et non nuls), et entre -3 et 3 pour les minutes (non nuls).

Il faut aussi s’arranger pour ne pas afficher les coefficients 1 et -1 (par exemple 1H s’écrit H et -1M s’écrit -M), pour cela on peut écrire cette fonction :

UN = n => Math.abs(n) != 1 ? n : n == 1 ? '' : '-'

>> UN(5)
5
>> UN(1)
''
>> UN(-1)
'-'

Version binaire

Téléchargez | Voir la démo en ligne

01111 = 1 + 2 + 4 + 8 = 15 et 011110 = 2 + 4 + 8 + 16 = 30, il est 15 h 30 min

Le programme est encore plus simple puisqu’en JavaScript on transforme un nombre en binaire par :

>> (15).toString(2)
'1111'
>> (30).toString(2)
'11110'

Pour écrire les heures nous avons besoin d’au plus 5 bits et 6 bits pour les minutes.

>> BIN = (n, s) => ('0'.repeat(5) + n.toString(2)).slice(-s)

>> BIN(15,5)    // 15 écrit sur 5 bits
'01111'

>> BIN(30,6)    // 30 écrit sur 6 bits 
'011110'

Version binaire plus simple

Téléchargez | Voir la démo en ligne

Les colonnes correspondent aux dizaines et unités pour les heures, minutes et secondes
Une colonne se lit de bas en haut et les fenêtres valent 1, 2, 4 et 8
Dizaine pour les heures = 1, Unités pour les heures = 2 + 4 = 6
Dizaine pour les minutes = 1 + 2 = 3, Unités pour les minutes = 1 + 2 + 4 = 7
Dizaines pour les secondes = 4, Unités pour les secondes = 8
Il est 16 h 37 min 48 s

Une vraie horloge existe, elle se nomme « The City Clock » et vous la trouverez ici.

Le dessin a été réalisé avec Inkscape, les fenêtres ont été nommées hd1, hd2…, hu1, hu2,… pour les dizaines et unités des heures, idem avec les md, mu et sd, su.

Exemple avec 16 h : On récupère la dizaine (1) et l’unité (6) que l’on transforme en binaire (1 et 110). On parcourt les 4 fenêtres de la colonne dizaine et on met en jaune s’il y a un « 1 » sinon marron. Donc avec « 1 » seule la fenêtre du bas sera allumée. Avec 6, on parcourt les 4 fenêtres de la colonne unité et on allume la 2e et 3e fenêtre.

BIN = n => [...'0'.repeat(3)+n.toString(2)].reverse().join('')

>> BIN(6)
'011000'

>> BIN(1)
'1000'

ETAT = (v, col) => {    // Exemple v = 6 et col = 'hu'
  b = BIN(v)      // Transformation du chiffre en binaire
  for (let i = 0; i < 4; i++) {    // 4 fenêtres par colonne
      c = document.getElementById(col+(i+1))  // La fenêtre
      c.setAttribute('fill', b[i] == '0' ? '#490101' : 'yellow');
  }
 }

>> ETAT(6, 'hu') va allumer ou éteindre la colonne "heure unités" pour afficher 6

Version hexadécimale (pour les designers)

Téléchargez | Voir la démo en ligne

#0E = 14, #2A = 2*16+10=42, #14=1*16+4=20, il est 14 h 42 min 20 s

La notation utilisée est celle que l’on trouve pour le codage des couleurs (retouche d’images, HTML…), par exemple le rouge vif correspond à #FF0000. Le programme est quasi identique à la version binaire :

>> HEX = n => ('0' + n.toString(16)).slice(-2).toUpperCase()

>> HEX(14)
'0E'
>> HEX(42)
'2A'
>> HEX(20)
'14'

Inversement, pour décoder, il faut prendre l’unité (entre 0 et F) et ajouter 16 fois la dizaine.

Horloge de Fibonacci

Téléchargez | Voir la démo en ligne

7e nombre de Fibonacci = 13, 9e+6e+3e = 34+8+2 = 44, il est 13 h 44 min

La suite de Fibonacci est : 0,1,1,2,3,5,8,13,21,34,55,89… où le terme suivant est la somme des 2 précédents.

Théorème de Zeckendorf : Tous les entiers peuvent s’écrire comme une somme de nombres de Fibonacci.

// Liste des nombres de Fibonacci qui seront utiles
>> F = [0,1,1,2,3,5,8,13,21,34,55]

// Décomposition de n en somme
>> FIBO = n => {
res = [ ]        // Résultat final
while (n > 0) {  // Tant que n n'est pas nul
 // On cherche le plus grand nb de Fibonacci inférieur à n
 a = F.filter(v => v <= n).slice(-1)[0]
 // On l'ajoute au tableau
 res.push(F.indexOf(a))
 // n diminue du nombre trouvé
 n -= a
}
return res   // On retourne le résultat
}

>> FIBO(13)
[7]            // 13 = F(7)

>> FIBO(44)
[9, 6, 3]      // 44 = F(9)+F(6)+F(3)

>> FIBO(51)
(4) [9, 7, 4, 1]  // 51 = F(9)+F(7)+F(4)+F(1)

Horloge romaine

Téléchargez | Voir la démo en ligne

IX = 9, XLVIII = 48, XXIV=24, il est 9 h 48 min 24 s

On trouve facilement sur Internet un algorithme pour convertir un nombre en numérotation romaine :

var arabe = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
var romain = 'M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I'.split(',')
 
var CONV = nb => {
 if (nb == 0) return ' '
 var s = ''
 for (i in arabe) {
  var q = 0 | nb / arabe[i];     // division entière
  var nb = nb % arabe[i]         // reste de la division 
  s +=  romain[i].repeat(q)
 }
 return s
}

>> CONV(9)
'IX'

>> CONV(48)
'XLVIII'

>> CONV(24)
'XXIV'

Exemple du déroulement de l’algorithme pour 47 (Div = Division):

Reste = 47
Div du reste par 1000 = 0, reste = 47, ajout 0 = 
Div du reste par 900 = 0, reste = 47, ajout 0 = 
Div du reste par 500 = 0, reste = 47, ajout 0 = 
Div du reste par 400 = 0, reste = 47, ajout 0 = 
Div du reste par 100 = 0, reste = 47, ajout 0 = 
Div du reste par 90 = 0, reste = 47, ajout 0 = 
Div du reste par 50 = 0, reste = 47, ajout 0 = 
Div du reste par 40 = 1, reste = 7, ajout 40 = XL   // 40*1
Div du reste par 10 = 0, reste = 7, ajout 0 = XL
Div du reste par 9 = 0, reste = 7, ajout 0 = XL
Div du reste par 5 = 1, reste = 2, ajout 5 = XLV    // 5*1
Div du reste par 4 = 0, reste = 2, ajout 0 = XLV
Div du reste par 1 = 2, reste = 0, ajout 2 = XLVII  // 1*2

Pour ne pas voir les secondes, utilisez ce code :

setInterval(function x() {
  var hm = HM(new Date().toLocaleTimeString())
  document.querySelector("#hr").innerHTML = CONV(hm[0])
  document.querySelector("#mn").innerHTML = CONV(hm[1])
  return x
}(), 60000);

et supprimez la ligne :

<div id='se'></div> 

Horloge « IL RESTE »

Téléchargez (changement toutes les 30 secondes) | Voir la démo (changement toutes les 4 secondes)

Nombre de minutes avant la prochaine heure entière, ici encore 33 minutes

C’est le même programme que addition et soustraction, il suffit de remplacer l’heure par IL RESTE et de trouver un calcul qui donnera le nombre 60 – minutes

Carte de France en Python 500 octets

Suite à un Tweet de NumWorks présentant le visuel d’une carte de France, j’ai lancé le challenge de réaliser une carte aussi réaliste que possible (ou faussement réaliste) en Python et en moins de 500 octets.

Retour dans les années 80

Dans les années 80 est sorti un petit ordinateur individuel, le ZX-81. Il n’avait que 1Ko de RAM (soit 1000 caractères) mais permettait de s’initier à la programmation et de créer quelques jeux. L’achat d’une extension 16Ko ou 32Ko était cependant assez rapidement nécessaire.

Voici un programme proposé dans le livre « Pilotez votre ZX 81 » de Patrick Gueule :

La machine possédait des caractères semi-graphiques, comme par exemple ◧ ◨. L’astuce dans ce programme est de mémoriser le nombre d’espaces à afficher à partir de la gauche puis le(s) caractère(s) semi-graphique(s), à nouveau le nombre d’espaces ensuite le(s) caractère(s) et terminer par 0 pour passer à la ligne suivante. Ainsi le 7780 de la variable A$ indique qu’il faut afficher 7+7+8=22 espaces et revenir à la ligne (ligne blanche au-dessus de la carte). Ensuite 6+5=11 espaces puis 3 caractères semi-graphiques et retour à la ligne :

Remarquez que les caractères semi-graphiques ayant une dimension de 2×2, cela permet d’afficher 2 rangées de la carte à la fois.

Même idée en Python

Dessinons la carte de France en tapant des 1 dans certaines cellules d’Excel (pour cela importez une image de la France dans Mise en Page – Arrière Plan, sélectionnez toutes les cellules puis Accueil – Mise en forme conditionnelle – Règle de surlignage – Egal à 1 – Mettre une couleur de remplissage).

A côté de la carte tapez la formule =A1+2*B1+4*A2+8*B2. Cela permet de convertir les 4 cellules (jaune sur la carte) en un nombre entre 1 et 1+2+4+8=15.

On peut alors étendre cette formule horizontalement et verticalement pour recouvrir toute la carte.

Si on écrit le 9 de la première ligne en binaire :

> bin(9)
'0b1001'

Cela signifie que les cellules 1 et 4 contiennent un 1 et les autres un 0. Il s’agit du caractère ci-dessous :

On est alors dans la même configuration que sur le ZX-81, on doit compter le nombre d’espaces (les 0) puis un caractère graphique codé sur 4 cases.

Voici le début du codage :

Les lettres F et I de la première ligne sont simplement les 6e et 9e lettres de l’alphabet et permettent donc de coder les nombres 6 et 9.

Le caractère * a 42 comme code Ascii, notre référence étant le code 33, ce qui fait une différence de 9 soit 9 espaces.

> ord('*')
42
> chr(33)
'!'

Enfin, j’utiliserai le caractère ‘!’ pour les fins de ligne. Le contour de la carte peut donc être traduit par :

FR = '*FI!*E,ID!(...'

Pour le programme principal, il suffit, suivant le code Ascii, de décider si l’on doit revenir à la ligne (caractère ‘!’ de code 33), se décaler suivant l’axe des x d’un certain nombre d’espaces ou afficher un caractère semi-graphique :

x, y = 0, 0
for s in FR:
 n = ord(s)
 if n == 33: x, y = 0, y + 10        # Retour à la ligne
 elif n < 55: x = 10 * (n - 33)      # 10 pixels par "espace"
 else: 
  car(n - 64)   # Affichage du caractère semi-graphique
  x += 10       # Et décalage à droite de 10 pixels

Pour la fonction car, soit on décompose le paramètre en binaire pour savoir quelles cases on doit remplir, soit on les récupère petit à petit. Par exemple, si le caractère semi-graphique est L :

> ord('L')      # on récupère son code Ascii
76
> 76 - 64       
12              # 12e lettre
> bin(12)       
'0b1100'    # 2 premières cases noires et suivantes blanches
> 12 >> 0 & 1   # On peut aussi récupérer 1-1-0-0 petit à petit 
0
> 12 >> 1 & 1
0
> 12 >> 2 & 1
1
> 12 >> 3 & 1
1

Fonction car avec des carrés noirs de 5*5 pixels :

def car(x, y, n):
 for i in range(4):
  if n >> i & 1:
   fill_rect(x + i % 2 * 5, y + i // 2 * 5, 5, 5, (0,0,0))

Programme final ici

Avec la tortue

Une autre idée est de parcourir le contour de la carte avec la tortue. Pour rester dans les 500 octets imposés, il ne faudra utiliser que quelques points stratégiques.

Pour cela on peut ouvrir la carte de France dans Gimp et utiliser l’outil Chemin :

On note les coordonnées des points dans un tableur. L’idée est de partir d’un des points du contour puis de déplacer la tortue en utilisant uniquement les différences entre les coordonnées :

Par exemple, pour passer du point (64,58) au point (62, 61) on se décale du vecteur (-2,3). L’intérêt ? On utilisera moins de caractères pour mémoriser les coordonnées !

Voici le codage de la carte, sachant que le point initial est en (90,-60) qui correspond au nord de la Corse

F = '18!23!3!30...'

Déplacer la tortue du vecteur (1,8) puis (-2,3) puis (-3,-30) etc.

Ce qui donne cette version :

from turtle import *

F = '18!23!3!30!53!11!2!8!5!55!32!9!3!5305!40!6!3!8!1!3!33!D22!2!5!4!6!1!4!4!3!4!1!2!12!1!2!10!28!11260!2!720124!12!25!11!73098E5!29!66043!223!1B51'

def f(s = 1): 
 global i
 if F[i] == '!': i, s = i + 1, -1
 i += 1
 return s * int(F[i - 1], 16)

x = y = i = 0
penup()
while i < len(F):
 goto(90 + 3 * x, -60 - 3 * y)
 pendown()
 x += f()
 y += f()
hideturtle()

Mais le résultat n’est pas très joli car trop rectiligne et la Corse est reliée à la métropole

On va ajouter de l’aléatoire en faisant varier la trajectoire entre 2 coordonnées. Pour cela on doit décomposer le segment (x1,y1) vers (x2,y2) en sous-segments :

for j in range(9):   # Décomposition en 9 étapes...
  goto(90 + g(u,x,j),-60 - g(v,y,j))  # ...entre (u,v) et (x,y)

def g(a, b, j): return 3 * (a + (b - a) * j / 9)   # Interpolation

Et avec de l’aléatoire :

def g(a,b,j): return 3 * a + 2 * random() + (b - a) * j / 3

Concernant la séparation avec la Corse, l’astuce utilisée est qu’avec la NumWorks pensize(0) ne trace pas de trait. Ainsi en ajoutant :

pensize(not(18 < i < 23))

On aura un trait d’épaisseur 1 sauf si i est entre 18 et 23 qui correspond au trait reliant la Corse.

Enfin, on peut dessiner de petits cercles à chaque étapes plutôt qu’un trait simple, on obtient finalement ce script qui fait exactement 500 octets avec le résultat suivant :

Versions Notebook des exercices Python et JavaScript

Titre de l’exercicePythonJavaScript
1. Je ne veux pas de 5 !📙📗
2. Nombre du milieu📙📗
3. Heterogramme📙📗
4. Prendre tant que…📙📗
5. Les rats et le joueur de flûte📙📗
6.Compression d’un texte📙📗
7. Persistance d’un nombre📙📗
8. Notation polonaise inverse (RPN)📙📗
9. Lapins de Fibonacci📙📗
10. Paires de gants📙📗
11. Rotations d’une matrice carrée📙📗
12. Explosion d’un nombre📙📗
13. Une pizza gratuite !📙📗

Treizième exercice en Python, JavaScript et APL

Résumé en français : Une pizzeria récompense ses meilleurs clients en offrant une pizza gratuite s’ils ont fait au moins 5 achats d’un montant au moins égal à 20 EUR. Cependant, ce système est susceptible d’être modifié dans le futur. On vous demande de créer une fonction qui à partir du nombre d’achats minimum, du montant minimum et d’un dictionnaire contenant les données sur vos clients, va renvoyer la liste de ceux qui auront une pizza gratuite.

# Système 1 : Pour avoir une pizza gratuite, il faut avoir au moins 5 achats d'un montant minimum de 20 EUR.

min_achats = 5
min_prix = 20
conso = {
'John Doe' : [22, 30, 11, 17, 15, 52, 27, 12],  # Montants des achats
'Jane Doe' : [5, 17, 30, 33, 40, 22, 26, 10, 11, 45]
}

>> free(conso, min_achats, min_prix)
['Jane Doe']     # Elle seule aura une pizza gratuite

# Système 2 : Pour avoir une pizza gratuite, il faut avoir au moins 2 achats d'un montant minimum de 50 EUR.

min_achats = 2
min_prix = 50
conso = {
'Joey Bonzo' : [22, 67, 53, 29],       # Montants des achats
'Jennifer Bonzo' : [51, 19]
}

>> free(conso, min_achats, min_prix)
['Joey Bonzo']

Version classique

Pour chaque consommateur, on va compter le nombre d’achats dont le montant est ≥ au montant minimum imposé. Si ce nombre est ≥ au minimum d’achats, la personne aura une pizza gratuite.

On peut imaginer une première boucle pour parcourir les consommateurs, une seconde pour parcourir les achats et enfin un test pour savoir si cette personne doit avoir une pizza.

Comment :
– récupérer les différents consommateurs ?
– récupérer leurs achats ?

Partons de cet exemple :

conso = {
'John Doe' : [22, 30, 11, 17, 15, 52, 27, 12],
'Jane Doe' : [5, 17, 30, 33, 40, 22, 26, 10, 11, 45]
}

Python

>> conso.keys()                        # Autre solution plus bas
dict_keys(['John Doe', 'Jane Doe'])

>> list(conso.keys())
['John Doe', 'Jane Doe']

JavaScript

>> Object.keys(conso)
['John Doe', 'Jane Doe']

APL

conso ← ('John Doe' 22 30 11 17 15 52 27 12) 
        ('Jane Doe' 5 17 30 33 40 22 26 10 11 45)

      1↑¨conso             ⍝ Premier élément de chaque
┌──────────┬──────────┐
│┌────────┐│┌────────┐│
││John Doe│││Jane Doe││
│└────────┘│└────────┘│
└──────────┴──────────┘

Et pour récupérer les achats d’un consommateur :

Python & JavaScript

>> conso['John Doe']
[22, 30, 11, 17, 15, 52, 27, 12]


APL

      1↓¨ conso         ⍝ Achats des différents clients
┌───────────────────────┬────────────────────────────┐
│22 30 11 17 15 52 27 12│5 17 30 33 40 22 26 10 11 45│
└───────────────────────┴────────────────────────────┘

python

On peut également parcourir à la fois les clés et les valeurs. Voici un exemple qui calcule le montant total des achats des consommateurs :

>> conso = {
'John Doe' : [22, 30, 11, 17, 15, 52, 27, 12],
'Jane Doe' : [5, 17, 30, 33, 40, 22, 26, 10, 11, 45]
}

>> for (p, achats) in conso.items():
     print('Total pour {} : {}'.format(p, sum(achats)))

Total pour John Doe : 186
Total pour Jane Doe : 239

Version finale à tester ici qui reprend notre première approche :

def free(conso, min_achats, min_prix):
  gagnants = [ ]             # Personnes qui auront une pizza gratuite
  for p in conso.keys():     # On parcourt les consommateurs
    achats = conso[p]        # Récupération des achats
    total = 0                # Nb d'achats ≥ montant min
    for m in achats:         # On parcourt les achats
      if m >= min_prix :     # Si montant ≥ montant min
        total += 1           # On ajoute +1 
    if total >= min_achats:  # Suffisamment d'achats ?
      gagnants.append(p)     # Il aura une pizza gratuite
  return gagnants            # Retour de la liste des gagnants

>> free(conso, min_achats, min_prix)     # Avec l'exemple 1
['Jane Doe']

javascript

Vous pouvez tester cette version ici :

const free = (conso, min_achats, min_prix) => {
    gagnants = [ ];
    for (p of Object.keys(conso)) 
    {
     achats = conso[p];
     total = 0 ;
     for (m of achats)
     {
      if (m >= min_prix) total +=1
     }
     if (total >= min_achats) gagnants.push(p)
    }
    return gagnants}

>> free(conso, min_achats, min_prix)     // Avec l'exemple 1
['Jane Doe']

Version plus moderne

Nous devons filtrer les consommateurs suivant un double critère : Nombre de pizzas achetés et ayant un prix ≥ montant minimum. Rappelons brièvement comment on peut filtrer en Python, JavaScript et APL, par exemple en cherchant quels étudiants ont des notes ≥ 10 :

notes = [5, 12, 11, 9, 3, 17, 18, 6]

Python

>> [v for v in notes if v >= 10]
[12, 11, 17, 18]

JavaScript

>> notes.filter(v => v >= 10)
[12, 11, 17, 18]

APL

      notes ← 5 12 11 9 3 17 18 6

      (notes ≥ 10) / notes      ⍝ Version 1
12 11 17 18

      (10 ≤ notes) ⊆ notes      ⍝ Version 2
┌─────┬─────┐
│12 11│17 18│
└─────┴─────┘

      10 (≤ ⊆ ⊢) notes          ⍝ Version "train"
┌─────┬─────┐
│12 11│17 18│
└─────┴─────┘

     ∊ (10 ≤ notes) ⊆ notes
12 11 17 18

      10 (∊ < ⊆ ⊢) notes
12 11 17 18

Et pour compter le nombre d’étudiants reçus (c’est-à-dire avec une note ≥ 10 :

notes = [5, 12, 11, 9, 3, 17, 18, 6]

Python

>> len([v for v in notes if v >= 10])  # Taille du tableau
4

>> sum([v >= 10 for v in notes])       # Somme de True ou False
4

>> sum(v >= 10 for v in notes)         # Parenthèses inutiles
4


JavaScript

>> notes.filter(v => v >= 10).length
4

>> notes.reduce((a, v) => a + (v >= 10), 0)
4

APL

      notes ← 5 12 11 9 3 17 18 6

      notes +.≥ 10         ⍝ Somme des éléments ≥ 10
4

On obtient ainsi ces 2 versions plus modernes pour JavaScript et Python :

javascript

const free = (conso, min_achats, min_prix) =>
  Object.keys(conso)            // Liste de consommateurs
    .filter(p =>                // Pour chaque personne p   
       conso[p]                 // On filtre ses achats
        .filter(m => m >= min_prix)   // en gardant ceux ≥ min_prix
        .length                 // On compte le nombre d'achats ok
        >= min_achats           // On garde la personne si ≥ min_achats
    )

python

def free(conso, min_achats, min_prix):
  return [ \
    p for p in conso.keys() \       # on garde le consommateur si...
    if sum(m >= min_prix for m in conso[p]) \  # Nb achats ≥ min_prix
    >= min_achats \                 # ...dépasse min_achats
  ]

APL

On veut sélectionner ( / ) les noms des consommateurs, pour cela on va utiliser un vecteur logique (booléen) :

      1↑¨conso                ⍝ Noms des consommateurs
┌──────────┬──────────┐
│┌────────┐│┌────────┐│
││John Doe│││Jane Doe││
│└────────┘│└────────┘│
└──────────┴──────────┘
      1 0 / 1↑¨conso          ⍝ je veux le 1er et pas le 2e nom
┌──────────┐
│┌────────┐│
││John Doe││
│└────────┘│
└──────────┘

Créons le vecteur logique :

      conso ← ('John Doe' 22 30 11 17 15 52 27 12) 
              ('Jane Doe' 5 17 30 33 40 22 26 10 11 45)

      (1↓⊢)¨ conso            ⍝  Achats des consommateurs
┌───────────────────────┬────────────────────────────┐
│22 30 11 17 15 52 27 12│5 17 30 33 40 22 26 10 11 45│
└───────────────────────┴────────────────────────────┘
      (20 +.≤ 1↓⊢)¨ conso     ⍝  Nombre d'achats ≥ 20
4 6

      20 (⊣ +.≤ 1↓⊢)¨ conso     ⍝ Version plus générale
4 6

    5 ≤  20 (⊣ +.≤ 1↓⊢)¨ conso  ⍝ Ce nb d'achats est-il ≥ 5 ?
0 1

    (5 ≤  20 (⊣ +.≤ 1↓⊢)¨ conso) / 1↑¨conso   ⍝ Pizza gratuite pour
┌──────────┐
│┌────────┐│
││Jane Doe││
│└────────┘│
└──────────┘

Ce qui amène à cette version finale en APL à tester ici :

      free ← {(⍺[1] ≤ (⍺[2] +.≤ 1↓⊢)¨⍵) / 1↑¨⍵}

      5 20 free conso
┌──────────┐
│┌────────┐│
││Jane Doe││
│└────────┘│
└──────────┘
      2 50 free ('Joey Bonzo' 22 67 53 29) ('Jennifer Bonzo' 51 19)
┌────────────┐
│┌──────────┐│
││Joey Bonzo││
│└──────────┘│
└────────────┘

Douzième exercice en Python, JavaScript et APL

Résumé en français : On vous donne une chaine de caractères composée de « chiffres » (‘0’ à ‘9’). Vous devez écrire une fonction qui renvoie une chaine où chaque chiffre est répété le nombre de fois correspondant à sa valeur. Par exemple avec la chaine « 312 », on doit répéter 3 fois le « 3 », 1 fois le « 1 » et 2 fois le « 2 », ce qui donne la chaine « 333122 ».

Version classique

Première idée, utiliser 2 boucles. La première pour récupérer un à un les caractères de la chaine et la seconde pour dupliquer le bon nombre de fois chacun de ces caractères.

python

def explose(s):
  sortie = ''                      # initialisation du résultat final
  for c in s:                      # on parcourt la chaine
    for n in range(int(c)):        # on ajoute le bon nombre de fois...
      sortie += c                  # ...le caractère
  return sortie                    # retour du résultat

>>  explose("312")
'333122'
>> explose("302")
'33322'
>> explose("102269")
'12222666666999999999'

Une seule boucle + répéter

En Python, JavaScript ou APL, il est simple de répéter un caractère :

Python

>> 'a' * 5
'aaaaa'

JavaScript

>> 'a'.repeat(5)
'aaaaa'

APL

       5 ⍴ 'a'
aaaaa

On peut également répéter un caractère 0 fois, dans ce cas on obtient la chaine vide. D’où cette seconde version :

Python

def explose(s):
  sortie = ''
  for c in s:
    sortie += c * int(c)        # on répète le caractère
  return sortie

JavaScript

const explose = s => {
    sortie = '';
    for (c of s) sortie += c.repeat(+c);     // Voir dessous pour +c
    return sortie
}

>> + '5'             // Transformer une chaine en nombre
5

>> Number('5')       // Même chose que Number
5

Autres écritures : join, map, reduce

Nous devons transformer (map) chaque caractère en sa répétition, ce qui donne un tableau de taille celle de la chaine initiale :

Python

>> [c * int(c) for c in "312"]         # Transformer 3 "chiffres"
['333', '1', '22']                     # Tableau à 3 éléments

JavaScript

>> [..."312"].map(c => c.repeat(+c))   // map = transformation
['333', '1', '22']

APL

     3 1 2 ⍴¨ '312'      ⍝ le ¨ signifie "pour chaque"
┌───┬─┬──┐
│333│1│22│
└───┴─┴──┘

Il suffit ensuite de joindre les différents éléments, d’où cette troisième version :

Python

def explose(s):
  return ''.join(c * int(c) for c in s)

>> explose("44012")
'44444444122'

JavaScript v1

const explose = s => [...s].map(c => c.repeat(+c)).join('')

>> explose('55011')
'555555555511'

JavaScript est tolérant sur les mélanges de types :

>> 'a'.repeat('3')     // utilisation de '3' au lieu de 3
'aaa'
>> 3 * '4'             // multiplication d'un nombre par un caractère
12

JavaScript v2

>> const explose = s => [...s].map(c => c.repeat(c)).join``

On peut également utiliser reduce, c’est-à-dire partir d’une chaine vide et au fur et à mesure ajouter les caractères répétés, voici une version en JavaScript :

const explose = s => [...s].reduce((a, c) => a + c.repeat(c), '')

>> explose("44012")
'44444444122'

APL

Nous avons déjà vu comment transformer une chaine en vecteur :

      s ← '312'

      ⍎¨s          ⍝ On obtient un vecteur de 3 caractères
3 1 2

Remarquons que nous devons dupliquer les caractères et ensuite les concaténer :

      (3 ⍴ '3') (1 ⍴ '1') (2 ⍴ '2')      ⍝ On duplique les caractères  
┌───┬─┬──┐
│333│1│22│
└───┴─┴──┘
     ,/ (3 ⍴ '3') (1 ⍴ '1') (2 ⍴ '2')    ⍝ Concaténation
┌──────┐
│333122│
└──────┘

C’est exactement ce que fait un produit interne f.g, à savoir :

x1 x2 x3 f.g y1 y2 y3 signifie réduction f/ appliquée à (x1 g y1) (x2 g y2) (x3 g y3)

      3 1 2 ,.⍴ '312'       ⍝ On duplique puis concatène
┌──────┐
│333122│
└──────┘

      {(⍎¨⍵) ,.⍴ ⍵} '312'   ⍝ Créons notre fonction
┌──────┐
│333122│
└──────┘

      (⍎¨,.⍴⊢) '31402'      ⍝ Même version sans utiliser ⍵
┌──────────┐
│3331444422│
└──────────┘

⍝ Version finale en APL

      explose ← ⍎¨ ,.⍴ ⊢

      explose '314159'
┌───────────────────────┐
│33314444155555999999999│
└───────────────────────┘

      explose ← ∊ ⍎¨ ,.⍴ ⊢

      explose '314159'
33314444155555999999999

Expressions régulières

Une autre idée est de ce dire que chaque « chiffre » doit être remplacé par sa duplication. Voyons comment on effectue des remplacements en Python et JavaScript :

javascript

>> 'bonjour'.replace('o','*')     // Un seul 'o' sera remplacé par '*'
'b*njour'

>> 'bonjour'.replace(/o/g,'*')    // Tous les 'o' sont remplacés
'b*nj*ur'                         // 'g' pour global

>> "3a1b22".replace(/\d/g, '*')   // Remplacer les chiffres (digits)
'*a*b**'

>> '4032'.replace(/./g, v => 9 - v)  // '.' = caractère quelconque
'5967'       // Les chiffres sont remplacés par 9 - valeur

// Mettre toutes les voyelles en majuscules

>> "okjaicompris".replace(/a|e|i|o|u/g, c => c.toUpperCase())
'OkjAIcOmprIs'

D’où cette version finale en JavaScript :

const explose = s => s.replace(/./g, v => v.repeat(v))

python

Python a la méthode replace pour des remplacements simples.

>> 'bonjour'.replace('o','*')     # Tous les 'o' sont remplacés
'b*nj*ur'

D’où l’idée de remplacer chacun des caractères de ‘0’ à ‘9’ par leur duplication :

def explose(s):
    for i in range(10):
        s = s.replace(str(i), str(i) * i)
    return s

>> explose('314159')
'33314444155555999999999'

Pour utiliser des expressions régulières (Regex), nous devons importer la bibliothèque re.

>> import re
>> re.sub(r'\d','*','3a1b22')     # Remplacer les chiffres par '*'
'*a*b**'

On peut également effectuer des transformations, pour cela on :
recherche les éléments à modifier à l’aide d’une expression régulière
récupère la chaine correspondante (group ou [0])
– effectue la transformation (lambda x : …)

# Mettre toutes les voyelles en majuscules

>> re.sub(r'a|e|i|o|u', lambda x: x.group().upper(), 'okjaicompris')
'OkjAIcOmprIs'

# Ecriture équivalente en utilisant [0]

>> re.sub(r'a|e|i|o|u', lambda x: x[0].upper(), 'okjaicompris')
'OkjAIcOmprIs'

# Transformer chaque chiffre en 9 - chiffre :

>> re.sub(r'.',lambda x: str(9 - int(x[0])), '4032')
'5967'

Ce qui nous donne cette version finale en Python :

import re

def explose(s):
  return re.sub(r'.',lambda v: v[0] * int(v[0]), s)

Onzième exercice en Python, JavaScript et APL

Résumé en français : On vous donne une matrice carrée et un nombre n, vous devez renvoyer cette matrice dont les tous les termes ont été tournés (n rotations) dans le sens anti-horaire. Exemple avec une matrice 3 x 3 :

      Matrice initiale
1 2 3
4 5 6
7 8 9
      n = 1 rotation anti-horaire
3 6 9
2 5 8
1 4 7
      n = 2 rotations anti-horaire
9 8 7
6 5 4
3 2 1
      n = 3 rotations anti-horaire
7 4 1
8 5 2
9 6 3

Python : Facile avec une bibliothèque

La méthode rot90 de la bibliothèque Python numpy permet d’effectuer des rotations de tableaux :

>> import numpy as np

>> np.rot90([[1, 2], [3, 4]], 1)         # 1 rotation anti-horaire
array([[2, 4],
       [1, 3]])

>> np.rot90([[1, 2, 3], [4, 5, 6]], 2)   # 2 rotations, matrice 2 x 3
array([[6, 5, 4],
       [3, 2, 1]])

Remarquons que 2 rotations n1 et n2 sont équivalentes si la différence n1 – n2 est un multiple de 4. Par exemple, effectuer 1 rotation anti-horaire est équivalent à faire 5 rotations anti-horaires.

De façon plus générale, n rotations anti-horaires sont équivalentes à n % 4 rotations anti-horaires. D’où cette version finale en Python :

import numpy as np

def rotation(matrice, n):
    return np.rot90(matrice, n % 4).tolist()

>> rotation([[1, 2], [4, 5]], 2)
[[5, 4], [2, 1]]

JavaScript & APL : Effort moyen avec renversements et transposée

Renversements et transposée

Le diagramme ci-dessous montre que l’on peut obtenir une rotation anti-horaire à l’aide de (transposée) et ⊖ (renversement vertical) ou de ⍉ et ⌽ (renversement horizontal) :

APL

APL dispose de plusieurs primitives pour effectuer des renversements et transposée :

      m ← 2 2 ⍴ ⍳4         ⍝ Matrice 2 x 2
      m
1 2
3 4
      ⌽ m                   ⍝ renversement horizontal
2 1
4 3
      ⊖ m                   ⍝ renversement vertical
3 4
1 2
      ⍉ m                   ⍝ transposée
1 3
2 4

Vérifions :

      m ← 3 3 ⍴ ⍳9
      m
1 2 3
4 5 6
7 8 9
      (⊖⍉) m
3 6 9
2 5 8
1 4 7
      (⍉⌽) m
3 6 9
2 5 8
1 4 7

Nous avons vu dans l’exercice n°9 que ⍣ permet de répéter une opération plusieurs fois, par exemple pour 4 rotations anti-horaires (ce qui redonnera bien sûr la matrice initiale) :

      ((⊖⍉) ⍣ 4) m
1 2 3
4 5 6
7 8 9

D’où cette version finale en APL :

      rotation ← { (⍉⌽) ⍣ (4|⍺) ⊢ ⍵ }

      3 rotation 3 3 ⍴ ⍳9
7 4 1
8 5 2
9 6 3
      1 rotation 4 4 ⍴ ⍳16
4 8 12 16
3 7 11 15
2 6 10 14
1 5  9 13

Javascript

La bibliothèque JavaScript Ramda permet également de faire des renversements et de transposer des tableaux. On peut donc comme en APL remplacer la rotation anti-horaire par la combinaison transpose et reverse. Exemple que vous pouvez tester ici :

R.transpose([[1, 2], [3, 4]]).reverse()
[[2, 4], [1, 3]]

Version finale récursive à tester ici :

var rotation = (matrice, n) => {
  n %= 4                                     // reste division par 4
  if (n == 0) return matrice                 // fin récursivité
  matrice = R.transpose(matrice).reverse()   // rotation anti-horaire   
  return rotation(matrice, n - 1)            // appel récursif
}

>> rotation([[1, 2], [3, 4]], 1)
[[2, 4], [1, 3]]

JavaScript & Python : Version sans bibliothèque

Pour se fixer les idées, supposons que l’on ait une matrice 3 x 3. Observez que faire une rotation anti-horaire, c’est remplacer la 1ere ligne par la dernière colonne, la 2e ligne par la 2e colonne et la 3e ligne par la 1ere colonne :

matrice initiale

1 2 3
4 5 6
7 8 9

rotation anti-horaire

3 6 9       // 1ere ligne = 3e colonne de la matrice initiale
2 5 8       // 2e ligne = 2e colonne de la matrice initiale
1 4 7       // 3e ligne = 3e colonne de la matrice initiale

Dit autrement, faire une rotation anti-horaire, c’est prendre les colonnes de la droite vers la gauche et les écrire en lignes.

Ce que l’on peut traduire en Python ou JavaScript par :

anti_horaire = matrice => {
    res = [ ];                           // Matrice finale
    taille = matrice.length;             // Taille matrice
    for (l = 0; l < taille; l++) {       // Création de chaque ligne
        ligne = [ ];                     // Initialisation 
        for (i = 0; i < taille; i++) {   // Chaque élément de la ligne 
            ligne.push(matrice[i][taille - l - 1])
        };
        res.push(ligne)                  // Ajout de la ligne
    };
    return res;                          // On retourne le résultat
}

>> anti_horaire([[1,2,3], [4,5,6], [7,8,9]])
[3, 6, 9]
[2, 5, 8]
[1, 4, 7]

javascript

Comme il s’agit de transformer chacune des lignes, on peut également utiliser map. Voici ci-dessous la même version du programme précédent. Le matrice[0] permet de récupérer la première ligne de la matrice et donc un tableau qui a la largeur de cette matrice, son contenu ne nous intéresse pas puisqu’il va être calculé, d’où le _. Pour chaque numéro de ligne (variable l), on remplace les éléments par la colonne correspondante en partant de la droite (x.length – l – 1):

anti_horaire = matrice => 
    matrice[0].map((_,l) => matrice.map(x => x[x.length - l - 1]))

Version finale (sans bibliothèque) en JavaScript :

const rotation = (matrice, n) => {
    for (i = 0; i < n % 4; i++)
     matrice = matrice[0].map((_,l) => 
                matrice.map(x => x[x.length - l - 1]))
    return matrice
}

>> rotation([[1,2,3], [4,5,6], [7,8,9]], 1)
[3, 6, 9]
[2, 5, 8]
[1, 4, 7]

>> rotation([[1,2,3], [4,5,6], [7,8,9]], 2)
[9, 8, 7]
[6, 5, 4]
[3, 2, 1]

Python

Comme nous l’avons vu, faire une rotation anti-horaire, c’est faire une transposée (remplacer la 1ere ligne par la 1ere colonne, la 2e ligne par la 2e colonne etc.) puis inverser l’ordre des lignes :

Voici comment inverser les lignes en Python :

>> [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [::-1]
[[7, 8, 9], [4, 5, 6], [1, 2, 3]]

Ce qui donne ce programme final :

def rotation(matrice, n):
  for _ in range(n % 4):
    matrice = [[r[i] for r in matrice] for i in range(len(matrice))][::-1]
  return matrice

Ou cette autre version avancée qui utilise la notion de dépaquetage avec zip et * :

def rotation(matrice, n):
  for _ in range(n % 4):
    matrice = [list(col) for col in list(zip(*matrice))][::-1]
  return matrice

Quelques exemples pour mieux comprendre zip et * :

>> [* [[1, 2], [3, 4]]]           # Exemple n°1 de dépaquetage
[[1, 2], [3, 4]]

>> [* {1, 2, 3}]                  # Exemple n°2 de dépaquetage
[1, 2, 3]

>> [* 'abcd']                     # Exemple n°3 de dépaquetage
['a', 'b', 'c', 'd']

>> list(zip([1,2], [3,4]))
[(1, 3), (2, 4)]

>> list(zip([[1, 2], [3, 4]]))    # ne fonctionne pas
[([1, 2],), ([3, 4],)]

>> list(zip(* [[1, 2], [3, 4]]))  # Il faut déjà dépaqueter
[(1, 3), (2, 4)]

Dixième exercice en Python, JavaScript et APL

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

Neuvième exercice en Python, JavaScript et APL

Résumé en français : Des lapins naissent et deviennent matures au bout de 1 mois, âge auquel ils pourront se reproduire.
Créez une fonction qui détermine le nombre de paires de lapins matures après n mois en commençant par un unique couple de lapins immatures et qui se reproduisent à raison de b paires à la fin de chaque mois. Voir le tableau ci-dessus dans le cas de n = 5 mois avec un taux de reproduction de b = 3 pour bien comprendre le déroulement. Quelques autres exemples :

>> lapins(0, 4)
0                     # Après 0 mois, il n'y a pas de paire adultes
>> lapins(1, 4)
1                     # Après 1 mois, une seule paire d'adultes
>>lapins(4, 0)
1                     # Lapins stériles (taux = 0), on reste à 1
>> lapins(6, 3)       
40 
>> lapins(8, 12)
8425
>> lapins(7, 4)
181 

# (1 0) > (0 1) > (4 1) > (4 5) > (20 9) > (36 29) > (116 65) > 181

Cet exercice étant assez facile, proposons différentes versions :

Une simple boucle

On part de 0 adulte et d’une paire de lapins immatures. Chaque mois, le nouveau nombre d’immatures est égal au nombre d’adultes qui se reproduisent avec un taux b (c’est-à-dire la multiplication du nombre d’adultes par le coefficient b). Et le nouveau nombre d’adultes est égal au nombre d’adultes précédents + les immatures précédents qui deviennent adultes.

Il faut faire attention à l’écriture du processus, voici une version INCORRECTE :

def lapins(n, b):
    immatures, adultes = 1, 0
    for i in range(n):
        immatures = b * adultes         # on écrase immatures trop tôt
        adultes =  adultes + immatures
    return adultes

En effet, on commence par mettre à jour la variable immatures puis on utilise cette valeur à la ligne suivante, or nous avions besoin de la valeur précédente de immatures et non pas de la valeur actualisée. Une technique classique est d’utiliser une variable temporaire :

def lapins(n, b):
    immatures, adultes = 1, 0
    for i in range(n):
        temp = immatures            # On mémorise valeur précédente
        immatures = b * adultes
        adultes =  adultes + temp   # que l'on utilise ici
    return adultes

Mais en Python ou en JavaScript, on peut également utiliser cette écriture CORRECTE :

python

def lapins(n, b):
    immatures, adultes = 1, 0
    for i in range(n):
        immatures, adultes = b * adultes, adultes + immatures
    return adultes

>> lapins(8,12)
8425
>> lapins(0,4)
0
>> lapins(4,0)
1

javascript

La traduction est quasi identique en JavaScript :

 const lapins = (n, b) => {
  let [immatures, adultes] = [1, 0];
  for (let i = 0; i < n; i++) {
    [immatures, adultes] = [adultes * b, immatures + adultes];
  }
  return adultes;
}

Avec d’infinies variations, par exemple en utilisant un objet et une boucle Tant que :

const lapins = (n, b) => {
  const tous = {immatures: 1, adultes: 0};    // Tous les lapins
  mois = 0;
  while (mois < n) {
    let temp = tous.adultes;
    tous.adultes += tous.immatures;
    tous.immatures = temp * b;
    mois++;
  }  
  return tous.adultes;
}

Version récursive

Reprenons l’exemple proposé dans l’énoncé avec n = 5 et b = 3. Le nombre de paires d’adultes matures est successivement : 0 → 1 → 1 → 4 → 7 → 19

Si on note u la suite donnant le nombre d’adultes au fil des mois, on a u(0) = 0, u(1) = 1 etc.

Cette suite peut être définie par une relation de récurrence :

Ce qui signifie que le nombre de paires d’adultes au mois n+1 est 3 fois le nombre de paires d’adultes 2 mois avant (reproduction) + les immatures du mois précédent qui deviennent adultes.

Essayez en effet de vous convaincre que 0 → 1 → 14719 correspond à :

u(2) = 1 = 3 * 0 + 1, u(3) = 4 = 3 * 1 + 1, u(4) = 7 = 3 * 1 + 4, u(5) = 19 = 3 * 4 + 7 🤔

Les traductions en Python et JavaScript sont immédiates :

Python

def lapins(n, b):
  if n <= 1: return n
  return b * lapins(n - 2, b) + lapins(n - 1, b)

JavaScript

const lapins = (n, b) => n <= 1 ? 
                         n : 
                         b * lapins(n - 2, b) + lapins(n - 1, b)

>> lapins(5,3)
19
>> lapins(8,12)
8425

Version matricielle

Autre vision en utilisant cette fois-ci un calcul matriciel. En effet, observons que :

On peut donc calculer u(n+1) et u(n) à l’aide des puissances d’une unique matrice 2 x 2 :

De façon plus générale, le nombre de paires d’adultes pour un taux de reproduction b peut être calculé par :

Python

Pour calculer la puissance d’une matrice 2 x 2, nous pouvons créer une fonction de multiplication ou utiliser une bibliothèque comme numpy :

import numpy as np                 # On importe numpy

m = np.array([[1, 3], [1, 0]])     # Création de la matrice m

for k in range(5):                 # Calcul de m^0, m^1... m^4
  print('m^{} = {}'.format(k, np.linalg.matrix_power(m, k)))

Résultats

m^0 = [[1 0], [0 1]]
m^1 = [[1 3], [1 0]]
m^2 = [[4 3], [1 3]]
m^3 = [[ 7 12], [ 4  3]]
m^4 = [[19 21], [ 7 12]]

Attention cependant, la bibliothèque numpy ne gère pas (par défaut) les entiers arbitrairement grands et peut donner des résultats FAUX :

>> np.linalg.matrix_power(m, 50)      # m à la puissance 50

[[ 827677709047869124 1078278355240672323]
 [ 359426118413557441  468251590634311683]]    # Résultat EXACT

>> np.linalg.matrix_power(m, 70)      # m à la puissance 70
[[   23110438186405259  6654818438609454037]
 [-3930641878366699193  3953752316553104452]]  # Résultat FAUX !

On peut malgré tout préciser comment les données doivent être stockées (entier, flottant, objet) :

import numpy as np

m = np.array([[1, 3], [1, 0]], dtype=object)  # en tant qu'objet

>> np.linalg.matrix_power(m, 70)
[[14551031556125490725277067 18956729415189764489429973]
 [6318909805063254829809991 8232121751062235895467076]]   # EXACT !

Programme final en Python :

import numpy as np

def lapins(n, b):
    m = np.array([[1, b], [1, 0]], dtype=object)
    return np.linalg.matrix_power(m, n)[1][0]    # on récupère u(n)

>> lapins(8, 12)
8425
>> lapins(0, 4)
0
>> lapins(4, 0)
1

Javascript

Il existe des bibliothèques JavaScript pour faire du calcul matriciel, par exemple math.js :

>> m = [[1, 3], [1, 0]]

>> math.pow(m,4)
0: [19, 21]
1: [7, 12]

>> math.pow(m,70)
0: [1.455103155612549e+25, 1.8956729415189765e+25]
1: [6.318909805063255e+24, 8.232121751062236e+24]

Sinon, vous pouvez vous créer une petite fonction permettant de mettre une matrice 2 x 2 à une puissance quelconque, par exemple :

const power = (m, n) =>      // Matrice m à la puissance n
{
    [[a, b], [c, d]] = m;    // On récupère les coefficients
    r = [[1, 0], [0, 1]]     // Matrice unité
    for (i = 0; i < n; i++)  // n multiplications matricielles
    {
      [e, f] = [a * r[0][0] + c * r[0][1], b * r[0][0] + d * r[0][1]];
      [g, h] = [a * r[1][0] + c * r[1][1], b * r[1][0] + d * r[1][1]];
      r = [[e, f], [g, h]];
    };
    return r
}

>> power([[1, 3],[1, 0]], 4)
0: [19, 21]
1: [7, 12]

>> power([[1, 3],[1, 0]], 70)
0: [1.455103155612549e+25, 1.8956729415189765e+25]
1: [6.318909805063255e+24, 8.232121751062236e+24]

Programme final en JavaScript qui utilise la fonction power ci-dessus :

lapins = (n, b) =>  power([[1, b],[1, 0]], n)[1][0]

>> lapins(8, 12)
8425

Version APL

Reprenons l’idée du calcul matriciel. En APL, on définit une matrice en précisant ses dimensions suivi de ⍴ et des valeurs :

      m ← 2 2 ⍴ 1 3 1 0     ⍝  Matrice 2 x 2
1 3
1 0

Pour la mettre au carré on utilise le produit interne (ici somme des produits) :

      m +.× m
4 3
1 3

Et avec une réduction on peut obtenir par exemple m^4 :

      +.×/ m m m m
┌─────┐
│19 21│
│ 7 12│
└─────┘

Pour généraliser à une puissance quelconque r, il va falloir dupliquer la matrice r fois, exemple avec r = 4 :

      4 ⍴ ⊂ m
┌───┬───┬───┬───┐
│1 3│1 3│1 3│1 3│
│1 0│1 0│1 0│1 0│
└───┴───┴───┴───┘

D’où cette fonction pour mettre une matrice m à la puissance r :

      power ← {+.×/ ⍺ ⍴ ⊂ ⍵}

      4 power m
┌─────┐
│19 21│
│ 7 12│
└─────┘
      1 power m
┌───┐
│1 3│
│1 0│
└───┘
      0 power m
DOMAIN ERROR

Cette alternative suggérée par Dyalog APL sur Twitter a l’avantage de gérer le cas r = 0 :

      power ← {+.× ⍣ (⍺ - 1) ⍨ ⍵}

      4 power m
19 21
 7 12
      1 power m
1 3
1 0
      0 power m      ⍝ On obtient bien la matrice identité
1 0
0 1

⍣ permet de répéter une opération plusieurs fois et ⍨ d’inverser les paramètres :

      ×⍣3 ⍨ 2       ⍝ 2 → 2 × 2 = 4 → 4 × 4 = 16
16
      +⍣3 ⍨ 2       ⍝ 2 → 2 + 2 = 4 → 4 + 4 = 8
8
      +∘÷⍣ 20 ⍨1    ⍝ 1 + 1 / (1 + 1 / (1 + ...)) ≃ Nombre d'or
1.618033985

Une fois que l’on aura calculé la puissance de la matrice, il faut récupérer l’élément à la ligne 2 et colonne 1. Pour cela, on utilise ⊃ (pick) et on accole (laminate) les lignes de la matrice :

      m ← 2 2  ⍴ 7 9 5 8     ⍝ Matrice 2 x 2
      ,/ m                   ⍝ Laminage (on accole les lignes)
┌───┬───┐
│7 9│5 8│
└───┴───┘
      2 ⊃ ,/ m               ⍝ 2e terme
5 8
      2 1 ⊃ ,/ m             ⍝ 1er terme du 2e terme
5

⍝ On peut également utiliser ⌷ (index)

      2 1 ⌷ m
5

Programme final en APL :

      lapins ←  {2 1 ⌷ +.× ⍣ (⍺ - 1) ⍨ 2 2 ⍴ 1 ⍵ 1 0} 

      8 lapins 12
8425
      0 lapins 4
0
      4 lapins 0
1
      7 lapins 4
181

Huitième exercice en Python, JavaScript et APL

Quelques explications sur la notation polonaise inverse (RPN), utilisée par exemple sur les calculatrices de la marque HP (vidéo sur ma chaine Youtube pour en savoir plus) :

Aucune description disponible.
Calculateur HP-11C utilisant le mode RPN (collection personnelle)

Utilisez ce simulateur pour faire les calculs ci-dessous :

2 ENTER 3 +
Affichage : 5

3 ENTER 4 ENTER 5 * +
Affichage : 23

Ces calculatrices utilisent une pile (stack) pour placer (empiler) les valeurs (opérandes) et les calculs sont effectués dès que l’on appuie sur un opérateur (+, -, *, sin, etc.). Pour cela la machine dépile 1 ou plusieurs éléments sur le principe du « dernier arrivé, premier sorti » (LIFO = Last In First Out). Pour des opérateurs dyadiques comme l’addition ou la multiplication, il faut dépiler 2 éléments. Pour un opérateur monadique, comme sinus, on ne dépile qu’une seule valeur.

Reprenons les étapes de l’exemple proposé dans l’énoncé : 5 1 2 + 4 * + 3 –

5 ENTER 1 ENTER 2  // Pile = 5 | 1 | 2     (3 éléments empilés)
+                  // Pile = 5 | 3         (calcul 1 + 2 = 3)
4                  // Pile = 5 | 3 | 4     (4 empilé)
*                  // Pile = 5 | 12        (calcul 3 * 4 = 12)
+                  // Pile = 17            (calcul 5 + 12 = 17) 
3                  // Pile = 17 | 3        (3 empilé)
-                  // Pile = 14            (calcul 17 - 3 = 14) 

Un des intérêts du RPN est qu’il n’y a pas besoin de parenthèses, d’ailleurs vous n’en trouverez pas sur les anciennes calculatrices HP.

Les piles en python et javascript

Les piles sont simplement des listes où l’on va pouvoir empiler et/ou dépiler des éléments :

En Python

>> pile = [ ]        # pile vide
>> pile.append(2)    # on empile la valeur 2
>> pile.append(9)    # et la valeur 9
>> pile
[2, 9]
>> pile.pop()        # On dépile suivant "Last In First Out"
9
>> pile
[2]                  # Il n'y a plus qu'un seul élément dans la pile

En JavaScript

>> pile = [ ]
>> pile.push(2)
1
>> pile.push(9)
2
>> pile
[2, 9]
>> pile.pop()
9
>> pile
[2]

Evaluer une expression en python et javascript

Une première solution (Python et JavaScript) est d’utiliser eval :

>> eval('2 + 3')
5

Une autre idée est de voir 2 + 3 comme l’opérateur + appliqué aux opérandes 2 et 3, c’est-à-dire +(2,3). C’est tout simplement la notation f(x,y) utilisée en mathématique.

Voici comment traduire les 4 opérations en JavaScript à l’aide d’un dictionnaire :

>> OPS = {
  '+': (x, y) => x + y, '-': (x, y) => x - y, 
  '*': (x, y) => x * y, '/': (x, y) => x / y
}

>> OPS['+'](2,3)
5

Et en Python :

>> OPS = {  \
  '+': lambda x, y: x + y, '-': lambda x, y: x - y, \
  '*': lambda x, y: x * y, '/': lambda x, y: x / y  \
  }

>> OPS['+'](2,3)
5

Idée du programme

Gardons l’exemple : 5 1 2 + 4 * + 3 –

On va séparer (split) les différents éléments de la chaine puis, en partant de la gauche, empiler si c’est un nombre, sinon si c’est un opérateur, dépiler les 2 derniers éléments (les 4 opérateurs +-/* étant tous dyadiques), effectuer le calcul et empiler le résultat.

On empile 5 puis 1 puis 2
'+' étant un opérateur dyadique, on dépile 1 et 2
On effectue le calcul +(1,2) qui donne 3
On empile cette valeur, etc.

Python

Vous pouvez tester le programme ici :

def calc(s):
  OPS = {  \
  '+': lambda x, y: x + y, '-': lambda x, y: x - y, \
  '*': lambda x, y: x * y, '/': lambda x, y: x / y  \
  }
  pile = [ ]                         # Pile vide
  for v in s.split():                # On parcourt les éléments
    if v in OPS:                     # Est-ce un opérateur ?
      b, a = pile.pop(), pile.pop()  # on dépile 2 éléments
      pile.append(OPS[v](a, b))      # calcul + empiler le résultat
    else:                            # sinon
      pile.append(float(v))          # on empile la valeur
  return pile.pop()                  # Contenu de la pile

>> calc('5 1 2 + 4 * + 3 -')
14.0
>> calc('3.5 2.5 +')
6.0

JavaScript

Pour récupèrer les clés d’un dictionnaire on peut utiliser la fonction Object.keys. Vous pouvez tester le programme ici :

>> const calc = s => 
{
    OPS = 
    {
      '+': (x, y) => x + y, '-': (x, y) => x - y, 
      '*': (x, y) => x * y, '/': (x, y) => x / y
    };
    pile = [ ];
    for (v of s.split(' ')) 
    {
      if (Object.keys(OPS).includes(v))    // includes = contient
      {
         [b, a] = [pile.pop(), pile.pop()];
         pile.push(OPS[v](a, b))     // Ajout du résultat
      }
      else 
      {
         pile.push(+v)        // '+' pour convertir en nombre
      }
    }
    return pile.pop()
}

>> calc('5 1 2 + 4 * + 3 -')
14
>> calc('3.5 2.5 +')
6

Version APL

Un peu plus loin avec les réductions

Les calculs s’effectuant de la droite vers la gauche, nous allons déjà retourner le vecteur :

      s ← 5 1 2 '+' 4 '×' '+' 3 '-'
      ⌽s
- 3 +× 4 + 2 1 5

Nous avons vu des réductions simples comme +/, ×/ etc :

      +/ 1 2 3 4       ⍝ Somme des éléments du vecteur
10
      ×/ 1 2 3 4       ⍝ Produit des éléments du vecteur
24

Mais il est possible de faire des réductions plus complexes, premier exemple :

            {⍺,⍺,⍵} / 1 3 4
┌─────────┐
│1 1 3 3 4│
└─────────┘

Etape 1 : ⍵ = 4 (terme de droite)
Etape 2 : ⍺ = 3 que l’on ajoute 2 fois à ⍵ (concaténation ⍺,⍺,⍵), ce qui donne ⍵ = 3 3 4
Etape 3 : ⍺ = 1 que l’on ajoute 2 fois à ⍵ = 3 3 4 d’où le 1 1 3 3 4

Autre exemple :

      {⍺, ⌽⍵} / 1 2 3 4
┌───────┐
│1 3 4 2│
└───────┘

Etape 1 : ⍵ = 4 (terme de droite)
Etape 2 : Ajouter ⍺ = 3 et inverser ⍵ = 4, on obtient ⍵ = 3 4
Etape 3 : Ajouter ⍺ = 2 et inverser ⍵ = 3 4, on obtient ⍵ = 2 4 3
Etape 4 : Ajouter ⍺ = 1 et inverser ⍵ = 2 4 3, on obtient ⍵ = 1 3 4 2

évaluation d’une expression

Voici comment on peut transformer un vecteur à 3 éléments, par exemple ‘+’ 4 2 en ‘4 + 2’ et l’évaluer :

      '+' 4 2 [2 1 3]    ⍝ Prendre 2e 1er et 3e élément dans cet ordre
4 + 2                    ⍝ Le résultat reste un vecteur à 3 éléments
     ⍕ '+' 4 2 [2 1 3]   ⍝ Transformer ce vecteur en chaine avec ⍕
4 + 2
    ⍎ ⍕ '+' 4 2 [2 1 3]  ⍝ Evaluer le résultat avec ⍎
6

simulation d’une pile

      pile ← 4 6 8 9        ⍝ Une pile de 4 éléments
      ¯1↑pile               ⍝ Récupérer le dernier élément
9
      ¯1↓pile               ⍝ Supprimer le dernier élément
4 6 8
      ¯2↑pile               ⍝ Récupérer les 2 derniers éléments
8 9

Programme final

Lien pour tester directement le code ci-dessous :

      calc ← {⍺ ∊ '+-×÷' : (¯2↓⍵), ⍎⍕ (⍺,¯2↑⍵)[2 1 3] ⋄ ⍵, ⍺} / ⌽

      calc 4 2 '+'
┌─┐
│6│
└─┘
      calc 5 1 2 '+' 4 '×' '+' 3 '-'
┌──┐
│14│
└──┘

Explications :

Si l’élément du vecteur est un opérateur (⍺ ∊ ‘+-×÷’) alors supprimer les 2 derniers éléments de la pile ( ¯2↓⍵ ) et concaténer le calcul () entre l’opérateur et les 2 opérandes au sommet de la pile ( ¯2↑⍵ ) en les mettant dans le bon ordre ([2 1 3]). Sinon, ajouter la valeur à la pile ( ⍵,⍺ ).

Septième exercice en Python, JavaScript et APL 

Résumé en français : Ecrire une fonction qui admet en paramètre un nombre entier positif et qui retourne le nombre de fois où vous devez multiplier ses chiffres pour obtenir un seul chiffre.

Version classique

On doit compter (variable compteur) combien de fois il faut multiplier les chiffres entre eux jusqu’à obtenir un seul chiffre. Ce nombre d’itérations étant inconnu, nous allons naturellement utiliser une boucle Tant Que (while). Maintenant, comment faire la multiplication des chiffres d’un nombre ? On peut par exemple transformer ce nombre en chaine puis en liste et multiplier les éléments de cette liste grâce à une boucle.

Python

def mul(n):
  chaine = str(n)            # Transformation nombre en chaine
  liste = list(chaine)       # puis en liste
  produit = 1                # Initialisation du résultat du produit
  for c in liste:
    produit *= int(c)        # int = convertir chaine en entier
  return produit  

>> mul(999)
729

On peut également utiliser une librairie comme operator ou numpy :

import numpy as np

def mul(n):
  liste = list(str(n))                      # Nombre en liste
  return np.prod([int(v) for v in liste])   # "prod" pour produit

>> mul(999)
729

javascript

const mul = n => 
{
     liste = [...''+n] ;    // Conversion nombre > chaine > liste
     produit = 1 ;
     for (c of liste) produit *= +c ;
     return produit
}

>> mul(999)
729

APL

Pour transformer un nombre en chaine on utilise et inversement transforme une chaine en nombre :

      '2',⍕3     ⍝ Concaténation de la chaine '2' et de '3'
23
      ⍎ '2+3'    ⍝ Transformation de la chaine en nombre
5

Ainsi, en écrivant :

      ⍎¨⍕ 987
9 8 7

On transforme le nombre 987 en un vecteur composé de ses chiffres, le ¨ signifiant pour chaque (for each). Il suffit ensuite de faire le produit des termes, c’est-à-dire une réduction :

      ×/ ⍎¨⍕ 999
729

Programme finaL version classique en javascript

A tester ici :

const persistence = n =>
{
   var compteur = 0;                  // Notre compteur de tours
   while (n > 9) {
     compteur ++;
     produit = 1;                     // Calcul du produit des chiffres
     liste = [...''+n];               // Conversion du nombre en liste
     for (c of liste) produit *= +c;  // +c --> entier
     n = produit  
   }
   
   return compteur;
}

>> persistence(999)
4

Programme finaL version classique en python

import numpy as np

def persistence(n):
  compteur = 0
  while n > 9:
    compteur += 1
    n = np.prod([int(v) for v in list(str(n))])
  return compteur 

>> persistence(999)
4

Version récursive

Si un nombre est plus petit que 10, sa persistence est 0. Sinon, sa persistence est 1 + la persistence du produit de ses chiffres. Par exemple :

persistence(39) = 1 + persistence(3 * 9)
                = 1 + persistence(27)
                = 1 + (1 + persistence(2 * 7)) 
                = 1 + 1 + persistence(14)
                = 1 + 1 + (1 + persistence(1 * 4))
                = 1 + 1 + 1 + persistence(4)              
                = 1 + 1 + 1 + 0
                = 3

version finale récursive en python

import numpy as np

def persistence(n):
    if n < 10: return 0
    p = np.prod([int(v) for v in list(str(n))])
    return 1 + persistence(p) 

version finale récursive en javascript

La multiplication des chiffres peut se faire par reduce plutôt que par une boucle for classique :

>> [...'999'].reduce((a,c) => a * (+c), 1)   // avec parenthèses
729

>> [...'999'].reduce((a,c) => a * +c, 1)    // ou sans parenthèse !
729

>> [...'999'].reduce((a,c) => a * +c)      // ou sans initialisation !!
729

On obtient finalement :

persistence = num => 
    num < 10 ? 
    0 :
    1 + persistence([...'' + num].reduce((a, c) => a * +c))

Version finale récursive en apl

La récurvisité en APL existe en utilisant le symbole . Exemple classique de la factorielle :

      {⍵ = 1 : 1 ⋄ ⍵ × ∇ ⍵ - 1} 10
3628800
      !10
3628800

La forme est test : valeurSiVrai ⋄ valeurSiFaux où ⋄ (diamant) est le séparateur.

Voici une proposition pour notre problème :

      persistence ← {⍵ < 10 : 0 ⋄ 1 + ∇ ×/ ⍎¨ ⍕ ⍵}

      persistence 999
4

Qui est la traduction de : Si le nombre ⍵ est inférieur à 10, renvoyer 0 sinon, faire 1 plus la persistence du produit des chiffres de ⍵.