Un mème en Python

 

Pattern Lock - Combien de combinaisons ?

Allez tiens, un bon post bien geek aujourd'hui. Franchement si vous n'êtes pas fan de combinatoire et de python ne perdez pas trop de temps à lire… En échange je vous mets le clip de Djiin. (*)

Alors un midi comme ça on discutait des schémas de déverrouillage pour smartphones. Ces glyphes qu'on trace du doigt pour dire à notre smartphone que c'est bien nous. On s'est demandé combien de combinaisons ça pouvait bien faire. L’intuition ambiante oscillait entre pas tant que ça et pas bézef.

Posons un peu mieux le problème

On a neuf touches, numérotées de un à neuf. Attends je vérifie... ouais c'est ça, neuf. On fixe la longueur max du code à huit mouvements, j'expleek pourquoi plus loin. La longueur minimum c'est zéro mouvement. Zéro mouvement ça correspond au gros fainéant qui appuie juste sur une touche et fait même pas glisser son doigt. J'ai honte pour lui.

D’abord le cas simple

Le cas le plus facile à calculer c'est quand il n'y a pas de contrainte particulière : on peut aller d'une touche vers n'importe quelle autre touche, on peut repasser plusieurs fois par une même touche. Ben oui c'est simple parce qu’on choisit une touche de départ (neufs possibilités) et de là on peut glisser vers n'importe quelle autre touche. À chaque étape il y a donc huit mouvements possibles. En tout il existe 9 codes de longueur zéro, plus 9 x 8 codes de longueur un, plus 9 x 8 x 8 codes de longueur deux, etc. Jusqu'à la longueur maximale fixée à huit mouvements, j'expleek pourquoi plus loin, je l'ai déjà dit. Je nous fais les multiplication et les sommes gratuitement et ça donne cent soixante-douze million cinq cent soixante-cinq mille six cent quarante combinaisons. De quoi voir venir, surtout si le téléphone se bloque genre trente secondes au bout de cinq essais. Faut près d'un siècle pour tout essayer, et encore, en dormant pas beaucoup.

Maintenant le cas intéressant

En prateek tous les mouvements ne sont pas nécessairement autorisés. On s'est demandé combien il y avait de combinaisons lorsque premièrement on interdit de réutiliser une touche et deuxièmement on n'autorise que les mouvements vers des touches contiguës (**). Voir croquis.

On peut remarquer que sous ces conditions la longueur maximale d'un code est huit mouvements. En effet, au bout de huit mouvements, toutes les touches ont été visitées une fois chacune. Voilà, je l'avais bien dit que j’expleekerai plus loin.

Alors je vous donne direct le résultat. Des codes comme ça il n'y en a que : dix mille trois cent cinq. Soit à peine plus que des PIN codes de carte bancaire à quatre chiffres. C'est peu : en même pas une semaine on peut tout essayer, et encore, en dormant bien. Marrant, à l'intuition j'aurais cru qu'il y avait encore moins de combinaisons que ça. À la louche j’aurais dit quelques centaines pas plus. Je me foutais donc le doigt dans l’œil sur deux ordres de grandeurs. Ça va, j’ai fait pire…

Un bout de python pour calculer ça

Le calcul n'est pas aussi direct que dans le cas simple. C’est même carrément coton. Pas moyen de trouver une formule explicite. Du coup j'ai fait un bout de python pour énumérer tout ça. Je vous le copie-colle ici et j'expleek après.

Version texte à la fin du post (si quelqu'un sait comment utiliser pygmentize dans blogspot, je veux bien un coup de main)

Quelques remarques sur le bout de python

1) Je n'ai pas mis le programme sur github. Ouais, j'aime bien à l'ancienne, copié-collé crade direct dans le post.

2) Je n’ai pas mis non plus de licence particulière. En fait c'est un Metallurgeeciel: tu peux en faire ce que tu veux mais je veux bien qu'on aille se boire une bière.

3) Les variables et les noms de fonctions font tou.t.e.s exactement quatre caractères. Un vieux T.O.C. ça m’a pris en classe de cinquième ça finira bien par passer. Dans le même esprit les commentaires sont tous obsessionnellement alignés au caractère près. Et le score sous pylint est de 10.00/10, comme quoi je respecte la PEP8 au pied de la lettre.

