Types-construits-carre-magique.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Activité : Les carrés magiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partie A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple   =  [[4, 14, 15, 1],\n",
    "              [9, 7, -42, 12],\n",
    "              [5, 11 , 10 , 8],\n",
    "              [16, 2, 3, 13]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(exemple) == len(exemple[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple[1][2]=6\n",
    "somme=0\n",
    "for elem in exemple:\n",
    "    somme+=elem[2]\n",
    "somme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ma_ligne = [16 ,  2,  3,  13]\n",
    "for case in ma_ligne:\n",
    "    print(case)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partie B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contient_nbr_carre(nbr, carre):\n",
    "    \"\"\" int, list[list[int]] −> bool\n",
    "    détermine si une liste de liste contient un nombre donné \"\"\"\n",
    "    for ligne in carre:\n",
    "        if contient_nbr(nbr, ligne):\n",
    "            return True\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "contient_nbr_carre(3,  [[1,5,2], [3,6,4], [4,7,9]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "contient_nbr_carre(5 ,  [[2 ,  4,  3],  [7 ,3,1],  [9 ,  8,  1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contient_nbr(nbr, ligne):\n",
    "    \"\"\"   int,   list[int]  −>  bool\n",
    "    détermine si la liste contient un nombre donné \"\"\"\n",
    "    if nbr in ligne:\n",
    "        return True\n",
    "    else :\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "contient_nbr(7 ,  [11 ,  24 ,  7,  20 ,   3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "contient_nbr(14 ,   [11 ,  24 ,  7,  20 ,   3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_normal(carre):\n",
    "    \"\"\"  list[list[int]]  −>  bool\n",
    "    détermine si le carré est normal\"\"\"\n",
    "    list_ref=[ i for i in range(1,len(carre)*2+1)]\n",
    "    list_compare=[]\n",
    "    for elem in carre:\n",
    "        for j in range(len(elem)):\n",
    "            list_compare.append(elem[j])\n",
    "    list_compare.sort()\n",
    "    \n",
    "    for i in range(len(list_ref)):\n",
    "        if list_ref[i]!=list_compare[i]:\n",
    "            return False\n",
    "    return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carre=[[2,1], [3,4]]\n",
    "est_normal(carre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carre=[[2,3], [1,3]]\n",
    "est_normal(carre)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partie C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme(ma_liste):\n",
    "    \"\"\"   list[int]  −>  int\n",
    "    renvoie la somme des élèments de la liste \"\"\"\n",
    "    somme=0\n",
    "    for elem in ma_liste:\n",
    "        somme+=elem\n",
    "    return somme\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "somme([2,1,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mystere(carre):\n",
    "    n  =  len(carre)\n",
    "    return [carre[i][n-1-i] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carre_test=  [[1,2,3],[4,5,6],[7,8,9]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystere(carre_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_diagonale(carre):\n",
    "    \"\"\"   list[int]  −>  list[int]\n",
    "    précondition: les dimensions de carre sont celles d’un carré\n",
    "    renvoie une liste contenant les mêmes valeurs que la  diagonale  \n",
    "    en partant de droite à gauche du carré \"\"\"\n",
    "    n  =  len(carre)\n",
    "    return [carre[i][n-1-i] for i in range(n)]\n",
    "\n",
    "liste_diagonale(carre_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def diag_1(carre):\n",
    "    \"\"\"   list[list[int]]\t>  list[int]\n",
    "    précondition: les dimensions de carre sont celles d’un carré\n",
    "    renvoie une liste contenant les mêmes valeurs que la 1ere diagonale \"\"\"\n",
    "    n  =  len(carre)\n",
    "    return [carre[i][i] for i in range(n)]\n",
    "\n",
    "diag_1(carre_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "diag_1([[9,1,5],[4 ,2,8],[7,3,6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def donne_colonne(j,carre):\n",
    "    \"\"\"   list[list[int]]>  list[int]\n",
    "    précondition: les dimensions de carre sont celles d’un carré\n",
    "    renvoie une liste contenant les mêmes valeurs que\n",
    "    la colonne d’indice j de carre \"\"\"\n",
    "    n  =  len(carre)\n",
    "    return [carre[i][j] for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "donne_colonne(1,[[9,1,5],[4 ,2,8],[7,3,6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def en_colonne(carre):\n",
    "    \"\"\"   list[list[int]]>  list[list[int]]\n",
    "    précondition: les dimensions de carre sont celles d’un carré\n",
    "    renvoie une liste contenant toutes les colonnes d’un tableau carré\"\"\"\n",
    "    n  =  len(carre)\n",
    "    liste_en_colonne=[]\n",
    "    \n",
    "    for num in range(n):\n",
    "        liste_en_colonne.append(donne_colonne(num,carre))\n",
    "    return liste_en_colonne    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "en_colonne([[9,1,5], [4,2,8], [7,3,6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def meme_somme(S, listes):\n",
    "    \"\"\"   int,   list[list[int]]>  bool\n",
    "    précondition: listes est non vide\n",
    "    détermine si la somme des éléments des listes est toujours égale à S \"\"\"\n",
    "    for elem in listes:\n",
    "        if S!=somme(elem):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "meme_somme(9 ,  [[2 ,  7],  [1 ,  8],  [5 ,  4],  [6 ,   3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "meme_somme(8 ,  [[2 ,  5,  4],  [1 ,  2,  5],  [3 ,  1,  4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_magique(carre):\n",
    "    \"\"\"   list[list[int]]>  bool\n",
    "    précondition: les dimensions de carré sont celles d’un carré, ses éléments sont positifs.\n",
    "    Détermine si le carré est magique \"\"\" \n",
    "    cst  = somme(diag_1(carre))\n",
    "    listes=carre[:]\n",
    "    listes.append(diag_1(carre))\n",
    "    listes.append(en_colonne(carre))\n",
    "    listes.append(liste_diagonale(carre))\n",
    "    return meme_somme(cst, carre)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_magique([[4,9,2],[3,5,7],[8,1,6]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partie D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cree_carre(n):\n",
    "    \"\"\"   int  −>  list[list[int]]\n",
    "    précondition:  n  est   positif   \"\"\"\n",
    "    return [[0 for i in range(n)] for j in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cree_carre(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carre_genere=cree_carre(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_occupe(pos, carre):\n",
    "    \"\"\"   tuple[int,  int],   list[list[int]]  −>  bool\n",
    "    précondition: pos est dans les limites du carré \"\"\"\n",
    "    ligne,col = pos\n",
    "    if carre[ligne][col]==0:\n",
    "        return False\n",
    "    else:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_occupe((0,2),carre_genere)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carre_genere[0][2]=1\n",
    "est_occupe((0,2),carre_genere)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def translate_bas(pos, taille):\n",
    "    \"\"\"   tuple[int,  int],  int  −>  tuple[int,  int]\n",
    "    précondition: pos est dans les limites du carré \"\"\"\n",
    "    ligne, col = pos\n",
    "    if ligne+1 <taille:\n",
    "        ligne+=1\n",
    "    else: \n",
    "        ligne=0\n",
    "    return ligne,col\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "translate_bas((0,0), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "translate_bas((4,2), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def translate_droite_haut(pos, taille):\n",
    "    \"\"\"   tuple[int,  int],  int  −>  tuple[int,  int]\n",
    "    précondition: pos est dans les limites du carré \"\"\"\n",
    "    ligne, col = pos\n",
    "    if col+1 <taille:\n",
    "        col+=1\n",
    "    else: \n",
    "        col=0\n",
    "    if ligne ==0:\n",
    "        ligne=taille-1\n",
    "    else: \n",
    "        ligne-=1\n",
    "    return ligne,col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "translate_droite_haut((0,0), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "translate_droite_haut((4,2), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def position_suivante(pos,carre):\n",
    "    \"\"\"   tuple[int,  int],   list[list[int]]  −>  tuple[int,  int]\n",
    "    précondition: pos est dans les limites du carré \"\"\"\n",
    "    taille=len(carre)\n",
    "    pos1=translate_droite_haut(pos,taille)\n",
    "    if not est_occupe(pos1, carre):\n",
    "        return pos1\n",
    "    else:\n",
    "        return translate_bas(pos, taille) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "position_suivante((2,1),[[1,0,0],[0,2,0],[0,3,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rempli_siamois(pos_init, taille):\n",
    "    \"\"\"   tuple[int,  int],  int  −>  list[list[int]]\n",
    "    précondition: pos_init est compatible avec taille, et taille >= 0  \"\"\"\n",
    "    \n",
    "    liste_a_remplir=cree_carre(taille)\n",
    "    ligne, col = pos_init\n",
    "    val=1\n",
    "    liste_a_remplir[ligne][col]=val\n",
    "    pos=pos_init\n",
    "    \n",
    "    for i in range(taille*taille-1):\n",
    "        pos = position_suivante(pos, liste_a_remplir)\n",
    "        ligne, col= pos\n",
    "        val+=1\n",
    "        liste_a_remplir[ligne][col]=val\n",
    "        \n",
    "    return liste_a_remplir\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste=rempli_siamois((0,1), 5)\n",
    "liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(est_magique(liste))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "taille=5\n",
    "for i in range(taille):\n",
    "    for j in range(taille):\n",
    "        \n",
    "        if est_magique(rempli_siamois((i,j),taille)):\n",
    "            print(i,j)\n",
    "            print(\"est magique\")\n",
    "            print(\"=====================================\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}