Défi: le compte est bon

[Cliffe]

Non pas forcément.

Si je prend : et . On a .
Maintenant je prend un fils de : , on a alors .
Donc on supprime .

[Zorro_X]

Cliffe, ton approche correspond justement et exactement à ce qu'on fait d'une heuristique !!! ;)

[Cliffe]

Cliffe, ton approche correspond justement et exactement à ce qu'on fait d'une heuristique !!!

C'est un Branch-and-Cut.
Ma remarque d'avant c'était juste parce-que vous parliez de résultats approchés. Ce qui n'a aucun intérêt.

[Cliffe]

Je viens de coder un truc et j'arrive à avoir des résultats en quelques secondes.
Exemple :

Code: Tout sélectionner

(18 - 8) * ((82 * 90 * 12 - 9) + 107 * (1 + 213) / 2)

[Zorro_X]

je crois que les parenthèses ne sont pas autorisées dans le jeu original car il s'agit d'un calcul séquentiel : une opération après l'autre, appliquée sur le résultat précédent...
Je suis en train de coder un truc, j'aurai sans doute quelque chose demain...

[fatal_error]

Je viens de coder un truc et j'arrive à avoir des résultats en quelques secondes.

En fait, dépendant des implémentations de chacun, trouver une solution en fonction d'une liste de plaque donnée n'est pas super.
En revanche, le temps mis pour affirmer qu'il n'y a pas de solution est plus intéressant

Il faudrait plutot majorer le temps de trouver une solution optimale si elle existe.

mis à part, je ne t'ai jamais vu mettre un code source mais seulement des résultats. Un peu frileux? :lol3:

Pour revenir à la majoration du temps, ca peut dépendre des valeurs des plaques que l'on a en entrée ainsi que du goal (certains plaques/goal permettront plus facilement de trouver des cuts que d'autres).
Rien que poser l'énoncé n'est finalement pas trivial :marteau:
Je vous invite à m'aider pour trouver un énoncé qui nous permette d'arriver à pouvoir comparer les résultats obtenus, dans le but de réduire le temps que l'on met pour trouver une solution...

je crois que les parenthèses ne sont pas autorisées dans le jeu original

la solution donnée par Cliffe est satisfaisante de ce point de vue là, mais effectivement avoir
(3+5/2)*4 pour trouver 22 n'est pas correct

[Cliffe]

on a le droit au multithread ?

[Zorro_X]

Au temps pour moi, j'étais parti dans la mauvaise direction : calcul uniquement séquentiel où je n'utilise pas de sous-opérations/sous-totaux. 5/2 n'est pas valide parce que la division n'est pas entière, ca j'avais pris en compte...
Par contre j'étais parti sur du réentrant, le temps limite est dès lors facilement contrôlable. Mais si j'ai bien compris il y a deux aspects :
1) trouver une solution le plus rapidement possible ;
2) pouvoir définir un temps limite pour arrêter la recherche; et dire à ce moment là qu'il n'y a pas de solution.

[fatal_error]

on a le droit au multithread ?

non, sauf si tu fais un truc style maitre esclave, mais si chaque thread fait la même chose, ca n'a pas grand intérêt, autant acheter un 32 cores... ou plus. Autrement dit c'est asse subjectif, mais si tu proposes une modélisation ou chaque thread a son rôle alors ca peut etre intéressant, oui.

1) trouver une solution le plus rapidement possible ;

non.

2) pouvoir définir un temps limite pour arrêter la recherche; et dire à ce moment là qu'il n'y a pas de solution.

non plus.

il faut pour une liste de plaque donnée, et un goal donné, minimiser le temps pour pouvoir affirmer qu'il n'y a pas de solution.
il ne s'agit pas de dire hop 1min est passée, j'arrête.

il s'agit de dire...ayayaye parmi tous les candidats qu'il me reste a explorer pe qu'il y a une solution alors je continue.
et de mesurer le temps jusqu'à ce que tu sais qu'il n'y a plus de candidats.

Un moyen de comparaison pas trop compliqué à mettre en place est le suivant.
Il faut trouver une main (liste de plaques + goal), goal < 1000000, plaques < 250, tq la main n'admet pas de solution.
Chacun doit se débrouiller pour pouvoir descendre sous la minute.
Une fois fait, il donne sa main, son code et les autres attestent du résultat.
Au final, il suffira que chacun soumette la main sur laquelle il échoue (ou pas) pour confronter l'algorithme des autres à celle-ci.

