LP - Exercices

LP - Exercices #

Ce document est mis à disposition selon les termes de la Licence Creative Commons Attribution 3.0 France.

  • Titre du document d’origine complet : Livret Pédagogique CodingUP
  • Auteurs : Laurent Signac, Emmanuel Laize, Freddy Lege, Caroline Tartary

Ce document est la troisième et dernière partie du Livret pédagogique, dans laquelle nous proposons quelques exemples d’exercices accompagnés de programmes de résolution.

Une phrase renversante #

Dans la ville de LavaL, NataN et sa sœur HannaH sont fans d’AbbA et de palindromes (texte ou mot dont l’ordre des lettres reste le même qu’on le lise de gauche à droite ou de droite à gauche). NataN lance le défi à sa sœur de faire un programme qui affiche une phrase à l’envers. Ni une ni deux, HannaH s’exclame « Engage le jeu que je le gagnE ». Pour vérifier si votre programme fonctionne, nous vous donnons la suite de caractères suivante : E4udr*peb!Athe=hufez

Vous devez écrire un programme qui retourne cette chaîne de caractères.

Réponse #

Python permet de simplement inverser les chaînes de caractères :

>>> s = "E4udr*peb!Athe=hufez"
>>> print("".join(reversed(s)))
zefuh=ehtA!bep*rdu4E

ou encore plus simplement :

>>> s = "E4udr*peb!Athe=hufez"
>>> s[::-1]
'zefuh=ehtA!bep*rdu4E'

Tu quoque mi fili #

Brutus a écrit des défis de programmation pour distraire ses amis. Il souhaite leur communiquer l’adresse Web sur laquelle il présente ses énoncés mais ne veut pas que son patron, Jules, y ait accès (Brutus est très secret). Il a donc décidé de protéger cette page par mot de passe et a cherché un moyen de communiquer ce mot de passe uniquement aux personnes de son choix. De nature méfiante, il a décidé :

  1. de chiffrer, par un moyen qu’il jugeait sûr, le texte suivant (il a remplacé les 12 étoiles par un mot de passe de 12 caractères) : lemotest************
  2. de noyer les 20 caractères ainsi obtenus quelque part au milieu d’autres caractères pris au hasard.
  3. de publier la séquence de 500 lettres résultante sur son site Web, avec un lien vers la page des défis.

Mal lui en a pris, Jules, était très familier de la méthode de chiffrement utilisée, malgré la petite variante imaginée par Brutus…

Saurez-vous accéder aux défis de Brutus ? Voici la séquence qu’il a publiée :

hmtyszjtggtwwsjonayjpgnujjsuidunahpvyrttersnavnetb
llgxkzhhdddzeritjtferwhuikkprvrnikxrfctwrrgiumuqih
vfrhrwxqbqhnzcnaucadalumuxnljuuwciputcrflfqzrfqavw
ovovifxukhbouacavplfybqeltycvhxdebgdursjtckcyjzixd
gzmbwhqbjoxuorijwsgnhlcvpiivwkwbbwculnqmbooiqhgrqn
lrmqhmcmegyuolmygbbpnfwparekepkjikopkljnfssumaxayk
dxvbunvxcnbcenwrermrerlrzihdswfakyziorpmmkapumjseb
dslezaklmeaziopazflsqdmxcbvrjnmfyfpgqtbtwvuexyzrxr
poaknmlbklqdovkgiafoivlrtnbugqogyxwkehcfvmqvluchua
ytfyrkjdhsmrfuaokvdeevljpfsnyucjvxchrxsgztzzpomeqj

Réponse # 

from string import ascii_lowercase as minltr

# Code de César
def cesar(s, n):
  return s.translate(str.maketrans(minltr, minltr[n:] + minltr[:n]))

# argument : nom du fichier contenant le cryptogramme
with open("fichiers_cryptogramme.txt", 'r') as f:
    brutus_msg = f.read().replace('\n','')

# On pourrait aussi entrer directement le cryptogramme dans le programme...

# Test de tous les décalages
for decalage in range(26):
  txt = cesar(brutus_msg, decalage)
  if "lemotest" in txt:
    print("Le mot de passe est :", txt[txt.find("lemotest"):][8:20])

Carré Infernal #

Le carré suivant est composé de 37×37 chiffres :

4288393591884397187618398681841676743
9254654991118441344374776533258599417
8893656819293184287565867762519861755
3121894958997282255935884528653254819
6526361449368947885343898691459859361
7354325265365771431811135662461975988
7828347682323954285662655995882611554
2241949216741583915379553221344294351
8126623837962559334865134372825564622
3676715419213945142632129779446464918
8388834887838797667267431432379744784
1188778373746431579685964653572827572
4511924185743244759694689756534132293
7656691646128331835675324847593318968
8512665395468838649395321514742278622
4486964239358216539696756866865132252
7239451276138383656525572975167851425
1861136136592246255722827792312161919
1113233114956848715353816376145884559
4245934131473888334594869214483283549
2424695994387162595595248753558228954
7886877493494928328782758835936297415
3154527421997874777127444957918186882
2828845672196572396965611949593779517
5658746953513563236338418674895284317
9446955314311234783595739991392111821
9764519995819593184683618238753887553
9624656157455735938143581532388888315
3598656397194334965979795453856591466
7364887553874729124931181953799185478
9872679654355252527119257344551982418
9512278479962556358384192624652328547
1263748964485996181761353888996882722
7874464567999685215128853445956611764
7125992553677897796537634396721642919
3541652678332294695839418472559579431
2418554264377316194474245665356656213