4) Les remarques 1) 2) et 3) n'ont rien à voir avec l'algorithme et le sujet du post. La remarque 4) non plus.

5) La fonction "code(path, many)" lignes 9-15 prend le début d'un code en argument et compte les suites possibles. Pour ça elle s'appelle récursivement autant de fois qu'il y a de mouvements possibles. Le programme connait par cœur les mouvements possibles à partir d'une touche. C'est à ça que sert le dictionnaire "MOVE" lignes 3-7. On est confiant que la récursion terminera car à chaque appel une nouvelle touche est visitée et des touches y en a que neuf (attends je vérifie... ouais c'est ça, neuf)

6) Pour faire moins de calculs, j'utilise le fait qu'il n'y a que trois sortes de codes : ceux qui commencent par un coin (touches 1, 3, 7, 9), ceux qui commencent par un milieu (touches 2, 4, 6, 8) ou ceux qui commencent pile par le centre (touche 5).

7) Du coup, je calcule le nombre de codes possibles en partant du coin 1 et le nombre de codes possibles en partant du milieu 2. Ces nombres là je les multiplie par quatre parce qu'il y a quatre coins et quatre milieux. Reste à ajouter le nombre de codes qui commencent par le centre.

8) On peut aussi calculer tous les chemins sans exploiter les symétries. C’est ce que fait la ligne 18 en commentaire. Truc de ouf, on trouve le même résultat.

Conclusion

Si le téléphone prend ton empreinte digitale et analyse ton ADN pendant que tu traces le code, et ben le nombre de combinaisons on s'en fout un peu.

Le programme à copier-coller

'''Pattern locks on a 9 digits keypad with just vert/horiz/diag moves and no digit reuse.'''

MOVE = {

    '1':'254', '3':'652', '9':'856', '7':'458',                 # Possible moves from corner

    '2':'36541', '6':'98523', '8':'74569', '4':'12587',         # Possible moves from middle

    '5':'12369874'                                              # Possible moves from center

    }

def code(path, many):                                           # Recursively research paths

    '''Count the codes starting with some path.'''

    #print(path)                                                # Un-comment for enumeration

    for move in MOVE[path[-1]]:                                 # Extend path with netx move

        if not move in path:                                    # Bypass already used digits

            many = code(path+move, many+1)                      # Count one path and recurse

    return many                                                 # Return the number of paths

print(code('1', 1)*4+code('2', 1)*4+code('5', 1), __doc__)      # 4 symmetries except center

#print(sum([code(base, 1) for base in MOVE.keys()]), __doc__)   # Alternate counting formula

(*) Djiin avec deux "i" comme dans Giin Tooneek (ta race).

(**) Contiguës ça s'écrit exactement comme Noël, sauf tu mets un C au début comme dans "Christmas".

La fonction identité en python

Même Disney fait du Python.

Allez, un post geek pour changer. Si le blabla vous fait chier, sautez directement à la section "Codage de la fonction identité en python" où vous trouverez - c’est dingue - plusieurs manières de coder la fonction identité en Python. D’ailleurs, si vous connaissez d’autres méthodes, je suis preneur.

La fonction Identité

La fonction identité c’est la fonction qui renvoie ses arguments tels quels, sans rien changer. Par exemple la fonction identité à un seul argument sur l’ensemble E est définie par Id : E -> E, Id(x) = x.

J’adore la fonction identité pour plusieurs raisons. Tout d’abord, cette fonction ne sert à rien. Je veux dire à rien de concret, rien de commercial, rien de monnayable. Moi, les trucs qui servent à rien de concret, j’adore ça ! Supposons qu’on ait déjà quelque chose noté x et bien c’est totalement inutile de lui appliquer en plus une fonction Id qui le transforme en lui-même. C’est un peu comme frotter une lampe mageek et, quand le génie nous demande un uneek vœu, on lui dit "que rien ne change". Puissant !

