Livraisons à Manhattan

Un livreur new-yorkais organise sa tournée. Le quartier dans lequel il évolue est un quadrillage : toutes les rues suivent l'axe Nord ↔ Sud ou l'axe Est ↔ Ouest.

Les adresses de ses livraisons sont donc des couples de coordonnées, (2, 3) par exemple. La première coordonnée est l'abscisse du point, la seconde son ordonnée.

Ces adresses de livraison sont données dans une liste python. Par exemple :

🐍 Script Python

livraisons = [(2, 0), (0, 1), (3, 3), (2, 3)]

Ce qui correspond à la carte ci-dessous :

Afin de déterminer son itinéraire, il décide de toujours livrer en priorité l'adresse la plus « proche » de sa position actuelle. Se déplaçant le long des rues, il mesure la distance $AB$ entre deux points de coordonnées $(x_A\,; y_A)$ et $(x_B\,; y_B)$ en faisant :

\[AB = \text{abs}(x_B-x_A)+\text{abs}(y_B-y_A)\]

où $\text{abs}(x)$ est la valeur absolue du nombre $x$ : $\text{abs}(3-5)=\text{abs}(5-3)=2$.

Coup de pouce (1)

Avec Python, abs(x) renvoie la valeur absolue de x

Coup de pouce (2)

On rappelle que Python permet de récupérer facilement les différents valeurs d'un tuple grâce au décompactage (unpacking en anglais). Par exemple :

🐍 Console Python

>>> x, y = (3, 8)
>>> x
3
>>> y
8

On se propose dans cet exercice d'aider le livreur à déterminer son trajet en écrivant les deux fonctions décrites ci-dessous.

Fonction distance

Écrire la fonction distance qui prend en paramètres les coordonnées de deux points A et B donnés chacun sous la forme d'un tuple de deux entiers et qui calcule la distance entre ces deux points.

Exemples

>>> A = (0, 1)
>>> B = (2, 3)
>>> C = (1, 6)
>>> distance(A, B)
4
>>> distance(B, A)
4
>>> distance(A, C)
6
>>> distance(B, C)
4

Évaluations restantes : 10/10

.128013s3obcdufvg/ly nABapSr1-me,(P2=4:+twkihx)050g0z0I0s0L0m0b0o0f0m0s0b0b0E010I0L0t010406050b0h0y0y0s0v0n040u0d0m0h0)0d0p050l0:0=0@0_0.0t041219051c0l1c1e190.0g0L0j0X0Z0#0%0M0L0k0M0m1s0M0I0,050S0e0m0z1n0!0$011r1t1v1t0I1B1D1z0I0e0d0g0_1A0v1a0I0M0X0|0b0t0s0p0%0D011F1p010i0U0z0p0s0y0z1z1%1)1.1H1;1D1@1_0,0a0o0C0v0d0t0d0b0L0 0p0o0Q1#0v0v0z0f2e121|0p1a0l1Z2r0I1X1W1Y0g1~0%1v0p1?2b1z1k1m0Y1G2B0L2D0p1T1l1z0t2k1a2p2r2V0/1(2f2J1/2O0v0?0m0,0w2o2Z0-2Y1}2#1H2%2)0,0D2-1)2/2p2A012@0s2*040c2{2q0.2~2=0%31330F362r2S0z2r2H2u0g2y2 0f1T1`1a3k1d2T2:2q3f053p0Q2U2Z2 0K0,0Q0i3y391o1H0J0,0o3J3D3a300i3G0L0b0S0p0f0z3Q2;3L0%0+040B3$2!3(300,0q3-2 3*0A3f3P3K2K3:040r3?3S3*0O0G3f060o483{3R3/0p0,0N3=132.3w3@0,3_4h2|4a3%3}4d040n4g2V4p3.3}0d0,0E3`4j3S4s4v2.47494E4c4e404n3x3|1/3^4D4R2?0,0n4O4w4L4z4B4U4b4r0,4Z4I494x3E0,2k0I0h0v114P044/4F0e0,0s0e0b413/3*3,4`4#2$4N4(4q1/4A040x5b4y59044f533}435h2 5e0H5p4}4 515m4S0,562X4V3b4X4,4o581H5e5g4`4|4M4t4H2|5H3)0,0O46123A3i1b3v0l3t2s3m122v2u1S1U2u501D3j1l2/5#0R0T0V04.

Fonction prochaine_livraison

Écrire la fonction prochaine_livraison qui prend en paramètres la liste des adresses de livraison et la position actuelle du livreur et renvoie les coordonnées du prochain point à livrer.

Si deux points sont à la même distance de la position actuelle du livreur on renverra les coordonnées du premier point rencontré dans la liste.

Une version valide de la fonction distance est chargée dans l'éditeur. Vous pouvez directement l'utiliser.

Fonctions, opérateurs ou modules interdits

Dans cet exercice on interdit d'utiliser :

min
sort
sorted

Exemples