On peut y lire les nombres verticalement de haut en bas, ou horizontalement de gauche à droite. Parmi tous les nombres que l’on peut ainsi construire et comportant de 2 à 4 chiffres, combien y a-t-il de multiples de 7 ?

Le nombre le multiples de 7 que vous trouverez constitue le mot de passe pour valider cet exercice.

Exemple #

Dans le carré suivant, qui ne contient que 5×5 chiffres, on peut lire 11 multiples de 7 :

34562
19385
32157
35613
12351

Horizontalement : 56, 938, 385, 21, 35, 56, 35 et verticalement : 133, 49, 252, 63. Il n’y a aucun multiple de 7 à 4 chiffres dans cet exemple :

Réponse #

Le programme suivant utilise les générateurs (mot clé yield)

def extract_nombres(s, tmin, tmax):
  for taille in range(tmin, tmax + 1):
    for debut in range(len(s) - taille + 1):
      yield int(s[debut:debut + talle])

# argument : nom du fichier contenant le carre
with open("fichier_carre.txt", 'r') as f:
    carre = f.read().splitlines()
# On ajoute la «transposée» du carré
carre.extend([''.join(c) for c in zip(*carre)])
mul7 = 0
for line in carre:
  # extrait tous les nombres de 2 a 4 chiffres
  for n in extract_nombres(line, 2, 4):
    if n % 7 == 0:
      print(n)
      mul7 += 1
 
print('Nombre de multiples de 7 = ', mul7)

Cryptarithmes #

Les cryptarithmes sont des cryptogrammes représentant généralement des égalités d’expressions arithmétiques, dans lesquelles les chiffres ont été remplacés par des lettres.

Le plus connu est sans doute celui d’Ernest Dudeney, publié en 1924 :

SEND + MORE = MONEY

Dans un bon cryptharithme, chaque chiffre n’a qu’un seul équivalent en lettre et le cryptarithme aura de préférence un sens.

Voici quelques exemples de cryptarithmes, visibles sur la page Wikipédia Cryptarithmes :

UN + UN + NEUF = ONZE
CINQ + CINQ + VINGT = TRENTE 
ZERO + NEUF + NEUF + DOUZE = TRENTE
ZERO + ZERO + ZERO + UN + DOUZE = TREIZE 
ZERO + ZERO + SEPT + SEPT + SEIZE = TRENTE
ZERO + UN + TROIS + ONZE + QUINZE = TRENTE
ZERO + TROIS + TROIS + TROIS + SEPT = SEIZE
ZERO + TROIS + TROIS + DOUZE + DOUZE = TRENTE
ZERO + QUATRE + QUATRE + ONZE + ONZE = TRENTE
UN + UN + QUATRE + DOUZE + DOUZE = TRENTE
UN + DEUX + DEUX + DEUX + DEUX = NEUF
UN + QUATRE + CINQ + CINQ + QUINZE = TRENTE
TROIS + TROIS + TROIS + CINQ + SEIZE = TRENTE
QUATRE + QUATRE + QUATRE + NEUF + NEUF = TRENTE
3 × MOT = TOM - 1.

La résolution informatique de ce type de problème implique une exploration presque systématique de toutes les substitutions possibles. Selon le langage utilisé, le programme final pourra être plus ou moins court.

Réponse #

Le programme Python suivant construit tout d’abord la liste des lettres du cryptarithme. S’il y en a N, chaque combinaison de N chiffres différents est substituée aux lettres. L’expression résultante est évaluée avec la fonction eval. Si elle est vraie, le cryptarithme est résolu. Notons qu’on ne peut pas entrer une constante numérique en Python qui commence par 0. Généralement, cette contrainte est aussi dans les règles du cryptarithme : aucun des nombres ne commence par un 0. Le problème est ici géré en capturant l’exception levée dans le cas ou on tente dévaluer une constante qui commence par 0. Malheureusement, la même exception est levée en cas d’autre faute dans l’expression (entrer x au lieu de * par exemple), et l’utilisateur n’est donc pas averti de cette faute.

import re
import itertools

def resolution (s):
    lettres = "".join(set(re.findall("[A-Z]", s)))
    for comb in itertools.combinations(range(0, 10), len(lettres)):
        for k in itertools.permutations(comb):
            repl = "".join([str(v) for v in k])
            s2 = s.translate(str.maketrans(lettres, repl))
            try:
                if eval(s2):
                    print(s2)
            except SyntaxError:
                pass

Nous pouvons tester la fonction (en la transformant en une expression python valide (= devient ==, x devient *…) :

>>> resolution("CINQ + CINQ + VINGT == TRENTE")
6483 + 6483 + 94851 == 107817

>>> resolution("SEND + MORE == MONEY")
9567 + 1085 == 10652

>>> resolution("3 * MOT == TOM - 1")
3 * 247 == 742 - 1

Le programme n’est pas très rapide (il teste bêtement toutes les possibilités, mêmes celles qu’on écarterait rapidement à la main), mais donne généralement la solution d’un cryptogramme en moins d’une minute (tout dépend du nombre de lettres «libres»).

octobre 17, 2024
Modifier cette page