Ensuite j’aime bien la fonction identité parce qu’elle sert quand même à des trucs théoreeks (et qui donc ne servent à rien de concret). Par exemple, la fonction identité sert d’élément neutre pour la composition des fonctions. Genre : f ° Id = f, où ° est l’opérateur de composition. Et c’est neutre à gauche aussi : Id ° f = f. Palpitant ! Si je défini fⁿ comme la composée n fois de f, genre f ° f ° … ° f ° f et bien on a f⁰ = Id. À vue de pied, quand on a une composition, un élément neutre et l’associativité on a une structure de monoïde, et ça, ça peut toujours être utile (ou pas).

Enfin, on peut utiliser la fonction identité pour obfusquer du code source. Obfusquer ça consiste essentiellement à rendre illisible (Un peu comme Metallurgeek :). Ça sert vaguement en sécurité informateek. Certes, il existe des tonnes d’autres méthodes, mais justement la variété des méthodes utilisées participe à la qualité de l’obfuscation. Donc, n’ayant vraiment rien à foutre de mieux, je me suis amusé à coder la fonction identité en Python, de plusieurs manières différentes. En voici des échantillons. Si vous avez d’autres idées je suis preneur.

Codages de la fonction identité en python

def Id01(x):

    return ([x][0])

def Id02(l):

    return [e for e in l]

def Id03(0):

    0-=-0

    return 0/2

def Id04(l):

    return l[::-1][::-1]

def Id05(l):

    try:

        return [l[0]] + Id05(l[1:])

    except:

        return []

Id06(x) = lambda x:

On peut appliquer l’identité au nombre 42 dont je vous parlerai dans un autre billet, nous avons donc : Id01(42)=42. Ce qui est une bonne chose parce que s’il y a bien un truc auquel il ne faut pas toucher c’est le nombre 42. On peut même appliquer l’identité à la fonction identité elle-même, et ça redonne quoi ? La fonction identité. Id01(Id01) == Id01. Grandiose !

Liste à trous en Python

L’autre nuit, j’avais besoin de fabriquer des listes à trous. Me demandez pas pourquoi, ça m’a pris comme ça… Plus précisément, il me fallait des listes de longueur arbitraire, se finissant par une plage de trous, commençant par une première partie avec les entiers dans l’ordre et juste une certaine proportion de trous.

Si j’avais représenté les trous par des zéros ça aurait donné ça par exemple : [1, 2, 3, 0,  5, 6, 0, 8, 9, 10, 11, 0, 0, 0, 0, 0, 0, 0]. Ou alors ça [1, 2, 3, 4, 5, 6, 7, 0, 8, 9, 10, 11, 12, 13, 0, 14, 15, 16, 17, 18, 0, 0, 0]. Le genre simple et de bon goût. Et on aurait été vite couché.

...

Ouaip.

...

Seulement voilà, j’ai décidé de représenter les trous par la valeur booléenne vraie. Qui se dit True en Python. Tout ça pour faire une « liste à True ». Je vous dis pas après, le reste du code qui utilise ce genre de liste, comment c’est crade ! Mais bon, « liste à True » franchement, ça valait la peine ! (ou pas).

Voici le code de génération de la liste. long désigne la taille de la liste. coef désigne l’inverse de la densité de trous dans la première partie de la liste. stop désigne la fin de la première partie de la liste(*). Par défaut la valeur de stop est choisie au hasard.

from random import randintdef

listeàTrue(long=32, coef=4, stop=0):

  stop=stop or randint(1, long-1)

  return [1]+[(not randint(0, coef) or i+2) for i in range(stop)]+[True]*(long-stop-1)

print(listeàTrue(256, 10, 128))

Ah oui, ça me revient maintenant pourquoi j’avais besoin de ça : c’était pour tester un truc. Parce que je suis geek. Et les geeks, ça teste des trucs. Toute ressemblance avec un réplique de Merlin dans Kaamelott Livre VI(**) serait parfaitement volontaire.

(*) Ma vielle obsession des noms de variables faisant pile 4 lettres. Il y en a 456976, en général ça suffit.
(**) Je rappelle que "Livre VI" ça se lit "Livre 6" et pas "Livre Vie-Aïe".