Deux fois triste

Aujourd'hui mon coeur de métalleux saigne pour Ozzy Osbourne. Aujourd'hui mon coeur de geek saigne pour Gilles Dowek.

L'un des deux fut mon professeur en logique et théorie des languages. L'autre fut mon professeur en défonce et surdité. Je vous laisse deviner lequel est lequel.

Quand IA rien à faire

Voici l'écran que j'ai eu ce matin en me connectant à Google Gemini. Vous je ne sais pas, mais moi, qu'une IA soit capable de rien foutre ça me rassure. Fortement.

Herbe rêves-tu ?

Herbe rêves-tu ?

Je dis ça je dis rien

 

Avogadro, prêts, partez !

Que vaut 3,01107038 . 10²³ ?

Ouaip, une demi-mole.

Etonnant d'ailleurs que le terme "3,01107038" ne sorte que 2 fois sur Google et 5 fois sur Bing (2020/11/27)

1984 1984 1984 1984

La nuit dernière au lieu de hacker des trucs, je cherchais la version texte du roman 1984(*).

Chercher 1984

Pas trivial à dénicher mais pas trop compliqué non plus. Ma méthode préférée c'est 1) Je choisi un extrait caractéristeek et plutôt vers la fin du texte, 2) Je soumets cet extrait entre guillemets à un moteur de recherche, 3) Je vois ce qui remonte je sauvegarde tout ça. Et là je commence à réfléchir un peu.

4 fois 1984

L'extrait que j'ai choisi c'est but still noticing the astonishing difference in demeanour. Ce qui remonte, ce sont (notamment) quatre versions texte. Dont celle du projet Gutenberg Australien et celle de Archive.org, mais en fait peu importe la provenance. Ce qui importe c'est que j'ai sous la main quatre versions texte du même roman. Saisi d'un féroce accès d'originalité j'ai nommé les quatre fichiers 1984-1.txt 1984-2.txt 1984-3.txt et 1984-4.txt.

En toute naïveté, on aurait envie que les quatre fichiers soient parfaitement identeeks. Et si les fichiers ne sont pas identeeks, c'est par exemple qu'un des fichiers contient une coquille. Ou une erreur de numérisation ou d'impression ou de retranscription. Bref, si c'est différent ça découvre un petit bug, un truc potentiellement intéressant (**).

Comparaison n'est pas...

En fait, l'idée naïve que les fichiers doivent être identeeks, est quasiment la bonne. il faut juste effectuer quelques ajustements préalables. En gros, pour comparer les versions, il va falloir "normaliser" le texte. En effet, chacune des versions saute des lignes à sa manière, césure les mots ou pas, laisse les numéros de pages ou pas, inclue les annexes ou pas, etc.

Pour l'instant j'ai normalisé deux textes seulement. Ceux qui s'y prêtaient le mieux. Et la comparaison ne fait apparaitre qu'une seule différence. Dans l'une des versions, le mot his est doublé dans she was in his his arms. Intéressant non ? (**).

Je me demande bien ce qui a pu faire que le his est doublé dans cette version précise. Et je trouve génial que l'uneek différence tombe pile sur cette phrase là. Parce qu'elle est très belle cette phrase là. Tiens je te mets une copie d'écran sinon tu ne me croiras jamais. Et je reviens je-sais-pas-quand, au moment où j'aurai réussi à normaliser les deux autres versions.

Tu la vois la différence ?

(*) Une petite farce désopilante de George Orwell, je cherchais ça pour alimenter un prochain billet sur Metallurgeek.

(**) Alors oui, à ce stade je me dis que vous si êtes assez tordus pour avoir lu jusqu'ici, alors la découverte d'une minuscule différence entre des versions d'un même texte vous semblera intéressante. Et après on dit que c'est moi qui suis taré, pffff...

MIP*=RE !!!!

