Motifs de déverrouillage

Certains téléphones proposent de déverrouiller l'appareil en dessinant un motif à l'écran. Ce motif est dessiné sur une grille contenant $9$ cellules réparties sur $3$ lignes de $3$. Les cellules sont numérotées de $0$ à $8$ comme sur la figure ci-dessous qui illustre un motif issu de la cellule $0$ et passant par $5$ cellules au total.

Dans cet exercice, on appelle « motif » un chemin passant par au moins deux cellules. Depuis une cellule donnée, les seuls déplacements possibles sont :

passer à une cellule directement adjacente (horizontalement, verticalement ou en diagonale) ;
passer à une cellule située deux lignes et une colonne plus loin ;
passer à une cellule située deux colonnes et une ligne plus loin.

Les figures ci-dessous illustrent les déplacements possibles.

Cellules accessibles depuis $0$Cellules accessibles depuis $1$Cellules accessibles depuis $4$

$Cellules accessibles depuis $0$$

$Cellules accessibles depuis $1$$

$Cellules accessibles depuis $4$$

Un motif peut passer plusieurs fois par une cellule donnée mais pas consécutivement. Ainsi, le motif $5 \longrightarrow 6\longrightarrow 6$ est invalide car il passe deux fois de suite sur la cellule $6$.

Enfin, les déplacements passant par-dessus une cellule, tels que $0 \longrightarrow 2$ ou $0 \longrightarrow 8$, sont interdits.

On représente un motif en machine par un tuple contenant les numéros des cellules traversées. Ces valeurs sont données dans l'ordre du parcours. Ainsi, le motif illustré plus haut est représenté par le tuple (0, 4, 2, 7, 6).

Écrire la fonction motifs qui prend en paramètres les entiers source et longueur désignant respectivement la cellule de départ et la longueur des motifs souhaités. Cette fonction renvoie la liste des motifs issus de la cellule indiquée et de longueur donnée.

On garantit que la valeur de source est un entier entre $0$ et $8$ (inclus) et que la longueur des motifs cherchés est toujours comprise entre $2$ et $6$ (inclus).

Pas d'ordre

La liste de motifs renvoyée n'a pas besoin d'être triée. Les tests comparent les versions triées des listes renvoyées à celles attendues.

Exemples

>>> # motifs issus de 0 et de longueur 2
>>> motifs(0, 2)
[(0, 1), (0, 3), (0, 4), (0, 5), (0, 7)]
>>> # motifs issus de 1 et de longueur 3
>>> motifs(1, 3)
[(1, 0, 1), (1, 0, 3), (1, 0, 4), (1, 0, 5), (1, 0, 7), (1, 2, 1), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 7), (1, 3, 0), (1, 3, 1), (1, 3, 2), (1, 3, 4), (1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 4, 0), (1, 4, 1), (1, 4, 2), (1, 4, 3), (1, 4, 5), (1, 4, 6), (1, 4, 7), (1, 4,
8), (1, 5, 0), (1, 5, 1), (1, 5, 2), (1, 5, 4), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 6, 1), (1, 6, 3), (1, 6, 4), (1, 6, 5), (1, 6, 7), (1, 8, 1), (1, 8, 3), (1, 8, 4), (1, 8, 5), (1, 8, 7)]

Aides

Plusieurs approches sont possibles. L'une d'elles consiste à effectuer le parcours en profondeur d'un graphe, à l'aide d'une pile par exemple. On empile les motifs construits jusqu'à atteindre la longueur souhaitée.

On rappelle qu'il est possible de créer un tuple contenant un unique élément en faisant (element,).

Enfin, si a et b sont deux tuples, leur somme a + b est un nouveau tuple contenant les valeurs de a suivie par celles de b. Par exemple (0, 1) + (5, ) est égal à (0, 1, 5).

Version videVersion à trous

Évaluations restantes : 10/10

