Bonjour,

voilà hier j'ai fait la dernière évaluation pour entrée à l'école 42 (Créer par le fondateur de Free Xavier Niel). Encore un test bien surprenant à mes yeux, je réussi les deux premiers exercices en 10 mins avant de tomber sur un que les 110 minutes restantes ne m'ont pas suffit à résoudre. Même si c'est trop tard pour moi, j'aimerai cependant que vous m'aidiez à trouver la solution et si possible m'expliquer la démarche à suivre pour ce types d'exercices. (Je suis en Terminal S)

Le but de cet exercice est de manger tous les carreaux bleus, pour cela c'est simple des qu'on sort d'une case celle-ci est automatiquement manger. On ne peut pas passer sur une case blanche (ou manger). 

Merci d'avance à tous ceux qui prendrons la peine de chercher

Je dirais que ça revient à un parcours de graphe en profondeur et qu'il suffit de tourner toujours à gauche ou à droite. J'attends confirmation mais je le sens bien comme ça (j'ai pris quelques codéine faut pas trop m'écouter )

Merci de ta réponse rapide

Mais tourner toujours à droite ou toujours à gauche ne fonctionne pas

En attendant je vais faire quelques recherches sur les graphes ...

Ah oui en effet, faut que j'arrête le cocktail de médoc moi !

Je dirai que faut faire une sorte de découpage de blocs qu'il faudrait vider les uns après les autres.

Voilà suivant tes conseilles, et le peut que j'ai déjà pu lire sur ces graphes, il me semble impossible !!

En effet dans la zone jaune sur l'image ci-dessous on à jusqu'à 5 entrées/sorties si on veut ne pas finir dedans il faut donc en manger une sans laisser d'impasse. Cependant dans ce cas il est impossible de manger 100 des carreaux de cette zone.

Dans la zone rouge c'est pareil des qu'on rentre on ne peut pas tout manger et en ressortir.

On ce retrouve donc à mes yeux avec deux zones dans lesquels ont doit finir notre chemin

Ma question, maintenant est donc plutôt de savoir comment démontrer mathématiquement que cet exercice est impossible ou que je me trompe

-
Edité par Cbourree 23 mars 2014 à 14:31:12

 Bonjour,

je n'ai pas beaucoup cherché mais il semble effectivement y avoir un fort blocage sur la partie droite du dessin (...à ce stade, je dis pas encore impossibilité).

Par contre je me suis dit que l'on pouvait aller en diagonale sans passer formellement par les cases blanches   

dans le texte ce n'est pas explicitement interdit  et dans le schéma explicatif à droite, la configuration que je donne n'est pas représentée !

Bon , a contrario  , si c'était  autorisé, cela devient "ridiculement" facile .....  ...ou alors le 'piège' serait de penser à la diagonale

 edit

excuse pour  le gigantisme inutile du dessin ! mais, le changement de taille dans l'envoi d'images ne semble avoir aucun effet (?) 

-
Edité par Sennacherib 24 mars 2014 à 16:26:43

Bonjour et merci du temps que vous me consacrer, cependant je pensais que les flèches sur l’images jointe étaient suffisante ...

Fin bref, C'EST IMPOSSIBLE !!! Le vraie but de cet exercice était de "hacker" le site web, du moins c'est ce qu'un mec raconte sur un forum capture à l'appui. Cela me parait probable pour un recrutement d'école d'informatique ^^ 

Je met donc le sujet en résolu, mais si vous avez le courage de vérifier

Hmm ce problème est hélas très dur à résoudre puisqu'il s'agit du fameux chemin hamiltonien : y-a-t-il un chemin passant par tous les sommets (ici les cases) d'un graphe une et une seule fois ?
C'est un problème NP-complet en général (ça veut dire "pas faisable en temps raisonnable"), mais sur ces cas particuliers de grille c'est peut être polynomial, mais j'en doute.

Bonjour,

Théorème — Un graphe orienté simple fortement connexe à sommets dont chaque sommet est au moins de degré entrant et de degré sortant est hamiltonien.

dans les zones encadrés en  jaune et rouge il y a à chaque fois un nombre de sommets de degré différents de n/2. Je dirais donc CQFD

(Je n'ai absolument rien compris à ce que je viens d'écrire mais ça me paraît logique ...)

Tout ça pour dire que je suis incapable de résoudre ce genre d’exercices mathématiquement, alors bon votre intervention ne m'aide pas.

Surtout que aucune réponse m'a été donné pour mes deux preuves d'impossibilités ...

Cbourree a écrit:

Bonjour,

Théorème — Un graphe orienté simple fortement connexe à sommets dont chaque sommet est au moins de degré entrant et de degré sortant est hamiltonien.

dans les zones encadrés en  jaune et rouge il y a à chaque fois un nombre de sommets de degré différents de n/2. Je dirais donc CQFD

(Je n'ai absolument rien compris à ce que je viens d'écrire mais ça me paraît logique ...)