La théorie ça avance lentement, mais askip quand ça avance c'est juste violent ! Le résultat MIP*=RE vient de tomber. Je ne pensais pas voir ça de mon vivant. La dernière fois que j'ai pris des pieds(*) pareil c'était pour PRIMES is in P et au London Science Museum.

Le papier est là : https://arxiv.org/abs/2001.04383. Par contre, si quelqu'un se sent de me faire un petit résumé en deux deux je veux bien. Parce que là j'en suis à qu'à la page 4 sur 160 et déjà ça picote.

(*) Scientifiquement parlant.

Geek Background

Fabriquer une condition avec des opérations arithméteeks

Une à deux fois par nuit je me réveille en sueur froide avec une grande question existentielle dans la tête. En général c'est plus ou moins des histoires de zombie post-apocalypteek. Ou du hack. Des trucs fun quoi. Eh bien en ce moment c'est plutôt des questions de math et de programmation(*). Encore plus fun !

Ma question de cette nuit

Peut-on fabriquer une condition avec juste des opérations arithméteeks ?

Réponse courte : oui, on peut

Réponse longue comme... la fin de 2001 l'Odyssée de l'espace

Pour commencer l'énoncé mérite quelque précision(**). Par opérations arithméteeks j'entends des opérations usuelles sur les nombres. Par « condition » j'entends une structure du style : SI <gnagnagna> ALORS <pouetpouet>. 

La partie compliquée à réaliser c'est le <gnagnagna>. Quand on y pense il s'agit d'une fonction définie partout mais pas continue. On peut d'ailleurs concentrer la difficulté en un point précis et transformer l'énoncé en : fabriquer une fonction z(x) qui s'annule seulement quand x égale zéro. On va même épurer le problème en demandant que la fonction z soit « normalisée » c'est-à-dire : SI x=0 ALORS z(x)=0 SINON z(x)=1. Perso, si on me donne ça comme fonction, je sais réaliser n'importe quelle condition sans trop me fouler. Et du coup j'aurais moyen de me rendormir.

Des fonctions z de ce type là on en rencontre à tous les coins de rues. Enfin disons dans le moindre bout de code. Et c'est très facile à définir en utilisant une définition par cas(***).

Seulement voilà, la définition par cas n'est pas arithméteek. Mais alors pas arithméteek du tout. En gros elle ne travaille pas vraiment sur les nombres comme le font par exemple l'addition ou la multiplication. Du coup va falloir réfléchir deux minutes. Petite précision tant que j'y suis, je me suis interdit de chercher la solution direct sur Internet (en fait c'est surtout que je ne savais pas trop quoi googler comme question). Du coup, obligé de chercher dans ma tête. Tu verrais le foutoir là-dedans on dirait ma piaule !

Bricole ta fonction avec Metallurgeek

D'abord la fonction devrait être symétreek autour de zéro. Ben ouais, y pas de raison que ça marche moins bien pour les négatifs que pour les positifs, hein ? Après j'ai vaguement l'idée qu'il faudrait diviser un truc par un autre de manière à empêcher la fonction de croitre arbitrairement. Et pour que la fonction s'annule en zéro une puissance paire de x au numérateur pourrait l'affaire. Au dénominateur il faut un truc qui ne s'annule pas. Parce que quand on annule un dénominateur ça peut créer une vergence dans la force. Tant qu'on y est ça serait bien que le dénominateur soit un poil plus grand que le numérateur. Comme ça la fonction resterait gentiment inférieure à un. Dernier truc, j'ai besoin d'une primitive fondamentalement pas continue. C'est là que j'utilise la fonction plancher. Ça on ne va pas y couper parce que je sais trop fabriquer du discontinu avec que du continu. Reste plus qu'à inverser les retro-gradateurs de tension, stabiliser l'endo-phase éthylo-plasmateek, refroidir la planète, et ça devrait le faire.

