[pixis]

Postez ici vos messages.

[anthony63]

Ca ressemble fortement a un TSP

[pixis]

Telecom Sud Paris ? Oui, il parait que ce sont tous des alcooliques.

[ferbos]

Ca ressemble fortement a un TSP

Perso, je n'en serai pas si sûr ^^ Mais j'ai pas encore travaillé dessus, je pense à un truc plus commun.

D'ailleurs, à ce propos, je trouve qu'il a ze sacrée mémoire l'ivrogne ^^

ferbos

[Iansus]

Gaston qui part en blackout au premier verre
Sinon, Gaston connaît à l'avance les prix pratiqués dans les bars ?

[pixis]

Non. D'abord il décide de bouger, et ensuite une fois dans le bar il décide de sa boisson.

[Asphator]

Soit j'ai mal compris l'énoncé, soit c'est dommage que dès la 1ère boisson (de la liste) au 1er bar, on soit déjà dans la majorité des cas hors règles/probas. En effet, la 1ère boisson est rarement la moins chère (or quand on dit "en moyenne il choisira la moins chère"...).
Qu'ai-je zappé ?

Ex:
- le 1er bar est le numéro X
- la 1ère boisson de la liste est Y
- je descends jusqu'au bar X et regarde le prix de la boisson Y, c'est quasiment jamais la moins chère...

En attendant, je vais supposer que c'est l'exception ^^ m'enfin...

[harvey]

(or quand on dit "en moyenne il choisira la moins chère"...)

Ce n'est pas ce qui est dit.

En fait, la probabilité de choix d'une boisson est là encore inversement proportionnelle à son prix.

signifie qu'une boisson N fois moins chère qu'une autre a N fois plus de chances d'être choisie.
Même chose pour le choix des bars en fonction de la distance. Et tu n'as aucun moyen de savoir avec certitude que le premier bar est le bar X, le but est justement de retrouver le parcours *le plus probable* (ou le moins improbable) de tous.

[Asphator]

Merci Harvey.

En fait, j'ai bien saisi cette histoire de proba. Et je ne la discute pas pour les N+1 boissons/bars.
Sauf pour la toute 1ère.

tu n'as aucun moyen de savoir avec certitude que le premier bar est le bar X

C'est justement écrit noir sur blanc dans la page aléatoire : "Gaston a commencé sa tournée dans le bar numéro X."
Sur la trentaine de pages de tests que j'ai demandé, seulement une ou deux fois cette 1ère boisson s'est effectivement située dans le top des moins chères. Là est ma surprise. Je peux monter à un millier de tirage tu me diras, j'ai peut-être juste été improbablement malchanceux (ce que je vais supposer pour considérer ta réponse).

[harvey]

Zob, t'as raison. J'ai pas pris le temps de relire l'énoncé.
Mais ça ne change rien. En fait, le problème serait aussi soluble si Gaston partait d'une position quelconque sur la carte (pas forcément un bar). Note que si Gaston fait un choix improbable dans le premier bar, il le fait dans tous les parcours, et que ça n'a pas d'incidence sur les probabilités relatives des différents parcours, qui font l'objet de la question.

En fait, c'est sans doute dû à la manière dont les données sont générées. Le parcours "réel" de Gaston n'est pas généré par le script, et il n'y a pas d'effort pour que ce soit réaliste. D'ailleurs si c'était le cas, le parcours réel n'aurait qu'une assez faible probabilité d'être le plus probable, vu le nombre de parcours possible. Au contraire, les prix des consommations et les choix de Gaston doivent être choisis indépendamment.

Si tu préfères une explication plus psychologique - ce sont les souvenirs de Gaston qui créent le monde à mesure qu'il se réveille. Il dessine lui-même son passé, et le labyrinthe aux chemins tissés par son penchant pour l'alcool est en fait un subterfuge. Il ne se rappelle ces listes, ces lois, ces cartes et l'objet de désir qui les articule, que pour mieux oublier qu'il n'est que l'imagination de lui-même et que sa vie n'est qu'un rêve.

Voilà, voilà. 4 validations, ça doit quand même être faisable.

