URL: https://linuxfr.org/users/steph1978/journaux/resoudre-trouve-24
Title: résoudre "trouve 24"
Authors: steph1978
Date: 2022年02月23日T12:57:23+01:00
License: CC By-SA
Tags: langage_c, puzzle, jeu, c et mathématiques
Score: 15
[Wordle est mort](https://sebsauvage.net/links/?kc0IwA). Racheté par le capitalisme et blindé de tackers et de pubs.
Changeons de jeu : [trouver 24](https://lehollandaisvolant.net/tout/tools/24/).
Le but est de combiner les 4 nombres proposés en 3 opérations pour atteindre le nombre 24.
Un petit exemple : `8 5 7 1` sortent, on peut faire `8-5=3, 7+1=8, 3*8=24`.
Il est obligatoire d'utiliser tous les nombres. Par exemple : `1 2 3 8` sortent, on ne peut pas faire `8 * 3 = 24`, car `1` et `2` n'ont pas été utilisés.
J'ai joué un peu puis me suis dis "c'est un boulot pour une machine".
Le jeu resemble un peu au jeu [le compte est bon](https://fr.wikipedia.org/wiki/Des_chiffres_et_des_lettres#Le_Compte_est_Bon), avec 4 nombres au lieu de 6 et trouver 24 au lieu d'un nombre entre 101 et 999 et le fait qu'il faut utiliser tous les nombres.
J'ai donc ressorti un code que j'ai écrit en 1999 (oui monsieur!), en C et qui résolvait "le compte est bon" en une fraction de seconde sur un processeur PPC G3 de 233MHz.
Le programme est brute force. Il tente toutes les combinaisons possibles (733'188 si mon dénombrement est le bon) avec un parcours récursif systématique. Il ne tente pas de réutiliser les résultat précédents. Par exemple quand on calcule les combinaisons pour (a1,a2,a3,a4,a6), une grosse partie - (a1,a2a3,a4) - a déjà été exploré quand on a fait (a1,a2,a3,a4,a5). Mais mettre en place de la mémorisation m'a paru bien plus compliqué que le brute force.
Le [code](https://framagit.org/-/snippets/6516) est probablement très laid pour un pratiquant du C. Ce n'est pas mon cas. Et deux décennies après, j'ai pu m'y replonger et l'adapter sans problème. Je n'ai pas eu trop honte de mon ancien moi à la relecture :)
```shell
$ ./trouve_24 1 2 3 8
1 +たす 2 =わ 3 ; 3 * 8 = 24 ;
1 + 2 = 3 ; 8 * 3 = 24 ;
1 * 2 = 2 ; 3 * 8 = 24 ;
1 - 2 = 1 ; 3 * 8 = 24 ;
1 - 2 = 1 ; 8 * 1 = 8 ; 3 * 8 = 24 ;
1 + 3 = 4 ; 2 - 8 = 6 ; 4 * 6 = 24 ;
1 + 3 = 4 ; 8 + 4 = 12 ; 2 * 12 = 24 ;
1 * 3 = 3 ; 8 * 3 = 24 ;
1 + 8 = 9 ; 3 + 9 = 12 ; 2 * 12 = 24 ;
1 * 8 = 8 ; 3 * 8 = 24 ;
2 - 8 = 6 ; 1 + 3 = 4 ; 6 * 4 = 24 ;
3 + 8 = 11 ; 1 + 11 = 12 ; 2 * 12 = 24 ;
3 * 8 = 24 ;
420 numbers generated
13 solutions
```
À noter que le programme donne des solutions invalides qui n'utilisent pas tous les nombres, il faut filtrer. Je n'ai pas non plus implémenté la division qui me paraissait plus compliquée qu'utile à l'époque pour le compte est bon. Pour trouve 24, il peut être nécessaire de l'utiliser pour consommer des nombres. Dans ce cas, le programme ne donne pas de solution et il faut donc se dire qu'une division est nécessaire. Cela réduit alors le problème qui devient facilement résoluble de tête.
Est-ce que vous avez déjà tenté de résoudre ce type de puzzle ? Si oui quelle a été votre approche ?
Ah et si les chiffres c'est pas votre truc, mais que vous aimez la géographie, découvrez [worldle](https://worldle.teuteuf.fr/), avec ou sans openstreetmap sous les yeux, c'est pas le même délire.