Et c'est ainsi qu'on arrive à la fonction indiquée au début de l'article. Clairement je ne suis pas le premier à avoir (re)trouvé ça. À mon avis c'est déjà dessiné sur les grottes de Lascaux (Dordogne) ou sur les grottes de La Squaw (Wyoming). Mais quand même je suis content, j'ai mitonné ma petite fonction et je peux me rendormir du sommeil du juste.

Epilogue : à quoi ça sert ?

1. Dans la vraie vie, ça sert à se rendormir.
2. En hacking, ça sert à coder une condition dans un payload injecté sans avoir besoin du caractère espace.
3. En science fiction, ça sert à sauver les colons humains dans un vaisseau spatial dont l'IA a été contaminé par une intelligence mi-belliqueuse mi-hostile mi-traillette. Le seul module qu'on contrôle encore c'est le module arithméteek parce qu'il est de fabrication française et donc trop anteek pour être vérolé.

Epicologue : et les nombres complexes alors ?

Ben ouais, si x = i, le dénominateur il s'annule quand même ! Du coup, nouveau réveil en sueur froide...

(*) J'ai déjà ma question pour la prochaine nuit, et ce sera de la grammaire. Faut-il dire « en ce moment c'est plutôt des questions » ou « en ce moment ce sont plutôt des questions. » L'usage de base penche pour la solution 1, la doxa penche pour la solution 2. La bonne solution est surement la 3. Ou la 4.

(**) Quelque précision ? quelques précisions ?

(***) Ou encore plus pédantement en utilisant le crochet d'Iverson.

Si c'est probable, ça ne l'est pas

Amusant tous ces sites qui donnent les Sujets Probables du Bac 2019. Que se passe-t-il si un tel site publie à l'avance l'un des vrais sujets ? Une fuite d'info quoi. Obligé de re-faire l'épreuve, la galère !

Donc si un sujet apparaît dans la liste des sujets probables c'est - très probablement - parce qu'il ne sortira pas cette année. CQFD. Si c'est probable, ça ne l'est pas. Une sorte de variante probabiliste du paradoxe du menteur.

Sapiosexualité

Oulalah chaleur, ça parle de sexualité sur un blog de geek ?! Vite, vite, fuyons et codons du Python en mangeant des pizzas froides ! Ou alors restons lire quand même... Mais un tout petit peu, hein, comme ça du bout des yeux pour (sa)voir.

La suite de ce billet est pour lectorat azerty(*).

La sapiosexualité c'est le fait d'être sexuellement/érotiquement excité/attiré par l'intelligence/la science. Si vous relisez bien la phrase précédente vous remarquez qu'avec les "/" ça fait huit combinaisons. Huit phrases en une ça c'est de la compression de données ! J'en sens déjà qui ont les neurones qui pointent.

La meilleure illustration que je connaisse de la sapiosexualité, c'est cette chanson de Rachel Bloom que je co-picole là juste en dessous. Vas-y cleek, fais-toi plez, je reviens dans 2'40. Et si tu galères avec l'humour anglais, les paroles sont là (pour les jeux de mots sur les titres de Bradbury).

Et maintenant vous allez me demander pourquoi je vous parle de sapiosexualité là tout de suite maintenant ?

Ben déjà parce que c'est mon blog. Le jour où t'auras chopé mon mot de passe tu pourras écrire ; à ma place même, promis.

Ensuite parce que j'adore le mot. "Sapiosexualité" ça sonne plus sympa que "nécrophilie" non ? Ah ben si, quand même...

Enfin - et surtout - je vous parle de sapiosexualité parce que la semaine dernière j'ai eu la chance de passer une heure et quart au London Science Museum. Une heure et quart c'est pas beaucoup : juste le temps me me goinfrer la salle des mathémateeks. Deux fois !