[ferbos]

Je crois qu'il va falloir réviser les probas https://fr.wikipedia.org/wiki/Probabilit%C3%A9 ou plutôt la formulation:

- En règle générale, il essaie d'éviter de trop marcher entre deux bars (ce qui n'est pas toujours évident avec plusieurs grammes dans le sang). Il a constaté que la probabilité qu'il atterrisse dans un bar donné est inversement proportionnelle à la distance qui le sépare de l'établissement d'où il est parti. Par exemple, si le trajet 1->2 est deux fois plus petit que 1->3, il a deux fois plus de chance d'emprunter 1->2 que 1->3, en partant de 1.

Ce sont deux règles différentes, et la première ne respecte pas une règle fondamentale des probas.
Ex: B1, B2 et B3 trois et je pars de B0 et les 3 bars sont distants de 3, 6 et 12.
Les probabilités de choisir un bar suivant la distance sont P1=4/7 P2=2/7 et P3=1/7

Non. D'abord il décide de bouger, et ensuite une fois dans le bar il décide de sa boisson.

C'est le chemin de Gaston.
Cela n'a pas d'importance vu que l'on ne doit pas trouver le trajet de Gaston mais le trajet le plus probable qui grosso modo lui coûte le moins cher et le fait moins marcher néanmoins saoûl contraintes? Et pour cela, il n'y a pas forcément besoin de proba.
D'après ce que dit Pixis, on dirait une règle au coup par coup, ce qui est très simple....

J'ai peur qu'il y ait des cas où plusieurs trajets soient possibles. Donc j'espère que les cas ont été prédéterminés

ferbos

[harvey]

ferbos, je ne vois pas comment les deux règles se contredisent. Ton exemple respecte les deux:
il existe un k tel que P1 = k*1/3, P2 = k*1/6 et P3 = k*1/12. C'est bien une proportion inverse.

Il suffit que les trajets équiprobables soient très rares pour que ça ne soit pas gênant. C'est pas comme si tu pouvais rooter NC avec...

[Asphator]

Mais alors quel est le parcours le plus probable?
Celui le probablement moins cher?
Celui le probablement moins long?
Celui le probablement moins cher sachant celui le probablement moins long?
Celui le probablement moins long sachant celui le probablement moins cher?
J'estime (tout comme toi visiblement) qu'il faut boire un minimum avant de saisir la logique de Gaston.
Aussi, je retourne au bar pour m'inspirer ! ^^

les prix des consommations et les choix de Gaston doivent être choisis indépendamment

Cela est cohérent avec la remarque de Pixis. Du coup ça serait du boisson sachant chemin (hips).
J'ai pris un mauvais exemple au début. J'avais 3 choix possibles à même distance. Du coup, j'ai choisi celui ou la boisson était la mieux classée, sûrement à tort j'en déduis...

[ferbos]

ferbos, je ne vois pas comment les deux règles se contredisent. Ton exemple respecte les deux:
il existe un k tel que P1 = k*1/3, P2 = k*1/6 et P3 = k*1/12. C'est bien une proportion inverse.

Il suffit que les trajets équiprobables soient très rares pour que ça ne soit pas gênant. C'est pas comme si tu pouvais rooter NC avec...

Inversement proportionnel à la distance, je le prends comme ça: 1/3 1/6 1/12 donc évidemment même si l'exemple est clair là-dessus. Cela doit être de ma faut j'ai mal compris. Je me rendors ZZZzzzZZZzzz

Aussi, je retourne au bar pour m'inspirer ! ^^

C'est sûr qu'un coup de gnôle ne va pas faire de mal ^^

ferbos

[EtAk0]

Bonjour, pourrais-je savoir si certaines personnes ayant réussi cette épreuve l'ont faite en langages interprétés (type Python), parce que j'arrive à 4 sec avec mon algo oO (qui ne doit pas être très bien optimisé j'en déduis...) et je me demande jusqu'à combien je peux tomber en utilisant un langage compilé, sachant que je fais principalement de la manipulation de listes dans mon script d'à peine 100 lignes.
En tout cas chouette épreuve qui me donne du fil à retordre