addition — Recherche de solutions d’une énigme

Ce programme met en œuvre plusieurs algorithmes de recherche de solutions de l’énigme suivante.

Par quels chiffres faut-il remplacer les lettres pour que l’addition suivante soit correcte ?

\[\begin{split}\begin{array}{lcccc} & & &U&N \\ + & & &U&N \\ + & D&E&U&X \\ + & C&I&N&Q \\ \hline = & N&E&U&F \\ \end{array}\end{split}\]

La première solution présentée mets sept minutes à trouver les solutions, tandis que la dernière fait le même travail en moins de deux secondes.

Algorithmes

Version 1

 1def addition1():
 2    """Force brute, naïve."""
 3    for C in range(10):
 4        for D in range(10):
 5            for E in range(10):
 6                for F in range(10):
 7                    for I in range(10):
 8                        for N in range(10):
 9                            for Q in range(10):
10                                for U in range(10):
11                                    for X in range(10):
12                                        if (
13                                            C != D
14                                            and C != E
15                                            and C != F
16                                            and C != I
17                                            and C != N
18                                            and C != Q
19                                            and C != U
20                                            and C != X
21                                            and D != E
22                                            and D != F
23                                            and D != I
24                                            and D != N
25                                            and D != Q
26                                            and D != U
27                                            and D != X
28                                            and E != F
29                                            and E != I
30                                            and E != N
31                                            and E != Q
32                                            and E != U
33                                            and E != X
34                                            and F != I
35                                            and F != N
36                                            and F != Q
37                                            and F != U
38                                            and F != X
39                                            and I != N
40                                            and I != Q
41                                            and I != U
42                                            and I != X
43                                            and N != Q
44                                            and N != U
45                                            and N != X
46                                            and Q != U
47                                            and Q != X
48                                            and U != X
49                                        ):
50                                            if (10 * U + N) + (10 * U + N) + (
51                                                1000 * C + 100 * I + 10 * N + Q
52                                            ) + (
53                                                1000 * D + 100 * E + 10 * U + X
54                                            ) == 1000 * N + 100 * E + 10 * U + F:
55                                                yield (C, D, E, F, I, N, Q, U, X)

La première version est très naïve, et n’utilise aucune fonctionnalité avancée du langage Python (si ce n’est le yield pour itérer les solutions).

Chaque lettre a sa propre boucle (qui balaye tous les chiffres de 0 à 9), et avant de tester si les variables correspondent à une solution, on vérifie que chaque variable est différente avec un if qui teste chacune des 28 combinaisons possibles.

Cette version est très lente : l’exécution prend presque sept minutes.

Version 2

 1def addition2():
 2    """Manière un peu plus élégante de s'assurer que les lettres sont toutes différentes."""
 3    for C in range(10):
 4        for D in range(10):
 5            for E in range(10):
 6                for F in range(10):
 7                    for I in range(10):
 8                        for N in range(10):
 9                            for Q in range(10):
10                                for U in range(10):
11                                    for X in range(10):
12                                        if len(set((C, D, E, F, I, N, Q, U, X))) == 9:
13                                            if (10 * U + N) + (10 * U + N) + (
14                                                1000 * C + 100 * I + 10 * N + Q
15                                            ) + (
16                                                1000 * D + 100 * E + 10 * U + X
17                                            ) == 1000 * N + 100 * E + 10 * U + F:
18                                                yield (C, D, E, F, I, N, Q, U, X)

Le if de la première version (qui teste si les variables sont distinctes) n’est pas très élégant. Cette seconde version remplace cette trentaine de lignes par une unique : len(set((C, D, E, F, I, N, Q, U, X))) == 9. Ce test vérifie que l’ensemble des neuf variables contient neuf éléments (si deux variables sont égales, la taille de l’ensemble sera moindre).

J’ai été surpris de constater que cette version est plus lente que la précédente : plus de dix minutes.

Version 3

 1def addition3():
 2    """N'énumère que les cas où les valeurs des lettres sont toutes différentes."""
 3    for C in range(10):
 4        for D in range(10):
 5            if D == C:
 6                continue
 7            for E in range(10):
 8                if E in (C, D):
 9                    continue
10                for F in range(10):
11                    if F in (C, D, E):
12                        continue
13                    for I in range(10):
14                        if I in (C, D, E, F):
15                            continue
16                        for N in range(10):
17                            if N in (C, D, E, F, I):
18                                continue
19                            for Q in range(10):
20                                if Q in (C, D, E, F, I, N):
21                                    continue
22                                for U in range(10):
23                                    if U in (C, D, E, F, I, N, Q):
24                                        continue
25                                    for X in range(10):
26                                        if X in (C, D, E, F, I, N, Q, U):
27                                            continue
28                                        if (10 * U + N) + (10 * U + N) + (
29                                            1000 * C + 100 * I + 10 * N + Q
30                                        ) + (
31                                            1000 * D + 100 * E + 10 * U + X
32                                        ) == 1000 * N + 100 * E + 10 * U + F:
33                                            yield (C, D, E, F, I, N, Q, U, X)