Personne peut savoir les pieds que j'ai pris. Non mais juste la totale : papillons dans le ventre, larmes aux yeux, coeur à 200, chercher de l'air, l'électricité au bout des doigts. ça m'était pas arrivé depuis le CM1. À un moment j'ai même compté les puissances de deux dans ma tête. Jusqu'à 2^25 c'est pour dire !

Et je n'ai pas honte de le dire, j'ai suivi obsessionnellement les courbes sublimes des sculptures topologeeks au plafond. Juste pour vérifier qu'elles avaient bien un seul bord (oui !) Tiens j'en mets une en photo ; celle-là pour un peu je lui passais le ruban de Möebius au doigt.

Heureusement y pas grand monde dans la salle consacrée aux maths. J'aurais fini en taule pour exhibition scientifeek ! M'en fout j'aurais écrit des calculs sur les murs avec mon sang.

Maintenant que je me suis découvert sapiosexuel à fond, je passe un petit message perso : si vous connaissez des sites bien hard-science avec des gros théorèmes salaces, des preuves non-constructives mega-p0rn, des inversions de matrices, des récurrences transfinies, des skolémisations échevelées et des intégrales multiples, lâchez-moi ça dans les coms ou sur le Facebook. Parce que là je suis trop en manque.




(*) Un lectorat azerty en vaut deux c'est bien connu, comme ça je double mes impressionnants revenus publicitaires :)

Pattern Lock - Quelques compléments

Quelques compléments sur le billet de la semaine dernière à propos des codes de débloquage.

Nombre de combinaisons possible en fonction de la longueur du code.

Liste des 160 codes de longueur 2.
Merci @Manu pour celui-là ! Moi je suis une quiche en matplotlib.

Et sinon on a regardé sur divers téléphones : en fait on peut emprunter des chemins du type 1 vers 8 (comme le déplacement d'un cavalier aux échecs). Mais en prateek c'est pas simple à effectuer. Selon la largeur du doigt on risque de passer par une touche intermédiaire. Typiquement en allant de 1 vers 8 le doigt passe souvent par 5. Du coup ce type de trajet doit être très très rarement utilisé.

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

Bash Sampling

Parfois dans la vie on n'a pas besoin d'avoir toute l'info. Par exemple on peut s'intéresser à seulement un mille trois cent trente septième de l'info. Certes, ça fait pas beaucoup, sauf si on a trop d'info au départ (par exemple mille trois cent trente sept fois trop). Bref, voici une méthode pour faire du random sampling en bash. Eh ben en voilà un billet qu'il était nécessaire !

while read L; do ((RANDOM % 1337)) || echo $L; done < data > sample

Les derniers sauvages

Ayé, l'espèce humaine n'est plus 100% une espèce sauvage. Les premier.e.s humain.e.s génétiquement modifié.e.s, Lulu et Nana, sont né.e.s, les premier.e.s humain.e.s domesteeks en quelque sorte. Je suis trop nul en philo pour savoir si c'est plutôt bien ou plutôt mal. Mais je trouve que c'est plutôt intéressant.

Moi qui me suis toujours considéré comme un dinosaure, maintenant j'en suis certain.

Enigmateek la soluce

(Ce billet fait suite au billet Enigmateek. Si tu l’as pas lu vas y vite vite vite. Et profites en pour relire tout Metallurgeek depuis Juillet 2011. Prends ton temps je bouge pas. (…) Eh ben t’as fait vite. Allez, maintenant que tout le monde est là j’enchaîne).

Vraiment sympa cette énigme, en particulier avec toutes les ambiguïtés dans l’énoncé qui permettent des réponses intéressantes et très diverses. En fait, Science & Avenir aurait pu poser la question avec 9 épiciers au lieu de 6. Oui, la solution en deux pesées sur une balance à plateaux marche jusqu’à neufs sachets. Tu m’crois pas ? Voici la méthode, inspirée du mix de plusieurs réponses sur FB plus une bière et un morceau de fromage.

Je prends mes neufs sachets, j’en mets trois sur un plateau, trois autres sur l’autre plateau, et les trois derniers je les laisse sur ma table avec mes chamallows. Si la balance penche d’un côté j’en déduis que le sachet de l’escroc est du côté le plus léger. Si la balance est à l’équilibre je sais que le sachet du fumier (Hadès noircisse sa face !) est sur la table.

Dans tous les cas je me retrouve avec trois sachets dont un. Je mets l’un de ces sachets sur un plateau, l’autre sur l’autre plateau parce que j’aime bien les trucs symétreeks, et le troisième dans mon calecif pour la déconne. Si la balance penche, le sachet du fumier est du côté le plus léger. Si la balance est à l’équilibre, le sachet du fils de rat est dans mon calcif.

Et, sauf collision de trous noirs supermassifs, on ne peux pas faire mieux que 9 avec deux pesées. Paskeu si on regarde bien, chaque pesée permet de couper l’espace des solutions en trois (selon que ça penche à gauche, ou à droite, ou que ça penche pô). Et donc avec deux pesées on peux au mieux couper l’espace en trois et re en trois : 3x3=9. Merci kiki on plie les gaules on rentre chez mémé.

Ça me met dans des états ce genre d’énigmes ! Du coup je suis pas près d’acheter du safran, ni de la coke, ni quoique ce soit vendu en paquet d'un gramme. Je continue à me défoncer aux chamallows. Les roses surtout.

Enigmateek

Il est assez rare que j'achète le magazine "la recherche" mais là il y avait un article qui m'intéressait à mort, alors je me suis fendu de quelques euros. Avant de me précipiter sur l'article en question, j'ai rapidement feuilleté l'ensemble du magazine histoire de voir comment c'était ficelé. Quand je feuillette je commence toujours par la fin, une habitude. Et donc je suis tombé direct sur la section "énigmes" du magazine.

Résultat : 1) je suis à fond dans les énigmes depuis des jours, 2) je n'ai toujours pas feuilleté le reste du magazine, 3) je n'ai toujours pas lu l'article qui m'intéressait à mort, 4) d'ailleurs je ne sais plus trop de quel article il s'agissait, 5) au moins une énigme est difficile et va falloir que j'achète le numéro suivant pour la soluce.

