logo Homepage
+  NewbieContest
|-+  Challenges» Aide Programmation» Prog - Tournée des bars
Username:
Password:
Pages: [1] 2
  Retourner à l'épreuve    Imprimer  
Auteur Fil de discussion: Prog - Tournée des bars  (Lu 14721 fois)
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« le: 02 Décembre 2016 à 19:57:30 »

Postez ici vos messages.
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
anthony63

Profil challenge

Classement : 218/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 18


Voir le profil
« #1 le: 03 Décembre 2016 à 03:37:53 »

Ca ressemble fortement a un TSP
Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #2 le: 03 Décembre 2016 à 09:16:14 »

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

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
ferbos

Profil challenge

Classement : 11/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 356

The Godfather is back....


Voir le profil WWW
« #3 le: 03 Décembre 2016 à 10:00:10 »

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
Journalisée

"Les seules limites sont les fautes."
Iansus

Profil challenge

Classement : 50/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 262


Voir le profil WWW
« #4 le: 03 Décembre 2016 à 14:50:47 »

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

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #5 le: 03 Décembre 2016 à 14:54:41 »

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

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
Asphator

Profil challenge

Classement : 156/54254

Membre Complet
***
Hors ligne Hors ligne
Messages: 158


Voir le profil
« #6 le: 03 Décembre 2016 à 22:16:27 »

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...
« Dernière édition: 03 Décembre 2016 à 22:24:23 par Asphator » Journalisée

Les seules limites sont les nôtres...
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #7 le: 04 Décembre 2016 à 00:03:45 »

Citation
(or quand on dit "en moyenne il choisira la moins chère"...)
Ce n'est pas ce qui est dit.
Citation
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.
Journalisée

L'entropie vient en mangeant.
Asphator

Profil challenge

Classement : 156/54254

Membre Complet
***
Hors ligne Hors ligne
Messages: 158


Voir le profil
« #8 le: 04 Décembre 2016 à 00:24:37 »

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).
« Dernière édition: 04 Décembre 2016 à 00:28:46 par Asphator » Journalisée

Les seules limites sont les nôtres...
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #9 le: 04 Décembre 2016 à 02:21:23 »

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.
« Dernière édition: 04 Décembre 2016 à 02:24:00 par harvey » Journalisée

L'entropie vient en mangeant.
ferbos

Profil challenge

Classement : 11/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 356

The Godfather is back....


Voir le profil WWW
« #10 le: 04 Décembre 2016 à 06:14:24 »

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

"Les seules limites sont les fautes."
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #11 le: 04 Décembre 2016 à 17:09:28 »

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...
Journalisée

L'entropie vient en mangeant.
Asphator

Profil challenge

Classement : 156/54254

Membre Complet
***
Hors ligne Hors ligne
Messages: 158


Voir le profil
« #12 le: 04 Décembre 2016 à 18:54:47 »

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

Citation de: harvey
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...
Journalisée

Les seules limites sont les nôtres...
ferbos

Profil challenge

Classement : 11/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 356

The Godfather is back....


Voir le profil WWW
« #13 le: 04 Décembre 2016 à 19:30:46 »

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
Journalisée

"Les seules limites sont les fautes."
EtAk0

Profil challenge

Classement : 617/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 19


Voir le profil
« #14 le: 12 Avril 2017 à 10:22:35 »

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 
Journalisée
Pages: [1] 2
  Retourner à l'épreuve    Imprimer  
 
Aller à: