Aller au contenu

Paver un rectangle avec des dominos

Définitions

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

On peut la paver avec de petits rectangles de côtés 1×2 ou 2×1, qu'on appelle domino.

Un domino sera codé par un tuple (i, j, direction) 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)
  • direction sera une lettre parmi 'NSEO' et indique le prolongement du domino vers
    • 'N' : le Nord
    • 'S' : le Sud
    • 'E' : l'Est
    • 'O' : l'Ouest

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

  • Il y a un domino bleu : (0, 1, 'O')
  • Il y a un domino rouge : (2, 0, 'N')
  • Il y a un domino vert : (1, 1, 'S')

Exercice 1

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

Pour cet exercice, peu importe l'ordre des dominos. 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 dominos à afficher. Vous pourrez donc tester dessine(14, 16, pavage(14, 16)), 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 : ∞/∞
.128077.128013/.r;nbOylae%u)*d6z3×m(P+02@U],59fq!78 N_o=pcwgv41kRéhtsS[ji:E050r0m0%0l0,0k0(0N0T0k0l0(0(0R010%0,0S010406050(0o0w0w0l0e0j040)0Q0k0o120Q0g0N020l0w0S0f0N0!0m1c0e0J0o0m0(050c191b1d1f170S04051K1D1N0c1K170r0,0W0`0|0~100$0,0V0$0k1#0$0%15050=0h0k0m1W0}0 011!1$1(1$0%1.1:1,0%0e1L0%0$1=1Y010I0@0m0g1q0m010`1i0(0S0l0g100B1,2i2k261@291:2c0w2e040b0N0y0e0Q0S0Q0(0,1l1n0:2g0e0e0m0T2I1D2p0g1L0c242U2123221-0r2r101(0g2b2F1,1T1V0{1?2(0,2*0g0Q2.1,0S2N1L2S2U2 182j1n2:272^0e1c0k150N0Y2R3316322q351@37393b0B3e2k3g2S2%013l0l3a040N0u3p2T173s3j103v3x0N0X3B3r333t3H3b0G3L3D3N3F3u0Q383w3b0s3S3h341X3k3X3m3y0L3$3E3)3G3+3Z3y0M3/3U3;3W3Y3I0H3`3i3|3P040Y0A413(2;3}3,0Y3d1E3f3T424a440Y3o4f3q4h49363?3x0Y3A4n3C3%3O4s150Y3K4w3M4i4r3~4B3R4E1O2}1D2.2X0r232$3V0T2_2x0/1U1L2|0m2~3f3L054V0:4%4G1@0Z150:0I4)3:4a0U3b4@3{4j0I152j0W0l0V0m4|4.1014040x564q3k150g5c3t590F3L0N4y3V0g150w5h3V590p0-3S0N5y5m4^270(2n04011v0g0W0Q0,1;0o2*0N1(0(0%1;2K0r0Q0w2?2F0N1z0,0N512b0%0N5N0N2N2P2k0V1:0N0g0v0w015x5z5n434;5W5Y1C4E5A4}270Q150R5l5}4a590*0E5{5y6b274:040,4?636i5e045g6o5B1@67040n6a6u105X154m2 6457016w0R696t651@6C04474L6A01595w4E065z6Z6G5d106k0I3X6z6N3G150,6+6H0Q4`6l6s6F6p3G0h150e5:556S6,6U155b716H5p6r6:6$6I150c0c7a3t6P6E4(6T5u6W2 6Y6!7q6`016(6*6M77150+7g3V6=6.6^3f6#3O6|046~0g545s3|5975316T785r767b7m6g7q7Z7s785V5X2^627R726w0d7N4j150l0S0S2b0r7/277P7Q7k727i7A3|6w0q817:6l7`1@5j85367y8858155k7w7b0(0Y15000)008e73040p0p7Y7s6k0m1(6n6_7S5q8b6v156y8i7h0,6D8E106J6L8B7 8K6Q8q6V7Y6Z8w156)0e8M3u6.8$7C6@8$0g7I7K7M7V5i748q787E3q7s7X6X7Z6!8Y048!8,8d8I7B6?2?8,8.6 8U8?8;5o8D95827d7f9h4a809e7O155v8W8~5|8C047%618q7-8@7;7?7^9c5a7}8`9v6/9o6c8g8$9n8Q6;15849l8c047z9L7{9N9U1@8k8m0.8p9Y899q8u8}9u728x0^707+6H8V9/7r9v9x7)8)688$0Z0T150O1m9@4g7p6h6T6k2N0%0o0e8_2T7G9f9w609 6X1D4+4$4Mas0c4P1D0%4Rax2!2V0l1/au4P1J4-7b2N0w0P0I0l0Z0m0P0$0u151v1x1z1B0N7n4(1Q3g1K0D5O0(1i1k0,1m5!0o5$0g001B5*2j0_0%0Q0o0+a}0e0_0w1m0Q0T0$2C1c12aX1O3g2.3t1_1%1)1+aI3t2t2b2d152z0)0T0e135*0y0j241m4)4#aI304(arbk3V6k4=8q6?5m9+3G4 045153a89I727P9B79bN8r8h9Q7b7T9F9r9{ak3|5D155G2b5J5L5+5O5Q5S0N5Uan5Z5#5%0l0W5)b@5-2O0=7L5=5@5_8vac780,1r3X0%bK4{bZ0g787K7%cc727$b}7*7F7s6J8$6d6fb+906m93bYb$3t6w8HcG3V9Pcv6T8O9O8S6R9^7W15a!4o8~90929#6-87c#6I97ai3y7#9a7LbT2T8{9dcT3O5fa0047ecQ8LbZ8|7o9t9:6H7u8#c(789XcK82c*996}9bc c?7~7x047Uc@5t9qcW3Cd29|9;6.8AcNcrde0gcpbZ9Acldy0r8/c:bG9p5a8qcMbU9_9qc`6Kc}8Tdg04dp16dr9t7#5 7(2F9z157.dD047=7@dz9F0x9Hc;6TdMajcw9ScE9KdmdJb#dwdjd9dicU04e03qb,4a9%048n9*d~9M8s9.d1dYd37b9=0(dHc=dV9seke99V9~d%dBd)bXd-9EdUd;dL8S7je8d`049Tda86d}e17b6w0zdS4eef9Ze6cEe3dNe5e7d_6Teb000Oeee48=eheseu4/6}0;agc+e;c$ewcucXel3t9=cDd79geM668GdSeHe%7,688PeP8J15cSe-dnerb+8Xac8Z7vf56qeOeIcOdcd7c.8:eV9,dKd+c+eqb*ejd2cZfpfealeZfa6;fvfq6{dyfyfidJd=dI86dlfK9ic{9kfQ01d^fXeWfF4getabdt6ldvftdx7J2kdAfz8Nezd+codGd:eFc~f|8reif!4acPc(6Pfhe!e.dWaaf/f:dje|d(04d*g578eBd/eDfWd!c%g58agbeGc`eLg89VfMf+fAe$c,e(8lec9)b)g7e~et908yeo9Fgggifmf^gleygneA9Dgsgx74gu9J9FgIe`f)gAc(83eYc`eSgz4Bg.8$e)0ie,gefj8te:90aee^cEg!fGg:enep7lcVh5fn7Je@aha2a404a62*3$0cbFat2UaG1M1Lcf0V0N3w0%100a2f3V0%0U1w0Q0+8K0N0(0e0T1Z1}0S0(0-7e0T0r0g0d0+0(0:1(0W0e0d2*0%0c1$0c0+0:0TaP0r2VhJb3hM0C0Y0G0d0Y0d0A0c1?0;0(1E0W0V0c0Y0I0X0X0r0d0(ia2f120%1:100-0z0Y0-010c3y0.0~0l0j0m0tb{1;4V0g5R0ea;2Nb@1;52bt2kb`b 2Eag6~2H5+125Q0m0e5PaY0X2g0o1:ag0_0KbcaH0y1d0=54iC5J211;cfbS0`0e0#0#1;0Kj2i.4O0;0?0^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
    • 

  • dominos : une liste de dominos. Un domino est donné avec un tuple, (i, j, direction) :
      

    • i désigne la ligne d'une case
      • 

    • j désigne la colonne de cette case
      • 

    • direction indique le prolongement de la seconde case.
      • 

    

    • 



Un pavage est valide,


    

  • s'il couvre tout le rectangle,
    • 

  • s'il n'y a pas deux dominos qui partagent une même case
    • 





###(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;nbOylaeu)*dV63m?(P+02-],59f!7}8 N_o={pcwgv4F1kIéhtsSàLj[i:E050q0m0%0l0.0k0(0L0S0k0l0(0(0P010%0.0R010406050(0n0u0u0l0e0j040)0O0k0n140O0g050b1b1d1f1h190R04051x1q1A0b1x190q0.0V0|0~10120$0.0U0$0k1O0$0%17050@0h0k0m1J0 11011N1P1R1P0%1X1Z1V0%0e1y0%0$1#1L010G0_0m0g0l0u0m010|1k0(0R0l0g120A1V26281_1%1|1Z1 21170a0L0x0e0O0R0O0(0.1n0g0L0=240e0e0m0S2v1q2d0g1y0b1@2I1;1?1=1W0q2f121R0g1~2s1V1G1I0}1$2S0.2U0g0O2Y1V0R2B1y2G2I2:1a272w2!1`2)0e1e0k170L0Y2F2@182?2e2_1%2{2}2 0A3228342G2R01390l2~040L0t3d2H193g37123j3l0L0W3p3f2@3h3v2 0E3z3r3B3t3i0O2|3k2 0s3G352^1K383L3a3m0I3Q3s3T3u3V3N3m0K3Z3I3#3K3M3w0F3+363-3D040Y0z3=3S2#3.3W0Y311r333H3?3~3^0Y3c433e453}2`3%3l0Y3o4b3q3R3C4g170Y3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0Y3;4Q4u3U4C0A3{4W4e4Y3W0A422:4A4H4N0A4a4,4G3@4/4j4=4L4v4)4r4`4R4|3(0A4y4 4X3$4Z4E554%574)4J5a4B4)4P5f4.4Z4V5j4@4C0t4#5n4S3W0t4+444?5t3(0t4;5x4{4(5A4_331B2.1q2Y2L0q1?2Q3J0S2*221y5M1z5K2=4s055S0=2/501%0Z170=0G3z5y1`0T2 5/5E3u0G170m0(0%0N270V0l0U0m5@5)1216040w65563i171p5!5^01680D3z0L5:38170u6b5b6i176k4s6m6h0g5,0O0u2%2s6r3h680o0/3G0L6L6x66010(2b04010+1!60621!5|0%0B0_0L611R2y0v016K6M6n120S0Y17030L0!0g2u0.3k0.0(0l2E4z6M6N6c6z040q0#0,0*0N6C0(6l6/010O170P7f6h680-0C6-6L7g5+040G3L7l6O760N7x6c0O5=042%7B6s0g0h170e28636F3J686a6g7y6e7P3-6H6J72736.6y171+2U7H3h7i047k6w7g7n7W3~0Z0S170X3k0(647:6h7t7v0e7+4H177A7 6O7D177G88757K047M0g7O7T6c7R7?2`6p8n1%6H7p7!7#747I5,797b7d8q127-0c8C6d040l0R0R1~0q8G8m8k8x047)7~2=7m170o3G06737g6;6?2n0l618j4,8#801782847X177S8V7U7F8O6u8=47170,8|046v2:8w3C5,0.2B2D0.1o928Y8d6s8a7F6f957g760q6B6D7e8Q6G177Z8-8v9685770m0k0@8~1`7-7/9l8W040Q8G0(6=04000M00929v339y8?698G7-0B8G6C4p92949V7g9%045r5I9J0o9*3e9W3~9N17000)9S9s7Q9u9E8r8@9$0.9(9 9X9?2H9^1`9-9/3e7;8Xaa3m7g9`9P0:9~8_8la19g9t9Ya83~ae9)a2129-5wag9;ajac1%am000iap9:6O689U9@ahavaq6sayaw1`6jaA7h179#aX1%aC9e0J7q7#9m98azat9z0q91a=3-9Ga!9n9B9Da(67170-8G9n992C71aUau8t9w8v7s8b5.a_3~8Pb99z0.a!7-029C0fa!aWbk9X9f9I897E7wbhaYa4b08HbmbB1%bo0U0%0f9H9+7%049kaNar04bwbOby17bAbxbT8^bS8Ra^b!9h17bpbLbsa69.9ebnbz83bHb1aTb%9704b)bW7Cb,bKbMa|8pbE7Ya-9xaH127t2B0%0n0ebRaR807_047{0`8U44cabe7Fbgb*aub$aE8`bGcv3J7-0yc577cAc0b+04b-brb_01btb|a0bUb?bYb^cB9Xcx2Ha/8{cNcDcF1Gbnc2bLbNcj8`cicZ9;cT04bZcIcwb490c*04cEcN9nb c.c1cKbqb/17afc;aO8Xc?c^d36sbjcQ3@c|c$17c cW8 77d2ab7gbJc,cF6qc78XaQ3qca8.6Ocd0?cgc:akck7`7|cp4ccr8/ctc(8z7c6~92b3bE76cHcybT0CdXbudpdr5(d$ddcVc_a?dT8Bdy04d(didpd!ds6hc%d0a:d@d%c{b~c}dnd:djdq920CdA18dC7$dE7LdGcha!7^dLcoc9eg758y7adU9rd)bCd^e4d|d,dg17e3dYdkewa304bbe83~a{cNem040d0e0ndNdB9xc!78etd?eHb`d_d#8ReAcba#c~c(eAaSeEe#8Hd+e+d do8oeae2c}c-d}dEcleReT8ZdD6c8%046@0r0#0e0.1|0S709cdI8!eq6s81def0erc#e`bI7E8cfs3u8f8h8,d`excYeBb}dIaS6Iep7rdQ8;e0e5c$fudIe+7J7L7NeUfEcRfDc!dxe=c88udCcsfec?2)0%dSeZdVd@e%dafqe/9Je;fB6ofOf$eDedfkeff6fmeicfekeOclcn7}f5fl3hf8fa1f6|0g0%1!2y0~6%fcfe0.fgb8cqge3J7tf+d08f2i92fZbP9o6C2)evf|b`bVdf7,170pd7045CgNcC170He dJc/c}gQfNf#gK6t04g1dPeh8gejfR7sgadMgdfK6Ogg0L0d0O1m0L6Z0L0h9df(cscedHelf2eSfW190b5$0m2I2-hg5L1H5N2L2O2J0l1Yhj0b5Mhd0=0@0_0(04.