J'en partage une ici, d'énigme. Pas trop difficile et assez connue, mais particulièrement édifiante. Six épiciers vendent du safran de grande qualité par sachets de 1 gramme. L'un des épiciers triche et ne met en fait que 3/10 gramme dans ses sachets. L'enfoiré ! J'ai connu un dealer qui faisait pareil avec la coke ça m'a agacé je l'ai cloué à la porte du tribunal. Bref. On récupère un sachet chez chaque épicier. Sur une balance à plateaux, combien faut-il de pesées au minimum pour être certain de débusquer l'empafé d'épicier et le clouer à côté du dealer ?

Je vous laisse réfléchir dans vos têtes. Et si j'en voie un qui surfe pour trouver la réponse toute faite sur Internet, sérieux je le cloue avec les deux autres.

Ma meilleure soluce pour l'instant (spoil): je prends deux sachets au hasard et je les mets sur le plateau plateau de droite, je prends deux autres sachets au hasard et je les mets sur le plateau de gauche. Là, trois cas peuvent se produire: 1) ça pencha à droite, 2) ça penche à gauche, 3) ça penche pas. Chacun des cas me permet de savoir lequel des groupes de deux sachets contient celui de l'enflure d'épicier. Là je prends le groupe concerné et je fais une seconde pesée : un sachet sur chaque plateau. Le plus léger est celui de l'enflure d'épicier.

Une légère variante envoyée par une lectrice: elle met trois sachets sur chaque plateau. Du coup ça penche forcément d'un côté. Elle prend au hasard deux sachets dans le groupe le plus léger et refait une pesée avec (un sur chaque plateau).

