{"id":460,"date":"2022-06-12T06:35:23","date_gmt":"2022-06-12T05:35:23","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=460"},"modified":"2022-06-19T08:03:20","modified_gmt":"2022-06-19T07:03:20","slug":"kata11","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2022\/06\/12\/kata11\/","title":{"rendered":"Onzi\u00e8me exercice en Python, JavaScript et APL"},"content":{"rendered":"\n
\"\"<\/a><\/figure>\n\n\n\n

R\u00e9sum\u00e9 en fran\u00e7ais<\/span> : On vous donne une matrice carr\u00e9e<\/strong> et un nombre<\/strong> n<\/strong>, vous devez renvoyer cette matrice dont les tous les termes ont \u00e9t\u00e9 tourn\u00e9s (n<\/strong> rotations) dans le sens anti-horaire<\/strong>. Exemple avec une matrice 3 x 3<\/span> :<\/p>\n\n\n\n

      Matrice initiale\n1 2 3\n4 5 6\n7 8 9\n      n = 1 rotation anti-horaire\n3 6 9\n2 5 8\n1 4 7\n      n = 2 rotations anti-horaire\n9 8 7\n6 5 4\n3 2 1\n      n = 3 rotations anti-horaire\n7 4 1\n8 5 2\n9 6 3<\/code><\/pre>\n\n\n\n
Python : Facile avec une biblioth\u00e8que<\/h2>\n\n\n\n
La m\u00e9thode rot90<\/strong> de la biblioth\u00e8que Python<\/strong> numpy<\/strong> permet d’effectuer des rotations de tableaux :<\/p>\n\n\n\n
>> import numpy as np\n\n>> np.rot90([[1, 2], [3, 4]], 1)         # 1 rotation anti-horaire\narray([[2, 4],\n       [1, 3]])\n\n>> np.rot90([[1, 2, 3], [4, 5, 6]], 2)   # 2 rotations, matrice 2 x 3\narray([[6, 5, 4],\n       [3, 2, 1]])<\/code><\/pre>\n\n\n\n
Remarquons que 2 rotations n1<\/sub><\/strong> et n2<\/sub><\/strong> sont \u00e9quivalentes<\/strong> si la diff\u00e9rence n1<\/sub> – n2<\/sub><\/strong> est un multiple de 4<\/strong>. Par exemple, effectuer 1<\/strong> rotation anti-horaire est \u00e9quivalent \u00e0 faire 5<\/strong> rotations anti-horaires.<\/p>\n\n\n\n
De fa\u00e7on plus g\u00e9n\u00e9rale, n<\/strong> rotations anti-horaires sont \u00e9quivalentes \u00e0 n % 4<\/strong> rotations anti-horaires. D’o\u00f9 cette version finale en Python :<\/p>\n\n\n\n
import numpy as np\n\ndef rotation(matrice, n):\n    return np.rot90(matrice, n % 4).tolist()\n\n>> rotation([[1, 2], [4, 5]], 2)\n[[5, 4], [2, 1]]<\/code><\/pre>\n\n\n\n
JavaScript & APL : Effort moyen avec renversements et transpos\u00e9e<\/h2>\n\n\n\n
Renversements et transpos\u00e9e<\/h3>\n\n\n\n
Le diagramme<\/strong> ci-dessous montre que l’on peut obtenir une rotation anti-horaire \u21ba<\/strong> \u00e0 l’aide de \u2349<\/strong> (transpos\u00e9e<\/strong>) et \u2296 (renversement<\/strong> vertical) ou de \u2349 et \u233d<\/strong> (renversement<\/strong> horizontal) :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
APL<\/h3>\n\n\n\n
APL dispose de plusieurs primitives<\/strong> pour effectuer des renversements<\/strong> et transpos\u00e9e<\/strong> :<\/p>\n\n\n\n
      m \u2190 2 2 \u2374 \u23734         \u235d Matrice 2 x 2\n      m\n1 2\n3 4\n      \u233d m                   \u235d renversement horizontal\n2 1\n4 3\n      \u2296 m                   \u235d renversement vertical\n3 4\n1 2\n      \u2349 m                   \u235d transpos\u00e9e\n1 3\n2 4<\/code><\/pre>\n\n\n\n
V\u00e9rifions : <\/p>\n\n\n\n
      m \u2190 3 3 \u2374 \u23739\n      m\n1 2 3\n4 5 6\n7 8 9\n      (\u2296\u2349) m\n3 6 9\n2 5 8\n1 4 7\n      (\u2349\u233d) m\n3 6 9\n2 5 8\n1 4 7<\/code><\/pre>\n\n\n\n
Nous avons vu dans l’exercice n\u00b09 que \u2363 permet de r\u00e9p\u00e9ter<\/strong> une op\u00e9ration plusieurs fois, par exemple pour 4 rotations anti-horaires (ce qui redonnera bien s\u00fbr la matrice initiale) :<\/p>\n\n\n\n
      ((\u2296\u2349) \u2363 4) m\n1 2 3\n4 5 6\n7 8 9<\/code><\/pre>\n\n\n\n
D’o\u00f9 cette version finale<\/strong> en APL<\/strong> :<\/p>\n\n\n\n
      rotation \u2190 { (\u2349\u233d) \u2363 (4|\u237a) \u22a2 \u2375 }\n\n      3 rotation 3 3 \u2374 \u23739\n7 4 1\n8 5 2\n9 6 3\n      1 rotation 4 4 \u2374 \u237316\n4 8 12 16\n3 7 11 15\n2 6 10 14\n1 5  9 13<\/code><\/pre>\n\n\n\n
Javascript<\/h3>\n\n\n\n
La biblioth\u00e8que JavaScript Ramda<\/a> permet \u00e9galement de faire des renversements et de transposer des tableaux. On peut donc comme en APL remplacer la rotation anti-horaire<\/strong> par la combinaison transpose<\/strong> et reverse<\/strong>. Exemple que vous pouvez tester ici<\/a> :<\/p>\n\n\n\n
R.transpose([[1, 2], [3, 4]]).reverse()\n[[2, 4], [1, 3]]<\/code><\/pre>\n\n\n\n
Version finale r\u00e9cursive<\/strong> \u00e0 tester ici<\/a> : <\/p>\n\n\n\n
var rotation = (matrice, n) => {\n  n %= 4                                     \/\/ reste division par 4\n  if (n == 0) return matrice                 \/\/ fin r\u00e9cursivit\u00e9\n  matrice = R.transpose(matrice).reverse()   \/\/ rotation anti-horaire   \n  return rotation(matrice, n - 1)            \/\/ appel r\u00e9cursif\n}\n\n>> rotation([[1, 2], [3, 4]], 1)\n[[2, 4], [1, 3]]<\/code><\/pre>\n\n\n\n
JavaScript & Python : Version sans biblioth\u00e8que<\/h2>\n\n\n\n
Pour se fixer les id\u00e9es, supposons que l’on ait une matrice 3 x 3. Observez que faire une rotation anti-horaire, c’est remplacer<\/strong> la 1ere ligne<\/strong> par la derni\u00e8re colonne<\/strong>, la 2e ligne par la 2e colonne et la 3e ligne par la 1ere colonne :<\/p>\n\n\n\n
matrice initiale\n\n1 2 3\n4 5 6\n7 8 9\n\nrotation anti-horaire\n\n3 6 9       \/\/ 1ere ligne = 3e colonne de la matrice initiale\n2 5 8       \/\/ 2e ligne = 2e colonne de la matrice initiale\n1 4 7       \/\/ 3e ligne = 3e colonne de la matrice initiale<\/code><\/pre>\n\n\n\n
Dit autrement, faire une rotation anti-horaire<\/strong>, c’est prendre les colonnes<\/strong> de la droite vers la gauche<\/strong> et les \u00e9crire en lignes<\/strong>.<\/p>\n\n\n\n
Ce que l’on peut traduire en Python ou JavaScript par :<\/p>\n\n\n\n
anti_horaire = matrice => {\n    res = [ ];                           \/\/ Matrice finale\n    taille = matrice.length;             \/\/ Taille matrice\n    for (l = 0; l < taille; l++) {       \/\/ Cr\u00e9ation de chaque ligne\n        ligne = [ ];                     \/\/ Initialisation \n        for (i = 0; i < taille; i++) {   \/\/ Chaque \u00e9l\u00e9ment de la ligne \n            ligne.push(matrice[i][taille - l - 1])\n        };\n        res.push(ligne)                  \/\/ Ajout de la ligne\n    };\n    return res;                          \/\/ On retourne le r\u00e9sultat\n}\n\n>> anti_horaire([[1,2,3], [4,5,6], [7,8,9]])\n[3, 6, 9]\n[2, 5, 8]\n[1, 4, 7]<\/code><\/pre>\n\n\n\n
javascript<\/h3>\n\n\n\n
Comme il s’agit de transformer<\/strong> chacune des lignes, on peut \u00e9galement utiliser map<\/strong>. Voici ci-dessous la m\u00eame version du programme pr\u00e9c\u00e9dent. Le matrice[0]<\/strong> permet de r\u00e9cup\u00e9rer la premi\u00e8re ligne de la matrice et donc un tableau qui a la largeur de cette matrice<\/strong>, son contenu ne nous int\u00e9resse pas puisqu’il va \u00eatre calcul\u00e9, d’o\u00f9 le _<\/strong>. Pour chaque num\u00e9ro de ligne (variable l<\/code>), on remplace les \u00e9l\u00e9ments par la colonne correspondante en partant de la droite (x.length – l – 1<\/strong>):<\/p>\n\n\n\n
anti_horaire = matrice => \n    matrice[0].map((_,l) => matrice.map(x => x[x.length - l - 1]))<\/code><\/pre>\n\n\n\n
Version finale<\/strong> (sans biblioth\u00e8que) en JavaScript<\/strong> :<\/p>\n\n\n\n
const rotation = (matrice, n) => {\n    for (i = 0; i < n % 4; i++)\n     matrice = matrice[0].map((_,l) => \n                matrice.map(x => x[x.length - l - 1]))\n    return matrice\n}\n\n>> rotation([[1,2,3], [4,5,6], [7,8,9]], 1)\n[3, 6, 9]\n[2, 5, 8]\n[1, 4, 7]\n\n>> rotation([[1,2,3], [4,5,6], [7,8,9]], 2)\n[9, 8, 7]\n[6, 5, 4]\n[3, 2, 1]<\/code><\/pre>\n\n\n\n
Python<\/h3>\n\n\n\n
Comme nous l’avons vu, faire une rotation anti-horaire<\/strong>, c’est faire une transpos\u00e9e<\/strong> (remplacer la 1ere ligne par la 1ere colonne, la 2e ligne par la 2e colonne etc.) puis inverser<\/strong> l’ordre des lignes<\/strong> :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Voici comment inverser les lignes<\/strong> en Python :<\/p>\n\n\n\n
>> [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [::-1]\n[[7, 8, 9], [4, 5, 6], [1, 2, 3]]<\/code><\/pre>\n\n\n\n
Ce qui donne ce programme final<\/strong> :<\/p>\n\n\n\n
def rotation(matrice, n):\n  for _ in range(n % 4):\n    matrice = [[r[i] for r in matrice] for i in range(len(matrice))][::-1]\n  return matrice<\/code><\/pre>\n\n\n\n
Ou cette autre version avanc\u00e9e<\/strong> qui utilise la notion de d\u00e9paquetage<\/strong> avec zip<\/strong> et *<\/strong> :<\/p>\n\n\n\n
def rotation(matrice, n):\n  for _ in range(n % 4):\n    matrice = [list(col) for col in list(zip(*matrice))][::-1]\n  return matrice<\/code><\/pre>\n\n\n\n
Quelques exemples pour mieux comprendre zip<\/strong> et *<\/strong> :<\/p>\n\n\n\n
>> [* [[1, 2], [3, 4]]]           # Exemple n\u00b01 de d\u00e9paquetage\n[[1, 2], [3, 4]]\n\n>> [* {1, 2, 3}]                  # Exemple n\u00b02 de d\u00e9paquetage\n[1, 2, 3]\n\n>> [* 'abcd']                     # Exemple n\u00b03 de d\u00e9paquetage\n['a', 'b', 'c', 'd']\n\n>> list(zip([1,2], [3,4]))\n[(1, 3), (2, 4)]\n\n>> list(zip([[1, 2], [3, 4]]))    # ne fonctionne pas\n[([1, 2],), ([3, 4],)]\n\n>> list(zip(* [[1, 2], [3, 4]]))  # Il faut d\u00e9j\u00e0 d\u00e9paqueter\n[(1, 3), (2, 4)]<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
R\u00e9sum\u00e9 en fran\u00e7ais : On vous donne une matrice carr\u00e9e et un nombre n, vous devez renvoyer cette matrice dont les tous les termes ont \u00e9t\u00e9 tourn\u00e9s (n rotations) dans le sens anti-horaire. Exemple avec une matrice 3 x 3 … 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-460","post","type-post","status-publish","format-standard","hentry","category-twitter"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/460","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=460"}],"version-history":[{"count":19,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/460\/revisions"}],"predecessor-version":[{"id":660,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/460\/revisions\/660"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}