Enigmo 15 : L'interrupteur aléatoire

Posté par mikayaou mikayaou

Et toc !...

second degré, bien sûr

Posté par infophile infophile

Bonsoir

Juste pour parler un peu de la programmation :

Jusqu'à l'année dernière où je n'avais jamais touché à la programmation je pensais que c'était un "outil magique" qui en tapant deux trois lignes de codes fournissait la réponse à l'énigme sans se casser la tête. J'avais tord, car pour obtenir la réponse de cette façon il faut pouvoir concevoir le programme de A et Z, et il faut faire preuve comme en maths de rigueur et de logique :

1) Etablir une stratégie pour résoudre le problème, c'est-à-dire concevoir un algorithme répondant au problème.
2) Mettre en forme celui-ci avec le langage utilisé.
3) Optimiser le programme ainsi crée.
4) Vérifier la robustesse de ce dernier, en d'autres termes s'assurer que l'exécution du programme couvre bien tous les cas.

Et étant débutant je vous assure que ce n'est franchement pas évident

Donc même si le recours à l'informatique est moins "élégant" qu'une belle démonstration mathématique, cette méthode reste toutefois intéressante et loin d'être simple.

A+

Posté par master_och master_och

Bonjour

Tout à fait d'accord avec toi infophile, il m'arrive parfois de commencer la réalisation d'un programme pour generer toutes les solutions et au cours de sa réalisation je me dit que j'aurai pu economiser beaucoup de temps si j'ai essayé de trouver une seule solution à la main.

Posté par dhalte dhalte

Je rejoins tout à fait infophile, qui en passant, a dû choisir son pseudo après sa conversion.