Bon, reste plus qu'à trouver une solution en une seule pesée. Pas facile. Peut-être en utilisant le fait que le sachet de ce rapia d'épicier pèse 3/10 grammes.

My humble tribute to xkcd

Without xkcd the Web would be even more boring. Tonight, I was thinking about what generative adversarial network could bring whenever trained with xkcd cartoons. And some extra weight on my favorites pics.

S.O.S (Sense-Of-Self)

Oulah, long time no see!

J'ai profité d'être cloué au lit avec angine et oreilles qui saignent pour réfléchir dans ma tête. Du coup lecteurs adorés, je vous écris ! L'arrêt maladie ça a du bon, tant que ça ne dure pas trop longtemps.

Pour une fois je ne me suis pas pris la tête avec des mots de passe, ou du vim ou du ROT13. Faut changer d'obsession de temps en temps. Du coup j'ai repris un vieux sujet datant de mes recherches fondamentales (genre). Il s’agit du sens du soi. Sense-Of-Self en anglais, ça fait tout de suite plus classe. D'autant que les initiales c'est "S.O.S" d'où le titre de ce billet. C'est bien ficelé hein ?

Version courte et compliquée

J'ai enfin trouvé un programme python dont l'uneek fonction est de se reconnaître lui-même, et seulement lui-même. Pour la métaphore disons un "système immunitaire". Le voici en action :

$ cat sos.py
D='Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D]) 
$ cat sos.py | python3 sos.py 
1 
$ echo "je suis un virus" | sos.py
0
À quoi ça sert ? Ben a rien comme d'hab. Sérieux, après toutes ces années à me lire vous posez encore la question ;)

Version longue et délicatement parsemée d'humour bien relou

Le Sense-Of-Self c'est la propriété qui permet à une entité de se distinguer elle-même de tout le reste. Le monde se divise alors en deux catégories : le soi et le non-soi.

Je suis reparti sur cette piste parce que je pensais notamment à toutes les conneries que fait mon organisme en ce moment : inflammation, système immunitaire survolté, allergies. Autant de réactions justement liées à ce fameux "sens-du-soi". Le stade ultime c'est les réactions auto-immunes où l'organisme s'attaque lui-même parce qu'il se prend pour du non-soi. Truc de ouf.

En terme informateek, le Sense-Of-Self prend une résonnance intéressante. De loin c'est peut-être lié à la question - autrement plus fumeuse - de la conscience des machines. Deux trois gugusses ont d'ailleurs vaguement réfléchi à ça : Alan Turing, John Von Neumann, Marvin Minsky, Andrei Kolmogorov... Plus récemment Raymond Smullyan, David Naccache(*), Adrian Perrig(*), etc. Du coup je me suis dit comme ça : euh, pourquoi pas moi ?

N'étant pas précisément équipé du même appareil cérébral que les personnes susnommées, je me suis contenté d'une version simplifiée du problème. Formalisons :

Existe-t-il un programme SOS qui affiche "1" lorsqu'il est appliqué à lui-même et qui affiche "0" lorsqu'il est appliqué à toute autre entrée ?

Autrement dit, le programme se reconnaît lui-même (1) et fait la différence avec tout le reste (0). On aurait : SOS(SOS)=1 et SOS(other)=0.

De plus, je me suis demandé s'il existe un programme SOS qui ne fait QUE ça. Par exemple il n'en profite pas pour nous afficher en plus de la pub ou pour envoyer nos données personnelles sous forme de cookies à un serveur dans un autre pays. Je recherche un programme en quelque sorte minimal, qui se réduirait à la fonction Sense-Of-Self. Toujours dans l'esprit minimaliste, je voudrais que le programme soit court, voire même le plus court possible tant qu'on y est. Dans l'idée d'isoler l'essence même du sens-de-soi. "Isoler l'essence même du sens-de-soi" ça veut pas dire grand-chose mais j'adore écrire des phrases comme ça.

