Nombre de chaînes

On a codé une chaîne de caractères en adoptant la transformation suivante :

Caractère "A" "B" "C" ... "Z"
Code "1" "2" "3" ... "26"

Ainsi, la chaîne "ABC" est devenue "123".

Cette méthode de chiffrement très rudimentaire présente plusieurs défauts. L'un d'entre eux est qu'elle n'est pas « injective » : plusieurs chaînes de départ peuvent donner le même code d'arrivée. En effet, le code "123" peut être déchiffré de plusieurs façons :

  • "1" + "2" + "3" qui donne "ABC" ;
  • "12" "3" qui donne "LC" ;
  • "1" + "23" qui donne "AW".

Le code "123" peut donc être déchiffré de 3 façons différentes.

Écrire en python la fonction nb_chaines qui prend en paramètres une chaîne de caractères non vide code uniquement composée de chiffres ("0", "1", ..., "9") et renvoie le nombre de façons dont cette chaîne peut être déchiffrée.

On garantit que le code passé en paramètre correspond toujours à au moins une chaîne de caractères. On précise de plus que les chaînes "0", "01", "02", ..., "09" ne correspondent à aucun caractère (en effet "01" est différent de "1").

Exemples
>>> nb_chaines("5")  # "E"
1
>>> nb_chaines("11")  # "AA" ou "K"
2
>>> nb_chaines("123")  # "ABC" ou "LC" ou "AW" 
3
>>> nb_chaines("11111111")  # "AAAAAAAA" ou "AAAAAAK" ou ...
34
>>> nb_chaines("10101010")  # "JJJJ"
1
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013s3_8èufv»Iy 7nGaêS1me(P4C2:Kjtw«i]Dç[hE)6Oo;bcdUgM/0lîàqABp!.rL-,}=+Nk%{95Rxé050V0v0E0q0H0#0b0m0U0#0q0b0b0?010E0H0+010406050b0g0u0u0q0.0l040s0R0#0g1h0R0o0m020q0u0+0S0m0~0v1r0.0(0g0v0b050Z1o1q1s1u1m0+041S1Z051$0Z1$1(1Z1m0V0H0i191b1d1f0M0H0X0M0#1_0M0E1k05140T0#0v1;1c1e011^1`1|1`0E2224200E0T0R0V1u210.1!0E0M191x0b0+0q0o1f0A01261?010h160v0o1F0v202u2w2B282E242H0u2J040a0m0x0.0R0+0R0b0H1A1C122s0.0.0v0U2(1S2L0o1!0Z2q2@0E2o2n2p0V2N1f1|0o2G2#201.1:1a27310H330o2k1/200+2-1!2=2@3l1n2v1C392C3e0.1r0#1k0m0t2;3p1l3o2M3r283t3v3x0A3A2w3C2=30013H0q3w040m0c3L2?1m3O3F1f3R3T0m0y3X3N3p3P3%3x0}3+3Z3-3#3Q0R3u3S3x0P3=3D3q1=3G3`3I3U0n3 3!423$443|3U0e483@4a3_3{3(0|4g3E4i3/040t0!4n413a4j450t3z1T3B3?4o4w4q0t3K4B3M4D4v3s4c3T0t3W4J3Y403.4O1k0t3*4S3,4E4N4k4X3;4!1#3j1S372`0V2~3P0U2k2T111/1!3i0v3k3B3+054@124 4$280_1k120h51494w0F3x5c4h4F0h1k0o0T0d0U0M15331R4+5d2C1j040w5h563$1k530v5A4M285x0O0B3=0m5N0m4U3^0o1k2S0u0R3+5P5v280R1k0?5X5Q4i5x0L5G3P0u0H1k4t4!5Y5i2C58040h3`5(5Z5C040d5~5^5!5f043c635B3Q0T1k0.2w0X5F5u641f5x5z6i6a5m1k2Q5-3^6l6s4p5D4^6v4w5J695H1f5#040@6C5.5:4r6z5w1k0O0I5M5O5)4F5T1L5W6n6D015+6M3G6c046r6Y3P6u6+5R6x126$6k6O6Q5?6T2C6F5%6_5 015/4X6R5N6`571k0H5b6~6j3Q6:6h3n6 6#6.4p6(6*7f7b6-7m6o7d6=6!6O6I3^6F0:7v4i716L7i6A1k6^3l5@6a6F0,6}7H751f0b2z04010!017s5x5L4!065O7#7I6Z5S045U6X7p6Z7h7-3.7k2G7W1k6m7:6/045E7@040O7z4w7x812C7B4A7`5*7F845!5$8b1f86737%3P5`5|0.8e7c678n0R66687a6o6(6e0o6g7~7_506 6p6)7?7D6N5y7s7)7}8H5I7u8u6Z838Q6J1k4I887E040;8q1k7y8N8f6K878C7n1k8!8T7w8$7s8g8(7t7 7Y3l7!7$748D1k0E0R140#8#047M3B8i3^7B5=8|8~8 7b5`788n8L6y8^7/8,7q8p9n8a8:4i7K983M9a4i7Q1k7T7V9s048{4C9f7$7O8o9294960@9x2?9z6U7*6W7~5,8^7)0H9P8n8@8X8I7G9I9J6S907|0R0g0+24969R3U9L9l6;9F9Y9)3G777~9+9y9L6F6H9u9U8Ma06?049 9p7(a2a96{1ka87N6 9(ag6,9t9e9-9g6a9i79an7b8E3c0E8A8K6x9=9@9F80aj8c04020#0E0S9%6K0A479F9H4Kau8~9{91933S9P9_9T3s6V5V9XaF9raz7JalaS8Va38h7#a#9Va.9~a:9#9Fa49Sa68daL609Na(7Z8}av6Z5`2-0E0g0.0o9ka-7,aq6t1kaf3M9L9ca`7Z1S5E2@4}2@4/1S0E4;bE2|2^2j2l2`0q234~4.4{1Y556Z2-0u0d0h0q0_0v0d0M0c1k1K1M1O1Q0maX2?1#3C1Z0z0v1b0m0+0v1z0m1o0.4}0o0V2-0m1r0H180U130m0v0 0v0.0U0Hc9b~256e0u0f330m0%2s1G0Ece0m24c80M1L3c180b102v8x0E0m120g0 b~0R1q13180V2w180g1C0X6e0+cy0m3`0H2G0E100-b;bS0z1B2$0V102Y0o182Gcb0h0hca242s2*524^3P2a1{1}1 bT3P9B7S0A4zaU9E3n0Zbz0-0mb@c}25b{b}0r2{25c/5p780h0.10cH25c 2*3^d22c1~2K7b7B4*debz0mbY0Kc-b.c*050g0#3C1|1!5Ed11}dDd59Ld8012z9$b801d%0tdd99b66G8nd-d/a56 a7d?7Rd(d^b5d`a@d+d%0nd 2@dK2!bj5PdXdBdZd4dF6ad%0*0)0)0*0pe6by4^04aR0ZdV1mdVdz25ed2befd63^d%d)d+d{e3d}4ze6a+aMamd:6 eEeLd;eOd_7be4eodfeqb`9;0.ebd0ezd32deg6Zei0CemeYbzeseu05ewec4idCeBd$d}eFa=8Re2f2d7eJeSe1d=eI9C4Hf87beHf5eDd}e551eZ54e#eaexdYeAe,eC9Ad}ej0/enfle?1Se^e`e)e|eefte 9Cdafea?fafhfvfcfMf3fOePeWf0fS3PfgfVehfje=e!e9e%fqe*d!e-f69C0Welfz4+fm4~e@0HdUf|f,fGfsdEfu4weEd.d*fPg4eJf1f#fTeUe0fW9Cfkf^e8e$e(dAg0e+g2fJ7S0Wfyf(54c)etf|1m0ZdSb=04b@cPdtc:c$b-dMdOdm0ic$0mdoc4aCce3i10c%b-4@cNdxcxczc=0m3S1b0ocG0V0gcLcNcGf 4we}fIeQf0dbgidJe!0qg/0bcM2Sg=e{g@fHgqg`9Cgv4~cHcRcv25cV0qcXey0H0:121d9;0bgx1,1%1!0q3P0Xd!2j0 2AcQ140:0E0lb{1f0H1r6ghC0qhE0F0H0V2q1fh092hNhEcyd4hU1z5#0m0M2-0h1@2e0+0b0B0Zf_0 0-8l6g0-hjh.0-0vg.0UhO0H1Bh@0.0Z2Edsce0b0Zcccecgc9ia5m0d125E1)0l2qc-0Z0ihRb#0~0N0Y0Zhihk0-0b0i0XhX0qhn1Q0U0:2!2$2(1f2j2ecM20hK0Xg)aP1f0pcWcy2A3^hV1xd419gJ0.2A0bcfh,0Eh.h:h=h@3`h_h{hrh~0gi02(i4i6ch1^i9ibcdcfch1Q0Zihij4^ilinc=ipir0ditivixcyiziB2AhQhS0M1f0}0!0`200Z0qbAgD0Jhfcijl0v0;195qb,g:h4g)foe%gW0Hb,2e25b_h20g0b0:5p0q0$co4@2,1Q2!c22wcGh0dk0m2-0b14g,cp0mgTc0dvct0.dh0k0#cbj?g)jX2$e#1d0HbOcH00270Rcgcuj!jKh2g;j_0#003c1.cig.b`bVc#e%i06e2/0fc4j=j@g-hfb_j!j$253c2%0H3S250BhgjLca2*c/cEcG1Qj.hpcgdwcqknkpj7gmeygof.g3a,a;bp9vb7ac706K9d50f_8ZkQkkjM0Vkd2,1/1025k$koc2k)g?2Cg^h9aAaik@6|8?6KdIk;82k?lm3s7=bl9F8Bbt9/ablp8O7 fAeqhsgD0/3`0bjKkn1Bk3cGiK0gdwb 0mcTkRcG16lLk82$kb2*2v1dcucqlSk ca0i0Rc73cb~0HdP1)3CgCevf|c|4}5/kh1s0qkzc42*jVhqjZ5qkIlW1.c_gIj^c~h6lch8d#ha7S7UlBfnf{f}049;l:kQ4@aH258l0udwhodxcJktczi919l m1b-0w0bkok2ccc7ct0OlWlSdX0i3Sir0m0wc$c4lb28ldmigg7S4shc3Ucam$1@mhf/fifK0Pm-0Ogxe^gBdTbS0Q1Chwdr1^c_dv2+2-2/1LgPc|dXk7lJn20m2{9;0idwmTcy5/1C2S2Hmdh1h3m/mfm%m=k.a1k:lvfflonD6abvgjg nuklm:29nza}b2lhnFb:8DlraE9Z7raJmm4~lD1mh)lEhwh21y2(kt2Z2#l5b`1smu0.cGkGm7conNm(m?6w9:9}g~fnm3hw2E1CgO0.18c|c/0T1zdh0)jI0qjKgWhj25lK0bdq1L2w2*mLlVkXlXkaodeyc-hRgIe%ndmH0EkAjUg/cqc9lUl9cimrcwmBcKkxm0oIj=cvjXj_kV0He%dAcak(cigZ2SlR3q4^dh0sl;9;0HjHlK4@c=hRoJ0m1OmMcb0 mP25hVj-o/jIg%c52Gp8o)oOkql6cvl8phl:binm1C8xiS9?o!0#l-1C0wmrcIcKpq18psocpvmslKhw1yoTjIdtj=m{dQ1Zn1n/0U0f2*5rk70DjXp1l7o+dynxm;g1m)9qnRly6EnTnA8)5;n#3U1Ol;oxc91yl;ksl|kvmGkyoXdqg/5En%05n)bSk10mom2%k5k9oylZdl2Y0U1012o(mw0qdNpp100Ubj2$gOcbcU1scQj^2{m0or18dv1oaPhO18kek!qMmCp$cPgYoHoJcP100DcqgW0g1.10187Yht37frgpp+6Z2Ppd2S1k0)0+3ikfcYdvqvob1/25qEmV16g+lMeaoSqR51bB403m50bz9L5`5a7s665P9Z5k04ihj!3c1QnXk@9|7ep.8_8/g8k/p-nGfT9_buk_7~rygc3.bn7sli8^0_0U1k0^1BrvrCar8`8hrf77ayrJ7{7+8q8s5trz57rQ04rS337~b/1l9Ja}r(eGp:eMadbsnUnE048%k@apeVaw1k8lbm61r)77lsr,3$8w6frUs06a7orw8E7lrwsmrV7{lxss89lAr{fUs66Zs5sk7.6@a{9.lfa~bosv8Yr p;6b6q8Gk@srsDrKo2sjsO5Jb49`f9a*rF727Za|6 axsar`sSbrb1bwsf016|s%f9s3rwsCsY1kr?bd9K9/ba95sys`dGrGs*9frZ67r#sAsVsusUbqaes=b3967Ld|9CmlaWsGa!t4a%t6s@a7t89qro5qrqr+sq7^a:tis 8ZsarBgffNges#t9s)s:tMd+7)s/tHsxatautd9jtXlgr$k=aNaP0StB7(nWlttJ9mtVaKtz8=d+7B8Wt!t1aZt3sImu9?sXr}s^r|a}tK9L9osLrAs?t,lnsztPahsWa/nYnCumfZf4uj858*uiaYu3sHs7te9k6(aCrssnaGu77~t{uvaMaOaQa^04aUr=tuuAa}t5a)satD5rrrt@uqud7g8.tNg7uNp=uSrHs.9Wn!tbtvsItZuglzsNnQuyus8;97sauYu_u9bg13bjseu/8ou|tjswu 9/tOtLs!gAre1)4-0Z4/n01C3ej~hwb,jHqCc813ct0moa2$lKq|qwq jHb_0Gc5105Vo%250jlWkK1hmWcCp6gO0Ug#k*q,k-d;s|u}u:8+btk|dh0N1C0vc_13vLhwmV24fpp(nOp*o04wnIo4hddmcG2-gVoqg,cucT25v|b|e%v|mXo*0okLvXcuvMvOvQc4vTcqn~nPaotaw51l1L0+0r5pce15g-dqmP3c0X1PoFb-wgqw0m0odSoSc/qYmG0#qv0#l5qSi(0#oSkCp8oM3Sw!cedhdjq_230fo.cooqk8dl1cheg(knh{qlcY2%c:i1qykxjHcEn^p8c|2f0vj/ksoeb}k$o73cjHki1PvEkNea0o00ox2-0oo|2{n=cai0wZdSn=p1wecjdSmwl-hrdQqahupRw7qgk7my5V0.c7wpwPxsobv$5EqWwXq!q$18mZ1C9?qrp8chl;wqxVl-wth(lGdxcvo71B2/i23q25p_x j;2G2 dv1z16c7bNc|pux$l1hVoYh{b^cS1h1|0bpeb-2!n_y3w%x(j`12g,jR1P0bmRq)3Cq+f-e~6 q:2R2Tq@q_wFj;quvJqyr115w)p8lQoSx(r94-de3nre9/vftSfNt;rW0{7sd%eou+9GuRv.vg8YrItgm@mky^8-y`t~wzt!0=3=4L8j59v@ri5grl5l5nrp5suHv,8ou*z45KrYs,r!satKu98r5l93sc67vcz0o1y-uet0uVuXtx9^uRk`uzu`uCt)s@ruups4z7zn5xs!zx1ktpe3d.04000!00uUv7r^6 0Uz)03dk0L0t0B0IlW100X3Sj_nekFqkmEkwqU2-uVs+sIv6t|v4t*rnzjtEzlu(rtnZtVvitT7CtVz{uM9y0mt2z:9hzutXt?tVluy}k/zpsl8PAd020XuQz6tUvdzy04otuEsdaDAkuIuo9~r?s(u;b3Atv2t-uPt:uR0A3~ttz/aZ9Lz=1kz@5E0L0Az{z}z k2oMd0yrx0b-pzmDl}x$oVmItGzPuWtw9Osy9Qu!Ahu$BcAElzADsOzUb08^t r=0IA(3UAvAx9qzGy_Ao9qAGsE04z!d;y:7{Ac9,bezc04bhvbu?a Ant^o3t!vmep544,bPvrbRq92obSv=o8jHowk4h0qhiJlYoAy80ovFwpkdq^x30vdh0/0010w#nrwIj;6fv%yJg_sIvkB#hdksxfj/www1BqrLnJfnw9qIgJkQ3e0u0Tm2oBmAma0hmc0E18lI00lKxSquxXc4c@ycyqxdqTq3qVx~dXm3pklav n sOw4k{dKp#oPp%fFh7Cnv0Cqhd0w3c1ajXm{0m0)v!p9oqdSq2oWo CJb|g-qu4^e%ccoWnbj^Cmq-w2uwAOv/dKkHco0Vy1Cck,yKu{u@BWBtzXBnadBJs$y{p@C325CwCyr0txCVn|b-ox3Sx}Dev)y,Dtt!BEt=sQzDDx8_Bpuct_t!Bxz#s2DBtnC;04q8yIDqCe6ayM2I1k2V0s0UxX0+cG0xim0M1By%bPy)rdeqtdrh8^rj8Krmu#tFzmDYBrt`u2uBunDXy.rDAT8FEozH8Ju)D$zYAIBOu9tYDSzEukBLvhljp?d+8k5}Af62eG8sEoEBsh8ysXEuD!9/Ety_6PzsDsBVDTEI04zODYzZzMANAqvdA@04z@0tj:0qC}oGCTCzCa8y0mE,r@EmBQzSvd7)ERd;AKAMs@s~Eur?BP3^E?z@6gj?y3cHq6A7pik%C+3yzJztuDAfBGrWDU8UE;EyBItoEGw3DwtLElt%DRE(FFFC9buxD,AdBiE:y|F4FNAyFyzTuFg,EhCoAYDuzWEJtVDzs1tREBAmE)DvDiE-7FD(Fbt/FIDhuSA/ArA9tcFOsKF|tlF`FEGaF;tQG128s~t2tds9AfvkzxEQErpqEVy_EXApu0FFy A)9UEZzqFMu4zRtfGAAFExGaFRo1Cgy_GffTz%s@d%tsG5A;zQunBCz4GM9UGOz4GQut6GGh60G!AHGbAlursO8SF.GdvlFwF#F7EEG24s96A+G-sPzCAVACBXGtG#tmAdv+GIGiFTF:u.G nBFAtkG$uhA%H2G0A-G4u15XAwG7E%G9tLHonBG(G:G*v3FWzTCpF-AXGov*A-v1FZv86dvabkBUHAEuHC60Fas{D+Hibxk|B%bCB*vr13yX0b04.
Aide

On peut résoudre le problème initial en parcourant le code au fur et à mesure. À chaque étape on fait une ou deux hypothèses (le chiffre à l'indice i est un code et/ou le couple des deux chiffres aux indices i et i + 1 est un code).

Si l'on est en train de décoder le chiffre à l'indice i on peut se demander :

  • est-ce que ce chiffre est égal à "0" ? Tous les codes débutant par "0" ("0", "01", ..., "09") sont invalides. Dans ce cas, le décodage étudié est incorrect ;
  • s'il est différent "0", on peut :
    • passer au chiffre suivant d'indice i + 1;
    • se demander si le couple des deux chiffres aux indices i et i + 1 est valide (de "10" à "26"). Dans ce cas, on peut aussi sauter un chiffre et passer à celui d'indice i + 2.

Si en effectuant ce parcours, on parvient à lire le code en entier (jusqu'à l'indice i == len(code)) alors ce décodage est valide.

On a ici décrit une approche récursive explorant les différents décodages jusqu'au cas de base que représente la fin du code. Il est aussi possible de procéder de façon itérative en « remontant » le code. On est alors certain de ne rencontrer que des décodages « valides ».


On notera enfin que différentes hypothèses (étude du chiffre à l'indice i ou du couple code[i] + code[i + 1]) peuvent amener à l'étude de la même situation. Par exemple lors de l'étude du code "123", étudier "1" puis "2" ou étudier en une fois "12" amène dans les deux cas à étudier le chiffre "3".

Les sous-problèmes sont donc interdépendants. Afin d'éviter de répéter certains calculs (« combien de chaînes peuvent être décodées à partir du caractère d'indice i=2 ?»), on pourra conserver les résultats intermédiaires.