J'ajoute qu'une branche très importante et très active des mathématiques actuelles étudie justement les processus de programmation (algorithmique, preuves, optimisations, cryptages, et j'en passe), et que c'est justement en grande partie grâce à cette recherche que vous pouvez, amis Toiliens, partager aujourd'hui de si beaux instants mathématiques à travers le réseau, les images si rapidement échangées et affichées, le silicium qui, de vulgaire sable de plage, est devenu le cerveau oh combien performant de vos ordinateurs.

La recherche de solutions singulières dans la théorie des groupes n'a pu se faire que grâce à des programmes informatiques et donc grâce à des chercheurs mathématiciens qui, heureusement pour l'avancement des sciences, ne se sont pas sentis dévalorisés par l'utilisation de cet outil.

Notre activité à nous est ludique. Les énigmes proposées ont déjà été résolues, nos trouvailles ne vont pas faire avancer la connaissance de l'humanité. Aussi, il est concevable que celui qui propose l'énigme émette des règles du jeu, comme par exemple l'interdiction de tout moyen électromécanique pour prouver sa solution. Mais en dehors de tels préceptes explicitement énoncés à l'occasion de chaque énigme, je ne vois pas quel manque d'élégance il y aurait à utiliser un outil ma foi fort puissant.

Et la maitrise de l'outil n'est pas en soi un motif de rejet, ce serait comme de reprocher à un sauteur à la perche sa grande taille. Ou à Srivanasa Ramanujan son cerveau ou les conditions de sa jeunesse qui l'ont poussé vers la voie qu'il a choisie.

Au final, les résolutions que je mène par ordinateur m'apportent moins de satisfaction que celles que je résouds par la logique pure, mais quand celle-ci se montre rétive à ma sagacité, j'avoue que l'alternative me convient.

@master : je te conseille par la suite d'inverser le processus, de commencer d'abord par rechercher des solutions par la logique. C'est cette recherche, si elle s'avère stérile dans un premier temps, qui doit mener aux idées qui vont te permettre de concevoir un programme adapté, voire élégant.

Ceci dit, je vais maintenant à la manif. Il n'y a pas, hélas, que les activités purement intellectuelles dans la vie.

Posté par master_och master_och

Bien dit dhalte .

Posté par borneo borneo

Hello,

ceux qui pensent que le recours à l'informatique est "fastoche" sont souvent ceux qui ne savent pas s'en servir  

Posté par matovitch matovitch

Bonjour à tous!
Je ne sais pas si c'était du second degré, mais en tout cas c'était de l'humour!
Je fais partie des sous-programmeur (et même en-dessous ) vu que je programme particulièrement en VB6...
qui d'après de nombreux avis (issus de codes sources) est plus rapide que le VB.net.
J'ai aussi fait un test entre le VB6 et le C (avec un test de primalité), et le C s'avère un peu plus rapide.
Je vais essayer de verifier tes calculs en faisant mon algorythme on pourra ainsi comparer.

Posté par dhalte dhalte

Alors c'était du second degré, ou de l'auto dérision.

algorithme et pas algorythme, quoique dans un algorithme qui balance, on y trouve souvent du rythme.

Bonne programmation à toi alors.

Posté par matovitch matovitch

Merci dhalte, mais j'ai du mal! (ça fait une demi heure que je fait du débug )

Posté par matovitch matovitch

ouille! (je fais)
Peux-tu m'expliquer brièvement comment fonctionne ton programme ?
(une boucle que tu  mets en binaire ?)

Posté par dhalte dhalte

  ' Technique de recherche de connectivité des circuits :
  ' On part de circuits élémentaires qui sont représentés par les extrémités de chaque cavalier.
  ' On compare chaque circuit avec les autres pour déterminer s'ils ont au moins un point en commun.
  ' Si oui, on fusionne ces deux circuits.
  ' On recommence tant que on trouve au moins une intersection.
  ' A la fin, on a les circuits individuels.
  '
  ' Dans notre cas présent, on ajoute aux circuits représentés par les 9 cavaliers les deux circuits reliant d'une part les quatre plots de gauche, et d'autre part les quatre plots de droite.
  ' Ainsi au final, si on trouve un circuit contenant le plot en haut à gauche ainsi que le plot en bas à droite, alors les deux bords sont connectés.

Posté par dhalte dhalte

J'ai oublié de dire que cette recherche que je décris dans mon topic précédent concerne uniquement une configuration donnée. Je fais aussi une boucle externe sur les positions possibles des cavaliers.

L'algorithme définitif de recherche de connectivité est légèrement différent de l'explication car j'y ai ajouté des optimisations purement techniques.

Posté par matovitch matovitch

Je me noie dans ton vocabulaire technique, enfin de toute manière quand on programme, on ne comprend jamais que soit même, et ce malgré l'abondance des commentaires

Posté par matovitch matovitch

Ouf!
J'ai enfin terminé mon programme, mais, chose inquiètante : je ne trouve pas pareil que toi !

P(1) = 1 (instantané)
P(2) = 14/16 (instantané)
P(3) = 434/512 (instatané)
P(4) = 54704/65536 (5 secondes)

Je vais mettre le code sur internet ce soir...si tu veux plus d'informations je suis disponible.
(sache que je suis persuadé que mon algo marche je l'ai verifié et revérifié...)

Posté par dhalte dhalte

Matovitch. Je crois que Code Source a analysé ton programme et qu'il l'a refusé, va savoir pourquoi...

Plutôt que polluer le topic de crapul, je te propose de continuer à polluer Enigmo15.

Posté par matovitch matovitch

Oui, pardon excuse-moi, c'est bon (j'ai du télécharger firefox   )
Voici le lien (pas d'exe et désolé pour le multipost):

Posté par matovitch matovitch

Je trouve : P(5) = 27811232/33554432 (1h 5min)

Posté par dhalte dhalte

Désolé, mais avec aucun commentaire pour me guider, je n'ai pas la fibre humanitaire suffisante pour déboguer ton programme.

Posté par matovitch matovitch

Alors tu es humain !
D'accord, je mets à jour tout de suite !

Posté par matovitch matovitch

Bonsoir dhalte!
J'avais tort, il y a un bug dans mon programme.
Il ne prends pas en compte les vrai rebroussement comme :

Posté par matovitch matovitch



Je te renverrai la version corrigée de mon programme (commentée)!
Sinon merci, car tu m'as fait aprécier la vrai difficulté du problème.

Posté par dhalte dhalte

Parce qu'il y a des vrais et des faux rebroussements ?

Posté par simon92 simon92

tu savais pas?

Posté par dhalte dhalte

Eh, Simon, tu te marres comme une baleine et ça fait vraiment plaisir à voir.
Tu l'avais cherchée la réponse à cette énigme ? Qu'est-ce que tu en penses ?

Posté par simon92 simon92

oulala, j'essaie de mettre de la bonne humeur, j'espère que c'est pas reproché.
En tout cas, je vous felicite tous pour vos programmes car je serais incapable de faire votre travail.
J'ai lu plus haut que tu n'aimais les gens qui disaient que c'était de la triche les solutions programmées et tout, je suis tout a fait d'accord avec toi, mais je pense tout de même qu'une solution purement mathématiques, est beaucoup plus élégante.
Je n'ai pas reflechit à ce problème car, je fais moins souvents maintenant les enigmes mensuelles, je vais peut-être m'y remettre un peu .  Vu que celle ci ne m'a pas inspiré et ne m'aurait rapporté qu'un poisson je n'ai donc pas participé .
J'espère que j'ai le droit de parler sur ce topic si je n'ai pas participer a l'énigme.

J'espère avoir mal compris le sens de ton post

Posté par borneo borneo

Hello,

moi j'ai cherché, mais pas trouvé.

Bravo à ceux qui s'y sont risqués.

Posté par isisstruiss isisstruiss

Bonsoir,

Je me permets de m'immiscer dans votre discussion maths/info pour apporter un nouveau regard, étant moi-même amatrice de mathématiques appliquées, donc à cheval entre les deux manières de procéder.

Autant en maths qu'en info on peut se contenter de raisonnements très bêtes ou développer la manière de procéder. Faire un algorithme "force brute" pour résoudre un problème est du même niveau que tester toutes les possibilités de tête, à la main, avec un tableur ou peu importe. On peut, de tête, éliminer beaucoup de possibilités et chercher une solution au problème par raisonnement. De même, on peut, de tête, réfléchir à un algorithme efficace, c'est-à-dire de faible compléxité, qui ne se contentera pas de faire des bêtes boucles. L'algorithme réfléchi éliminera certains sous-arbres de l'exploration soit parce qu'on ne trouvera pas de meilleure solution que celle trouvée pour l'instant, soit parce que le calcul est équivalent à un autre sous-arbre. On évitera à l'ordinateur de faire le même calcul des nombreuses fois tout comme on ne le ferait pas nous-même. Ceci est très important dans les algorithmes itératifs ou dans des nombreuses boucles.

Ma conclusion est que choisir entre papier-crayon et programmation n'est en aucun cas une indication du niveau du raisonnement caché derrière. Tout réside dans la manière de le faire. Et le choix papier/programmation doit dépendre aussi du problème à traiter.

En particulier à propos des énigmes de l', on les fait tous pour le plaisir. Ceux qui ne jurent que par le papier-crayon, qu'ils soient heureux ainsi. Ceux qui prennent plus de plaisir à développer un algorithme et programmer, qu'ils s'amusent aussi. Soyez un peu plus ouverts d'esprit pour vous rendre compte que nous sommes tous différents et qu'il est très bien ainsi, il n'y a pas une seule vérité. La beauté est subjective.

Isis

Posté par infophile infophile

+1 Isis

Posté par matovitch matovitch

Je dis "vrai" rebroussement, car le chemin que suit le circuit "recule" d'une colonne, ce qui est possible lorsque l'on a 16 cavaliers où plus...
D'où le bug...que je corrige avant ce soir.

Posté par dhalte dhalte

A Simon :

Tu as tout à fait mal interprété le sens de mon message. Je pensais que mon smiley tout souriant éviterait la méprise. Je suis franchement et sincèrement désolé que tu aies pu même un instant avoir un doute.

Comme tu avais répondu à nos échanges, je souhaitais seulement t'inviter au débat.

Je t'assure que tu es le bienvenu et te réaffirme qu'il n'y avait strictement aucune acrimonie dans mon propos précédent, bien au contraire.

A isisstruiss :
Bienvenue dans notre Club, où Infophile et moi (les deux seuls membres actuellement, mais il reste très ouvert) partageons tes vues.
- Recherche initiale cérébrale
- Analyse du problème, recherche des invariants, d'une méthode de résolution (c'est l' "algorithme", mais il peut très bien être à ce moment humainement réalisable).
- Si le résultat des cogitations ne permet pas humainement de trouver la solution, création d'un "programme" informatique qui réalise le "programme" cérébral établi ci-dessus.
- Plus la réflexion humaine aura été féconde, plus le programme sera compact, élégant, efficace.

Finalement, se jeter sur l'écriture d'un programme sans avoir réfléchi à simplifier le problème initialement, c'est une attitude qui va à l'encontre de l'esprit des énigmes, mais inversement, s'interdire l'outil par principe quand le cerveau seul ne peut aller plus loin dans la démarche, c'est se condamner à continuer à vivre au 16ième siècle.

Mathématiquement et informatiquement vôtre.

Posté par gloubi gloubi

Bonjour,

dhalte, matovitch >> Très étonné du temps de réflexion de vos programmes !

Pour ma part, je trouve p(4) = 54722/2¹⁶ en 0.016 s
et p(5) = 27858752/2²⁵ en 9 s !

J'ai fait des essais sur des interrupteurs rectangulaires;
largeur d'électrode 5, distance inter-électrodes 6: p(5*6) = 783996236/2³⁰ en 422 s,

de même p(6*5) = 968197822/2³⁰ en 360 s.

Je ne me suis pas attaqué au cas 6*6, qui devrait prendre environ 7 heures.


L'explication vient certainement de l'algorithme utilisé.
Personnellement j'emploie la "méthode du labyrinthe":
partant de la case du haut à gauche je suis le "mur de gauche", jusqu'à me retrouver sur une des cases de droite (le courant passe),
ou alors retour sur l'électrode de gauche, case du bas (pas de solution).

Je tiens la procédure, en Pascal (sous Delphi), à votre disposition.

A+,
gloubi
  

Posté par dhalte dhalte

Super, gloubi.

Ton idée est bonne, mais ton explication surement insuffisante, car si je suis ta directive, je trouve que le circuit ci dessous ne connecte pas les bords. Je suppose que tu t'autorises à traverser quelques murs !

Mais elle est effectivement à retenir car certainement plus efficace que mon approche de fusion des circuits, au vu des temps que tu annonces.

J'avais pensé à cette approche de fusion plutôt que de labyrinthe pour le cas d'un interrupteur à 3 dimensions, où l'algo du labyrinthe tombe en défaut.

Posté par matovitch matovitch

Bonjour gloubi!
Je précise que mon programme ne marche pas...
Et je dis bravo à vous 2 car j'ai laissé tomber !

Posté par gloubi gloubi

Bonjour,

dhalte >>



Lequel?

Et pour info, je n'ai pas de murs a traverser! S'il y a un chemin d'une électrode à l'autre, je le trouve forcément.
Pour un interrupteur à deux dimensions, bien sûr.

gloubi

Posté par dhalte dhalte

Tiens, c'est vrai, lequel ?
J'ai dû faire une fausse manœuvre, parce que l'aperçu montrait l'image jointe.

Bon, je la reposte :
Tu disais partir "de la case du haut à gauche" et suivre le "mur de gauche". Je ne dois certainement pas comprendre ce qui est pourtant limpide...

Posté par gloubi gloubi

Bonjour,

Le mur de gauche, en rouge sur le dessin:
en bleu, les murs inutilisés.

A propos j'ai testé le cas 6*6, mais avec une variable qui ne sait compter que jusqu'à 2 milliards et des brouettes,
j'en ai été pour mes frais (6h45 de temps PC perdu). Je vais recommencer avec un réel sur 80 bits, ce sera mieux !

gloubi

Posté par dhalte dhalte

Pigé, j'étais parti sur l'idée que tu considérais les cavaliers comme les murs. En fait, le cavalier est le chemin... De plus, les bords sont eux aussi reliés.
J'ai donc compris ton idée jusqu'au bout. Félicitations.