n personnes, n mains

[Zorro_X]

Si tu veux pouvoir être sur qu'il n'y a pas de solution il faut alors parcourir tous les états possibles et valides, donc respectant les conditions que Cliff a déjà énoncé : pas de division non-entière, pas de passage sous zéro, etc...

[Rockleader]

Au risque de dire une connerie, si vous chercher la rapidité, pourquoi ne pas faire tourner plusieurs processus en simultané ? Linux fait ça très bien en théorie^^

[Zorro_X]

Ce n'est pas une bêtise Rockleader, c'est ce que demandait Cliffe en faisant référence au multithread. Dans notre cas vu que le calcul prend quelques secondes c'est plutôt inutile, mais cela reste faisable, à condition de bien séparer les branches calculées par chaque processus/thread pour éviter de calculer deux fois la même chose (cf. fatal_error). ;)

[Rockleader]

Viens de comprendre ce que thread voulait dire :ptdr: Merci :zen:

[Zorro_X]

un thread n'est pas tout à fait un processus, c'est ce qu'en français on appelle un "processus léger". Ce sont bien des bouts de code qui tournent en parallèle, mais pour simplifier, la plus grosse différence concrète réside dans le fait que deux threads sont dans un même processus et partagent donc le même espace mémoire, par conséquent ont tous deux accès aux variables globales. Un processus c'est comme un "programme" à part entière, ca ne partage pas grand chose avec d'autres processus, sauf si besoin par le biais des "IPC" (Inter-Process Communication : tunnels, mémoire partagée, sémaphores/mutex, fichiers du système, communication réseau, etc...)...
Mais je m'éloigne du sujet initial, tu vas certainement apprendre tout ca en cours... ;)

[Cliffe]

Mon appli :lol3: :

[CENTER] [/CENTER]

Personne n'a essayé ?

[Zorro_X]

je suis en train de créer la plus grosse usine à gaz du monde... mais si, je suis en train d'essayer, je n'ai encore rien de concluant mais je crois que je vais avoir du mal à te rattraper Cliffe...

[Ben314]

Perso, le bidule que j'ai fait trouve sa première solution :
1 + 2 = 3
8 x 12 = 96
90 / 9 = 10
18 + 96 = 114
107 x 114 = 12198
12198 - 3 = 12195
82 x 12195 = 999990
10 + 999990 = 1000000
en moins d'une minute, mais ensuite il en trouve des tonnes d'autres (6240 précisément) mais en plus d'une heure (j'ai pas chronométré...)

[anthony_unac]

Bonsoir,
Le compte est bon certes mais il serait encore meilleure en posant comme contrainte d'avoir pour seuls outils (papier+crayon) ou pire encore rien du tout : vous prenez les joueurs vous les enfermez dans une pièce et vous affichez juste au tableau le compte et les nombres (ou pire encore vous dictez le tout une fois et une seule fois dans une pièce obscure).
Le premier qui trouve la solution quitte la pièce pour donner le résultat.

[Zorro_X]

Le premier qui trouve la solution quitte la pièce pour donner le résultat.

Il me semblait que dans la section "informatique" nous cherchions un algorithme optimisé amusant plutôt qu'une punition intellectuelle...

[Ben314]

C'est pas franchement lié à ce topic spécifique, mais pour ajouter un truc à ce que dit Zorro_X, perso. j'ai toujours trouvé très différent les (éventuels) plaisir qu'on peut avoir à résoudre un problème donné versus le plaisir qu'on peut avoir à faire un programme pour résoudre le problème en question.

Par exemple, les Sudoku, j'ai jamais "accroché" en temps que joueur (les gouts et les couleurs...) mais j'avais pris pas mal de plaisir à faire un programme pour les résoudre, puis au moins autant à regarder sur le Net les différents algos qui avait été proposés (dont certains pas mal chiadé...)

Et pour "le compte est bon", c'est pareil : de jouer "pour de vrai" au jeu, on peut vraiment pas dire que j'en rêve la nuit, donc les modalités d'un jeu "en vrai", par exemple est-ce que ça serait mieux sans papier ni crayon qu'avec ?, on peut pas dire que ça m'intéresse. Alors que de chercher un Algo. plus ou moins optimal, je trouve ça très marrant.

@Fatal : tu as essayé de regardé la méthode dont je parle plus haut ?
Je peut te filer le code que j'ai, mais tu va hurler... (et éventuellement y passer des plombes vu l'illisibilité du bidule)