QCM 2011 Sujet 4

Peut-on passer 2 fois sur la même case ? Ou bien une fois que la case a été le centre du pinceau, on ne peut plus passer dessus avec le centre ?

Je crois que rien n'empêche de repasser sur un point donné. Maintenant je doute de l'utilité de ce mouvement.

Inutile de repassé sur le même point? Oulalala, je suis encore plus embrouillé, je voit vraiment pas comment m'y prendre, pour l'instant, mon algorithme peut passer par moment 3/4 fois par le même points (pas à la suite, mais après d'autres opération), et ne résous pas tout les cas, juste quelques uns...

@TLN : Ça va, tu t'amuses bien à les appâter ? ;)
La réponse commence par un 4 et finie par un 2.

Mais euh, si on a plus le droit d'être evil. De toutes façons il y a paraît-il une solution super rusée, que je n'ai a priori pas trouvée, donc j'ai pas vraiment le droit de me la péter pour l'instant =)

Bon ne trouvant toujours pas, et là les indices qui n'aide absolument pas, j'ai loué quelques bouquins d'algorithmique à la Bibliotheque... J'espère trouver mon bonheur... Encore si je savais où chercher...

C'plus de la réflexion personnelle qu'un algo tout fait à trouver dans un bouquin je pense. Le tout c'est de :
1) Trouver un exo qui résoud le problème (même en un temps exponentiel affreux)
2) Remarquer quelques "propriétés" de ce sujet, cf le post de Mvy par exemple (que se passe-t-il si on applique deux fois le pinceau sur la même case ?)
Une fois qu'on a remarqué certains trucs, on peut "réorganiser" son algo de manière à ce qu'il passe en temps.

Ouaip les bouquins m'ont pas aider, je penser trouver certaine notion mais bon....
Sinon bah mon algo résouds les problèmes, mais pas dans tout les cas... Donc faut corriger ça... Sinon me reste a remarquer les propriétés...

Il n'est écrit nulle part que Joseph Marchand a effectivement réussi à craquer son logiciel, on sait juste qu'il a corrompu son pinceau.
est-ce que je peux considérer que le logiciel ne fonctionne toujours pas et qu'il est incapable de faire le moindre dessin et donc toujours faux? mdr :-)

Bon franchement, je deviens chauve, mais j'aimerais savoir si je cherche la bonne chose...
Doit-on vraiment faire un programme qui cherche à n'avoir que des 0 dans le tableau?
Car j'ai de plus en plus la conviction que faire ça ne sert strictement à rien... En effet dans le cas où la résolution est impossible, le programme va tournée en boucle...
Donc je me demande, s'il ne faudrait pas plutôt trouver une condition qui dit que le programme est possible ou non sans chercher à le résoudre?

Il existe un algo qui essaye de faire son possible pour obtenir l'image cherchée et qui termine quoi qu'il arrive (fin mon algo fonctionne exactement de la même manière que la réponse finale soit 1, ou 0). En espérant que ça t'aide :p

Fin dit autrement : ton algo ne doit pas boucler indéfiniment en faisant toujours la même chose. (Essaye à la main sur un dessin genre 2x2, tu verras qu'il n'y a pas une infinité de modifications possible => un algo qui marche peut donc tester si l'image est reproduisible en effectuant un nombre fini d'opérations (comme on ferait à la main quoi), donc sans boucler indéfiniment).

Oui je sais comment éviter qu'il boucle à l'infinie, j'ai fait un tableau qui enregistre toute les "entrée final" et si deux entrée son identique, c'est qu'il tourne en rond, donc sorti du programme... Problème, par moment, il tourne en boucle sur des cas possible, et là je vois pas mon erreur x) à certain, il va me trouver une solution, à d'autre non... C'est galère... J'aimerais exposer mon raisonnement pour qu'on me dise où se situe mon erreur, mais j'ai peur d'en dire trop et que je me fasse taper sur les doigts x). N'y aurais t'il pas une âme charitable pouvant m'écouter en privée, et me dire où se situe le problème dans mon raisonnement? Attention je ne veux aucune réponse par contre, juste dire je suis bien parti ou pas dans ma résolution...

Une question pertinente à se poser c'est : est-ce que l'ordre des cases sur lesquelles je clique a une importance ? Autrement dit, est-ce qu'il faut retourner les pixels dans un ordre précis ou est-ce que ça ne change rien ?

Ya déjà assez d'indice comme ca non ?
Faut quand même laisser un peu de réflexion, c'est un peu l'intérêt de cet exercice qui pour une fois n'est pas que question d'algorithmie mais surtout une sorte de casse-tête :).

@volent: +1
Pour une fois qu'un coup de google ne résolve pas le le problème…

Google ne résous pas le problème certes, mais peu aider, si on connais le nom du casse tête, par exemple le jeu original est de taille 5*5 et j'ai pu voir comment résoudre en cette taille là... Hélas, je ne sais pas comment étendre a toute taille...
Puis un petit truc qui m'as fait sourire, je joué à SAW II blood and flesh sur Xbox, et là je tombe sur une énigme... Et deviné quoi? C'est exactement le problème de l'exo 4... Je me suis dit "Punaise, ce maudit exo que je sais pas faire me suit partout" xD

Pfff... Trop facile, les exos d'éliminatoires, cette année :-p

Si on ne compte pas les erreurs de module Python pas disponibles sur le serveur (allez, "copy" quoi ! vous pouviez quand même nous laisser utiliser copy...), j'ai passé tous les tests de tous les exos du premier coup. Et même en local \^\^

En plus j'ai écris les exos 1 à 3 hier en genre 30 minutes. Et le 4 ce matin en 1 heure.

Comment voulez-vous qu'on impressionne les petits nouveaux, quand les exos sont aussi simples :-p

J'ai une question sur cet exo, j'ai trouvé une méthode de résolution qui utilise de l'algèbre linéaire. Je dois expliquer ma solution lors de ma soumissions ou bien juste donner le code comme ça?

Un code bien commenté est généralement apprécié. Par bien commenté, j'entend des commentaires clairs et au possible concis.
Bien sur cela ne sert à rien de commenter chaque ligne de code, si celui-ci est clair, juste décrire le fonctionnement général de l'algo peut-être suffisant ;)

Me revoilà,

toujours sans solution pour cette exercice, du moins presque sans solution, car j'en ai trouvé une utilisant l'algèbre linéaire, mais pour ça faut initialisé des matrices pour avoir un système d'équation, puis après faire un pivot de gauss, ect...

Je doute que ce soit la bonne méthode, sachant que tous ont moins de 20 ans, ce qui ne laisse pas beaucoup de monde ayant vu les matrices... Ça fermerais les portes a beaucoup de monde, donc je me dit qu'il y a une autre solution, vu que certain arrive en plus a la solution en 50 lignes de codes...

J'ai beau avoir trouvé les propriété d'ordre et de ce qu'il se passe en appuyant sur la même touche, hélas, je trouve pas de résultat facile, en faite, je n'arrive même pas a résoudre le problème facilement intuitivement (sauf en faisant de grande matrice, et faire un pivot de gausse de taille gigantesque qui me prend 4 page de calcul tellement les matrices sont grande).

Je me pose aussi une question, chercher a revenir à l'état d'origine ou venir à l'état actuelle est elle la bonne méthode? Car bon, sans passé par l'algèbre linéaire, je vois pas la méthode qui permet d'arriver a chaque fois au résultat... De plus on demande juste si c'est possible ou non, donc pas forcement de le résoudre.

Bref je désespère sur ce malheureux exo4 ...