>>> A = (0, 1)
>>> B = (2, 3)
>>> distance(A, B)
4
>>> livraisons_1 = [(2, 0), (0, 1), (3, 3), (2, 3)]
>>> prochaine_livraison(livraisons_1, (0, 0))
(0, 1)
>>> livraisons_2 = [(2, 0), (3, 3), (2, 3)]
>>> prochaine_livraison(livraisons_2, (0, 1))
(2, 0)
>>> livraisons_3 = [(3, 3), (2, 3)]
>>> prochaine_livraison(livraisons_3, (2, 0))
(2, 3)
>>> livraisons_4 = [(3, 3)]
>>> prochaine_livraison(livraisons_4, (2, 3))
(3, 3)
>>> livraisons_5 = [(1, 0), (0, 1)]
>>> prochaine_livraison(livraisons_5, (0, 0))
(1, 0)

Évaluations restantes : 10/10

.128013.339s3o_;8bcdufvgI/0lyàq n7apS.r1LFmeh,(P2=4:Cjtwki9][5R)é6050k0I0T0z0W0s0c0w0j0s0z0c0c0O010T0W0A010406050c0l0H0H0z0D0t040B0e0s0l0|0e0x0w020z0H0A0g0w0#0I160D0v0l0I0c050q13151719110A041x1E051H0q1H1J1E110k0W0n0;0?0^0`0J0W0o0J0s1X0J0T0 050,0i0s0I1S0@0_011W1Y1!1Y0T1*1,1(0T0i0e0k191)0D1F0T0J0;1c0c0A0z0x0`0N011.1U010m0.0I0x1k0I1(292b2g1:2j1,2m0H2o040a0w0M0D0e0A0e0c0W1f1h0*270D0D0I0j2J1x2q0x1F0q252V0T2322240k2s0`1!0x2l2G1(1P1R0=1/2)0W2+0x1 1Q1(0A2O1F2T2V30122a1h2;2h2_0D160s0 0w0E2S3410332r361:383a3c0N3f2b3h2T2(013m0z3b040w0d3q2U113t3k0`3w3y0w0P3C3s343u3I3c0!3M3E3O3G3v0e393x3c0(3T3i351T3l3Y3n3z0y3%3F3*3H3,3!3z0h3:3V3=3X3Z3J0X3{3j3}3Q040E0r3M1G2~1x2/2Y0k2$3u0j1 2y0)1Q1F2}0I2 3g494i0*4q432=010V0 0*0m493;4x0U3c4D3|4x0x0m0 2}0e0j0J0-2+0f1!0n0D0-0c1g4I4w2h0~040L4#3)4K0 4V4X0W4Z0x1w1y4r4E4%0 0K3M0w3(3P4N2G2I0W1g0f0z2Q1u0s1,4+3u4(0$0Q3T0w5j4 4`3l4N1d0c0f4O4Q0I4~503W0e0 0O5v5m3H4.1Q4:4=4@325C014(0Z5d3W0H0W0 484^3r5w3}4(0Y5i5k5W4-041P0c0,0x0j0I0f5Q0x0W3a5u5U2U5l4J2h5y045A5^3z5$374A4;5+5-5O5X0 4*60625n042F2H2J57590I5b5@5J5{1:4(4}605`4$6e0A5p5r2D5t684x5f5!5j6d0`4z040m3Y5B6p5D040W6N6v0`0e4G6Q0x6S4,370i0 4X0x0o6n4_6O5L6a6C2h5Q0 3e6c5K6r6Z3P6$042v6:6q6/6^6-0x5E4W4Y1g5I6,6T6.040$5g6F5k6G5K756f6A4R2@6{5x5z7q44765G79700`5M7y3v0 6R737c5Y7h7i6H7C5(652b5-6z4P7o6Y6t7K5}5 306u6!6e5)666+5V6_726o7c7l6g5456580T5a5c7F7!7z4|7t5%5s7S7B6E60067i7J5K6J0W4C7U7k645*7O5.7 4S7}5|0 020s0T0g8j7#7N5,5.5:5=3x7(2U7K4(5h83858E7Z516f6y7 8y615K7W8q6P8h7p8D8F86748d7%5/2@8w7^7Y7V7s8b8W7M8e8t7Q4Q8i8T7j6-6J2O7?0D7T8%8c8I0l5q8K3%0q4t4p4a960q4d1x0T4f9b2!2W1~202Y0z1+984d1D4v7`012O0H0f0m0z0V5.0J0d0 1p1r1t1v0w8C321K3h1E0p0s0w0c000z0o2I0w2l0w0D0%3x2I0%0w0k000l2+9W2P0J0I0D5t9$1-8v0H140C1G9K040F1-4/0I0l0D0w0Aa00T274?2Z0l0W2O9O1g0w2Z0z0S0+9U1h0I0m0m2P7?2ba61Pan0%2O0x0T9F2O5t9/9-0:130j5-0^1Q1v9_9J9o0R0+ay9+aB9:2Lagaia60c1-9v9T9V4Q0e4;4;0car0w0u0;4R9E0w0%0,a40w0?a37n4S9~5F781ha`6x90a{7R1-2Lb2532J0w7=7@0I0C0w0G582ka-0w2x1_ac9V0b0l4W0I0K0;aP9=a?0J4j0w9*0o17ar9T2a0:a;a`0s1g0o1ua1af0e0,1,9$0laf4XaWad9Tb25p27a1ayaL1N4c0+0-0/04.