{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans ce billet, nous allons implémenter l'algorithme du \"radoteur\", un algorithme attribué à [Roland Moreno](https://fr.wikipedia.org/wiki/Roland_Moreno). Cet algorithme a pour but de générer, à partir d'un texte descriptif d'un produit, un nom susceptible d'être utilisé comme marque pour ce produit. L'intérêt conceptuel de l'algorithme est de produire une suite de caractères qui peut être vue comme la somme des mots qui le décrivent.\n",
    "\n",
    "Ce billet se base sur l'explication de l'algorithme trouvée [ici](ftp://ftp-public.4d.fr/Notes_Techniques/NT/2001/200107-23-Radoteur.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Description de l'algorithme\n",
    "\n",
    "\n",
    "Pour fonctionner, l'algorithme a besoin de données d'entrée, c'est-à-dire une série de mots à partir de laquelle on veut en générer de nouveaux. Dans notre post nous utiliserons la chaîne de caractères suivante (tirée du document cité en introduction) :\n",
    "\n",
    "> SOIENT CINQUANTE MOTS D’ANGLAIS PRIS AU HASARD, SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI.\n",
    "\n",
    "Ensuite, l'algorithme procède de la manière suivante :\n",
    "\n",
    "- initialisation : on tire un mot de la suite au hasard et on en garde la première lettre. Ceci définit en même temps une position donnée dans la chaîne, à partir de laquelle on va continuer à appliquer l'algorithme.\n",
    "- construction de caractères successifs \n",
    "    - à partir de la position courante, on avance dans la chaîne jusqu'à rencontrer à nouveau la lettre actuelle\n",
    "    - la prochaine lettre à garder est la lettre qui vient après la lettre trouvée\n",
    "    - on reprend la recherche à partir de la position de la nouvelle lettre\n",
    "- l'algorithme termine quand le dernier caractère ajouté à notre suite est un espace, une virgule..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implémentation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit tout d'abord la chaîne de caractères avec laquelle on travaille :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "input_string = \"SOIENT CINQUANTE MOTS D’ANGLAIS PRIS AU HASARD, SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ensuite, on choisit l'un des mots présents pour démarrer notre algorithme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "words = input_string.split(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import randint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CETTE'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words[randint(0, len(words) - 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut résumer ces étapes sous la forme d'une fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def init_chain(input_string):\n",
    "    \"\"\"Retourne le caractère de départ et la position dans la chaîne, \n",
    "    choisis au hasard.\"\"\"\n",
    "    words = input_string.split(' ')\n",
    "    r = randint(0, len(words) - 1)\n",
    "    start_char = words[r][0]\n",
    "    position = 0 + r + sum([len(w) for w in words[:r]]) \n",
    "    return start_char, position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On vérifie le fonctionnement de la fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('S', 48)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "init_chain(input_string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'S'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_string[48]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme on le voit, la lettre et la position se correspondent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('C', 7)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "init_chain(input_string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'C'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_string[7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut maintenant implémenter la recherche du prochain caractère. Il suffit pour cela de démarrer la recherche de la prochaine occurence de la lettre courante à partir de la position actuelle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "start_char = 'C'\n",
    "position = 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "72"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "while input_string[position + 1] != start_char:\n",
    "    position = (position + 1) % len(input_string)\n",
    "position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'C'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_string[73]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant que les bases sont posées, nous pouvons résumer ceci sous forme d'une fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def build_chain(input_string, start_char, position):\n",
    "    \"\"\"Construit une chaîne selon l'algorithme du radoteur.\"\"\"\n",
    "    chain = start_char\n",
    "    while chain[-1] not in (' ', ',', '.') and len(chain) < 30:\n",
    "        while input_string[(position + 1) % len(input_string)] != chain[-1]:\n",
    "            position = (position + 1) % len(input_string)\n",
    "        chain += input_string[(position + 2) % len(input_string)]\n",
    "        position = (position + 2) % len(input_string)\n",
    "    return chain "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'STE '"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "build_chain(input_string, 'S', 48)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SHANNON POSTULE L’EXISTENCE D’UNE LOI DE COMPOSITION DE CE SOUS-ENSEMBLE DE LA LANGUE, NON NEUTRE, ENTIÈREMENT DÉTERMINÉ, ET VA S’ATTACHER À DEMONTRER LA RIGUEUR DE CETTE LOI.'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_string[48:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On s'attend effectivement à la sortie 'STE' pour ces caractères de départ. L'algorithme est donc bien implémenté. A noter que l'on a ici utilisé deux subtilités dans le code :\n",
    "\n",
    "- une position modulo la longueur de la chaîne afin d'introduire un cycle dans la recherche des lettres\n",
    "- une limite de caractères de 30 pour éviter des chaînes trop longues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut maintenant générer pleins de mots de cette manière : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ASHEMONCOSONE,',\n",
       " 'CE ',\n",
       " 'CENGURISIOUEUE ',\n",
       " 'CHARENTETTR ',\n",
       " 'CIS ',\n",
       " 'D,',\n",
       " 'DE ',\n",
       " 'DE,',\n",
       " 'DERI.',\n",
       " 'DETENQU ',\n",
       " 'DÉ,',\n",
       " 'D’ENE ',\n",
       " 'EMIGLEXI ',\n",
       " 'EREUANN ',\n",
       " 'HA ',\n",
       " 'LA ',\n",
       " 'LANGUTINTT ',\n",
       " 'LAUL’USE ',\n",
       " 'LE ',\n",
       " 'LOINTS ',\n",
       " 'LOMBLANONTE ',\n",
       " 'MPRD’ACE ',\n",
       " 'N ',\n",
       " 'NT ',\n",
       " 'POITRENÉT ',\n",
       " 'PONS’AISANOSTIÈRMOIE ',\n",
       " 'R ',\n",
       " 'S ',\n",
       " 'S-EMER ',\n",
       " 'SOTUN ',\n",
       " 'STE ',\n",
       " 'VATA ',\n",
       " 'À '}"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set([build_chain(input_string, *init_chain(input_string)) for i in range(5000)]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut appliquer cette technique à d'autres ensemble. Par exemple pour trouver des noms de marques (comme on peut le lire sur la notice wikipédia de son inventeur). Imaginons que l'on cherche à créer un produit avec la description suivante :\n",
    "\n",
    "> Parfum capiteux, doux, subtil, idéal pour les soirées en ville.\n",
    "\n",
    "On peut lui appliquer notre algorithme :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "input_string = 'Parfum capiteux, doux, subtil, idéal pour les soirées en ville.'.upper()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'CALESURÉAR ',\n",
       " 'DÉEN ',\n",
       " 'E.',\n",
       " 'IRFUX,',\n",
       " 'LL,',\n",
       " 'PAPOILEUX,',\n",
       " 'PIL ',\n",
       " 'S ',\n",
       " 'VITIDOUM '}"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set([build_chain(input_string, *init_chain(input_string)) for i in range(5000)]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parmi ces propositions, on pourrait garder le Vitidoum, le Papoileux ou encore l'Irfux."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons implémenté l'algorithme du radoteur. Les résultats sont intéressants, mais pas forcéments tous valides. Je pense que ceci explique pourquoi cet algorithme ne peut fournir que des candidats qu'il faut ensuite trier manuellement pour retenir ceux qui sont pertinents."
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}