Aller au contenu

Paver un rectangle avec des monominos

Définitions

On considère une grille rectangulaire à côtés entiers et parallèles aux axes.

On peut la paver avec de petits carrés de côtés 1, qu'on appelle monomino. (Un domino est lui constitué de deux monominos). Un tel pavage est complètement élémentaire !

Un monomino sera codé par le tuple de ses coordonnées (i, j) où

  • i sera l'indice de la ligne (on débute à zéro)
  • j sera l'indice de la colonne (on débute à zéro)

Paver signifie qu'on veut remplir toute la grille, sans découpe ni chevauchement.

Exercice 1

Coder une fonction pavage qui prend en paramètres n et m deux entiers positifs, et qui renvoie une liste de monominos qui pavent une grille rectangulaire de n lignes et m colonnes.

Pour cet exercice, peu importe l'ordre des monominos. Toute solution sera acceptée.

⚠ Si le pavage est impossible, la fonction doit renvoyer None.

Une fonction dessine est disponible pour afficher votre pavage. Elle prend en paramètres n puis m puis la liste des monominos à afficher. Vous pourrez donc tester dessine(13, 15, pavage(13, 15)), par exemple !

###(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 : ∞/∞
.128013],5/f.q7rnb o=ylaepcwgu)vd4613k×RmhtsP(S2[ji:050A0s0K0r0S0q0L0m0u0q0r0L0L0o010K0S0t010406050L0x0I0I0r0j0p040O0n0q0x0.0n0k050e0^0`0|0~0?0t04051e171h0e1e0?0A0S0z0$0(0*0,0J0S0w0J0q1v0J0K0;050X0l0q0s1q0)0+011u1w1y1w0K1E1G1C0K0j1f0K0J1I1s010f0Z0s0k0r0I0s010$110L0t0r0k0,0P1C1:1=1Z1K1$1G1)1+0;0a0m0M0j0n0t0n0L0S140k0m0V1.0j0j0s0u2c171`0k1f0e1X2p1U1W1V1D0A1|0,1y0k1(291C1n1p0%1J2z0S2B0k0n2F1C0t2i1f2n2p2T0@1;2d2H1!2M0j0{0q0;0D2m2X0=2W1{2Z1K2#2%0;0P2+1=2-2n2y012=0r2(040E2_2o0?2|2:0,2 310B342{2X2}3a0;0d3d363f382~0n2$300;0C3k2.2Y1r2;3p2?040i3d1i2R172F2s0A1W2x3n0u2N1,1f3H1g3F2V182,053N0V2S3m3x0,0F0;0V0f3D373$010v0;0m3,3#2I2~0f0;1;0z0r0w0s3?2/3.0:040N413w3^0k0;163V2`3v2}440c3d3=3-490;0I474g0;0y0T3k0m4v4k3@1!0L1^04010H1(0z0n0S1H0x2B0m1y0L0K1H2f0I150n0I2K290m0h0x0S0m3|1(0K0m4K0m2i2k1=0w1G0m0k0G0I014u4w4f3n4a044S2M4V2M0L4j4|3.0n0;0o554l1!440Q0b4`4v563^3(040f3p5b4y2;0;0S5p423^0n3:042K5u482!0l0;0j4/404d2o5j5d0;465J3!5v2!4b4p3n444s5h4w5i5c1K5l5n0j5B3g0;0R5*3n5x5s4c2T4x5R2;5E045G0k3 5U435N5 4m4 625M045X5P065Z6b4{5#394n4T5229651K58040g6k6f040r0t0t1(0A6p01440N5O2V6e2~5s6x4h5.3.4~5-5P5L1K5W0y5Y6N3%5F0W0x0j5=2,5@5C5r4 6h4W5469173Y0s2p2Q6.3G1o3I2s2v2q0r1F6;0e3H0?6~0W0Y0!04. 




Exercice 2


Coder une fonction est_pavage qui renvoie un booléen, True si le pavage est valide, False sinon. La fonction prend en paramètres :


    

  • n : le nombre de lignes du rectangle
    • 

  • m : le nombre de colonnes du rectangle
    • 

  • monominos : une liste de monominos. Un monomino est donné avec un tuple, (i, j) :
      

    • i désigne sa ligne
      • 

    • j désigne sa colonne
      • 

    

    • 



Un pavage est valide,


    

  • s'il couvre tout le rectangle,
    • 

  • s'il n'y a pas deux monominos posés au même endroit.
    • 





###(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 : ∞/∞



.128013/.Tr;nbylaeu)*dV63m?(P02-],59f!78 _o=pcwgv4F1kIéhtsSàLj[i:050p0l0Y0k0)0j0Z0I0N0j0k0Z0Z0L010Y0)0M010406050Z0m0t0t0k0e0i040!0K0j0m0~0K0g050b1517191b130M04051r1k1u0b1r130p0)0Q0?0^0`0|0X0)0P0X0j1I0X0Y11050.0h0j0l1D0_0{011H1J1L1J0Y1R1T1P0Y0e1s0Y0X1V1F010E0:0l0g0k0t0l010?1e0Z0M0k0g0|0y1P20221:1X1?1T1_1{110a0I0w0e0K0M0K0Z0)1h0g0I0,1~0e0e0l0N2p1k270g1s0b1.2C1+1-1,1Q0p290|1L0g1^2m1P1A1C0@1W2M0)2O0g0K2S1P0M2v1s2A2C2*14212q2U1;2Z0e180j110I0T2z2.122-282:1X2=2@2_0y2|222~2A2L01330k2^040I0s372B133a310|3d3f0I0R3j392.3b3p2_0C3t3l3v3n3c0K2?3e2_0r3A2 2/1E323F343g0G3K3m3N3o3P3H3g0H3T3C3V3E3G3q0D3#303%3x040T0x3,3M2V3(3Q0T2{1l2}3B3-3^3/0T363}383 3@2;3X3f0T3i453k3L3w4a110T3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0T3+4K4o3O4w0y3=4Q484S3Q0y3|2*4u4B4H0y444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0y4s4_4R3W4T4y4 4X514Z4D544v4Z4J2,1x2(1k2S2F0p1-2K3D0N2!1|1s5h1t5f5d2,5n0,2)4`1X0U110,0E3t4-3^0O2_5F4=320E110l0Z0Y0J210Q0k0P0l5K5z0|10040v5Y503c111j4m5G1;5#0B3t0I5.32110t5(55015:5=5@3o5_1i0K0t2X2m5{3b5#0n0*3A0I6e5?5L0|0Z2504010$1U5T5V1U5P0Y0z0:0I5U1L2s0u016d6f60010N0T11030I0V0g2o0)3e0)0Z0k2y4t6f6g5Z5*040p0W0%0#0J650Z5 6h010K110L6+6X5#0(0A6C6e6E5B040E3F6;5)0g110J705|0K5I042X753w0h110e225W683D5#5%5-6,72045,2,6,6a6c6U6V6D7n111#2O7b3D6.046:4m6W5)6?7i3%0U0N110S3e0Z5X7H6{116~0e7C3.737Z3^77117a7U7n7d047f0g7h7m6=117l7r6X7o5`7=7J110n6^7v7w7I5|7o6!6$6(6Q7L7%110c8b2;110k0M0M1^0p8f1X7k8n61047A7T7_7~040n3A066V6E6G6I2h0k5U7;4$8B6,6|7X7$5/7@8q6Y0)8R5~7+7`110%8U7 8O1X7(797q2}843w622Z652Z6*7}5|5#7u8J838,3D6|0)5E8W8w7^2}6E7o8T917611020j0Y0f8$0|65114V8v8@8#983b8(6 9n7j8Q8?8-799f6-9a0P9d7G2*8|7!7p8!8x9x9p7Y9r3%8p9u4B8Y9J9a9c9e9M3^9h049j947s9m9D6E9K9x9O9k9v8Z9W1;7E029A0f9C8+955_9H6b6_8{6`8L7e0-0m0e8*389E3^7N7P7R8u3~a07V79909(7y6Z6#6%6)9H0(8R969H0Aar9P9F9/9-9s040A8_afa07x6X6|2v0Ya5a72Ba91;ab047Q0;ae46agal87ao8aax3^7Ka$8g9wa)8o11avas9Ra,5!a.9S7F9xaR0d0e0maV3k8AaH5)8D046J0q0W0e8 0)0N6S0)1i9 ah8N9:5^a+ak6X8(7*bm717-7/8I9#7?5$a:9Ga=5}7 aEaW8{bh9qbq85a;bI9o78bp9`7,7e7ga 5y92by7|aA9NbC9 aXaI7)ajbPbn782Z0Y9x86an898=bYa%11awb@a*97b{a-aCb`bv71bKc29laCbD3kaGbFa27.a4a6a`7OaSad8z8K6Xb4b6196O0g0Y1U2s0^6wb8babc6T8`a1b%aib/7-2c9H93389{040t638:67bA6aa^0F9_a8cLaN3g9)110ob/9|cR11c812b$5)aJcecYaP5AchaT7Sckb25|cn0I0d0K1g0I6s0I0hbf82c=0|c/aLcfbjd9cha|a~3K0b5w0l2C2%dl5g1B5i2F2I2D0k1Sdo0b5h13dy0-0/0;04.