{"id":690,"date":"2022-07-18T09:08:48","date_gmt":"2022-07-18T08:08:48","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=690"},"modified":"2022-07-18T14:45:06","modified_gmt":"2022-07-18T13:45:06","slug":"carte-de-france-en-python-500-octets","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2022\/07\/18\/carte-de-france-en-python-500-octets\/","title":{"rendered":"Carte de France en Python 500 octets"},"content":{"rendered":"\n

Suite \u00e0 un Tweet de NumWorks<\/a> pr\u00e9sentant le visuel d’une carte de France<\/strong>, j’ai lanc\u00e9 le challenge<\/strong> de r\u00e9aliser une carte aussi r\u00e9aliste que possible (ou faussement r\u00e9aliste) en Python et en moins de 500 octets<\/strong>.<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

Retour dans les ann\u00e9es 80<\/h2>\n\n\n\n

Dans les ann\u00e9es 80 est sorti un petit ordinateur individuel, le ZX-81<\/strong>. Il n’avait que 1Ko de RAM (soit 1000 caract\u00e8res) mais permettait de s’initier \u00e0 la programmation et de cr\u00e9er quelques jeux. L’achat d’une extension 16Ko ou 32Ko \u00e9tait cependant assez rapidement n\u00e9cessaire.<\/p>\n\n\n\n

Voici un programme propos\u00e9 dans le livre \u00ab\u00a0Pilotez votre ZX 81\u00a0\u00bb de Patrick Gueule :<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

La machine poss\u00e9dait des caract\u00e8res semi-graphiques, comme par exemple \u25e7 \u25e8. L’astuce dans ce programme est de m\u00e9moriser le nombre d’espaces \u00e0 afficher \u00e0 partir de la gauche puis le(s) caract\u00e8re(s) semi-graphique(s), \u00e0 nouveau le nombre d’espaces ensuite le(s) caract\u00e8re(s) et terminer par 0 pour passer \u00e0 la ligne suivante. Ainsi le 7780 de la variable A$ indique qu’il faut afficher 7+7+8=22 espaces et revenir \u00e0 la ligne (ligne blanche au-dessus de la carte). Ensuite 6+5=11 espaces puis 3 caract\u00e8res semi-graphiques et retour \u00e0 la ligne :<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

Remarquez que les caract\u00e8res semi-graphiques ayant une dimension de 2×2, cela permet d’afficher 2 rang\u00e9es de la carte \u00e0 la fois.<\/p>\n\n\n\n

M\u00eame id\u00e9e en Python<\/h2>\n\n\n\n

Dessinons la carte de France en tapant des 1<\/strong> dans certaines cellules d’Excel (pour cela importez une image de la France dans Mise en Page – Arri\u00e8re Plan<\/strong>, s\u00e9lectionnez toutes les cellules puis Accueil – Mise en forme conditionnelle – R\u00e8gle de surlignage<\/strong> – Egal \u00e0 1<\/strong> – Mettre une couleur de remplissage<\/strong>). <\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

A c\u00f4t\u00e9 de la carte tapez la formule =A1+2*B1+4*A2+8*B2<\/strong>. Cela permet de convertir les 4 cellules (jaune sur la carte) en un nombre entre 1 et 1+2+4+8=15. <\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

On peut alors \u00e9tendre cette formule horizontalement et verticalement pour recouvrir toute la carte.<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

Si on \u00e9crit le 9<\/strong> de la premi\u00e8re ligne en binaire :<\/p>\n\n\n\n

> bin(9)\n'0b1001'<\/code><\/pre>\n\n\n\n
Cela signifie que les cellules 1 et 4 contiennent un 1 et les autres un 0. Il s’agit du caract\u00e8re ci-dessous :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
On est alors dans la m\u00eame configuration que sur le ZX-81, on doit compter le nombre d’espaces (les 0) puis un caract\u00e8re graphique cod\u00e9 sur 4 cases.<\/p>\n\n\n\n
Voici le d\u00e9but du codage :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Les lettres F<\/strong> et I<\/strong> de la premi\u00e8re ligne sont simplement les 6<\/strong>e et 9<\/strong>e lettres de l’alphabet et permettent donc de coder les nombres 6 et 9.<\/p>\n\n\n\n
Le caract\u00e8re *<\/strong> a 42<\/strong> comme code Ascii, notre r\u00e9f\u00e9rence \u00e9tant le code 33<\/strong>, ce qui fait une diff\u00e9rence de 9 soit 9 espaces.<\/p>\n\n\n\n
> ord('*')\n42\n> chr(33)\n'!'<\/code><\/pre>\n\n\n\n
Enfin, j’utiliserai le caract\u00e8re ‘!’ pour les fins de ligne. Le contour de la carte peut donc \u00eatre traduit par :<\/p>\n\n\n\n
FR = '*FI!*E,ID!(...'<\/code><\/pre>\n\n\n\n
Pour le programme principal, il suffit, suivant le code Ascii, de d\u00e9cider si l’on doit revenir \u00e0 la ligne<\/strong> (caract\u00e8re ‘!’ de code 33), se d\u00e9caler suivant l’axe des x d’un certain nombre d’espaces<\/strong> ou afficher un caract\u00e8re semi-graphique<\/strong> :<\/p>\n\n\n\n
x, y = 0, 0\nfor s in FR:\n n = ord(s)\n if n == 33: x, y = 0, y + 10        # Retour \u00e0 la ligne\n elif n < 55: x = 10 * (n - 33)      # 10 pixels par \"espace\"\n else: \n  car(n - 64)   # Affichage du caract\u00e8re semi-graphique\n  x += 10       # Et d\u00e9calage \u00e0 droite de 10 pixels<\/code><\/pre>\n\n\n\n
Pour la fonction car<\/strong>, soit on d\u00e9compose le param\u00e8tre en binaire pour savoir quelles cases on doit remplir, soit on les r\u00e9cup\u00e8re petit \u00e0 petit. Par exemple, si le caract\u00e8re semi-graphique est L<\/strong> :<\/p>\n\n\n\n
> ord('L')      # on r\u00e9cup\u00e8re son code Ascii\n76\n> 76 - 64       \n12              # 12e lettre\n> bin(12)       \n'0b1100'    # 2 premi\u00e8res cases noires et suivantes blanches\n> 12 >> 0 & 1   # On peut aussi r\u00e9cup\u00e9rer 1-1-0-0 petit \u00e0 petit \n0\n> 12 >> 1 & 1\n0\n> 12 >> 2 & 1\n1\n> 12 >> 3 & 1\n1<\/code><\/pre>\n\n\n\n
Fonction car<\/strong> avec des carr\u00e9s noirs de 5*5 pixels :<\/p>\n\n\n\n
def car(x, y, n):\n for i in range(4):\n  if n >> i & 1:\n   fill_rect(x + i % 2 * 5, y + i \/\/ 2 * 5, 5, 5, (0,0,0))<\/code><\/pre>\n\n\n\n
Programme final ici<\/a><\/p>\n\n\n\n
Avec la tortue<\/h2>\n\n\n\n
Une autre id\u00e9e est de parcourir le contour de la carte avec la tortue. Pour rester dans les 500 octets impos\u00e9s, il ne faudra utiliser que quelques points strat\u00e9giques.<\/p>\n\n\n\n
Pour cela on peut ouvrir la carte de France dans Gimp et utiliser l’outil Chemin :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
On note les coordonn\u00e9es des points dans un tableur. L’id\u00e9e est de partir d’un des points du contour puis de d\u00e9placer la tortue en utilisant uniquement les diff\u00e9rences entre les coordonn\u00e9es :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Par exemple, pour passer du point (64,58) au point (62, 61) on se d\u00e9cale du vecteur (-2,3). L’int\u00e9r\u00eat ? On utilisera moins de caract\u00e8res pour m\u00e9moriser les coordonn\u00e9es !<\/p>\n\n\n\n
Voici le codage de la carte, sachant que le point initial est en (90,-60) qui correspond au nord de la Corse<\/p>\n\n\n\n
F = '18!23!3!30...'<\/code><\/pre>\n\n\n\n
D\u00e9placer la tortue du vecteur (1,8) puis (-2,3) puis (-3,-30) etc.<\/p>\n\n\n\n
Ce qui donne cette version :<\/p>\n\n\n\n
from turtle import *\n\nF = '18!23!3!30!53!11!2!8!5!55!32!9!3!5305!40!6!3!8!1!3!33!D22!2!5!4!6!1!4!4!3!4!1!2!12!1!2!10!28!11260!2!720124!12!25!11!73098E5!29!66043!223!1B51'\n\ndef f(s = 1): \n global i\n if F[i] == '!': i, s = i + 1, -1\n i += 1\n return s * int(F[i - 1], 16)\n\nx = y = i = 0\npenup()\nwhile i < len(F):\n goto(90 + 3 * x, -60 - 3 * y)\n pendown()\n x += f()\n y += f()\nhideturtle()<\/code><\/pre>\n\n\n\n
Mais le r\u00e9sultat n’est pas tr\u00e8s joli car trop rectiligne et la Corse est reli\u00e9e \u00e0 la m\u00e9tropole<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
On va ajouter de l’al\u00e9atoire<\/strong> en faisant varier la trajectoire entre 2 coordonn\u00e9es. Pour cela on doit d\u00e9composer le segment (x1,y1) vers (x2,y2) en sous-segments :<\/p>\n\n\n\n
for j in range(9):   # D\u00e9composition en 9 \u00e9tapes...\n  goto(90 + g(u,x,j),-60 - g(v,y,j))  # ...entre (u,v) et (x,y)\n\ndef g(a, b, j): return 3 * (a + (b - a) * j \/ 9)   # Interpolation<\/code><\/pre>\n\n\n\n
Et avec de l’al\u00e9atoire :<\/p>\n\n\n\n
def g(a,b,j): return 3 * a + 2 * random() + (b - a) * j \/ 3<\/code><\/pre>\n\n\n\n
Concernant la s\u00e9paration avec la Corse, l’astuce utilis\u00e9e est qu’avec la NumWorks pensize(0)<\/strong> ne trace pas de trait. Ainsi en ajoutant :<\/p>\n\n\n\n
pensize(not(18 < i < 23))<\/code><\/pre>\n\n\n\n
On aura un trait d’\u00e9paisseur 1 sauf si i<\/strong> est entre 18 et 23 qui correspond au trait reliant la Corse.<\/p>\n\n\n\n
Enfin, on peut dessiner de petits cercles \u00e0 chaque \u00e9tapes plut\u00f4t qu’un trait simple, on obtient finalement ce script<\/a> qui fait exactement 500 octets avec le r\u00e9sultat suivant :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n","protected":false},"excerpt":{"rendered":"
Suite \u00e0 un Tweet de NumWorks pr\u00e9sentant le visuel d’une carte de France, j’ai lanc\u00e9 le challenge de r\u00e9aliser une carte aussi r\u00e9aliste que possible (ou faussement r\u00e9aliste) en Python et en moins de 500 octets. Retour dans les ann\u00e9es … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-690","post","type-post","status-publish","format-standard","hentry","category-twitter"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/690","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=690"}],"version-history":[{"count":27,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/690\/revisions"}],"predecessor-version":[{"id":730,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/690\/revisions\/730"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=690"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=690"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=690"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}