{"id":212,"date":"2022-06-05T08:58:34","date_gmt":"2022-06-05T07:58:34","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=212"},"modified":"2022-06-19T08:02:14","modified_gmt":"2022-06-19T07:02:14","slug":"kata4","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2022\/06\/05\/kata4\/","title":{"rendered":"Quatri\u00e8me exercice en Python, JavaScript et APL"},"content":{"rendered":"\n
\"\"<\/a><\/figure>\n\n\n\n

R\u00e9sum\u00e9 en fran\u00e7ais<\/u> : On vous donne une suite de nombres ainsi qu’une fonction bool\u00e9enne. On cherche \u00e0 r\u00e9cup\u00e9rer le plus long pr\u00e9fixe (c’est-\u00e0-dire en commen\u00e7ant par le terme \u00e0 gauche) d’\u00e9l\u00e9ments v\u00e9rifi\u00e9s par cette fonction. Par exemple, si la fonction bool\u00e9enne est \u00ab\u00a0\u00eatre un nombre pair\u00a0\u00bb (isEven<\/strong> en anglais) et que la suite de nombres est [2,4,6,8,1,2,5,4,3,2], le plus long pr\u00e9fixe est [2,4,6,8] puisqu’ensuite 1 n’est pas pair.<\/p>\n\n\n\n

Cet exercice est plus abstrait que les pr\u00e9c\u00e9dents dans le sens o\u00f9 l’un des param\u00e8tres est une fonction.<\/p>\n\n\n\n

A quel endroit faut-il s’arr\u00eater ?<\/h2>\n\n\n\n

Une id\u00e9e est de chercher le rang<\/strong> (s’il existe) o\u00f9 la fonction bool\u00e9enne donnera faux<\/strong>. On devra alors garder les valeurs entre la position 0<\/strong> et rang – 1<\/strong>. Pour l’exemple donn\u00e9, la premi\u00e8re valeur impaire est \u00e0 la 4e position (le premier nombre est \u00e0 la position 0), on garde donc les nombres entre les positions 0 et 4-1=3. En JavaScript<\/strong> c’est assez simple, voici par exemple comment trouver la position du premier nombre impair :<\/p>\n\n\n\n

>> [2,4,6,8,1,2,5,4,3,2].findIndex(v => v % 2 != 0)\n4<\/code><\/pre>\n\n\n\n
Remarquez que v % 2 != 0<\/code> peut \u00eatre remplac\u00e9 par v % 2<\/code> uniquement puisque si un nombre est impair, v % 2<\/code> sera \u00e9gal \u00e0 1 qui correspond \u00e0 VRAI<\/strong> en Python ou JavaScript.<\/p>\n\n\n\n
Et lorsqu’aucune valeur ne remplit la condition, JavaScript retourne -1 :<\/p>\n\n\n\n
>> [2,4,6,8,1,2,5,4,3,2].findIndex(v => v > 10)  \/\/ Nb plus grand que 10 ?\n-1<\/code><\/pre>\n\n\n\n
On peut donc d\u00e9j\u00e0 \u00e9crire cette version finale en JavaScript<\/strong> \u00e0 tester ici <\/a>: <\/p>\n\n\n\n
const pair = n => n % 2 == 0     \/\/ true si n est pair, false sinon\n\ntakeWhile = (a, f) => {\n  let fin = a.findIndex(v => !f(v));       \/\/ On cherche o\u00f9 s'arr\u00eater\n  return fin == -1 ? a : a.slice(0, fin);  \/\/ Tableau complet ou d\u00e9coupage\n};\n\n>> takeWhile([2,4,6,8,1,2,5,4,3,2], pair)\n[2, 4, 6, 8]<\/code><\/pre>\n\n\n\n
Le if…else<\/strong> peut \u00eatre remplac\u00e9 par l’op\u00e9rateur ternaire :<\/p>\n\n\n\n
condition ? exprSiVrai : exprSiFaux<\/code><\/pre>\n\n\n\n
Dans notre cas, si fin vaut -1, renvoyer le tableau complet sinon faire le d\u00e9coupage. On peut utiliser notre programme avec des fonctions quelconques, par exemple pour trouver le plus long pr\u00e9fixe de carr\u00e9s (nombres de la forme n * n) dans un tableau :<\/p>\n\n\n\n
const carre = n => n == (Math.sqrt(n) | 0) ** 2\n\n>> takeWhile([4,9,36,48,100,121], carre)\n[4, 9, 36]<\/code><\/pre>\n\n\n\n
La notation n | 0<\/strong> est \u00e9quivalente \u00e0 un Math.floor(n)<\/strong><\/p>\n\n\n\n
En Python, on peut \u00e9galement rechercher l’index de la premi\u00e8re valeur ne v\u00e9rifiant pas une condition :<\/p>\n\n\n\n
>> next(i for i,v in enumerate([2,4,6,8,1,2,5,4,3,2]) if v%2 != 0)\n4<\/code><\/pre>\n\n\n\n
Et qui renvoie un message d’erreur lorsque la condition n’est jamais v\u00e9rifi\u00e9e :<\/p>\n\n\n\n
>> next(i for i,v in enumerate([2,4,6,8]) if v%2 != 0)\nTraceback (most recent call last):\n  File \"<stdin>\", line 1, in <module>\nStopIteration<\/code><\/pre>\n\n\n\n
Pour contourner le probl\u00e8me, on peut utiliser try<\/code> et except<\/code> :<\/p>\n\n\n\n
def cherche(a):\n  try:\n   return next(i for i,v in enumerate(a) if v%2 != 0)\n  except:\n   return -1\n\n>> cherche([2,4,6,8,1,2,5,4,3,2])\n4\n>> cherche([2,4,6,8])\n-1<\/code><\/pre>\n\n\n\n
Ce qui donne ce programme final<\/strong> :<\/p>\n\n\n\n
def pair(n): return n % 2 == 0   \n  \ndef takeWhile(a, f):\n  try:\n    fin = next(i for i,v in enumerate(a) if not(f(v)))\n    return a[:fin]\n  except:\n    return a\n\n>> takeWhile([2,4,6,8,1,2,5,4,3,2], pair)\n[2, 4, 6, 8]\n\n>> takeWhile([2,4,8,6], pair)\n[2, 4, 8, 6]<\/code><\/pre>\n\n\n\n
Passons \u00e0 APL<\/strong> en restant dans l’id\u00e9e de chercher le rang o\u00f9 arr\u00eater la s\u00e9lection.<\/p>\n\n\n\n
      a \u2190 2 4 6 8 1 2 5 4 3 2   \u235d Vecteur initial\n      0 = 2 | a                 \u235d Le reste par 2 vaut-il 0 ?\n1 1 1 1 0 1 0 1 0 1             \u235d Vrai pour les 4 premiers puis Faux...\n      \u2227\\ 0 = 2 | a              \u235d On fait un scan avec la fonction \u2227 (ET)\n1 1 1 1 0 0 0 0 0 0<\/code><\/pre>\n\n\n\n
Le test 0 = 2 | a peut aussi \u00eatre remplac\u00e9 par ~ 2 | (n\u00e9gation<\/strong>) :<\/p>\n\n\n\n
      ~ 2 | 2 4 6 8 1 2 5 4 3 2\n1 1 1 1 0 1 0 1 0 1<\/code><\/pre>\n\n\n\n
Ensuite la technique est de scanner<\/strong> (de la gauche vers la droite en APL) en utilisant le ET<\/strong>. Le premier terme (celui \u00e0 gauche) est toujours r\u00e9cup\u00e9r\u00e9 puis un ET<\/strong> est ex\u00e9cut\u00e9 entre les 2 premiers termes : 1 \u2227 1 = 1, ensuite entre les 3 premiers termes etc. Comme il s’agit de la fonction ET, d\u00e8s qu’un des nombres est nul, l’ensemble sera faux, d’o\u00f9 la suite de 0 \u00e0 partir du premier nombre impair.<\/p>\n\n\n\n
Ce vecteur bool\u00e9en va servir \u00e0 s\u00e9lectionner<\/strong> (filtrer) les \u00e9l\u00e9ments \u00e0 conserver :<\/p>\n\n\n\n
      (\u2227\\ 0 = 2 | a) \/ a\n2 4 6 8<\/code><\/pre>\n\n\n\n
Voyons comment g\u00e9n\u00e9raliser l’\u00e9criture \u00e0 une fonction bool\u00e9enne quelconque. Cr\u00e9ons par exemple isEven<\/strong> qui teste si le reste de la division du nombre par 2 est bien 0 :<\/p>\n\n\n\n
isEven \u2190 ~ 2 | \u22a2\n\n      isEven 4 5 2 11\n1 0 1 0<\/code><\/pre>\n\n\n\n
Pour mettre cette fonction en param\u00e8tre dans takeWhile<\/strong>, nous allons \u00e9crire son nom en tant que chaine puis utiliser \u234e pour l’ex\u00e9cuter :<\/p>\n\n\n\n
       takeWhile_essai \u2190 {(\u234e\u237a) \u2375}\n      'isEven' takeWhile_essai 4 5 2 11\n1 0 1 0<\/code><\/pre>\n\n\n\n
On ex\u00e9cute le terme de gauche (\u234e\u237a) en l’appliquant au terme de droite \u2375. D’o\u00f9 cette version finale :<\/p>\n\n\n\n
      takeWhile \u2190 { ( \u2227\\ (\u234e \u237a) \u2375 ) \/ \u2375 }\n\n      'isEven' takeWhile 2 4 6 8 1 2 5 4 3 2\n2 4 6 8<\/code><\/pre>\n\n\n\n
Comme me le fait remarquer Conor Hoekstra<\/a>, expert en APL, on peut aussi utiliser l’\u00e9criture :<\/p>\n\n\n\n
Lien pour tester directement le code ci-dessous<\/a> :<\/p>\n\n\n\n
takeWhile \u2190 {\u2375 \/\u2368 \u2227\\ \u237a\u237a \u2375}\n\n      isEven takeWhile 2 4 6 8 1 2 5 4 3 2\n2 4 6 8<\/code><\/pre>\n\n\n\n
Le symbole \u2368<\/strong> permettant de commuter les arguments et \u237a\u237a<\/strong> pour r\u00e9cup\u00e9rer la fonction (et donc inutile de la mettre sous forme de chaine)<\/p>\n\n\n\n
Modules existants pour Python et JavaScript<\/h2>\n\n\n\n
On retrouve takeWhile <\/strong>dans certaines biblioth\u00e8ques Python, comme itertools <\/strong>:<\/p>\n\n\n\n
>> from itertools import takewhile\n\n>> list(takewhile(lambda x: x%2 == 0, [2,4,6,8,1,2,5,4,3,2]))\n[2,4,6,8]<\/code><\/pre>\n\n\n\n
Ce qui permet de d\u00e9finir notre takeWhile <\/strong>(que nous noterons _takeWhile<\/strong>) par :<\/p>\n\n\n\n
from itertools import takewhile\n\ndef isEven(n):\n  return 0 == n % 2\n\ndef _takeWhile(a, f):\n  return list(takewhile(f, a))\n\n>> _takeWhile([2,4,6,8,1,2,5,4,3,2], isEven)\n[2, 4, 6, 8]<\/code><\/pre>\n\n\n\n
De m\u00eame on retrouve takewhile <\/strong>en JavaScript, par exemple dans la biblioth\u00e8que collect.js<\/strong><\/a>.<\/p>\n\n\n\n
>> a = collect([2,4,6,8,1,2,5,4,3,2])   \/\/ Cr\u00e9ation d'une collection\nObject { items: (10) [\u2026] }\n\n>> const isEven = n => 0 == n % 2       \/\/ notre fonction bool\u00e9enne\n\n>> a.takeWhile(isEven)\nObject { items: (4) [\u2026] }\n\n>> a.takeWhile(isEven).all()\nArray(4) [ 2, 4, 6, 8 ]<\/code><\/pre>\n\n\n\n
Ou en une seule ligne :<\/p>\n\n\n\n
>> collect([2,4,6,8,1,2,5,4,3,2]).takeWhile(isEven).all()\nArray(4) [ 2, 4, 6, 8 ]<\/code><\/pre>\n\n\n\n
Ce qui permet de d\u00e9finir notre fonction _takeWhile<\/strong> :<\/p>\n\n\n\n
>> _takeWhile = (a, f) => collect(a).takeWhile(f).all()\n\n>> _takeWhile([2,4,6,8,1,2,5,4,3,2], isEven)\nArray(4) [ 2, 4, 6, 8 ]<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
R\u00e9sum\u00e9 en fran\u00e7ais : On vous donne une suite de nombres ainsi qu’une fonction bool\u00e9enne. On cherche \u00e0 r\u00e9cup\u00e9rer le plus long pr\u00e9fixe (c’est-\u00e0-dire en commen\u00e7ant par le terme \u00e0 gauche) d’\u00e9l\u00e9ments v\u00e9rifi\u00e9s par cette fonction. Par exemple, si la … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-212","post","type-post","status-publish","format-standard","hentry","category-twitter"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=212"}],"version-history":[{"count":24,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/212\/revisions"}],"predecessor-version":[{"id":653,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/212\/revisions\/653"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}