from random import choice
# Initialisation des variables
codes = ".-+-...+-.-.+-..+.+..-.+--.+....+..+.---+-.-+.-..+--+-.+---+.--.+--.-+.-.+...+-+..-+...-+.--+-..-+-.--+--..".split("+")
chiffres = [chr(v) for v in range(48, 58)]
alphabet = [chr(v) for v in range(65,91)]
alphanum = chiffres + alphabet
morse = dict(zip(alphabet, codes))
def dicoChiffrement():
dico = {'.':[], '-':[], '+':[]}
cles = '.-+'
possibilites = list(alphanum) # Copie de alphanum
for i in range(36):
valeur = choice(possibilites)
possibilites.remove(valeur)
dico[cles[i % 3]].append(valeur)
return dico
def chiffrePollux(phrase:str):
phrase = phrase.upper()
dico = dicoChiffrement() # Création du dictionnaire
chiffre = ''
for c in phrase:
if 'A' <= c <= 'Z':
codeMorse = morse[c] + '+'
codageLettre = ''
for v in codeMorse:
codageLettre += choice(dico[v])
chiffre += codageLettre
return chiffre, dico
def dechiffrePollux(chiffre:str, dico):
# Traduction chiffré vers Morse
enMorse = chiffre.upper()
for k, v in dico.items():
for c in v: enMorse = enMorse.replace(c, k)
# Traduction Morse vers message clair
clair = ''
cleMorse = list(morse.keys())
valMorse = list(morse.values())
for m in enMorse.split('+'):
if m != '':
clair += cleMorse[valMorse.index(m)]
return clair
def enColonne(chiffre):
for i in range(0, len(chiffre), 5):
if i % 4 == 0 and i > 0: print()
print(chiffre[i:i + 5], end='\t')
message = 'rendezvouscesoiravingtheuresplacevictorhugo'
chiffre, dico = chiffrePollux(message)
print('Texte chiffré :')
enColonne(chiffre)
print('\nDictionnaire utilisé :')
print(dico)
print('Déchiffrement :')
print(dechiffrePollux(chiffre, dico))
from random import randint
def grilleVide():
grille = []
for i in range(6):
ligne = []
for j in range(6): ligne.append('⬛')
grille.append(ligne)
return grille
def rotate(m, n):
for _ in range(n): m = list(zip(*m))[::-1]
return m
def afficher(g):
for l in range(6): print(''.join(g[l]))
def creerGrille():
grille = grilleVide()
m = [[6 * l + c for c in range(6)] for l in range(6)]
for c in range(3):
for l in range(3):
m = rotate(m, randint(0, 3))
pos = m[l][c]
x, y = pos % 6, pos // 6
grille[y][x] = '⬜'
return grille
def completeEtoiles(phrase):
return phrase + "*" * (9 - len(phrase) % 9)
def listeTrous(g):
trous = []
for l in range(6):
for c in range(6):
if g[l][c] == '⬜': trous.append(6 * l + c)
return trous
def chiffrer(phrase, grille):
phrase = completeEtoiles(phrase)
chiffre = grilleVide()
trous = listeTrous(grille)
for i, v in enumerate(phrase):
pos = i % 9
if pos == 0 and i > 0:
grille = rotate(grille, 1)
trous = listeTrous(grille)
x, y = trous[pos] % 6, trous[pos] // 6
if v == "*": v = chr(randint(65, 90))
chiffre[y][x] = v
return chiffre
def dechiffrer(crypte, grille):
clair = ''
trous = listeTrous(grille)
for i in range(36):
pos = i % 9
if pos == 0 and i > 0:
grille = rotate(grille, 1)
trous = listeTrous(grille)
x, y = trous[pos] % 6, trous[pos] // 6
clair += crypte[y][x]
return clair
grille = creerGrille()
afficher(grille)
phrase='RENDEZVOUSAQUINZEHEURESPLACELECLERC'
crypte = chiffrer(phrase, grille)
afficher(crypte)
clair = dechiffrer(crypte, grille)
print(clair)
# Substitution simple
def subSimple(phrase:str, decalage:int):
phrase = phrase.upper()
chiffrement = ''
for c in phrase:
if 'A' <= c <= 'Z':
position = (ord(c) - 65 + decalage) % 26
chiffrement += chr(65 + position)
else:
chiffrement += c
return chiffrement
# Substitution double (avec clé numérique)
def subDouble(phrase:str, decalage):
phrase = phrase.upper()
chiffrement = ''
longueur = len(decalage)
for i,c in enumerate(phrase):
if 'A' <= c <= 'Z':
position = (ord(c) - 65 + decalage[i % longueur]) % 26
chiffrement += chr(65 + position)
else:
chiffrement += c
return chiffrement
# Substitution avec mot-clé
def fabriqueAlphabet(cle:str):
lettres = list(cle.upper()) + [chr(v) for v in range(65, 91)]
alphabet = ''
for c in lettres:
if c not in alphabet: alphabet += c
tailleCle = len(set(cle))
alphabetFinal = ''
for col in range(tailleCle):
suiv = col
while suiv < 26:
alphabetFinal += alphabet[suiv]
suiv += tailleCle
return alphabetFinal
def subCleSimple(phrase:str,cle:str):
alphabet = fabriqueAlphabet(cle)
phrase = phrase.upper()
chiffrement = ''
for c in phrase:
if 'A' <= c <= 'Z':
chiffrement += alphabet[ord(c) - 65]
else:
chiffrement += c
return chiffrement
Python & Cryptographie niveau lycée : Déchiffrement des substitutions
def decryptSimple(phrase:str):
freq = [0] * 26
for c in phrase:
if 'A' <= c <= 'Z':
freq[ord(c) - 65] += 1
decal = 4 - freq.index(max(freq))
return subSimple(phrase, decal)
def decryptDouble(phrase:str, taille:int):
clair = ''
res = []
for i in range(taille):
res.append(decryptSimple(phrase[i::taille]))
return ''.join(''.join(v) for v in zip(*res))
def inverseAlphabet(chiffre:str, clair:str):
alphabetDecode = ''
for i in range(65, 91):
c = chr(i)
if c in chiffre: code = clair[chiffre.index(c)]
else: code = '?'
alphabetDecode += code
return alphabetDecode
def decryptEnPartie(phrase:str,alphabet:str):
alphabet = alphabet.upper()
phrase = phrase.upper()
chiffrement = ''
for c in phrase:
if 'A' <= c <= 'Z':
chiffrement += chr(65 + alphabet.index(c))
else:
chiffrement += c
return chiffrement
Exemples de textes :
clair = 'CHOISISSEZUNTRAVAILQUEVOUSAIMEZETVOUSNAUREZPASATRAVAILLERUNSEULJOURDEVOTREVIE'
# Clé numérique [3, 2, 1, 0]
crypte = 'FJPIVKTSHBVNWTBVDKMQXGWOXUBIPGAEWXPUVPBUUGAPDUBTUCWALNMEUWOSHWMJRWSDHXPTUGWIH'
# Extrait du livre "Le petit Prince"
princeClair = 'LESGRANDESPERSONNESMONTCONSEILLEDELAISSERDECOTELESDESSINSDESERPENTSBOASOUVERTSOUFERMESETDEMINTERESSERPLUTOTALAGEOGRAPHIEALHISTOIREAUCALCULETALAGRAMMAIRECESTAINSIQUEJAIABANDONNEALAGEDESIXANSUNEMAGNIFIQUECARRIEREDEPEINTREJAVAISETEDECOURAGEPARLINSUCCESDEMONDESSINNUMERO1ETDEMONDESSINNUMEROLESGRANDESPERSONNESNECOMPRENNENTJAMAISRIENTOUTESSEULESETCESTFATIGANTPOURLESENFANTSDETOUJOURSETTOUJOURSLEURDONNERDESEXPLICATIONSJAIDONCDUCHOISIRUNAUTREMETIERETJAIAPPRISAPILOTERDESAVIONSJAIVOLEUNPEUPARTOUTDANSLEMONDEETLAGEOGRAPHIECESTEXACTMABEAUCOUPSERVIJESAVAISRECONNAITREDUPREMIERCOUPDŒILLACHINEDELARIZONACESTTRESUTILESILONESTEGAREPENDANTLANUITJAIAINSIEUAUCOURSDEMAVIEDESTASDECONTACTSAVECDESTASDEGENSSERIEUXJAIBEAUCOUPVECUCHEZLESGRANDESPERSONNESJELESAIVUESDETRESPRESCANAPASTROPAMELIOREMONOPINIONQUANDJENRENCONTRAISUNEQUIMEPARAISSAITUNPEULUCIDEJEFAISAISLEXPERIENCESURELLEDEMONDESSINNUMERO1QUEJAITOUJOURSCONSERVEJEVOULAISSAVOIRSIELLEETAITVRAIMENTCOMPREHENSIVEMAISTOUJOURSELLEMEREPONDAITCESTUNCHAPEAUALORSJENELUIPARLAISNIDESERPENTSBOASNIDEFORETSVIERGESNIDETOILESJEMEMETTAISASAPORTEEJELUIPARLAISDEBRIDGEDEGOLFDEPOLITIQUEETDECRAVATESETLAGRANDEPERSONNEETAITBIENCONTENTEDECONNAITREUNHOMMEAUSSIRAISONNABLE'
princeChiffre = 'OGTGUCODHUQEUUPNQGTMRPUCRPTELNMEGGMALUTEUFFCRVFLHUEEVUJNVFFSHTQEQVTBRCTOXXFRWUPUIGSMHUFTGGNIQVFRHUTEURMUWQUAOCHERISASJJEDNIIVVPIUGBUFCMCXNFTDNBGUCNMDKSEFGTTDKOSLSVEMCJAECODRPOEDNBGHFFSLZBNVWOEPCHNLHJQXGDAUTJEUGEESGJNWTFJDXBIVGUEGGDOXTBGHRBROKOSXEDEVFFMRPEEVUJNQWNEUQ1EWFFMRPEEVUJNQWNEUQMEVISAQFFSSGSSRPOEVPFCROQRHPOEQVKAPCJSUKFNWQVTHUTEXNFSHVDEVVGAWKHAQVQOXTMEVGOFDPUSGGUOXLPUUUFTWQVJRWSSOGVRGQONHTEEVGYPOKDAWKPNVLBIGQOCGWDHRKTIUWOAXVSEPGUIHTFTMCJASRSIVCQIOQUEUFFSDXJOQUKALXPLHWOPHWQAUVPUWFBNVNFMRPEEHVMAJGPGUCQHLGDEVVFXDEUMDDFAXEPUSUFRYKKEVCWALUSEFQONDKURHFVPUGNIHTDOXREŒLNMAFJJNHFFLDTJZRPBCHUUTUGTUWKMEVKMOQGTTHIBRHRFNGCOTOCOULVKALCJNVKFUDWDOXTTDHOBVLGEEVVBSGGDOQVBCWUBVHEEEVVBSGGHEQUTEUKFUALBIEGBUFQVPYGDUFJFZOGTGUCODHUQEUUPNQGTJHNFSDKWUHUEEWTFSSTFSFCOASCTTUQQAPGMIRTFMRPPPLPJOQSVAQFKEQTFNFQOTUCJSXPFQXKNESCSALUTALVVNSGVLXEJDHLFFDKTALUMEARFRLGOCHUVRHNMEGGNOQFFSVKONXOFRR1RUHLBIWQVJRWSSFQOSHTWEMGWOXNBIVUBVRKSSLGMLHGUALVWRDKNEQVDOPRSEKGOSLXFMDKTTRWKOXTTEONFMHTFPRPEALVDEVVVNFJBPHCVAOQSSMGOEOWJPDTMALUOIGGTEURFNWUCODUOIGGGOUGUSYKFRJGTNLFFTRKMEVLFMHOFTWCJSDUBPRTUEHLFLXKQAUNBIVFFBUKEGHFFGRNGDHRPLLVJQXGFTGGDRDXBTHUFTOCHRDPEESGSSRPOEHVBIWDJEQEPNWGOTHFFCRPOALVSEXPIOPOFAXUTIUCJSRPOAENF'
Des propositions de simulations pour quelques calculatrices HP :
Le calcul théorique est très simple :
La réponse à trouver était donc : 5 mouvements
Version en Python
from random import random
def simul(n:int):
tot = 0 # Total de tous les mouvements
for _ in range(n): # n simulations
r = 1 # Dernier mvt de 2 vers 1
# Aller-retour de 2 vers 3 ou 4 avec probabilité 2/3
while int(3 * random()) != 0: r += 2
# On ajoute le nb de mvt au total
tot += r
# Moyenne
return tot / n
>>> simul(1000)
4.752
>>> simul(10000)
5.0992
>>> simul(100000)
4.98308
David, un collègue enseignant, a posté un tweet sur l’utilisation du mode de représentation Truth sur les anciennes calculatrices HP 48G. Voici son premier résultat, le tapis de Sierpinski :
Avec cette équation très courte :
Quelques explications : R→B permet de convertir un nombre en binaire. Pour chaque abscisse X (entre 0 et 63) et chaque Y (entre 0 et 63), on regarde s’ils ont au moins un bit en commun dans leurs écritures binaires respectives. Par exemple si X = 12 = 1100b et Y = 6 = 110b ont un bit en commun à la 3e position, on affiche dans ce cas un pixel noir à l’écran.
A partir de là j’ai trouvé la page Binary Plot du site Wollfram avec quelques visuels que j’ai voulu reproduire en Python.
Les puissances 3, 2 et 1 des entiers de 1 à 160
from kandinsky import *
for y in range(30):
n = 2 ** y
for x in range(160):
for i in range(3):
if x ** (i + 1) & n > 0:
fill_rect(2 * x, 214 - 63 * i - 4 * y, 2, 4, (0, 0, 0))
En Python il est très simple de faire des opérations bit à bit. Pour le “ET” on utilise &. Par exemple :
1100b AND 110b donne 100b = 4
Pour le “OU” le symbole est |. Par exemple 12 | 6 = 14 car 1100b | 110b = 1110b
Et le “OU EXCLUSIF” par ^. Par exemple 12 ^ 6 = 10 car 1100b ^110b = 1010b
Passons à la représentation des coefficients binomiaux :
Enfin, l’idée m’est venue de représenter la conjecture de Syracuse (on part d’un entier, s’il est pair on le divise par 2 sinon on le multiplie par 3 et on ajoute 1, la conjecture prétend que l’on arrivera à 1 au bout d’un certain temps). Avec N = 27 comme départ on arrive à 1 au bout de 111 itérations (appelé temps de vol) et le maximum atteint est 9232.
Représentons les termes de la suite sous forme binaire :
Suite de Syracuse en partant de N = 27
Il est alors assez facile de lire la valeur exacte de chacune des colonnes, par exemple du maximum. Il suffit de repérer les numéros de lignes (En bas = 0). Sur le visuel on lit les lignes 4, 10 et 13. Le nombre correspondant est donc 2^4 + 2^10 + 2^13 = 9232.
« X Y 1 + / 12 * COS Y 2 / SIN > » (En mode radians)
Version HD
sin(x * x / (y + 1) * 2) >= sin( y / (x + 1) * 10)
Version HD
sin(x / 8) % 1 > sin(y / 8) % 1
sqrt(x) % 1 >= sqrt(y) % 1
Tapis de Sierpinski
from kandinsky import *
def tapis(x, y):
while x > 0 and y > 0:
if x % 3 == 1 and y % 3 == 1: return 0
x //= 3
y //= 3
return 1
for y in range(222):
for x in range(320):
if tapis(x, y): set_pixel(x, 221 - y, (0,) * 3)
Version HD : 729 * 729 pixels (729 = 3^6)
@ Adaptation d'un script de David Cobac pour HP-48
« 3 PICK 3 MOD » 'MOD3 STO
« 3 / IP SWAP » 'IP3 STO
{ (0 0) (130 63) X 0 (0 0) TRUTH Y } 'PPAR STO
« X Y
WHILE DUP2 *
MOD3 MOD3 *
1 ≠ *
REPEAT
IP3 IP3
END
* NOT » 'EQ STO
« ERASE DRAW {} PVIEW » 'TAP STO
Lancez TAP
Version 2 :
« X Y
WHILE DUP2 DUP2
3 MOD SWAP 3 MOD
* 1 ≠ * *
REPEAT
3 / IP SWAP 3 / IP
END
* NOT »
Il y a une dizaine d’années certains internautes se sont amusés à créer des graphiques en secteurs originaux, voyons comment les reproduire en Python avec la TI-83
Le coin de ma chambre
2 murs et le sol
import ti_plotlib as plt
from ti_draw import *
from math import *
data = {-14: (143, 133, 133), 90: (158, 143, 133), 214: (93, 42, 40)}
def dec(l,n,u): return [v[n] + u for v in l]
def secteurs(data):
plt.cls()
o = (0, 0)
xy = [o]
mini = min(data.keys())
for i in range(mini, 361 + mini):
xy.append((cos(radians(i)) * 100, -sin(radians(i)) * 100))
if i in data.keys():
if i != mini: fill_poly(dec(xy, 0, 160), dec(xy, 1, 105))
set_color(*data[i])
xy = [o] + xy[-1:]
fill_poly(dec(xy, 0, 160), dec(xy, 1, 105))
secteurs(data)
show_draw()
Les données sont représentées sous la forme angle : couleur. Pour l’exemple ci-dessus, on part de l’angle -14° avec la couleur (143, 133, 133), on trace le secteur jusqu’à l’angle 90° puis on change de couleur, etc.
L’idée du programme est de tracer un polygone en partant du centre de l’écran (160, 105), la variable i parcourt les entiers allant de l’angle le plus petit (-14° dans l’exemple) jusqu’à faire un tour complet (360 – 14 = 346°). On mémorise dans la variable xy les coordonnées des points sur le bord du cercle de 1° en 1° et dès qu’il y a un changement de couleur on trace le polygone xy.
La pyramide
Même programme que précédemment mais en changeant data.
from p5 import *
from random import *
def setup():
createCanvas(600, 600)
background(20,20,20)
fill(10, 25, 10)
blendMode(SCREEN)
for x in range(30):
for n in range(1 + x):
rect(20 * x + randint(0,10), randint(-100,600), 80, 80)
def draw():
noLoop()
run()
Mode multiplier – NUMWORKS
from kandinsky import *
from random import randint
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(255 * v for v in c)
def zip01(c1,c2): return zip(rvb01(c1), rvb01(c2))
def multiply(c1,c2): return rvb255(a * b for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,mode):
for i in range(w):
for j in range(h):
rvb = mode(c, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
for x in range(0,320,8):
for y in range(0,220,3):
rect(x + randint(0, 7), y + randint(0, 6), \
randint(1, 320 - x), randint(1, 9), (250, 100, 250), multiply)
Mode différences – NUMWORKS et P5
# Version - NUMWORKS
from kandinsky import *
from random import *
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(int(255 * v) for v in c)
def zip01(c1,c2): return zip(rvb01(c1),rvb01(c2))
def diff(c1,c2):
return rvb255(abs(a - b) for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,mode):
for i in range(w):
for j in range(h):
rvb = mode(c, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
fill_rect(0,0,320,222,(250, 100, 250))
for _ in range(500):
t = randint(20,40)
rect(randint(-10, 315), randint(-10, 220), t, t, (250, 100, 250), diff)
# Version P5 - Python
from p5 import *
from random import *
c = (250, 100, 250)
def setup():
createCanvas(900, 600)
background(c)
blendMode(DIFFERENCE)
fill(c)
for _ in range(1000):
t = randint(20,80)
rect(randint(-20,900), randint(-20,600), t, t)
def draw():
noLoop()
run()
Mode addition – NUMWORKS
from kandinsky import *
from random import *
from math import cos
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(int(255 * v) for v in c)
def zip01(c1,c2): return zip(rvb01(c1),rvb01(c2))
def add(c1,c2):
return rvb255(min(1,a+b) for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,mode):
for i in range(w):
for j in range(h):
rvb = mode(c, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
fill_rect(0,0,320,222,(40,40,40))
for i in range(50):
rect(randint(-20,300), randint(-20,200), 60, 60,\
(randint(0,255), randint(0,255), randint(0,255)), add)
TISSU écossais – p5
Cet exemple a été supprimé au montage de la vidéo:
from p5 import *
def setup():
createCanvas(770, 770)
noStroke()
background((40,40,40))
blendMode(SCREEN)
fill(20, 40, 20)
for i in range(10):
for j in range(10):
rect(60 * i, 60 * j, 50 + 20 * i, 50 + 20 * j)
def draw():
noLoop()
run()
MODE addition – p5 et NUMWORKS
from p5 import *
from random import *
def setup():
createCanvas(800, 400)
noStroke()
background((50,50,50))
blendMode(ADD)
fill(20, 140, 20)
x, y = 200, 0
for i in range(100):
textSize(1 + i)
x -= 2
y += randint(-5,11)
fill(20, 140, 20)
if random()<.2: fill(255, 0, 0)
text('PROGRAMMATION', x, y)
def draw():
noLoop()
run()
from kandinsky import *
from random import *
BL, WH = (0, 0, 0), (255,) * 3
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(int(255 * v) for v in c)
def zip01(c1,c2): return zip(rvb01(c1),rvb01(c2))
def screen(c1,c2):
return rvb255(1 - (1 - a) * (1 - b) for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,mode):
for i in range(w):
for j in range(h):
rvb = mode(c, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
def dot(x, y, c, fg, t):
draw_string(c, 0, 0, fg, (0,0,0))
for v in range(18):
for u in range(9):
rect(x + u * t, y + v * t, t, t, get_pixel(u, v), screen)
def aff(txt, x, y, t):
coul = (255, 0, 0)if random()<.3 else (20, 140, 20)
for i, c in enumerate(txt):
dot(x + i * t * 9, y, c, coul, t)
fill_rect(0,0,320,222,(50,50,50))
x, y = 150, -30
for i in range(80):
x -= 2
y += randint(1,4)
aff("PROGRAMMATION", x, y, i//20)
fill_rect(0,0,20,20,(50,50,50))
Dégradés – NUMWORKS
from kandinsky import *
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(int(255 * v) for v in c)
def zip01(c1,c2): return zip(rvb01(c1),rvb01(c2))
def alpha(c1, t, c2):
return rvb255(a * t + b * (1 - t) for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,d):
(dx,dy) = d
for i in range(w):
for j in range(h):
t = 1
if dx == 1: t = 1 - i / w
elif dx == -1: t = i / w
if dy == 1: t = 1 - j / h
elif dy == -1: t = j / h
rvb = alpha(c, t, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
rect(0, 0, 200, 200, (255, 0, 0), (1,0))
rect(0, 0, 200, 200, (0, 255, 0), (0,1))
rect(0, 0, 200, 200, (0, 0, 255), (-1,0))
Effet alpha – NUMWORKS
from kandinsky import *
from random import randint, choice
coul = (255,0,255), (255,255,0), (255,127,0), (255,0,127)
def rvb01(c): return tuple(v / 255 for v in c)
def rvb255(c): return tuple(int(255 * v) for v in c)
def zip01(c1,c2): return zip(rvb01(c1),rvb01(c2))
def alpha(c1, t, c2):
return rvb255(a * t + b * (1 - t) for (a, b) in zip01(c1,c2))
def rect(x,y,w,h,c,t):
for i in range(w):
for j in range(h):
if i == 0 or j == 0 or i == w - 1 or j == h - 1:
rvb = (255,255,255)
else:
rvb = alpha(c, t, get_pixel(x + i, y + j))
set_pixel(x + i, y + j, rvb)
def effet(t):
for _ in range(150):
x, y = randint(-10,300), randint(-10,200)
w, h = randint(10,80), randint(10,80)
rect(x,y,w,h,choice(coul),t)
effet(0.15)
Suite à ma vidéo d’initiation à JavaScript concernant la recherche de mots (palindromes, anacycliques, mots croissants…), je vous propose ici les traductions en Python
Importer les dictionnaires
Enregistrez le fichierdicos.py dans un dossier et créez un fichier recherche.py dans ce même dossier avec pour contenu :
import dicos
print(len(dicos.dico5))
En exécutant le fichier vous devriez voir le nombre 7276 qui correspond au nombre de mots de 5 lettres.
Mots en sens inverse et palindromes
import dicos
def inverse(mot):
return mot[::-1]
def palindrome(dico):
return [mot for mot in dico if mot == inverse(mot)]
Yann Le Du m’a fait découvrir via Twitter l’existence du langage K (première version en 1992 !), dont les caractéristiques sont proches de l’APL.
Cette page me servira de mémo pour noter mes découvertes et compréhensions de ce langage (appelé également Shakti). Ce n’est donc pas un cours mais juste des notes personnelles que je partage librement avec vous.
➡ Références que je vais utiliser : En ligne | PDF
📲 J’ai également une page spéciale consacrée à oK Mobile, une autre version de K.
Quelques challenges Twitter
J’avais proposé sur Twitter (menu Challenges Twitter en haut de ce blog) de résoudre quelques petits exercices en Python, JavaScript ou APL. C’est à cette occasion que Yann Le Du (YLD) a donné ses propres solutions en K. Essayons de décrypter ses réponses !
Isogrammes (Challenge n°3)
Un isogram (En français on parle d’heterogramme) est un mot qui ne contient aucune lettre répétée. Ecrire une fonction qui renvoie vrai ou faux suivant que le mot est un heterogramme, sans tenir compte de la casse (majuscule/minuscule)
L’opérateur ?, dans sa forme monadique, correspond à l’union (éléments pris de façon unique)
? "abracadabra"
"abcdr"
Sous sa forme dyadique, il permet de générer des nombres aléatoires, par exemple tirer 10 nombres aléatoires entre 0 et 2 :
10 ? 3
2 1 2 2 2 0 1 1 2 0
L’adverbe \: s’appelle “Converge scan” et /: “Converge over”. Les 2 vont répéter les calculs jusqu’à arriver à une convergence (dans le sens : le terme suivant est égal au terme précédent). On peut également imposer le nombre d’itérations :
{1+1%x}/:1 / u(n+1) = 1 + 1 / u(n) en partant de u(0) = 1
1.618034 / Affichage du résultat final (Nombre d'or)
(5;{1+1%x})/:1 / 5 itérations uniquement
1.625
{1+1%x}\:1 / Affichage des résultats intermédiaires
1
2.
1.5
1.666667
1.6
1.625 / On retrouve la 5e itération
1.615385
1.619048
1.617647
1.618182
...
1.618034
?\:"abracadabra"
abracadabra
abcdr
Par contre / (reduce) et scan (\) sont similaires à l’APL :
+/ 1 2 3 4 / Réduction par la somme
10
=/ 2 2 1 / 2 = 2 est Vrai puis Vrai = 1 est Vrai
1
=/ 2 3 0 / 2 = 3 est Faux puis Faux = 0 est Vrai
1
+\ 1 2 3 4 / Scan par la somme : 1, 1+2, 1+2+3, 1+2+3+4
1 3 6 10
L’adverbe ‘ signifie “pour chaque”, par exemple compter le nombre de lettres de chaque mot :
#' ("bonjour";"tout";"le";"monde")
7 4 2 5
Signification du code de YLD sur un exemple :
=/#'?\:_ "moOse" / moOse est-il un isogram ?
0 / Réponse = non
Etapes :
_ "moOse" / Mettre le mot en minuscules
"moose"
?\:_ "moOse" / Répéter "Union" jusqu'à valeur stable
moose / Il y aura donc le mot du départ
emos / et le mot sans doublon
#'?\:_ "moOse" / Chercher les tailles des 2 mots
5 4
=/#'?\:_ "moOse" / Ces tailles sont-elles identiques ?
0 / si oui c'est un isogram
Gimme (Challenge n°2)
Résumé en français : On vous donne 3 nombres différents dans un ordre quelconque. En sortie, donnez le rang du nombre qui est entre les 2 autres. Par exemple avec 2, 3, 1 c’est le chiffre 2 qui est entre 1 et 3, son rang dans 2, 3, 1 est 0.
Solution proposée par YLD :
gimme:*1_<
gimme 5 10 14
1
L’opérateur de tricroissant< fonctionne comme en APL :
< 14 5 10
1 2 0
/ Le plus petit nb est à la position 1, c'est le 5
/ Le second nb est à la position 2, c'est le 10
/ Le plus grand est à la position 0, c'est le 14
En version dyadique, _ permet d’enlever des éléments au début ou à la fin d’un tableau :
2_ 4 5 6 7 8 / On enlève les 2 premiers éléments
6 7 8
-2_ 4 5 6 7 8 / On enlève les 2 derniers éléments
4 5 6
En version monadique, * récupère le premier élément d’un tableau :
* 4 5 6 7
4
Signification du code de YLD sur un exemple :
*1_< 8 5 12
0
Etapes :
< 8 5 12 / Tri du tableau
1 0 2 / L'élément du milieu sera à la position 0
1_< 8 5 12 / Pour récupérer ce nb on supprime le 1er élément
0 2
*1_< 8 5 12 / Et on prend le premier élément du tableau
0
Positions des mots (Challenge n°6)
Résumé en français : Vous devez créer un programme qui à partir d’une phrase, met tous les mots distincts dans une liste et retourne une chaine donnant les positions des mots de la phrase initiale dans cette liste. On ne tiendra pas compte de la casse.
Solution proposée par YLD :
,/$'s?s:" "\_
compress:{,/$'s?s:" "\_x}
En version dyadique, \ permet de faire un scan, également de séparer une chaine suivant un caractère (split) mais aussi d’écrire un nombre dans une base quelconque !
2 +\ 4 5 6
6 11 17 / 2+4, 2+4+5, 2+4+5+6
","\ "bonjour,tout,le,monde" / split avec ','
bonjour
tout
le
monde
10\ 3574 / Décomposition de 3574 en base 10
3 5 7 4
2\ 35 / Décomposition de 35 en base 2
1 0 0 0 1 1
Nous avons vu ? en version monadique (Union ou nombres aléatoires), en version dyadique x?y permet de trouver l’index de y dans le tableau x :
5 7 8 6 ? 7 5 / Positions de 7 et de 5 dans le tableau 5 7 8 6
1 0 / 7 est à la position 1 et 5 à la position 0
s:"abcabc" / affectation de la chaine "abcabc" dans s
s?s
0 1 2 0 1 2
$ transforme, en version monadique, un nombre en chaine. L’opération inverse s’effectue via l’opérateur . :
$ 123 / Transformation d'un nombre en chaine
"123"
."123" / Transformation d'une chaine en nombre
123
."2+5" / Evaluation
7
Signification du code de YLD sur un exemple :
,/$'s?s:" "\_ "un deuX un Trois UN deux"
"010301"
Etapes :
_ "un deuX un Trois UN deux" / En minuscules
"un deux un trois un deux"
" "\_ "un deuX un Trois UN deux" / Split avec " "
un
deux
un
trois
un
deux
s:" "\_ "un deuX un Trois UN deux" / Affectation dans s
s?s:" "\_ "un deuX un Trois UN deux" / Positions des éléments
0 1 0 3 0 1
$'s?s:" "\_ "un deuX un Trois UN deux" / Conversion en chaine
0
1
0
3
0
1
,/ $'s?s:" "\_ "un deuX un Trois UN deux" / Concaténation
"010301"
Paires de gants (Challenge n°10)
Résumé en français : On vous donne une liste contenant des couleurs de moufles (donc pas de main gauche ou droite à distinguer). On vous demande le nombre de paires que vous pouvez constituer, c’est-à-dire avoir 2 moufles de la même couleur.
Solution proposée par YLD :
+/\:(0=)_div#'=
Pour grouper les indices d’un tableau à partir des valeurs, on utilise =.
= 8 5 8 8 5 3 / On groupe les indices à partir des valeurs
3|,5
5|1 4
8|0 2 3
= "abracadabra"
a|0 3 5 7 10
b|1 8
c|,4
d|,6
r|2 9
La fonction mathématique div permet d’effectuer une division entière :
3 div 17 / division entière de 17 par 3
5
div 17 / division entière par 2
8
Pour filtrer un tableau, on utilise # ou _ :
notes: 5 12 10 6 19 3 / Notes d'élèves
(10>)_ notes / on supprime les notes inférieures à 10
12 10 19
Tableau de symboles :
s:`red`blue`green
s@1 / élément à la position 1 (ou encore s[1])
`blue
Signification du code de YLD sur un exemple :
+/\:(0=)_div#'=`red`red`blue`red`blue`green
[blue:1;red:1]
2
Etapes :
=`red`red`blue`red`blue`green / Répartition des indices
blue |2 4
green|,5
red |0 1 3
#'=`red`red`blue`red`blue`green / Effectifs
blue |2
green|1
red |3
div#'=`red`red`blue`red`blue`green / Division par 2
blue |1
green|0
red |1
/ On supprime les restes qui sont nuls
/ "green" ne permet pas de faire au moins une paire
(0=)_div#'=`red`red`blue`red`blue`green
blue|1
red |1
/ On utilise ou non \: pour avoir le détail puis réduction par la somme
+/(0=)_div#'=`red`red`blue`red`blue`green
2
Explosion (challenge n°12)
Résumé en français : On vous donne une chaine de caractères composée de “chiffres” (‘0’ à ‘9’). Vous devez écrire une fonction qui renvoie une chaine où chaque chiffre est répété le nombre de fois correspondant à sa valeur. Par exemple avec la chaine “312”, on doit répéter 3 fois le “3”, 1 fois le “1” et 2 fois le “2”, ce qui donne la chaine “333122”.
Solution proposée par YLD :
s@&10\. s:
Nous reconnaissons l’affectation s:, la conversion . d’une chaine en numérique, la décomposition d’un nombre en base 10. Il reste à comprendre & et @.
& (where) permet de répliquer les indices d’un tableau autant de fois que les valeurs indiquées dans ce tableau. Exemple :
& 4 3 0 2 / Répéter 4 fois l'indice 0, 3 fois l'indice 1...
0 0 0 0 1 1 1 3 3
notes: 5 10 15 9 13 8 / Notes d'élèves
notes<10 / Positions des élèves n'ayant pas la moyenne
1 0 0 1 0 1
¬es<10 / Indices correspondants
0 3 5 / Les élèves n°0, 3 et 5 n'ont pas la moyenne
& 1 0 0 1 1 / Plus généralement, avec un tableau binaire
0 3 4 / on récupère les positions des "1"
x@y donne la valeur qui est à l’indice y du tableau x :
"sujet"@ 2 1 0 4 3 / Lettres aux positions 2,1,0,4 et 3
"juste"
Signification du code de YLD sur un exemple :
s@&10\. s:"102269"
"12222666666999999999"
s:"102269" / Mémorisation de la chaine dans "s"
. s:"102269" / Conversion en nombre
102269
10\. s:"102269" / Décomposition en base 10
1 0 2 2 6 9
&10\. s:"102269" / On réplique les indices suivant les valeurs
0 2 2 3 3 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5
/ Pour finir on récupère à partir de "s" le caractère à la position 0
/ puis 2 fois celui à la position 2, 2 fois celui à la position 3
/ 6 fois celui à la position 4 et 9 fois celui à la position 5
/ On obtient bien 1,22,22,666666,999999999
Misez p’tit Optimisez en version K
Sur le forum de Silicium, j’avais proposé différentes solutions de challenges (à l’origine pour des calculatrices de poche programmables) en version APL. Je vais en reprendre quelques uns et voir ce que cela peut donner en K.
MPO 9 : Somme des chiffres
Calculer la somme des chiffres d’un nombre. Par exemple : 352791 doit retourner 27
On a tout ce qu’il faut ! $ pour transformer un nombre en chaine, . pour faire l’inverse, la réduction +/ et ‘ qui signifie “pour chaque” :
MPO9: +/.'$
MPO9 352791
27
Tout aussi court, on peut utiliser la décomposition en base 10:
MPO9: +/10\
MPO9 352791
27
Si maintenant on veut continuer le processus jusqu’à obtenir un chiffre entre 0 et 9, par exemple :
352791 -> 27 -> 9
Il suffit d’utiliser /: ou \: pour créer la boucle :
(+/10\)\: 352791 / Affichage des résultats intermédiaires
352791 27 9
(+/10\)/: 352791 / Uniquement résultat final
9
MPO1 : Evaluation d’un polynôme
Il s’agit d’évaluer le polynôme P(x)=3x^3+4x^2+x+9 en une valeur donnée en paramètre.
Cela revient à convertir le tableau 3 4 1 9 en base x, d’où :
On vous donne une liste de hauteurs d’immeubles adjacents et on vous demande combien seront visibles si vous les regardez à partir de la gauche. Par exemple, si les hauteurs sont 2 3 5 2 1 6 4, en vert ci-dessous les 4 seuls immeubles qui seront visibles (les autres sont cachés par des bâtiments plus hauts)
On supposera dans un premier temps qu’il n’y a pas de zones vides entre les immeubles, c’est-à-dire que la liste ne contient pas de 0 (immeubles de hauteur nulle).
Dans un second temps, considérez le cas général.
L’OVNI scannera 4 immeubles
Je reprends le corrigé que j’avais mis sur Silicium mais en version K :
On va déjà scanner les immeubles pour récupérer les hauteurs maximales atteintes :
|\ 2 3 5 2 1 6 4 / On cherche les max progressivement
2 3 5 5 5 6 6
Il faut maintenant récupérer les hauteurs distinctes :
?|\ 2 3 5 2 1 6 4
2 3 5 6
Et les compter :
#?|\ 2 3 5 2 1 6 4
4
Le programme final :
scan:#?|\
scan 2 3 5 2 1 6 4
4
Si la liste commence par un ou plusieurs 0, le calcul sera faux :
scan 0 2 1
2
Ceci parce que les maximums progressifs sont { 0 2 2 } dont la réunion comporte 2 termes {0 2}. Il faut donc filtrer la liste des maximums pour enlever les 0.
(0=)_ 0 0 2 3 5 5 / Signifie enlever ceux égaux à 0
2 3 5 5