Les tas de lard

En bon geek, j'ai jeté un œil à l'état de l'art (voir illustration). Autant le reconnaître, il existe déjà beaucoup de choses sur le sujet, notamment sous l'angle des "Quines". Un Quine (une Quine ?) c'est un programme autoreproducteur : il ne fait rien d'autre qu'afficher son propre code, sans aide extérieure. Comme une bestiole qui vomirait son ADN, et seulement son ADN. Pas comme moi au HellFest. On est déjà très proche de ce que je recherche. Moi je veux un programme qui reconnaît son ADN au lieu de l'afficher.

Ouaip, et bien même en ayant déjà écrit des Quines par le passé, il m'a fallu quand même un sacré bout de temps pour trouver un programme Sense-Of-Self opérationnel ! Et j'ai mis plus de temps encore à le raccourcir. Quant à prouver que le résultat est de longueur minimale, ça je n'ai pas encore réussi. On n'aura qu'à dire que c'est à cause des médocs qui m'empêchent de me concentrer à fond.

Ah oui, avant de passer aux choses compliquées, j'ai oublié de préciser un point techneek : la longueur du code s'entend toujours relativement à un langage de programmation donné. Par exemple j'ai choisi Python vu que je sais à peu près faire que ça. Pas question donc de comparer des longueurs de code C / Python / Perl / Bash / Scala, etc.(**) De toute façon c'est le code C qui sera le plus long, tellement c'est pourri le C, beuurrrkkk.

Première tentative

Autant le dire tout de suite, cette première tentative ne fonctionne pas. Elle est là pour montrer précisément le point difficile. L'idée naïve c'est de se dire : le programme va contenir une copie de son ADN, va prendre l'entrée qu'on lui donne, comparer et afficher 0 ou 1 selon que c'est pareil ou pas. Vite fait bien fait comme ça on est direct rentré chez mémé pour aller regarder enquête d'action.

Et ben non parce que ça coince, cf. pseudo-code : If Input == ADN Then 1 Else 0. Avec la chaîne de caractère ADN qui contient une copie du programme. Ce qui donne chose comme ADN = 'If Input == ADN Then 1 Else 0'. Ah ben oui, mais maintenant la chaine 'ADN' contient aussi une copie la chaine 'ADN', c'est malin ! Du coup ça fait : ADN = 'If Input == 'If Input == ADN Then 1 Else 0' Then 1 Else 0'.

Là ça devient le Bronx, pleins de trucs ne vont pas : la nouvelle chaine contient toujours une référence à ADN, on a juste déplacé le problème d'un cran. Et surtout, de manière plus pernicieuse, se pointe une sérieuse galère avec les apostrophes : si j'utilise les mêmes apostrophes pour la première copie de ADN et la pour deuxième (et en fait pour toutes les copies ad-infinitum) on va plus savoir quelles apostrophes débutent quel ADN et quelles apostrophes terminent quel autre ADN. Merdier de ADN : tiens, je baptise ça "Syndrome de Monsanto" ça va me détendre.

Alors on la met où l'apostrophe ?

Dans ton Q ! Non lecteur adoré ce n'est pas un manque de respect. Je veux simplement indiquer qu’il faut encoder l'apostrophe dans une variable, que j’ai nommée Q comme Quote (apostrophe en anglais). Après c'est pas ma faute si en anglais le mot Quote commence par un Q et du coup ça fait un jeu de mot relou.

Foin de digressions, voici enfin la bête, Ta-Daaaaaa : 
D='Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])
Ça s'utilise comme ça: 
$ cat sos.py | python3 sos.py
1
$ echo "Je suis un virus" | python3 sos.py
0

Explications

Allez, quelques explications parce que je sens des scepteeks dans le fond de la salle.