Tout ça pour dire que je suis incapable de résoudre ce genre d’exercices mathématiquement, alors bon votre intervention ne m'aide pas.

Surtout que aucune réponse m'a été donné pour mes deux preuves d'impossibilités ...

Mon intervention servait donc à te donner le nom du problème auquel tu fais face, pour que tu cherches des outils mathématiques qui te permettent de prouver que c'est impossible.
Le théorème que tu as trouvé ne sert à rien dans ce cas. Il faudrait plutôt un théorème "négatif" : si un graphe contient ..., alors il n'existe pas de chemin hamiltonien.

-
Edité par Timot 26 mars 2014 à 16:36:40

Je me suis renseigné aussi sur cet exercice, ma réponse est un peu tard, mais elle servira surement à d'autres membres, il semblerait que cet exercice soit impossible, le seul moyen de le finir serait de ... pirater l'évaluation, fais quelques recherches sur google tout y est expliqué avec les outils de dev offert par Google

Bonjour,

j'aime bien les problèmes et je me suis pas mal cassé la tête avec celui-ci, espérant naïvement trouver une solution. Après avoir lu vos coms, j'ai compris qu'il n'y en avait vraisemblablement pas. J'ai trouvé sur le net une explication de la façon dont il fallait en réalité le résoudre, en "hackant" la page web où tournait l'application : http://nicotupe.fr/Blog/2013/05/ma-candidature-a-42-epreuve-5/.

Notez que l'explication de l'auteur de l'article n'est pas rigoureuse mathématiquement parlant. Mais il a effectivement détecté deux points dans son parcours d'où on doit soit démarrer, soit terminer. Comme le point de départ imposé n'est pas un de ces deux points, le parcours est à l'évidence infaisable.

Par contre, dans celui que vous avez présenté ici, la non faisabilité du parcours apparaît nettement moins facilement. J'ai quelque peu analysé celui-ci afin de "démontrer" que cela ne peut pas fonctionner (oui, je sais, j'ai du temps à perdre ).

Si je reprends le parcours, avec quelques annotations :

Ce qu'on peut en dire :

• On doit obligatoirement terminer le parcours quelque part dans la zone entourée en bleu.
• Le bloc central contient 6 points d'entrée/sortie (e/s) possibles : A, B, C, D, E et F.
• Il faut obligatoirement emprunter les e/s A, B et C sans quoi la case isolée qui les jouxte ne sera jamais mangée.
• Après pas mal d'essais, on se rend compte également que la D est obligatoire, sans quoi on se retrouve enfermé dans un des blocs juste au-dessus à droite.
• J'ai mis des flèches à des endroits où la direction est imposée. Pour celle à gauche du A c'est évident, sinon impossible de revenir à la branche de gauche par après.

En rassemblant les diverses infos :

