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".
