Le défi de Takeshi Kitano

Lancés en 2011 à la Fondation Cartier, le défi de Takeshi Kitano consistent à trouver une n-solution (avec n le plus petit possible) permettant d'atteindre un nombre entier cible (typiquement le numéro de l'année) avec une expression où interviennent successivement, dans l'ordre, les entiers de 1 à n séparés par des symboles mathématiques. Je n'ai pas trouvé la liste explicite de ces opérateurs, et ai considéré les opérateurs suivants : +, −, ×, ÷ et puissance en binaire ; −, √ et ! en unaire.

Le but ici est d'expliquer mon cheminement dans l'écriture d'un programme qui résout ce problème.

Un point d'intérêt concerne la nature entière ou réelle du calcul, et je n'ai pas trouvé de réponse à cette question. On peut douter de la vraisemblance du fait qu'un résultat intermédiare non entier donne un résultat final entier, mais cela reste en théorie possible. Je n'ai cependant considéré que les calculs entièrement entiers, c'est-à-dire dans lesquels tous les résultats intermédiaires sont entiers.

La première partie consiste à énumérer tous les arbres binaires pour un nombre N de feuilles donné (voir figure ci-dessous).


Énumération de tous les arbres binaires pour N = 4 (4 feuilles)

Il n'est pas trivial d'obtenir une et une seule fois chaque arbre par construction, et n'ayant pour l'instant pas réussi à faire un tel algorithme, je me suis contenté d'une approche récursive consistant à sélectionner toutes les paires consécutives possibles pour un niveau donné, puis à rappeler la sélection sur la partie construite. Cette approche a un cout en (N−1)!, et il faut détecter les arbres déjà explorés, ce que j'ai fait avec une représentation textuelle de l'arbre. Bien que cela puisse sembler inefficace (6 arbres au lieu de 5 pour N = 4, 24 arbres au lieu de 14 pour N = 5, etc.), le cout d'exploration des arbres est complètement négligeable devant le cout d'exploration des opérateurs pour un arbre donné. Une fois un arbre donné, il faut explorer toutes les configurations d'opérateurs possibles avant de calculer sa valeur. Si l'on considère uniquement les opérateurs binaires +, −, ×, ÷ et puissance, il y a 5^N−1 configurations pour un arbre donné. Pour les opérateurs unaire, ces derniers sont combinables un nombre arbitraire de fois, ce qui peut très vite faire exploser le nombre de configurations. Je n'ai donc considéré que certaines combinaisons d'opérateurs un nombre limité de fois. Plus particulièrement, les combinaisons considérées sont les suivantes :

• identité
• −
• √
• !
• −∘√
• √∘−
• !∘−
• −∘!

Concernant les combinaisons manquantes, nous pouvons lister les valeurs potentiellement pertinentes en entrée, que nous considérerons être celles dont l'entrée et la sortie sont de l'ordre de grandeur du nombre cible au maximum. Néanmoins, on peut noter qu'une valeur proche ou plus grande que celle de la cible a très peu de chances d'apparaitre dans un calcul optimal de la cible.

• !∘! : seule la valeur 3 est pertinente
• √∘√ : Les valeurs 16, 81, 256, 625, 1296, 2401 sont éventuellement pertinentes
• !∘√ : Les valeurs 9, 16, 25, 36, 49 sont pertinentes
• √∘! : Ne produit aucun entier jusqu'à 12 (> 21 886)
• √∘√∘√ : La valeur 256 est pertinente
• −∘!∘− : Pourrait être considéré au même titre que !∘−
• −∘√∘− : Pourrait être considéré au même titre que √∘−

Pour éviter d'explorer les combinaisons non voulues, les opérateurs unaires ont été combinés pour créer des opérateurs unaires en en composant directement plusieurs. Des noeuds unaires sont ajoutés dans l'arbre au-dessus de chaque noeud binaire. L'opérateur factorielle est implanté comme un tableau, mais pas la racine carré à cause de la taille du tableau et des effets sur le cache que cela induit (bien que selon mes expérimentations, cela ne change pas tant que ça).

Si l'on considère les 8 opérateurs unaires ainsi obtenus, il y a donc 5^N−1×8^2×N−1 combinaisons. Une approche naïve consiste ensuite simplement à énumérer ces combinaisons et calculer la valeur de l'arbre.

Néanmoins, une telle énumération naïve pose deux problèmes :

• D'une part, cela oblige à recalculer tout l'arbre à chaque changement d'opérateur, même si des noeuds intermédiaires sont corrects (par exemple si l'opérateur modifié est à la racine, seul ce calcul a besoin d'être refait)
• D'autre part, cela oblige à explorer des millions de configurations ayant possiblement à l'origine de l'arbre d'exploration un noeud qui correspondant à un calcul non pertinent.

Pour faire face à ces deux problèmes, l'idée est d'explorer les opérateurs en partant des profondeurs de l'arbre les plus grandes, afin de ne pouvoir ré-évaluer que le noeud courant, et de couper de l'arbre d'exploration tous les sous-arbres à partir du moment où un noeud donne un résultat non entier ou impossible (racine carré d'un nombre négatif, par exemple).
Le programme, dont le code se trouve ici donne les résultats suivants pour les nombres de 2011 à 2019 :

• 2011 = ((((1 + 2) + 3) ^ 4) − 5) + (6!)
• 2012 = −((((1 + 2)!) × (3!)) − sqrt(4 ^ (5 + 6)))
• 2013 = (((1 × 2) + ((3!) ^ 4)) − 5) + (6!)
• 2014 = (((1 + 2) + ((3!) ^ 4)) − 5) + (6!)
• 2015 = −(1 − ((((2 ^ 3)!) / 4) / 5))
• 2016 = (((−((1 − 2) − (3!)))!) × sqrt(4)) / 5
• 2017 = 1 + ((((2 ^ 3)!) / 4) / 5)
• 2018 = −((((1 + 2) − ((3!) ^ 4)) − 5) − (6!))
• 2019 = −((((1 × 2) − ((3!) ^ 4)) − 5) − (6!))

Compte-tenu de ces résultats, il est possible de considérer plus d'opérateurs unaires, en limitant la recherche aux tailles strictement inférieures (par exemple jusqu'à N = 5 pour 2011). Il est possible d'avoir un certain nombre d'opérateurs en plus pour ces tailles-là et que l'exploration se fasse en un temps tout à fait raisonnable.