.128013sH3_8ufvIy n7GaS1me(P24:twi]D[hE)6Oo;bcdg/0làqAp.r-,}=+k{95Rxé050O0t0z0p0B0S0b0l0N0S0p0b0b0$010z0B0W010406050b0g0s0s0p0Y0k040q0K0S0g120K0m0l020p0s0W0L0l0,0t1c0Y0U0g0t0b050Q191b1d1f170W041D1K051N0Q1N1P1K170O0B0i0`0|0~100F0B0P0F0S1%0F0z15050=0M0S0t1Y0}0 011$1(1*1(0z1:1=1.0z0M0K0O1f1/0Y1L0z0F0`1i0b0W0p0m100w011@1!010h0@0t0m1q0t1.2f2h2m1_2p1=2s0s2u040a0l0v0Y0K0W0K0b0B1l1n0:2d0Y0Y0t0N2P1D2w0m1L0Q2b2#0z29282a0O2y101*0m2r2M1.1V1X0{1^2/0B2;0m251W1.0W2U1L2Z2#36182g1n2`2n2 0Y1c0S150l0r2Y3a16392x3c1_3e3g3i0w3l2h3n2Z2.013s0p3h040l0d3w2!173z3q103C3E0l0x3I3y3a3A3O3i0+3S3K3U3M3B0K3f3D3i0I3Z3o3b1Z3r3(3t3F0n3-3L3:3N3=3*3F0f3_3#3{3%3)3P0*413p433W040r0R483/2{443?0r3k1E3m3!494h4b0r3v4m3x4o4g3d3}3E0r3H4u3J3.3V4z150r3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0r474-4N3;4V0w4e4?4x4^3?0w4l364T4!4*0w4t524Z4a554C584(4O4 4K5d4.5f3~0w4R381Q341D2^2(0O2,3A0N252E0/1W1L330t353m3S055x0:5F4@3N150o0,0V0v0c0G3S0l594h0K150$5V5X2n14040)3Z0l5-5W5e1_0s0B154{385:105)0y5$5`015)0E5H5 5=4I635j1_5)0!5~681065045c5G5 6a6c5M016f5h6i6d60156b4L5/6r6f5n6q6m6k6v5%5;5?044$5_6r5)0C6u525.6w6m6f516A4}5{155}6D6j15624L6E6e6G5^6U3A6C366Q6V6n6G576,3$6.3m6:3A6f6h3x6(6s046N6{716o676B6t6l6;6y786;6`3x6|3$6f4X6J79737b6}6G4,7m7f156M5,5.766?7e6-6X7p6_6#7B7j6G6T706!7o6Z6x6G6 2!717g2!7i43776%7M747h7z156z7L6K7a7O6R6G6I6^436L7#3J6P7%6g7H7=7D7-7u046$7t7q5@7|4h7U3F7`7K7S7!7E7X7A7Z7+7N6/7`6p7*7n7@89646G7l7;877,8k8r157:8n808p7W4h6f7s8u5(7v8p067_8y048m8c8i6Y8x8i828I6F858h8o8e8F7J868J8j758O6@8B7C8+7$8O7R5L8C8$2n7d8!8_7 84048t8/7F8;7V7`8A8R8#8 7I158H937}047w4S8N7P7(8)697~8U7n8W9f8%8Z83948D8a9n6W958q9l048.998~9q7c6G8Q8^8:9y8O929H9O8`8Y6H9A729P9E9e9S949i6O7y9Q9X5|9U9B9s9$8f668}9T9b9=7{9@9x9.6=159M7T8w8,9E7)9;8v9C8E8{7/9,8K7x5-97ad048Ta49r9X6f6+9t8*9Z7.159G9N9}9_9u9{9w9gas9Ka0aiaD90a6awaC9~7kaGaM7rai9(4n9kat049#aKa8ak8=8Van8(9|aLayab158@a2a98laOa+9VaJa/aH9c9Wa)a8aS4va/0#3Z0653430(150:0h9X0A3i9X0m0h150s0K120h1Ca}8*0ube150b0K0g0Y0N0ta=9J3V150S1m0P1Abuai0Ha!7^9*6r0m152U190S0=0zbmbz3$5Z045#a?9/0Cafaa3r150W2q9~bXbZbV9g0Ebpbnb)04bsbubwaG0Hb$9jbL6mb7040A1$1=9~0m0MbB2raib?aB4qb*b,b@9B0Hb-15020P0z0LaP9v8X9BbJ166PaU6;bN04bibkcmbYc8chc7cj01bX0Xbq042L0Wcdclc0cyb(10c30Bbab!3Bca042BcdcOcDcZbHcF0$b/alcAbBbDbF0Yaicw8McVcy71cBbP0gbR0pbT9XcMcO0p0W0W2r0Oc*cKcBc,c!cf8*cT9)cV71c30t0^bxcK9-cUc~ag5 cBbs1b0;c/cHcCbjc-du7GcKbX0Za%9?dk9o9hb%dxdp150h3(dF330K0N0F0?0mb-bc042}dF5P5R5Tai9:aY3dbr0KdC0zaRc|dxdUdzcIdtdQ10d8dg15dadc0mdedJ04cecu3BbhdHdjc=3AbX0%9~5)efaqb^d!d$d(b}dmaTc16;c32U0zbud)c#d11Bd3bSbU4n1D5J5E1M5q0Q5s1D0z5ueV2*2$24262(0p1;eQeT5B1Jd@1_2U0s0e0h0p0(0t0e0F0d151v1x1z1B0lcw1M3n1K0J1n1k0@0B0b1?0g1n2gbvbt0Y0_2r0ld!dXeb0tbu0l2O0.0Yd5cZ0l0b00e90g0k2h0zfyfrfe1?b+1=cN1Qf5040j0S0l1BfF0p0g0~0Bfm2M2Ne)0l2Reu0.0:0Y0l0Y0.0Nbu2N0i1w2r0z0X0lf70lf91*fc0`0B0Z0:0~bt0_fI0lfo2W0B1m0lfV0-fa0?2UfS0h0h2VeEfE0l1=fm1d5xf;fSff2Jfo0:fr0;2d1r0S0.0=0mfF0|0l0i1d0Be(gr5I5y3A1{1)1+1-e.5N040zbj3D5H0QeP3F0pf?0Nf%f1di0_2RbC0mbEfqf,0bfw0be?fbfE0tfM1T5A2_43gU1}1,2v6r2A2r2t152G0q0N0Y13fF0v0k2b1m5H5D8^375Gg*dV04b9bbbddgbgdGbk0e2U0Ndfe4ehb_fib|eda`4ac@g^c_bHd~eA3Ac3hzcKd+5WhCb*gy1mgAc`edera7d^04d$1wd-hPdFg@g_bGedbIdThX3$cYeka#6mcBh{hUc#b.c;i5aE04aph:dRhWd cWhLg#0=0Sd715fMhKcBe9ddhJegcBh?5=eGhK5)ey4ve06rdqdsc{i0doe1hMd{dEeH15iAh^iDdKhKdMdO4caRiMc 5 c3dXh-b:cgcP2JeviVelbWd+i=idbA04d/5S5Uedd?d0d_iQed0Cijiki1hRi/0Kgzg`ixesgZiUiCi?43enep15h/gYhLeud%i_ih9B0!0HhQi.i8jeia15dNc#6Sc.4Sc}dybM15ing%jDcGc#61b dnilcBfnh+jCiWeejpj2hMb{e3eg6ajyh`c^j!jk5YjEcsi#h~b%hxeDeFdFjOip4Yg)5y2#hs5re,1O040DfA1kgjfg0z0!gqf1dB2DbTf%0g0l0Pfv0W0F1?gGgpgG0Bf00z0.0_fgkifkgI0B0tfjge0S0|gIg/ilgN2b1c0z0t0-15090u0R09iF7V0TkPhkkRd5kUkW0u0fk!3Skh0@fS0bfF2LfXf$2R2U33kBf^kI0`dr0gg20NfYkDg82NgE1?f kTfSfF2 f82Q0Bgb1m2s0Bgj6Yh42^gT1+h9gX71hd2C2Ehhhjhl2Hho0Fhq6%k65o38hwiOi}d;jQic967Md?jKil61i!8bjq88il6~byj=a,8Pl)i`a{a^8djGacj58Lcz8:j18Oigl#a3l.9`ava_j^a.l;i-l+a1m6l*a@l-lT9E9Rl~a:8OaXa/a bKjLamcKjHh_l=a-md9DaVm98ijzl+l:mzj^98mhmmcxj9a8l{9El}m3mtj_j#mA9Vm2mam0azmy9am79VmgmOm!6)8zmvl%aQl@j{lUi!mNmVmeaVl!m%mbm)9Fm+7`m5mDmPmCmZm{9 91m~8OmFm`mWl+mk7MmHlWa/mLaVm=n1m(n6m_m?mwiemUnmn57YmRj^m$nqm,m*msnn8GaRl^mJ8*njienpnunc9Vn0n4nOm|mY9Inv6Gn3nVnSn6nanfnHmo80nK90nlnRm@nsn89EnQnZn/90nU9^nEnXn;aVnznNn^a{ne8ingl_94n+a{nMn.nr90n?n{nWaFnDoh04nYogn!6fn$o58Lml3-k35KeRe*5s17eT0;0?0^04.

Évaluations restantes : 10/10

.128013sH3_8ufvIy n7GaS1me(P24:twi]D[hE)6Oo;bcdg/0làqAp.r-,}=+k{95Rxé050O0t0z0p0B0S0b0l0N0S0p0b0b0$010z0B0W010406050b0g0s0s0p0Y0k040q0K0S0g120K0m0l020p0s0W0L0l0,0t1c0Y0U0g0t0b050Q191b1d1f170W041D1K051N0Q1N1P1K170O0B0i0`0|0~100F0B0P0F0S1%0F0z15050=0M0S0t1Y0}0 011$1(1*1(0z1:1=1.0z0M0K0O1f1/0Y1L0z0F0`1i0b0W0p0m100w011@1!010h0@0t0m1q0t1.2f2h2m1_2p1=2s0s2u040a0l0v0Y0K0W0K0b0B1l1n0:2d0Y0Y0t0N2P1D2w0m1L0Q2b2#0z29282a0O2y101*0m2r2M1.1V1X0{1^2/0B2;0m251W1.0W2U1L2Z2#36182g1n2`2n2 0Y1c0S150l0r2Y3a16392x3c1_3e3g3i0w3l2h3n2Z2.013s0p3h040l0d3w2!173z3q103C3E0l0x3I3y3a3A3O3i0+3S3K3U3M3B0K3f3D3i0I3Z3o3b1Z3r3(3t3F0n3-3L3:3N3=3*3F0f3_3#3{3%3)3P0*413p433W040r0R483/2{443?0r3k1E3m3!494h4b0r3v4m3x4o4g3d3}3E0r3H4u3J3.3V4z150r3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0r474-4N3;4V0w4e4?4x4^3?0w4l364T4!4*0w4t524Z4a554C584(4O4 4K5d4.5f3~0w4R381Q341D2^2(0O2,3A0N252E0/1W1L330t353m3S055x0:5F4@3N150o0,0V0v0c0G3S0l594h0K150$5V5X2n14040)3Z0l5-5W5e1_0s0B154{385:105)0y5$5`015)0E5H5 5=4I635j1_5)0!5~681065045c5G5 6a6c5M016f5h6i6d60156b4L5/6r6f5n6q6m6k6v5%5;5?044$5_6r5)0C6u525.6w6m6f516A4}5{155}6D6j15624L6E6e6G5^6U3A6C366Q6V6n6G576,3$6.3m6:3A6f6h3x6(6s046N6{716o676B6t6l6;6y786;6`3x6|3$6f4X6J79737b6}6G4,7m7f156M5,5.766?7e6-6X7p6_6#7B7j6G6T706!7o6Z6x6G6 2!717g2!7i43776%7M747h7z156z7L6K7a7O6R6G6I6^436L7#3J6P7%6g7H7=7D7-7u046$7t7q5@7|4h7U3F7`7K7S7!7E7X7A7Z7+7N6/7`6p7*7n7@89646G7l7;877,8k8r157:8n808p7W4h6f7s8u5(7v8p067_8y048m8c8i6Y8x8i828I6F858h8o8e8F7J868J8j758O6@8B7C8+7$8O7R5L8C8$2n7d8!8_7 84048t8/7F8;7V7`8A8R8#8 7I158H937}047w4S8N7P7(8)697~8U7n8W9f8%8Z83948D8a9n6W958q9l048.998~9q7c6G8Q8^8:9y8O929H9O8`8Y6H9A729P9E9e9S949i6O7y9Q9X5|9U9B9s9$8f668}9T9b9=7{9@9x9.6=159M7T8w8,9E7)9;8v9C8E8{7/9,8K7x5-97ad048Ta49r9X6f6+9t8*9Z7.159G9N9}9_9u9{9w9gas9Ka0aiaD90a6awaC9~7kaGaM7rai9(4n9kat049#aKa8ak8=8Van8(9|aLayab158@a2a98laOa+9VaJa/aH9c9Wa)a8aS4va/0#3Z0653430(150:0h9X0A3i9X0m0h150s0K120h1Ca}8*0ube150b0K0g0Y0N0ta=9J3V150S1m0P1Abuai0Ha!7^9*6r0m152U190S0=0zbmbz3$5Z045#a?9/0Cafaa3r150W2q9~bXbZbV9g0Ebpbnb)04bsbubwaG0Hb$9jbL6mb7040A1$1=9~0m0MbB2raib?aB4qb*b,b@9B0Hb-15020P0z0LaP9v8X9BbJ166PaU6;bN04bibkcmbYc8chc7cj01bX0Xbq042L0Wcdclc0cyb(10c30Bbab!3Bca042BcdcOcDcZbHcF0$b/alcAbBbDbF0Yaicw8McVcy71cBbP0gbR0pbT9XcMcO0p0W0W2r0Oc*cKcBc,c!cf8*cT9)cV71c30t0^bxcK9-cUc~ag5 cBbs1b0;c/cHcCbjc-du7GcKbX0Za%9?dk9o9hb%dxdp150h3(dF330K0N0F0?0mb-bc042}dF5P5R5Tai9:aY3dbr0KdC0zaRc|dxdUdzcIdtdQ10d8dg15dadc0mdedJ04cecu3BbhdHdjc=3AbX0%9~5)efaqb^d!d$d(b}dmaTc16;c32U0zbud)c#d11Bd3bSbU4n1D5J5E1M5q0Q5s1D0z5ueV2*2$24262(0p1;eQeT5B1Jd@1_2U0s0e0h0p0(0t0e0F0d151v1x1z1B0lcw1M3n1K0J1n1k0@0B0b1?0g1n2gbvbt0Y0_2r0ld!dXeb0tbu0l2O0.0Yd5cZ0l0b00e90g0k2h0zfyfrfe1?b+1=cN1Qf5040j0S0l1BfF0p0g0~0Bfm2M2Ne)0l2Reu0.0:0Y0l0Y0.0Nbu2N0i1w2r0z0X0lf70lf91*fc0`0B0Z0:0~bt0_fI0lfo2W0B1m0lfV0-fa0?2UfS0h0h2VeEfE0l1=fm1d5xf;fSff2Jfo0:fr0;2d1r0S0.0=0mfF0|0l0i1d0Be(gr5I5y3A1{1)1+1-e.5N040zbj3D5H0QeP3F0pf?0Nf%f1di0_2RbC0mbEfqf,0bfw0be?fbfE0tfM1T5A2_43gU1}1,2v6r2A2r2t152G0q0N0Y13fF0v0k2b1m5H5D8^375Gg*dV04b9bbbddgbgdGbk0e2U0Ndfe4ehb_fib|eda`4ac@g^c_bHd~eA3Ac3hzcKd+5WhCb*gy1mgAc`edera7d^04d$1wd-hPdFg@g_bGedbIdThX3$cYeka#6mcBh{hUc#b.c;i5aE04aph:dRhWd cWhLg#0=0Sd715fMhKcBe9ddhJegcBh?5=eGhK5)ey4ve06rdqdsc{i0doe1hMd{dEeH15iAh^iDdKhKdMdO4caRiMc 5 c3dXh-b:cgcP2JeviVelbWd+i=idbA04d/5S5Uedd?d0d_iQed0Cijiki1hRi/0Kgzg`ixesgZiUiCi?43enep15h/gYhLeud%i_ih9B0!0HhQi.i8jeia15dNc#6Sc.4Sc}dybM15ing%jDcGc#61b dnilcBfnh+jCiWeejpj2hMb{e3eg6ajyh`c^j!jk5YjEcsi#h~b%hxeDeFdFjOip4Yg)5y2#hs5re,1O040DfA1kgjfg0z0!gqf1dB2DbTf%0g0l0Pfv0W0F1?gGgpgG0Bf00z0.0_fgkifkgI0B0tfjge0S0|gIg/ilgN2b1c0z0t0-15090u0R09iF7V0TkPhkkRd5kUkW0u0fk!3Skh0@fS0bfF2LfXf$2R2U33kBf^kI0`dr0gg20NfYkDg82NgE1?f kTfSfF2 f82Q0Bgb1m2s0Bgj6Yh42^gT1+h9gX71hd2C2Ehhhjhl2Hho0Fhq6%k65o38hwiOi}d;jQic967Md?jKil61i!8bjq88il6~byj=a,8Pl)i`a{a^8djGacj58Lcz8:j18Oigl#a3l.9`ava_j^a.l;i-l+a1m6l*a@l-lT9E9Rl~a:8OaXa/a bKjLamcKjHh_l=a-md9DaVm98ijzl+l:mzj^98mhmmcxj9a8l{9El}m3mtj_j#mA9Vm2mam0azmy9am79VmgmOm!6)8zmvl%aQl@j{lUi!mNmVmeaVl!m%mbm)9Fm+7`m5mDmPmCmZm{9 91m~8OmFm`mWl+mk7MmHlWa/mLaVm=n1m(n6m_m?mwiemUnmn57YmRj^m$nqm,m*msnn8GaRl^mJ8*njienpnunc9Vn0n4nOm|mY9Inv6Gn3nVnSn6nanfnHmo80nK90nlnRm@nsn89EnQnZn/90nU9^nEnXn;aVnznNn^a{ne8ingl_94n+a{nMn.nr90n?n{nWaFnDoh04nYogn!6fn$o58Lml3-k35KeRe*5s17eT0;0?0^04.