• Vu qu'on doit terminer en-dehors du bloc central, cela signifie que la dernière porte qu'on emprunte, ce sera dans le sens "sortie". Vu qu'on commence par une sortie, il faut passer par un nombre impair de portes (exemple : s - e - s - e - s).
• Comme on a déjà 4 portes imposées (A, B, C et D), reste à voir s'il est possible d'entrer/sortir par E sans entrer/sortir par F (afin d'avoir 5 e/s). Or c'est impossible, car si on sort/entre par E, on coupe l'accès à la branche sur laquelle débouche F et réciproquement.

Conclusion : Problème insoluble.

Pour le fun, je vous montre quand même le meilleur "score" que j'ai réussi à faire sur cette map : 2 cases non mangées.

Au plaisir,

Ecu

EDIT : Si quelqu'un a une démonstration plus formelle (via la théorie des graphes ?) pour prouver que ce parcours est impossible, ça m'intéresse.

-
Edité par Ecu 28 mai 2014 à 16:20:09

Ravis de voir que cela t'auras au moins occupé ^^ 

Ayant passé des heures à me casser le tête dessus, je peux cependant t'assurer qu'il est possible de ne laisser qu'une seule case !! 

Je n'aurais vraiment pas le courage de me plonger à nouveau dedans afin de te donner cette solution mais celle ci existe donc si jamais tu as encore un peut de temps à perdre xD 

-
Edité par Cbourree 5 juin 2014 à 16:34:52

Bonjour, 

De mémoire, cet exercice est possible. J'ai passé le même l'an dernier, et j'ai bloqué deux exercices après ( qui lui me semblait bien impossible par contre ). Je vais voir si j'arrive à retrouver la réponse.

Bon je relis certain post en même temps que j'écris celui ci, l'exercice où j'ai bloqué (donc deux exercices plus loin que celui-ci) est celui indiqué dans le lien posté par Ecu.

Bon, c'est parti pour le casse tête alors

Petit (gros?) up, j'avais du temps à perdre donc j'ai esseyer de résoudre ce problème, pour moi c'est impossible à résoudre.

Cependant j'ai fait un chemin, où j'ai laisser une case, si ça peut inspirer d'autres personnes.

bonjour à tous, un autre qui semble impossible, j'ai lâche l'affaire^^ si vous aimez les casses têtes^^

-
Edité par Ben40000 5 novembre 2014 à 18:09:11

 @Ben4000

Il me semble que j'avais réussie le tiens et peut être Est-ce comme le mien :

le dernier exercice de ton dernier test est impossible il faut *hacker* le site pour pouvoir le finir(clique droit ->code source de la page->changer la grille par une solution simple)

@ Ben40000 : En fait la solution de ton exercice existe mais n'a aucune logique de prime abord :  en observant le déroulement du programme au dessus du schéma tu remarqueras peut-être que des instructions s'empilent quand tu boucles avant la fin de la fonction.

Il y a d'autres exercices qui font usage de cet empilement d'instructions.

-
Edité par EtienneDuport 7 décembre 2014 à 18:14:43

Une synthèse peut donner ceci ( une solution exacte ) :

-
Edité par ArbreAbuche 9 décembre 2014 à 23:46:16

Euh...

Non CE N'EST PAS POSSIBLE !!!

@ArbreAbuche tu as oublier que la case de départ est imposé

A tout ce qui disent que c'est possible : PROUVEZ LE !!!!

Cbourree a écrit:

A tout ce qui disent que c'est possible : PROUVEZ LE !!!!

Ça vaut aussi pour ceux qui disent que c'est impossible. Figure-toi que c'est même plus dur de démontrer que c'est impossible que l'inverse

L'impossibilité est relative - C'est en forçant le passage que les interdit tombent :

Tu as mangé un clown, ce matin ?

En effet, en forçant le passage ça marche ... mais pas dans les règles 

Bonjour Ben4000, pour ce qui est du casse tete avec les cases vertes et oranges, j'avoue que j'ai mis du temps, en fait il fallait faire (si je me souvient bien)

F1 : (haut)- F1vert- haut-gauche-haut-droite

-
Edité par lysafichot 22 janvier 2015 à 2:47:39

.

-
Edité par IliaLaliashvili 2 juin 2016 à 1:45:22

Bonjour,

j'ai fais les tests pour 42, piscine compris (je suis officiellement étudiant ).

Pour le test de 10 minutes j'utilisais un marqueur quand mon cerveau ne pouvait plus stocker le nombre de case^^

et pour celui de 2 heures je suis allé jusqu'au niveau 16.

tout les tableaux sont fesable, il n'y a pas de secrets. ta liste de fonction te permet de résoudre chaque tableau, a partir du niveau 5 il faut juste commencer a comprendre l'empilement d'action et les multiples retours de fonctions.

Je suis triste de voir que 42 recrute des gens, qui déterrent des sujet vieux de deux ans, qui disent des choses qu'ils sont incapable de démontrer, qui remplisse leur message de phrases inutiles et qui se la racle.

Mais sinon félicitation Florent Gréa.

Salut, 

Je profite du up (après tout, c'est pas moi qui a commencé :D)

Il y a 3 ans j'ai fait le test pour 42 (uniquement pour l'autosatisfaction et la curiosité de faire les tests). J'étais tombée sur un problème similaire (serait-ce le même ?) où j'avais prouvé qu'on ne pouvait pas le faire (du moins vite fait et sur brouillon). 

S'il fallait hacker pour réussir, je trouve ça nul... Après tout, 42 ne se dit-il (elle ?) pas ouvert(e) à tous et sans niveau minimum en informatique ?

Si j'ai le temps j'essaierai de voir ce que je peux faire

Edit preuve faite mais c'est fastidieux à expliquer : (par avance, désolée pour la taille des images)

Un premier jet où on relie tout ce qu'on peut déjà relier parce qu'on n'a pas le choix : (en marron, les "coins" formés par les autres traits)

 On déduit l'emplacement de la fin : le point rouge.

On déduit donc aussi que la case à gauche du départ est la deuxième case :

Maintenant zoomons au niveau de la fin : la case avec un point orange a deux possibilités de liens à gauche et en bas. Faisons l'hypothèse que c'est à gauche et voyons où ça mène:

Encore une fois on a deux possibilités (le deuxième point orange)

hypothèse 1-1 :

Le point rose est un soucis : dans cette configuration il n'a qu'un voisin possible donc c'est la fin. Ce qui est impossible puisqu'on a déjà une case finale

Donc on passe à l'autre possibilité, le bas et l'hypothèse 1_2

Encore une fois, pas possible donc l'hypothèse 1 est fausse, ce qui nous force à l'hypothèse 2 :

Et on se retrouve dans le même cas de figure qu'avec l'hypothèse 1 donc le problème n'a pas de solution.

Si je devais le faire d'une manière plus "mathématiques", je pense que j'utiliserais les arbres couvrants (enraciné si ça existe) pour voir s'il y a plusieurs feuilles (plus d'une si on accepte la racine qui est le point de départ)

-
Edité par Ccile 19 août 2016 à 20:32:53