{"id":13260,"date":"2013-05-07T16:50:00","date_gmt":"2013-05-07T14:50:00","guid":{"rendered":"https:\/\/blog.ouidou.fr\/?p=13260"},"modified":"2025-12-01T16:26:05","modified_gmt":"2025-12-01T15:26:05","slug":"exercice-de-programmation-codingame","status":"publish","type":"post","link":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame","title":{"rendered":"Exercice de programmation &#8211; Codingame"},"content":{"rendered":"\n<p class=\"has-text-color wp-block-paragraph\" style=\"color:#7c7676\"><em>Article \u00e9crit par Nicolas Zermati<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"http:\/\/www.codingame.com\/\" target=\"_blank\" rel=\"noreferrer noopener\">CodinGame<\/a>&nbsp;est un site web proposant des challenges de programmation. Ces \u00e9v\u00e8nements ont pour but de mettre en relation entreprises et postulants au travers de leur code. Cependant, il est tout \u00e0 fait possible de participer juste&nbsp;<em>pour le fun<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Le challenge se d\u00e9roule \u00e0 une date donn\u00e9e et se compose de plusieurs petits programmes qu\u2019il faut r\u00e9aliser les uns apr\u00e8s les autres.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Les programmes peuvent \u00eatre \u00e9crits en C, C++, Java, C#, PHP, Python ou Ruby. Un IDE en ligne permet d\u2019\u00e9crire son code et de le tester avec des jeux de donn\u00e9es fournis.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Cependant je pense que beaucoup de participants codent en local, dans leur \u00e9diteur favori avant de soumettre leur solutions dans l\u2019IDE.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dans cet article, je vous propose de reprendre le troisi\u00e8me exercice propos\u00e9 lors du CodinGame de janvier, de la m\u00eame mani\u00e8re que lors de l\u2019article sur la&nbsp;r\u00e9solution des grilles de Boggle.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"sujet-de-lexercice\">Sujet de l\u2019exercice<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><em><strong>Note<\/strong>&nbsp;: cette section est une copie du sujet pr\u00e9sent sur le site de CodinGame.<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous travaillez au mus\u00e9e de la R\u00e9sistance nationale et vous venez d\u2019exhumer des centaines de documents contenant des transmissions cod\u00e9es en Morse.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Le Morse est un codage compos\u00e9 de points et de traits repr\u00e9sentant des lettres de l\u2019alphabet. Voici la transciption d\u2019un alphabet en Morse&nbsp;:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>A&nbsp;:&nbsp;<code>.-<\/code><br>B&nbsp;:&nbsp;<code>-...<\/code><br>C&nbsp;:&nbsp;<code>-.-.<\/code><br>D&nbsp;:&nbsp;<code>-..<\/code><br>E&nbsp;:&nbsp;<code>.<\/code><br>F&nbsp;:&nbsp;<code>..-.<\/code><br>G&nbsp;:&nbsp;<code>--.<\/code><\/td><td>H&nbsp;:&nbsp;<code>....<\/code><br>I&nbsp;:&nbsp;<code>..<\/code><br>J&nbsp;:&nbsp;<code>.---<\/code><br>K&nbsp;:&nbsp;<code>-.-<\/code><br>L&nbsp;:&nbsp;<code>.-..<\/code><br>M&nbsp;:&nbsp;<code>--<\/code><br>N&nbsp;:&nbsp;<code>-.<\/code><\/td><td>O&nbsp;:&nbsp;<code>---<\/code><br>P&nbsp;:&nbsp;<code>.--.<\/code><br>Q&nbsp;:&nbsp;<code>--.-<\/code><br>R&nbsp;:&nbsp;<code>.-.<\/code><br>S&nbsp;:&nbsp;<code>...<\/code><br>T&nbsp;:&nbsp;<code>-<\/code><\/td><td>U&nbsp;:&nbsp;<code>..-<\/code><br>V&nbsp;:&nbsp;<code>...-<\/code><br>W&nbsp;:&nbsp;<code>.--<\/code><br>X&nbsp;:&nbsp;<code>-..-<\/code><br>Y&nbsp;:&nbsp;<code>-.--<\/code><br>Z&nbsp;:&nbsp;<code>--..<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Dans les documents, aucun espace n\u2019a \u00e9t\u00e9 retranscrit pour s\u00e9parer les lettres et les mots qui se cachent derri\u00e8re une s\u00e9quence en Morse. Une s\u00e9quence d\u00e9cod\u00e9e peut donc avoir diff\u00e9rentes interpr\u00e9tations.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Par exemple, la s\u00e9quence&nbsp;<code>-....--.-.<\/code>&nbsp;peut aussi bien correspondre \u00e0 BAC, BANN, DUC, DU TETE, \u2026<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Un \u00eatre humain est capable de reconna\u00eetre le d\u00e9coupage ad\u00e9quat gr\u00e2ce \u00e0 sa connaissance de la langue mais pour une machine c\u2019est plus d\u00e9licat. Pour que votre programme puisse faire l\u2019\u00e9quivalent vous avez \u00e0 votre disposition un dictionnaire contenant un ensemble de mots corrects.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Cependant, m\u00eame avec un dictionnaire, il est possible qu\u2019une s\u00e9quence puisse correspondre \u00e0 plusieurs messages valides (BAC, DUC, DU et TETE pourraient \u00eatre pr\u00e9sents dans le dictionnaire de l\u2019exemple pr\u00e9c\u00e9dent).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Votre programme devra d\u00e9terminer le nombre de messages diff\u00e9rents qu\u2019il est possible d\u2019obtenir \u00e0 partir d\u2019une s\u00e9quence en Morse et d\u2019un dictionnaire donn\u00e9.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>ENTR\u00c9E&nbsp;:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ligne 1&nbsp;: Une s\u00e9quence Morse de longueur maximale L<\/li>\n\n\n\n<li>Ligne 2&nbsp;: Un entier N correspondant au nombre de mots du dictionnaire<\/li>\n\n\n\n<li>Les N Lignes suivantes&nbsp;: Un mot du dictionnaire par ligne. Chaque mot a une longueur maximale M et n\u2019apparait qu\u2019une seule fois dans le dictionnaire.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>SORTIE&nbsp;:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Un entier R correspondant au nombre de messages qu\u2019il est possible de g\u00e9n\u00e9rer \u00e0 partir de la s\u00e9quence en Morse et du dictionnaire.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>CONTRAINTES&nbsp;:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>0 &lt; L &lt; 100000<\/li>\n\n\n\n<li>0 &lt; N &lt; 100000<\/li>\n\n\n\n<li>0 &lt; M &lt; 20<\/li>\n\n\n\n<li>0 &lt;= R &lt; 263<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>EXEMPLE&nbsp;:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\"><code>Entr\u00e9e\n......-...-..---.-----.-..-..-..\n5\nHELL\nHELLO\nOWORLD\nWORLD\nTEST\n\nSortie\n2\n<\/code><\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li>M\u00e9moire RAM disponible&nbsp;: 256Mo<\/li>\n\n\n\n<li>Dur\u00e9e maximum d\u2019ex\u00e9cution&nbsp;: 6 secondes<\/li>\n\n\n\n<li>Le programme doit lire les entr\u00e9es depuis l\u2019entr\u00e9e standard<\/li>\n\n\n\n<li>Le programme doit \u00e9crire la r\u00e9ponse dans la sortie standard<\/li>\n\n\n\n<li>Le programme doit fonctionner dans l\u2019environnement de test fourni<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"avant-de-commencer\">Avant de commencer\u2026<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Plut\u00f4t que d\u2019ex\u00e9cuter les tests sur les serveurs de CodinGame, je pr\u00e9f\u00e8re le faire en local. En effet, cela \u00e9vite de surcharger inutilement les serveurs et cela va beaucoup plus vite.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour r\u00e9soudre ce type de petit probl\u00e8me, je rassemble donc dans un m\u00eame r\u00e9pertoire les fichiers suivants&nbsp;:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\"><code>in1.txt    # Entr\u00e9es n\u00b01\nout1.txt   # Sorties attendues pour les entr\u00e9es n\u00b01\n...\nscript.rb  # Script permettant de r\u00e9soudre le probl\u00e8me\ntest.sh    # Script de test<\/code><\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Pour chaque fichier d\u2019entr\u00e9es,&nbsp;<code>test.sh<\/code>&nbsp;compare les sorties du programme avec les sorties attendues. Bien entendu, il faut que les fichiers respectent les formats suivants&nbsp;:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>in[0-9]+.txt<\/code>&nbsp;pour les fichiers d\u2019entr\u00e9es et<\/li>\n\n\n\n<li><code>out[0-9]+.txt<\/code>&nbsp;pour les fichiers de sorties.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ainsi, vous n\u2019avez qu\u2019\u00e0 lancer&nbsp;<code>.\/test.sh<\/code>&nbsp;pour avoir le r\u00e9sultat des tests&nbsp;:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\"><code>Testing scenario #1... success\nTesting scenario #3... success\nTesting scenario #2... success\nTesting scenario #4... success<\/code><\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Lorsqu\u2019une erreur se produit, la suite de tests est interrompue et un diff est affich\u00e9&nbsp;:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\"><code>Testing scenario #1... failure\n1c1\n&lt; 1\n---\n&gt; 2<\/code><\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Ici, la r\u00e9ponse attendue est&nbsp;<code>1<\/code>&nbsp;mais la r\u00e9ponse affich\u00e9e par le script est&nbsp;<code>2<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous trouverez tous les fichiers sur le&nbsp;<a href=\"https:\/\/github.com\/synbioz\/article-codingame\" target=\"_blank\" rel=\"noreferrer noopener\">d\u00e9pot Github associ\u00e9 \u00e0 l\u2019article<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"analysons-le-problme\">Analysons le probl\u00e8me<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Commen\u00e7ons par \u00e9tudier les entr\u00e9es du probl\u00e8me. On a&nbsp;:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>des lettres en ASCII ainsi que leur \u00e9quivalent en morse,<\/li>\n\n\n\n<li>une liste de mots en ASCII et<\/li>\n\n\n\n<li>une s\u00e9quence de caract\u00e8res morse sans s\u00e9parateurs.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Puisque l\u2019inconnue du probl\u00e8me est en morse autant consid\u00e9rer le dictionnaire comme \u00e9tant lui aussi en morse. Voila un exemple de code permettant de r\u00e9cup\u00e9rer les entr\u00e9es.<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>$ascii_morse_mapping <strong>=<\/strong> {'A'<strong>=&gt;<\/strong>'.-', 'B'<strong>=&gt;<\/strong>'-...', <strong>[.<\/strong>.<strong>.]<\/strong> 'Y'<strong>=&gt;<\/strong>'-.--', 'Z'<strong>=&gt;<\/strong>'--..'} <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>$sequence <strong>=<\/strong> gets<strong>.<\/strong>chomp <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>$dico <strong>=<\/strong> (1<strong>.<\/strong>.gets<strong>.<\/strong>to_i)<strong>.<\/strong>map <strong>do<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <strong>=<\/strong> '' <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>gets<strong>.<\/strong>chomp<strong>.<\/strong>each_char{ <strong>|<\/strong>char<strong>|<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <strong>&lt;&lt;<\/strong> $ascii_morse_mapping<strong>.<\/strong>fetch(char) } <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong><code>end<\/code><\/strong><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">On peut remarquer qu\u2019un mot en morse peut correspondre \u00e0 des mots diff\u00e9rents en ASCII. Par exemple&nbsp;<code>.........-<\/code>&nbsp;peut se traduire par&nbsp;<code>SHIT<\/code>&nbsp;ou bien&nbsp;<code>HIV<\/code>. Ainsi&nbsp;<code>$dico<\/code>&nbsp;est susceptible de contenir des doublons.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">L\u2019objectif est de trouver le nombre de d\u00e9coupages possibles de&nbsp;<code>$sequence<\/code>&nbsp;en mots de&nbsp;<code>$dico<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"rentrons-dans-le-tas\">Rentrons dans le tas&nbsp;!<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Comme je l\u2019avais fait pour la r\u00e9solution du Boggle, je vais d\u2019abord commencer par un algo na\u00eff.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dans les fichiers de test 1 et 2, la s\u00e9quence correspond \u00e0 un seul et unique mot du dictionnaire. En cons\u00e9quence, la solution suivante va fonctionner :<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>$dico<strong>.<\/strong>select{<strong>|<\/strong>word<strong>|<\/strong> word <strong>==<\/strong> sequence}<strong>.<\/strong>size<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">L\u2019exemple n\u00b03 se complique&nbsp;: plusieurs mots forment la s\u00e9quence. On va donc, pour chaque mot, tenter de le faire correspondre avec le d\u00e9but de la s\u00e9quence. S\u2019il correspond, alors on recommencera l\u2019op\u00e9ration avec le reste de la s\u00e9quence. Lorsque la s\u00e9quence est vide, on a une seule interpr\u00e9tation possible.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Cet algorithme se d\u00e9crit tr\u00e8s bien \u00e0 l\u2019aide d\u2019une fonction r\u00e9cursive&nbsp;:<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code><strong>defpossibilities<\/strong>(seq) <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>return<\/strong> 1 <strong>if<\/strong> seq<strong>.<\/strong>size <strong>==<\/strong> 0 <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>$dico<strong>.<\/strong>reduce(0) <strong>do|<\/strong>total, word<strong>|<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>if<\/strong> word <strong>==<\/strong> seq<strong>[<\/strong>0, word<strong>.<\/strong>size<strong>]<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>total <strong>+=<\/strong> possibilities(seq<strong>[<\/strong>word<strong>.<\/strong>size, seq<strong>.<\/strong>size <strong>-<\/strong> word<strong>.<\/strong>size<strong>]<\/strong>) <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>total<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">La fonction&nbsp;<code>possibilities<\/code>&nbsp;donne donc le nombre de combinaisons possibles pour la s\u00e9quence en param\u00e8tre. Lorsque l\u2019on appelle cette fonction avec&nbsp;<code>$sequence<\/code>&nbsp;en param\u00e8tre on a bien le r\u00e9sultat attendu pour les tests 1, 2 et 3. Le test n\u00b04, lui, ne termine pas en en temps acceptable\u2026<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"optimisation\">Optimisation<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Le probl\u00e8me et notre algorithme de r\u00e9solution peuvent \u00eatre vus comment un&nbsp;<a href=\"http:\/\/fr.wikipedia.org\/wiki\/Arbre_enracin%C3%A9\" target=\"_blank\" rel=\"noreferrer noopener\">arbre<\/a>&nbsp;:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Les n\u0153uds de l\u2019arbre contiennent la s\u00e9quence dont on cherche \u00e0 d\u00e9terminer le nombre d\u2019interpr\u00e9tations.<\/li>\n\n\n\n<li>Les branches de l\u2019arbre repr\u00e9sentent la correspondance d\u2019un mot du dictionnaire en t\u00eate de cette s\u00e9quence.<\/li>\n\n\n\n<li>Les feuilles de l\u2019arbre sont des n\u0153uds dont la s\u00e9quence est vide.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La racine de l\u2019arbre contient&nbsp;<code>$sequence<\/code>. La fonction&nbsp;<code>possibilities(seq)<\/code>&nbsp;retourne le nombre de feuilles pour une s\u00e9quence donn\u00e9e. Le nombre de feuilles est calcul\u00e9 r\u00e9cursivement&nbsp;: c\u2019est la somme du nombre de feuilles de chacun des sous-arbres du n\u0153ud.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Voici un exemple de repr\u00e9sentation du probl\u00e8me (en ASCII). Dans l\u2019exemple la s\u00e9quence est&nbsp;<em>ABCD<\/em>&nbsp;et le dictionnaire est :&nbsp;<em>A, AB, B, BC, C, CD<\/em>. Ici la s\u00e9quence est en ASCII plut\u00f4t qu\u2019en morse pour plus de lisibilit\u00e9.<img decoding=\"async\" src=\"https:\/\/synbioz-website-attachments.s3.eu-west-1.amazonaws.com\/articles\/morse_graph.png\" alt=\"Exemple d'arbre\" loading=\"lazy\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Avec cet exemple l\u2019ordre des appels \u00e0 la fonction possibilities est le suivant&nbsp;:<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>possibilities('ABCD') <strong>=&gt;<\/strong> 2 <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('BCD') <strong>=&gt;<\/strong> 1<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('CD') <strong>=&gt;<\/strong> 1<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('D') <strong>=&gt;<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('') <strong>=&gt;<\/strong> 1<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('D') <strong>=&gt;<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('CD') <strong>=&gt;<\/strong> 1<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('D') <strong>=&gt;<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>possibilities('') <strong>=&gt;<\/strong> 1<\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Sur le graphe comme dans les appels, on remarque qu\u2019on a plusieurs portions identiques. Respectivement, il s\u2019agit des sous-arbres&nbsp;<em>CD<\/em>&nbsp;et&nbsp;<em>D<\/em>&nbsp;et des appels \u00e0&nbsp;<code>possibilities<\/code>&nbsp;avec les arguments&nbsp;:&nbsp;<code>'CD'<\/code>,&nbsp;<code>'D'<\/code>&nbsp;ou&nbsp;<code>''<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"memoize\">Memoize<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">La fonction&nbsp;<code>possibilities<\/code>&nbsp;est dite pure. En effet, \u00e0 l\u2019exception de son usage de la variable&nbsp;<code>$dico<\/code>&nbsp;que l\u2019on consid\u00e8re plut\u00f4t comme une constante,&nbsp;<code>possibilities<\/code>&nbsp;ne tient pas compte du contexte d\u2019ex\u00e9cution mais uniquement de ses param\u00e8tres.. Pour les m\u00eames param\u00e8tres, elle retournera toujours le m\u00eame r\u00e9sultat.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Cette propri\u00e9t\u00e9 va nous permettre de conserver en m\u00e9moire les r\u00e9sultats des appels \u00e0 la fonction. De cette mani\u00e8re, on ne calculera pas un sous arbre d\u00e9j\u00e0 calcul\u00e9.<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>$possibilities_memory <strong>=<\/strong> {}<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>defpossibilities<\/strong>(seq)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>return<\/strong> 1 <strong>if<\/strong> seq<strong>.<\/strong>size <strong>==<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>return<\/strong> $possibilities_memory<strong>[<\/strong>seq<strong>]if<\/strong> $possibilities_memory<strong>.<\/strong>has_key?(seq)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <strong>=<\/strong> $dico<strong>.<\/strong>reduce(0) <strong>do|<\/strong>total, word<strong>|<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>if<\/strong> word <strong>==<\/strong> seq<strong>[<\/strong>0, word<strong>.<\/strong>size<strong>]<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>total <strong>+=<\/strong> possibilities(seq<strong>[<\/strong>word<strong>.<\/strong>size, seq<strong>.<\/strong>size <strong>-<\/strong> word<strong>.<\/strong>size<strong>]<\/strong>) <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>total <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>$possibilities_memory<strong>[<\/strong>seq<strong>]=<\/strong> result <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Cette optimisation permet de terminer dans un temps raisonnable l\u2019exemple n\u00b04 (~7 secondes). L\u2019algorithme n\u2019a quasiment pas chang\u00e9&nbsp;!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"dictionnaire\">Dictionnaire<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Pour optimiser \u00e0 nouveau notre programme, regardons d\u2019un peu plus pr\u00e8s son fonctionnement interne. Pour cela, on peut instrumenter le code pour obtenir certaines m\u00e9triques sur les op\u00e9rations les plus courantes. On peut \u00e9galement faire une analyse de complexit\u00e9. Dans cet article je vais utiliser l\u2019instrumentation.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous trouverez sur Github une&nbsp;<a href=\"https:\/\/github.com\/synbioz\/article-codingame\/blob\/ecf61edb39c0a49c9d9644e3835c47a1607017f1\/script.rb\">version instrument\u00e9e<\/a>&nbsp;du code pr\u00e9c\u00e9dent. Voici ce que j\u2019obtiens sur l\u2019exemple n\u00b04&nbsp;:<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>{ :calls <strong>=&gt;<\/strong> 1284, <em># Nombre d'appel \u00e0 la fonction<\/em> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>:nodes <strong>=&gt;<\/strong> 1194, <em># Nombre de sous-arbres parcourus<\/em><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>:cuts <strong>=&gt;<\/strong> 89, <em># Nombre de sous-arbres non recalcul\u00e9s<\/em><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>:match <strong>=&gt;<\/strong> 1283, <em># Nombre de branches cr\u00e9es<\/em><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>:unmatch <strong>=&gt;<\/strong> 11274853 } <em># Nombre de branches non-cr\u00e9es<\/em><\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">On peut voir que notre algorithme calcule assez peu de sous arbres (de l\u2019ordre d\u2019un millier). Par contre il fait beaucoup d\u2019essais pour faire correspondre les mots du dictionnaire au d\u00e9but de la s\u00e9quence (de l\u2019ordre d\u2019une dizaine de millions). Pour chaque n\u0153ud calcul\u00e9 on va tester chaque mot du dictionnaire avec le d\u00e9but de la s\u00e9quence. Il y a 9444 mots dans le dictionnaire, on a donc 9444 * 1194 comparaisons.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour \u00e9viter de parcourir le dictionnaire \u00e0 chaque n\u0153ud, on va prendre l\u2019approche inverse. On va chercher \u00e0 faire correspondre le d\u00e9but de la s\u00e9quence \u00e0 un mot du dictionnaire. Pour cela on va parcourir le d\u00e9but de la s\u00e9quence, et v\u00e9rifier si oui ou non il existe une correspondance dans le dictionnaire.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour limiter le nombre d\u2019appel au dictionnaire on ne s\u2019int\u00e9resse qu\u2019aux s\u00e9quences pouvant effectivement \u00eatre un mot. Cette limite est mise en place en ne prenant que des pr\u00e9fixes de la taille des mots du dictionnaire.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Voici le corps de ce que pourrait \u00eatre notre nouvelle m\u00e9thode&nbsp;<code>possibilities<\/code>.<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>result <strong>=<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>min <strong>=<\/strong> $dico<strong>.<\/strong>min_size<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>max <strong>=[<\/strong>$dico<strong>.<\/strong>max_size, seq<strong>.<\/strong>size<strong>].<\/strong>min<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>for<\/strong> size <strong>in<\/strong> (min<strong>.<\/strong>.max)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>if<\/strong> $dico<strong>.<\/strong>exists?(seq<strong>[<\/strong>0, size<strong>]<\/strong>)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <strong>+=<\/strong> possibilities(seq<strong>[<\/strong>size, seq<strong>.<\/strong>size <strong>-<\/strong> size<strong>]<\/strong>)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result<\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">L\u2019une des premi\u00e8res choses que l\u2019on remarque c\u2019est que&nbsp;<code>$dico<\/code>&nbsp;ne semble plus \u00eatre une simple liste. Comme on l\u2019a vu plus t\u00f4t, plusieurs mots peuvent avoir une m\u00eame repr\u00e9sentation en morse. En plus de savoir si un pr\u00e9fixe de&nbsp;<code>seq<\/code>&nbsp;est dans le dictionnaire, il faut savoir combien de fois il y est. L\u2019algorithme change l\u00e9g\u00e8rement afin de prendre en compte ce d\u00e9tail&nbsp;:<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code>result <strong>=<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>min <strong>=<\/strong> $dico<strong>.<\/strong>min_size<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>max <strong>=[<\/strong>$dico<strong>.<\/strong>max_size, seq<strong>.<\/strong>size<strong>].<\/strong>min<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>for<\/strong> size <strong>in<\/strong> (min<strong>.<\/strong>.max) <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>count <strong>=<\/strong> $dico<strong>.<\/strong>count(seq<strong>[<\/strong>0, size<strong>]<\/strong>)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>if<\/strong> count <strong>&gt;<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result <strong>+=<\/strong> count <strong>*<\/strong> possibilities(seq<strong>[<\/strong>size, seq<strong>.<\/strong>size <strong>-<\/strong> size<strong>]<\/strong>) <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>result<\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Voici maintenant le code du dictionnaire&nbsp;:<\/p>\n\n\n\n<div class=\"wp-block-group is-vertical is-layout-flex wp-container-core-group-is-layout-4fc3f8e1 wp-block-group-is-layout-flex\">\n<p class=\"wp-block-paragraph\"><code><strong>classDictionnary<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>def initialize<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_hash <strong>=<\/strong> {} <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>def push<\/strong>(morse)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_max_size <strong>=nil<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_min_size <strong>=nil<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_hash<strong>[<\/strong>morse<strong>]=<\/strong> count(morse) <strong>+<\/strong> 1<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>def count<\/strong>(morse)<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_hash<strong>[<\/strong>morse<strong>]||<\/strong> 0<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>def max_size<\/strong> <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>@_max_size <strong>||=<\/strong> @_hash<strong>.<\/strong>keys<strong>.<\/strong>max_by(<strong>&amp;<\/strong>:size)<strong>.<\/strong>size <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>def min_size<\/strong> @_min_size <strong>||=<\/strong> @_hash<strong>.<\/strong>keys<strong>.<\/strong>min_by(<strong>&amp;<\/strong>:size)<strong>.<\/strong>size <\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code><strong>end<\/strong><\/code><\/p>\n<\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Cette impl\u00e9mentation permet de r\u00e9soudre le test n\u00b04 instantan\u00e9ment (~20 millisecondes). Voici les r\u00e9sultats donn\u00e9s par le m\u00eame type d\u2019instrumentation que pr\u00e9c\u00e9demment&nbsp;:{ :calls <strong>=&gt;<\/strong> 1284, <em># Nombre d&rsquo;appel \u00e0 la fonction<\/em> :nodes <strong>=&gt;<\/strong> 1224, <em># Nombre de sous-arbres parcourus<\/em> :cuts <strong>=&gt;<\/strong> 59, <em># Nombre de sous-arbres non recalcul\u00e9s<\/em> :match <strong>=&gt;<\/strong> 1283, <em># Nombre de branches cr\u00e9es<\/em> :unmatch <strong>=&gt;<\/strong> 48901 } <em># Nombre de branches non-cr\u00e9es<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Le nombre de recherches dans le dictionnaire qui n\u2019aboutissent pas est beaucoup moins \u00e9lev\u00e9 (il s\u2019agit d\u2019un facteur 1&nbsp;000).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La diff\u00e9rence de sous arbres non recalcul\u00e9 vient probablement de la diff\u00e9rence dans l\u2019ordre de parcours. Cette diff\u00e9rence laisse penser que l\u2019on pourrait ordonner l\u2019exploration pour maximiser le nombre de sous-arbres non explor\u00e9s. Ce sera peut \u00eatre le sujet d\u2019un prochain billet\u2026<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour plus de lisibilit\u00e9, le code est refactor\u00e9 en trois classes&nbsp;:&nbsp;<code>Dictionnary<\/code>,&nbsp;<code>Word<\/code>&nbsp;et&nbsp;<code>Problem<\/code>. Vous pouvez voir l\u2019int\u00e9gralit\u00e9 du&nbsp;<a href=\"https:\/\/github.com\/synbioz\/article-codingame\/blob\/cb92314fa5dd2e025370da60023fc322f303c472\/script.rb\" target=\"_blank\" rel=\"noreferrer noopener\">script r\u00e9sultant<\/a>&nbsp;sur Github.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"mmoire\">M\u00e9moire<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Un derni\u00e8re optimisation (pour aujourd\u2019hui) consiste \u00e0 ne plus utiliser des cha\u00eenes de caract\u00e8res lors des r\u00e9cursions ou lors de la m\u00e9moization. En effet, on pr\u00e9f\u00e9rera utiliser un indice associ\u00e9 \u00e0 une variable d\u2019instance de la classe&nbsp;<code>Problem<\/code>. De cette mani\u00e8re&nbsp;<code>Problem<\/code>&nbsp;reste fonctionnel, dans le sens ou le r\u00e9sultats de ses m\u00e9thodes ne d\u00e9pendent que de lui et de ses propres variables.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Vous pouvez consulter le\u00a0<a href=\"https:\/\/github.com\/synbioz\/article-codingame\/blob\/b9d6c3e7a926de920e923a442d4da45fd35d7f2c\/script.rb\" target=\"_blank\" rel=\"noreferrer noopener\">code associ\u00e9 \u00e0 cette optimisation<\/a>\u00a0sur Github. Cette version inclut l\u2019instrumentation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"#adaptateur-primaire\"><\/a><\/h3>\n","protected":false},"excerpt":{"rendered":"<p>Article \u00e9crit par Nicolas Zermati CodinGame&nbsp;est un site web proposant des challenges de programmation. Ces \u00e9v\u00e8nements ont pour but de mettre en relation entreprises et postulants<span class=\"excerpt-hellip\"> [\u2026]<\/span><\/p>\n","protected":false},"author":10,"featured_media":13276,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","inline_featured_image":false,"fifu_image_url":"","fifu_image_alt":"","footnotes":""},"categories":[34],"tags":[],"class_list":["post-13260","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-articles-techniques"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.9 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Exercice de programmation - Codingame - Ouidou<\/title>\n<meta name=\"description\" content=\"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Exercice de programmation - Codingame - Ouidou\" \/>\n<meta property=\"og:description\" content=\"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?\" \/>\n<meta property=\"og:url\" content=\"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame\" \/>\n<meta property=\"og:site_name\" content=\"Ouidou\" \/>\n<meta property=\"article:published_time\" content=\"2013-05-07T14:50:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-12-01T15:26:05+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1105\" \/>\n\t<meta property=\"og:image:height\" content=\"564\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Sara Lourties\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"Sara Lourties\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame\"},\"author\":{\"name\":\"Sara Lourties\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#\\\/schema\\\/person\\\/e1d66085fb7c22ede319ce56adc373a4\"},\"headline\":\"Exercice de programmation &#8211; Codingame\",\"datePublished\":\"2013-05-07T14:50:00+00:00\",\"dateModified\":\"2025-12-01T15:26:05+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame\"},\"wordCount\":2072,\"publisher\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#organization\"},\"image\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/Exercice-de-programmation-Codingame.png\",\"articleSection\":[\"Articles Techniques\"],\"inLanguage\":\"fr-FR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame\",\"url\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame\",\"name\":\"Exercice de programmation - Codingame - Ouidou\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/Exercice-de-programmation-Codingame.png\",\"datePublished\":\"2013-05-07T14:50:00+00:00\",\"dateModified\":\"2025-12-01T15:26:05+00:00\",\"description\":\"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#primaryimage\",\"url\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/Exercice-de-programmation-Codingame.png\",\"contentUrl\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/Exercice-de-programmation-Codingame.png\",\"width\":1105,\"height\":564,\"caption\":\"Exercice de programmation - Codingame - visuel article technique\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/articles-techniques\\\/exercice-de-programmation-codingame#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Accueil\",\"item\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Exercice de programmation &#8211; Codingame\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/\",\"name\":\"Blog Ouidou\",\"description\":\"Conseil et expertise en technologies\",\"publisher\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#organization\",\"name\":\"Ouidou\",\"url\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/04\\\/image_2022-04-13_150237378.png\",\"contentUrl\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/04\\\/image_2022-04-13_150237378.png\",\"width\":180,\"height\":180,\"caption\":\"Ouidou\"},\"image\":{\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/ouidou.fr\\\/blog\\\/#\\\/schema\\\/person\\\/e1d66085fb7c22ede319ce56adc373a4\",\"name\":\"Sara Lourties\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g\",\"caption\":\"Sara Lourties\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Exercice de programmation - Codingame - Ouidou","description":"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame","og_locale":"fr_FR","og_type":"article","og_title":"Exercice de programmation - Codingame - Ouidou","og_description":"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?","og_url":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame","og_site_name":"Ouidou","article_published_time":"2013-05-07T14:50:00+00:00","article_modified_time":"2025-12-01T15:26:05+00:00","og_image":[{"width":1105,"height":564,"url":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png","type":"image\/png"}],"author":"Sara Lourties","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"Sara Lourties","Dur\u00e9e de lecture estim\u00e9e":"10 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#article","isPartOf":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame"},"author":{"name":"Sara Lourties","@id":"https:\/\/ouidou.fr\/blog\/#\/schema\/person\/e1d66085fb7c22ede319ce56adc373a4"},"headline":"Exercice de programmation &#8211; Codingame","datePublished":"2013-05-07T14:50:00+00:00","dateModified":"2025-12-01T15:26:05+00:00","mainEntityOfPage":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame"},"wordCount":2072,"publisher":{"@id":"https:\/\/ouidou.fr\/blog\/#organization"},"image":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#primaryimage"},"thumbnailUrl":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png","articleSection":["Articles Techniques"],"inLanguage":"fr-FR"},{"@type":"WebPage","@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame","url":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame","name":"Exercice de programmation - Codingame - Ouidou","isPartOf":{"@id":"https:\/\/ouidou.fr\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#primaryimage"},"image":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#primaryimage"},"thumbnailUrl":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png","datePublished":"2013-05-07T14:50:00+00:00","dateModified":"2025-12-01T15:26:05+00:00","description":"Comment r\u00e9soudre un exercice de programmation de CodinGame en d\u00e9codant des s\u00e9quences en Morse ?","breadcrumb":{"@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame"]}]},{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#primaryimage","url":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png","contentUrl":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2013\/05\/Exercice-de-programmation-Codingame.png","width":1105,"height":564,"caption":"Exercice de programmation - Codingame - visuel article technique"},{"@type":"BreadcrumbList","@id":"https:\/\/ouidou.fr\/blog\/articles-techniques\/exercice-de-programmation-codingame#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Accueil","item":"https:\/\/ouidou.fr\/blog\/"},{"@type":"ListItem","position":2,"name":"Exercice de programmation &#8211; Codingame"}]},{"@type":"WebSite","@id":"https:\/\/ouidou.fr\/blog\/#website","url":"https:\/\/ouidou.fr\/blog\/","name":"Blog Ouidou","description":"Conseil et expertise en technologies","publisher":{"@id":"https:\/\/ouidou.fr\/blog\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/ouidou.fr\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"fr-FR"},{"@type":"Organization","@id":"https:\/\/ouidou.fr\/blog\/#organization","name":"Ouidou","url":"https:\/\/ouidou.fr\/blog\/","logo":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/ouidou.fr\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2022\/04\/image_2022-04-13_150237378.png","contentUrl":"https:\/\/ouidou.fr\/blog\/wp-content\/uploads\/2022\/04\/image_2022-04-13_150237378.png","width":180,"height":180,"caption":"Ouidou"},"image":{"@id":"https:\/\/ouidou.fr\/blog\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/ouidou.fr\/blog\/#\/schema\/person\/e1d66085fb7c22ede319ce56adc373a4","name":"Sara Lourties","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/secure.gravatar.com\/avatar\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/b2ef32f9fc1e16168b39587a2ec1dafedc70a9d41fa1b4a930ec7744b3e35ec7?s=96&d=mm&r=g","caption":"Sara Lourties"}}]}},"_links":{"self":[{"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/posts\/13260","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/comments?post=13260"}],"version-history":[{"count":4,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/posts\/13260\/revisions"}],"predecessor-version":[{"id":17950,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/posts\/13260\/revisions\/17950"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/media\/13276"}],"wp:attachment":[{"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/media?parent=13260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/categories?post=13260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ouidou.fr\/blog\/wp-json\/wp\/v2\/tags?post=13260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}