Dans les versions précédentes, chacune des variables prend chacune des dix valeurs possibles, et c’est seulement juste avant de tester si l’addition est vérifiée ou non que l’on teste si les variables sont distinctes. C’est une perte de temps : dés qu’une variable prend la même valeur qu’une variable déjà définie, on peut passer à la valeur supérieure. C’est ce qui est mis en œuvre dans la fonction suivante.

Dans les deux versions précédentes, les boucles itèrent sur \(10^9\) éléments (soit un milliard). Avec cette version (ainsi que toutes les suivantes), les boucles n’itèrent plus que sur \(A^9_{10}\) arrangements (soit environ 3,6 millions). Cela fait 300 fois moins de tests, et explique que le temps d’exécution passe de sept minutes à seulemnt 8,5 secondes.

Version 4

1def addition4():
2    """Utilisation de `itertools.permutations`."""
3    for C, D, E, F, I, N, Q, U, X in itertools.permutations(range(10), 9):
4        if (10 * U + N) + (10 * U + N) + (1000 * C + 100 * I + 10 * N + Q) + (
5            1000 * D + 100 * E + 10 * U + X
6        ) == 1000 * N + 100 * E + 10 * U + F:
7            yield (C, D, E, F, I, N, Q, U, X)

Cette version est la même que la précédente, sauf que l’énumération des arrangements n’est pas fait « à la main », mais en utilisant la fonction itertools.permutations() correspondante de la bibliothèque standard de Python. Ces fonctions de la bibliothèque standard ont été écrites par des gens plus intelligents que moi, testées depuis des années, écrites en C pour certaines : sauf cas très particulier, elles sont plus rapides que ce que je pourrais écrire.

Et en effet, le simple fait de remplacer mon implémentation des arrangements par l’appel de la bonne fonction de la bibliothèque standard fait passer le temps d’exécution de 8,5 secondes à 3,3 secondes (trois fois plus rapide).

Version 5

1def addition5():
2    """Réduction du nombre de multiplications."""
3    for C, D, E, F, I, N, Q, U, X in itertools.permutations(range(10), 9):
4        if 1000 * (C + D - N) + 100 * I + 10 * (2 * U + N) + (2 * N + Q + X - F) == 0:
5            yield (C, D, E, F, I, N, Q, U, X)

Lors de la vérification de l’égalité \((10 \times U + N) + (10 \times U + N) + (1000 \times C + 100 \times I + 10 \times N + Q) + (1000 \times D + 100 \times E + 10 \times U + X) = 1000 \times N + 100 \times E + 10 \times U + F\), onze multiplications sont effectuées. En réarrangeant cette équation (en factorisant par 10, 100, et 1000), on obtient le test \(1000 \times (C + D - N) + 100 \times I + 10 \times (2 \times U + N) + (2 \times N + Q + X - F) = 0\) qui ne contient plus que trois multiplications (en ignorant les multiplications par 2). Cette simple optimisation fait-elle gagner de temps ?

Oui : elle permet de passer de 3,3 secondes à 2,1 secondes (soit un gain d’un tiers).

Version 6

1def _sousfonction6(C):
2    solutions = set()
3    for D, E, F, I, N, Q, U, X in itertools.permutations(
4        itertools.chain(range(0, C), range(C + 1, 10)), 8
5    ):
6        if 1000 * (C + D - N) + 100 * I + 10 * (2 * U + N) + (2 * N + Q + X - F) == 0:
7            solutions.add((C, D, E, F, I, N, Q, U, X))
8    return solutions
1def addition6():
2    """Parallélisation."""
3    with multiprocessing.Pool() as pool:
4        yield from itertools.chain(*pool.imap_unordered(_sousfonction6, range(10)))

La dernière optimisation permet de profiter des plusieurs processeurs utilisés par la plupart des ordinateurs modernes. La fonction de recherche est exécutée 10 fois, pour chacune des valeurs possibles de la première lettre C. Ces fonctions sont appelées avec autant d’exécution parallèles que de processeurs, en utilisant la classe multiprocessing.pool.Pool de la bibliothèque standand, qui gère tout cela de manière automatique.

Sur ma machine (qui possède quatre cœurs), cela permet de passer de 2 secondes d’exécution à seulement 1 seconde. Cela divise le temps d’exécution par deux, ce qui est moins que ce que l’on aurait pu attendre (une division par quatre avec quatre cœurs), mais c’est déjà bien.

Conclusion

Trois principales optimisations sont à remarquer.

  • La réduction de l’espace des solutions recherchées (des versions 2 à 3) a produit un algorithme 300 fois plus rapide. C’est la seule des optisations présentées ici qui réduit la complexité de l’algorithme.

  • L’utilisation de la bibliothèque standard de Python (modules itertools et multiprocessing).

  • La réduction du nombre de multiplications (versions 4 à 5).

Usage

Le binaire python -m jouets.addition n’accepte aucune option (plus précisément, il les ignore toutes). Il recherche les solutions de l’énigme en utilisant toutes les variantes possibles, affiche ces solutions, et le temps d’exécution de chaque fonction.