Considérons d'abord le cas où le programme se reconnaît effectivement lui-même : $ python3 sos.py < sos.py répond 1. Le code lancé est contenu dans le fichier sos.py et l'entrée est aussi dans sos.py. Le programme s'exécute ainsi :

• Affecte une chaine de caractères à la variable D, comme ADN.
• Affecte chr(39) à la variable Q, comme Quote.
• Affiche le résultat d'une comparaison logeek (==) et ajoute un peu de formatage idomateek python, "01"[...] valant "0" pour False et "1" pour "True"(***).

Il faut probablement un peu de temps pour se rendre compte que le ADN du programme dépend en fait du programme lui-même (et vice-versa). C'est très précisément là que se situe la difficulté, comme avec les Quines. Dès qu'on change un iota quelque part il faut refléter ce changement ailleurs dans le programme. Mais au moins on a résolu le problème d'encodage. En effet le terme Q=chr(39) représente bien l'apostrophe mais sans l'utiliser de manière littérale.

Voyons maintenant le cas où le programme détecte autre chose que lui-même : comme précédemment, le programme reconstruit une version complète de lui-même à l'aide de son ADN et de l'apostrophe encodée (c'est la partie "D="+Q+D+Q+";"+D). Mais là il constate que cette version est différente de l'entrée (comparaison ==) et affiche finalement "0".

Reste à s'occuper de la longueur du programme : 103 symboles. Pour faire plus court, on peut déjà remarquer que les techneeks "classeeks" de code golfing ne marchent pas très bien ici : typiquement, renommer la fonction print en une fonction plus courte (mettons p) devrait être fait deux fois. Une fois dans le ADN une fois dans le programme. Il faudrait alors écrire deux fois "p=print;" ce qui consommerai en tout 16 caractères. Pas bon car au final on n’en regagne que 8 en écrivant (deux fois) p au lieu de print. J'entrevois d'autres pistes en utilisant soit la fonction eval() de python, soit l'embryon de lambda calcul intégré au langage. J’ai fait deux trois tentatives du bout des orteils, pas simple. Si on est moins regardant sur les sorties, et qu'on utilise directement "True" et "False" au lieu de "1" et "0", on tombe à 91 symboles, mais ça triche un peu par rapport à l'énoncé de départ :

D='Q=chr(39);print(input()=="D="+Q+D+Q+";"+D)';Q=chr(39);print(input()=="D="+Q+D+Q+";"+D)

Conclusion 

Il est possible d'écrire un programme court ayant "le sens-du-soi" et ne remplissant que cette fonction.

Pour ceux que les applications intéressent quand même, il n'est pas bien compliqué d'adjoindre une fonction utile au SOS de base. Par exemple pour acheter des t-shirts sur Rock A Gogo. Ce qui donne par exemple:
D='Q=chr(39);print("buy-death-metal-t-shirts");print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("buy-death-metal-t-shirts");print("01"[input()=="D="+Q+D+Q+";"+D])
Notez que si la fonction utile contient beaucoup de symboles on peut stoker son ADN sous forme compressée. Et même, en se contentant de stoker un condensat cryptograpeek (ouais, un hash) on retombe sur une méthode connue de vérification d'intégrité du code. En fait cette méthode-là peut être trouvée plus directement sans se prendre la tête avec toutes ces histoires de sense-of-self.

Pour ceux que les applications n'excitent pas plus que ça, faites juste tourner le concept dans votre tête : il existe une machine dont l'uneek fonction est de se différencier de tout le reste.

Nan, j'déconne.

(*) Merde, parmi les gens cités il y en a qui vivent encore, et je viens de les traiter de gugusses. Alors que j'ai un infini respect pour eux.

(**) On me souffle dans l'oreillette que Kolmogorov et Chaitin avaient déjà expliqué ça genre il y a 50 ans. Désolé les gars, je vulgarise. Par contre si on pouvait arrêter de me souffler dans les oreillettes, j'ai une double otite, merci.

(***) "1" pour True, tous pour un !