python/automates/automates.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "fb230b39",
   "metadata": {},
   "source": [
    "# Automates\n",
    "Voir par exemple les paragraphes 3.1, 5.1.1, 5.1.2, 5.1.3, 5.1.4, 5.2.1 et 5.2.2 de ce [poly](https://1drv.ms/b/s!Aqb1Bqn8IHzxmm0bQRQeJfZoOZux?e=XZf5aQ)\n",
    "## 1. Déterminisation et recherche des mots de longueur minimale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "abf3ded0",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "class AF:\n",
    "    \"\"\"Automate fini non deterministe.\"\"\"\n",
    "    \n",
    "    def __init__(self, symboles, etats, etatsInitiaux, etatsFinaux, transitions):\n",
    "        self.symboles = symboles\n",
    "        self.etats = etats\n",
    "        self.etatsInitiaux = etatsInitiaux\n",
    "        self.etatsFinaux  = etatsFinaux\n",
    "        self.transitions = transitions\n",
    "        \n",
    "    def delta0(self,q,x):\n",
    "        \"\"\"q est un etat, x une lettre\"\"\"\n",
    "        try:\n",
    "            return self.transitions[q][x]\n",
    "        except KeyError :\n",
    "            return set()\n",
    "\n",
    "    def delta1(self,e,x):\n",
    "        \"\"\"e est un ensemble d'etats, x une lettre\"\"\"\n",
    "        return set().union(*[self.delta0(q,x) for q in e])\n",
    "\n",
    "    def afd_fonctionnel(self):\n",
    "        return AFD_fonctionnel(\n",
    "            symboles = self.symboles,\n",
    "            etatInitial = frozenset(self.etatsInitiaux),\n",
    "            estFinal = lambda e: not self.etatsFinaux.isdisjoint(e),\n",
    "            delta = lambda e,x: frozenset(self.delta1(e,x))\n",
    "        )\n",
    "\n",
    "class AFD_fonctionnel:\n",
    "    \"\"\"Automate fini deterministe\"\"\"\n",
    "\n",
    "    def __init__(self, symboles, etatInitial, estFinal, delta):\n",
    "        self.symboles = symboles\n",
    "        self.etatInitial = etatInitial\n",
    "        self.estFinal  = estFinal\n",
    "        self.delta = delta\n",
    "\n",
    "    def motDeLongueurMinimale(self):\n",
    "        q = deque([([],self.etatInitial)])\n",
    "        cont = True\n",
    "        etats = {self.etatInitial}\n",
    "        while q:\n",
    "            mot, etat = q.pop()\n",
    "            if etat is not None: # etat n'est pas un état puit\n",
    "                if self.estFinal(etat):\n",
    "                    return mot\n",
    "                for symbole in self.symboles:\n",
    "                    etat_ = self.delta(etat,symbole)\n",
    "                    if etat_ not in etats:\n",
    "                        q.appendleft((mot + [symbole],etat_))\n",
    "                        etats.add(etat_)\n",
    "        \n",
    "    def afd(self):\n",
    "        alphabet = list(self.symboles)\n",
    "        p = len(alphabet)\n",
    "        t = dict()          # {etat : numero,..}\n",
    "        f = deque()         # file des etats restant a traiter\n",
    "        n = 0               # nombre d'etats\n",
    "        etatsFinaux = set()\n",
    "        delta = [] \n",
    "        def numeroOfEtat(q):\n",
    "            # l'etat q est rajoute a t et a f si necessaire\n",
    "            nonlocal n\n",
    "            try:\n",
    "                return t[q]\n",
    "            except KeyError :\n",
    "                t[q] = n\n",
    "                f.append(q)\n",
    "                if self.estFinal(q):\n",
    "                    etatsFinaux.add(n)\n",
    "                n += 1\n",
    "                return n - 1\n",
    "        _ = numeroOfEtat(self.etatInitial)\n",
    "        while f:\n",
    "            q = f.popleft()\n",
    "            l = []\n",
    "            for i in range(p):\n",
    "                l.append(numeroOfEtat(self.delta(q,alphabet[i])))\n",
    "            delta.append(l)\n",
    "        return AFD(alphabet, etatsFinaux, delta)\n",
    "    \n",
    "    def complementaire(self):\n",
    "        return AFD_fonctionnel(self.symboles, self.etatInitial, (lambda q: not self.estFinal(q)), self.delta)\n",
    "\n",
    " \n",
    "class AFD:\n",
    "    \"\"\"Automate fini deterministe\"\"\"    \n",
    "\n",
    "    def __init__(self, symboles, etatsFinaux, delta):\n",
    "        self.symboles = symboles\n",
    "        self.etatsFinaux  = etatsFinaux\n",
    "        self.delta = delta\n",
    "\n",
    "    def __str__(self,largeur = 3):\n",
    "        p = len(self.symboles)\n",
    "        n = len(self.delta)\n",
    "        motif = '{0:^' + str(largeur) + '}'\n",
    "        s = 'Etat initial : 0\\n'\n",
    "        s += 'Etats finaux : {}\\n'.format(self.etatsFinaux)\n",
    "        s += (' ' * largeur) + '|'\n",
    "        for x in self.symboles:\n",
    "            s += motif.format(x)\n",
    "        s += '\\n' + '-' * largeur + '+' + '-' * (largeur * p) + '\\n'\n",
    "        for q in range(n):\n",
    "            s += motif.format(q) + '|'\n",
    "            for i in range(p):\n",
    "                s += motif.format(self.delta[q][i])\n",
    "            s += '\\n'\n",
    "        return s        \n",
    "        \n",
    "    def motsDeLongueurMinimale(self,long = -1):\n",
    "        \"\"\"si long >= 0, renvoie les mots de longueur long\"\"\"\n",
    "        if self.etatsFinaux:\n",
    "            p = len(self.symboles)\n",
    "            n = len(self.delta)\n",
    "            l = []\n",
    "            for q in range(n):\n",
    "                l.append({''} if q in self.etatsFinaux else set())\n",
    "            t = [l]\n",
    "            k = 0\n",
    "            while k < long or (long == -1 and t[-1][0] == set()):\n",
    "                k += 1\n",
    "                l = []\n",
    "                for q in range(n):\n",
    "                    e = set()\n",
    "                    for x in range(p):\n",
    "                        for v in t[-1][self.delta[q][x]]:\n",
    "                            e.add(self.symboles[x] + v)\n",
    "                    l.append(e)\n",
    "                t.append(l)\n",
    "            return t[-1][0]\n",
    "        else:\n",
    "            return set()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "b4665463",
   "metadata": {},
   "source": [
    "### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "685ab454",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Un plus petit mot du langage : ['a', 'b', 'a']\n",
      "\n",
      "Etat initial : 0\n",
      "Etats finaux : {3}\n",
      "   | a  b \n",
      "---+------\n",
      " 0 | 1  0 \n",
      " 1 | 1  2 \n",
      " 2 | 3  0 \n",
      " 3 | 1  2 \n",
      "\n",
      "Tous les plus petits mots du langage : {'aba'}\n"
     ]
    }
   ],
   "source": [
    "# mots se terminant par 'aba'\n",
    "af = AF(\n",
    "    symboles = {'a','b'},\n",
    "    etats = {1,2,3,4},\n",
    "    etatsInitiaux = {1},\n",
    "    etatsFinaux = {4},\n",
    "    transitions = {\n",
    "        1 : {'a' : {1,2}, 'b' : {1}},\n",
    "        2 : {'b' : {3}},\n",
    "        3 : {'a' : {4}}\n",
    "    }\n",
    ")\n",
    "\n",
    "afd_fonctionnel = af.afd_fonctionnel()\n",
    "print('Un plus petit mot du langage : {}\\n'.format(afd_fonctionnel.motDeLongueurMinimale()))\n",
    "\n",
    "afd = afd_fonctionnel.afd()  \n",
    "print(afd)\n",
    "print('Tous les plus petits mots du langage : {}'.format(afd.motsDeLongueurMinimale()))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7cfe2bf3",
   "metadata": {},
   "source": [
    "## 2. Le problème des 3 bouteilles"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a1a52e48",
   "metadata": {},
   "source": [
    "3 bouteilles de contenances $u$, $v$ et $w$ litres contiennent initialement $a$, $b$ et $c$ litres.\n",
    "\n",
    "Le but est d'obtenir $x$ litres dans l'une des bouteilles en versant les bouteilles les unes dans les autres successivement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "88c4045f",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "contenances         8  5  3\n",
      "état initial        8  0  0\n",
      "verser 1 dans 2 ->  3  5  0\n",
      "verser 2 dans 3 ->  3  2  3\n",
      "verser 3 dans 1 ->  6  2  0\n",
      "verser 2 dans 3 ->  6  0  2\n",
      "verser 1 dans 2 ->  1  5  2\n",
      "verser 2 dans 3 ->  1  4  3\n",
      "\n",
      "contenances        10  5  6\n",
      "état initial       10  1  0\n",
      "verser 1 dans 3 ->  4  1  6\n",
      "verser 3 dans 2 ->  4  5  2\n",
      "verser 2 dans 1 ->  9  0  2\n",
      "verser 3 dans 2 ->  9  2  0\n",
      "verser 1 dans 3 ->  3  2  6\n",
      "verser 3 dans 2 ->  3  5  3\n",
      "verser 2 dans 1 ->  8  0  3\n"
     ]
    }
   ],
   "source": [
    "def troisBouteilles(contenances, contenus, x):\n",
    "    \n",
    "    # (i,j) = vider (une part de) la bouteille i dans j\n",
    "    symboles = {(i,j) for i in range(3) for j in range(3) if i != j}\n",
    "    \n",
    "    etatInitial = contenus\n",
    "    \n",
    "    def estFinal(q):\n",
    "        return q[0] == x or q[1] == x or q[2] == x\n",
    "    \n",
    "    def delta(q,s):\n",
    "        i,j = s\n",
    "        l = list(q)\n",
    "        if l[i] and l[j] < contenances[j]:\n",
    "            if l[i] + l[j] <= contenances[j]:\n",
    "                l[j] += l[i]\n",
    "                l[i] = 0\n",
    "            else:\n",
    "                l[i] -= contenances[j] - l[j]\n",
    "                l[j] = contenances[j]\n",
    "            return tuple(l)\n",
    "        \n",
    "    a = AFD_fonctionnel(symboles, etatInitial, estFinal, delta)\n",
    "    sol = a.motDeLongueurMinimale()\n",
    "    \n",
    "    def str_etat(q):\n",
    "        a, b, c = q\n",
    "        return f'{a:>2} {b:>2} {c:>2}'\n",
    "    \n",
    "    q = etatInitial    \n",
    "    print(f'\\n{\"contenances\":<19}{str_etat(contenances)}')\n",
    "    print(f'{\"état initial\":<19}{str_etat(q)}')\n",
    "    for i,j in sol:\n",
    "        q = delta(q,(i,j))\n",
    "        print(f'verser {i+1} dans {j+1} -> {str_etat(q)}')\n",
    "        \n",
    "troisBouteilles((8,5,3),(8,0,0),4)\n",
    "troisBouteilles((10,5,6),(10,1,0),8)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7f07378e",
   "metadata": {},
   "source": [
    "## 3. [Loup chèvre chou](https://fr.wikipedia.org/wiki/Le_loup,_la_ch%C3%A8vre_et_le_chou)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e80ea1cb",
   "metadata": {},
   "source": [
    "Sur une rive d'un fleuve, il y a 3 humains, 1 grand singe, 2 petits singes\n",
    "et 1 barque.  \n",
    "Les humains et le grand singe sont capables de manœuvrer la barque,\n",
    "pas les petits singes.  \n",
    "La barque peut convenir à 1 ou 2 occupants.  \n",
    "De plus, il ne faut pas que les humains soient en infériorité numérique,\n",
    "sinon ils se font attaquer par les singes.  \n",
    "Comment emmener tout ce petit monde de l’autre côté du fleuve ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "43600437",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    rive gauche             rive droite             traversée\n",
      "\n",
      " 0  H H H S s s B                                      H s ->\n",
      " 1  H H   S s               H       s   B           <- H     \n",
      " 2  H H H S s   B                   s                  S s ->\n",
      " 3  H H H                         S s s B           <- S     \n",
      " 4  H H H S     B                   s s                H H ->\n",
      " 5  H     S                 H H     s s B           <- H s   \n",
      " 6  H H   S s   B           H       s                  H S ->\n",
      " 7  H       s               H H   S s   B           <- H s   \n",
      " 8  H H     s s B           H     S                    H H ->\n",
      " 9          s s             H H H S     B           <- S     \n",
      "10        S s s B           H H H                      S s ->\n",
      "11          s               H H H S s   B           <- H     \n",
      "12  H       s   B           H H   S s                  H s ->\n",
      "13                          H H H S s s B          \n"
     ]
    }
   ],
   "source": [
    "# Un état est un quadruplet\n",
    "# nombre d'humains, de grands singes, de petits singes, de barques\n",
    "# sur la rive gauche (rive où se trouve tout le monde au début)\n",
    "\n",
    "symboles = {('H','H'), ('H','S'), ('H','s'), ('H',), ('S','s'), ('S',)}\n",
    "\n",
    "etatInitial = 3,1,2,1\n",
    "\n",
    "def estFinal(q):\n",
    "    return q == (0,0,0,0)\n",
    "\n",
    "def estCorrect(q):\n",
    "    H,S,s,_ = q\n",
    "    return H >= 0 and S >= 0 and s >= 0 and ( H == 0 or H >= S + s)\n",
    "\n",
    "def etatOppose(q):\n",
    "    H,S,s,B = q\n",
    "    return 3 - H, 1 - S, 2 - s, 1 - B\n",
    "\n",
    "def delta(q, l):\n",
    "    H, S, s, B = q\n",
    "    eps = -1 if B else 1\n",
    "    for x in l:\n",
    "        if x == 'H':\n",
    "            H += eps\n",
    "        elif x == 'S':\n",
    "            S += eps\n",
    "        elif x == 's':\n",
    "            s += eps \n",
    "    p = H, S, s, 1 - B\n",
    "    if estCorrect(p) and estCorrect(etatOppose(p)):\n",
    "        return H, S, s, 1 - B\n",
    "    \n",
    "automate = AFD_fonctionnel(symboles, etatInitial, estFinal, delta)\n",
    "\n",
    "sol = automate.motDeLongueurMinimale()\n",
    "   \n",
    "def str_etat(q):\n",
    "    def str_elt(e,n,m):\n",
    "        return f'{e:>2}' * n + ' ' * 2 * (m - n)\n",
    "    def aux(q):\n",
    "        H, S, s, B = q\n",
    "        return str_elt('H',H,3) + str_elt('S',S,1) + str_elt('s',s,2) + str_elt('B',B,1) + ' ' * 10\n",
    "    return aux(q) + aux(etatOppose(q))\n",
    "    \n",
    "q = etatInitial\n",
    "rg, rd = 'rive gauche', 'rive droite'\n",
    "print(' ' * 4 + f'{rg:<24}' + f'{rd:<24}traversée\\n')\n",
    "for i,l in enumerate(sol):\n",
    "    fl1,fl2 =  (' <- ', '   ') if i % 2 else ('    ', ' ->')\n",
    "    print(f'{i:>2} ' + str_etat(q),end = '')\n",
    "    print(fl1 + l[0],end = ' ')\n",
    "    print((l[1] if len(l) == 2 else ' ') + fl2)\n",
    "    q = automate.delta(q,l)\n",
    "print(f'{len(sol):>2} ' + str_etat(q)) "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a99c5fe1",
   "metadata": {},
   "source": [
    "## 4. Jeu sur un graphe"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "b74a564e",
   "metadata": {},
   "source": [
    "Les lettres $A,B,C,D,E$  ont été mélangées. À chaque coup,\n",
    "une lettre va de sa zone à la zone vide, à condition qu'il\n",
    "existe un chemin y menant.\n",
    "Il s'agit de replacer  les lettres comme indiqué :  \n",
    "![graphe](graphe.jpg)  \n",
    "Il y a une solution simple en 12 coups : $DEABCDEABCDE$.\n",
    "\n",
    "Trouver une solution en 10 coups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6a8e512e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 solutions DEACDEABDE CAEBDCAECA CBDEBCEACE DACDABDEBA CABDCAEBCA DECDEACBDE CADCAEBDCA DEBACDEADE DEBCDEACDE "
     ]
    }
   ],
   "source": [
    "graphe =[[1,5],[0,2,3,4],[1,3,4,5],[1,2,4,5],[1,2,3,5],[0,2,3,4]]\n",
    "\n",
    "symboles = {'A', 'B', 'C', 'D', 'E'}\n",
    "\n",
    "etatInitial = 'vDEABC'\n",
    "\n",
    "def estFinal(q):\n",
    "    return q == 'vABCDE'\n",
    "\n",
    "def delta(q,x):\n",
    "    if q is None: return None\n",
    "    i, j = q.index(x), q.index('v')\n",
    "    if j in graphe[i]:\n",
    "        def f(k): return x if k == j else 'v' if k == i else q[k]\n",
    "        return f(0)+f(1)+f(2)+f(3)+f(4)+f(5)\n",
    "\n",
    "automate = AFD_fonctionnel(symboles, etatInitial, estFinal, delta).afd()\n",
    "    \n",
    "l = automate.motsDeLongueurMinimale(long = 10)\n",
    "\n",
    "print(len(l),'solutions',end = ' ')\n",
    "for s in l: print(s, end = ' ')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "2a26fe5e",
   "metadata": {},
   "source": [
    "## 5. Le problème des 4 jetons (d'après [Jean-Eric Pin](https://www.irif.fr/~jep/indexAnglais.html)) \n",
    "### Enoncé"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e37fe476",
   "metadata": {},
   "source": [
    "Le joueur a les yeux bandés. Face à lui, un plateau sur lequel sont disposés en carré quatre jetons, blancs d'un côté et noirs de l'autre. Le but du jeu est d'avoir les quatre jetons du côté blanc. Pour cela, le joueur peut retourner autant de jetons qu'il le souhaite, mais sans les déplacer. A chaque tour, le maître de jeu annonce si la configuration obtenue est gagnante ou pas, puis effectue une rotation du plateau de zéro, un, deux ou trois quarts de tours. La configuration de départ est inconnue du joueur, mais le maître de jeu annonce avant le début du jeu qu'elle n'est pas gagnante. Chaque annonce prend une seconde, et il faut 3 secondes au joueur pour retourner les jetons. Pouvez-vous aider le joueur à gagner en moins d'une minute ?\n",
    "\n",
    "![fig](JEPin.jpg)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "85a6826e",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7b5fedaf",
   "metadata": {},
   "source": [
    "Le plateau peut avoir six configurations différentes :\n",
    "- *0* : les 4 jetons sont du côté blanc\n",
    "- *1* : 1 jeton est noir\n",
    "- *a* : 2 jetons sont blancs et ils sont adjacents\n",
    "- *o* : 2 jetons sont blancs et ils sont diagonalement opposés\n",
    "- *3* : 1 jeton est blanc\n",
    "- *4* : les 4 jetons sont noirs\n",
    "\n",
    "Seule la configuration *0* est gagnante.\n",
    "\n",
    "Le joueur peut retourner un jeton, deux jetons adjacents, deux jetons opposés, trois jetons ou quatre jetons. Nous noterons respectivement *1*, *a*, *o*, *3* et *4* ces différentes actions. Les transitions définies par ces actions sont représentées par l'automate `af` suivant dans lequel toutes les transitions arrivant sur la configuration gagnante ont été omises. Comme tous les états sont finaux, cet automate reconnait le complémentaire du langage cherché."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "33a83161",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4o4a4o434o4a4o4"
     ]
    }
   ],
   "source": [
    "X = {'1','a','o','3','4'}\n",
    "\n",
    "af = AF(\n",
    "    symboles = X,\n",
    "    etats  = X,\n",
    "    etatsInitiaux = X,\n",
    "    etatsFinaux = X,\n",
    "    transitions = {\n",
    "      '1' : {'1' : {'a','o'},     'a' : {'1','3'}, 'o' : {'1','3'}, '3' : {'a','o','4'}, '4' : {'3'}},\n",
    "      'a' : {'1' : {'1','3'},     'a' : {'o','4'}, 'o' : {'a'},     '3' : {'1','3'},     '4' : {'a'}},\n",
    "      'o' : {'1' : {'1','3'},     'a' : {'a'},     'o' : {'4'},     '3' : {'1','3'},     '4' : {'o'}},\n",
    "      '3' : {'1' : {'a','o','4'}, 'a' : {'1','3'}, 'o' : {'1','3'}, '3' : {'a','o'},     '4' : {'1'}},\n",
    "      '4' : {'1' : {'3'},         'a' : {'a'},     'o' : {'o'},     '3' : {'1'}}\n",
    "    }\n",
    ")\n",
    "\n",
    "afd = af.afd_fonctionnel().complementaire()\n",
    "\n",
    "for x in afd.motDeLongueurMinimale(): print(x, end = '')"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}