NewbieContest

Postez ici vos messages.

Ca ressemble fortement a un TSP

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

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

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

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

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...

Ce n'est pas ce qui est dit.
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.

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.
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).

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.

Je crois qu'il va falloir réviser les probas https://fr.wikipedia.org/wiki/Probabilit%C3%A9 (https://fr.wikipedia.org/wiki/Probabilit%C3%A9) ou plutôt la formulation:
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

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 =D

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...

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 ! ^^

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...

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

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

ferbos

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  =D

Oui, c'est très faisable en Python.

Admettons qu'on ait la composition suivante

- - - -
12 - 3
- - - -

la distance entre 1 -> 2 est de 1.
la distance entre 1-> 3 est de 3 ou de 5???

la question reformulée autrement est, peut-on passer sur une case où il y a un bar pour atteindre un autre bar (pour calculer la distance)?

Oui on peut, un bar est une case comme les autres.

Du coup, une remarque basique me vient. Si Gaston choisit d'abord le bar et seulement ensuite la boisson, le deuxième bar qu'il fréquentera sera probablement le plus proche. Ensuite, quel que soit le prix de la boisson, le choix du troisième bar devrait se faire de la même façon, uniquement en fonction de sa distance au deuxième, et ainsi de suite.

Un tel parcours conduirait en fait à revenir au premier bar après avoir visité le deuxième, puis le deuxième à nouveau, puis le premier, etc, ce qui me paraît un peu simple et fortement improbable. Il y a donc un truc que je ne pige pas.

Quelqu'un peut-il me remettre dans le droit chemin ou, du moins, dans une direction moins... circulaire ?

Hello,

La liste des boissons qu'il a consommées est importante. En effet, s'il fait l'aller retour entre deux bar, on risque de souvent avoir des choix de boissons très improbables. En revanche, il peut aller dans un bar un poil plus loin pour ensuite choisir une boisson qui, dans ce bar, est bien plus probable.


Par ailleurs, lorsqu'il est expliqué que d'abord il choisit de bouger, ça ne veut pas dire qu'il va forcément aller au bar le plus probable.


Probablement, oui, mais pas certain.


Ben il a une plus grande probabilité d'aller au bar le plus proche. Mais encore une fois, le choix des boissons est imposé, donc il faut tout prendre en compte pour la probabilité globale.

Salut,

Merci pour ces précisions, Pixis.


Il peut mais, dans ce cas, c'est un peu comme s'il prenait en compte le prix des boissons pour choisir le bar suivant, finalement.


Non, par forcément, bien sûr, mais comme il s'agit justement de trouver le trajet le plus probable...


Si je comprends bien, il faut vraiment trouver LE chemin optimal parmi tous les chemins possibles... (c'est possible, ça ?!)

Au final, c'est un peu ce que je craignais. Il va falloir réfléchir (mince !).  :( :D

Et bien un exemple

3 Bars A B C donc les distances les uns aux autres sont :
(A,B) = 1
(A,C) = 2
(B,C) = 3

2 boissons X,Y dont les prix dans les trois bars sont :
A (X=1000€, Y=1€)
B (X=1€,    Y=1000€)
C (X=1000€, Y=1€)

L'énoncé dit que le mec en partant de A a pris d'abord Y puis X. (Ça, c'est un fait, c'est l'énoncé, c'est immuable).

On voit bien que le mec n'a probablement pas fait A->B (avec une boisson à 1000€) puis B->A (Avec une boisson à 1000€).  Pourtant c'est le chemin le plus probable indépendamment des boissons.
Il a plus probablement fait A->C (avec une boisson à 1€) puis C->B (Avec une boisson à 1€)

Donc comme quoi, c'est pas juste dépendant des distances. A toi de mettre tout ça en place :)

Ouais, même pour un très bon whisky, ça fait chérot.

Bon ben... je vais essayer de m'y atteler. Je crois que je ne voyais pas les choses sous le bon angle.

Salut à tous les tourneurs de bars.

Mettons qu'il existe deux bars B et C. Gaston est parti d'un bar A quelconque, équidistant de B et de C, et a bu une boisson X dans l'un des deux (B ou C).

• X est à 2 € dans B, avec une proba sur la carte de B P_B(X)=0,15.
• X est à 1 € dans C, avec la meilleure proba sur la carte de C : P_C(X)=0,10.

Doit-on considérer la présence de Gaston comme plus probable en B parce que P_B(X) > P_C(X) ?
Ou bien C est-il plus probable parce que X y a la meilleure proba de la carte (a priori le prix ne joue pas de rôle direct ici, mis à part pour le calcul de la probabilité...) ?

Est-ce que j'en demande trop ?

Merci d'avance à ceux qui mettront fin à mes insomnies alcoolisées.

Euh la proba en B est meilleure qu'en C

Merci Pixis.

Du coup, nouvelle question au risque d'en demander vraiment trop. Pour que la distance joue aussi un rôle dans la détermination du chemin le plus probable, la proba à calculer pour choisir un bar à un moment donné doit être une "combinaison" de la "proba boisson" et de la "proba distance", non ?

Désolé, je me permets d'insister parce que NC s'obstine à me dire que "la séquence proposée n'est pas optimale" et que, même si "c'est bien tenté", je dormirai mieux en ayant résolu ce challenge. Bon, d'accord, ça ne compte pas. Mais disons que la "combinaison" de probas que j'essaye me donne un trajet du style 5-7-5-7-5-7... la plupart du temps, donc pas top, et je ne vois plus trop dans quelle direction aller. Ou alors il faut voir plus loin que le seul prochain bar à chaque étape ? En tout cas, ce que j'ai essayé dans le domaine ne fonctionne pas non plus.

Tout est à prendre en compte, et il ne faut pas réfléchir en mode "choix indépendant". Le verre X pris au 4ème bar influence l'ordre des bars précédents. En effet, il y a plus de chance que le bar 3 soit près d'un bar qui a un verre X pas cher, et que le bar 2 soit proche de ce bar 3 etc.

Bref, faut tout prendre en compte.

Allez, bon courage !

D'accord.

T'as l'art de m'annoncer de mauvaises nouvelles, Pixis. Mon algo qui essayait d'optimiser l'ensemble du parcours était carrément trop lent. Je vais essayer de revoir ma copie.

En tout cas merci pour tes éclaircissements !

EDIT : J'ai fini par trouver, le lendemain de ces derniers conseils, je crois; comme quoi une tournée des bars bien menée peut rapporter un certain "succès". Et en effet, plus on voit loin, moins on perd Gaston de vue (en espérant que ça puisse aider un peu mais pas trop).

hi
Q1) is 1st bar of starting point located at 1st of sequece ?? right ??
Q2) if [ distance, price, bar index]
      starting bar:[0, 9, '2'],
      nearest bar: [4, 7, '5']
      
      what bar is on more high probability ??  starting bar or 2nd bar(=nearest bar)..