Top 20

1 0x00h 686 pts
2 boris39 686 pts
3 thefinder 686 pts
4 neoxquick 667 pts
5 maf-ia 649 pts
6 eax 648 pts
7 nikokks 605 pts
8 benito255 596 pts
9 mego 579 pts
10 madbat2 570 pts
11 plucth 553 pts
12 Mart 540 pts
13 rostale 540 pts
14 Stupefy 521 pts
15 tehron 505 pts
16 LouisJ 492 pts
17 Kithyane 489 pts
18 egosum 464 pts
19 malose 419 pts
20 CoYoTe99 408 pts

Classement complet

Shoutbox

8 Oct - 10:01 am

Salut nikokks Ce problème n'est pas évident en effet. Une manière de faire est de trouver les formes les plus simples, et de les "effacer" de l'image avant de chercher les formes plus complexes ;)

4 Oct - 11:56 am

Salut a tous =) , je bug sur le problème 28 (forme analysis). Quelqu'un aurait il une piste ?

29 Sep - 5:38 pm

Coucou oui, tu peux m'envoyer un mail si tu veux. Le plus simple, ce serait d'avoir un package pour python 3. J'ai essayé et ça n'a pas marché!

17 Sep - 11:51 am

Salut thefinder, ça faisait longtemps ! Oula ça en fait des problèmes :'( Le premier challenge ? La somme de deux nombres ?

23 Jul - 2:13 am

Coucou, j'ai essayé de reprendre avec python. J'ai plusieurs soucis. 1) Il faut rajouter headers={'Content-Type': 'application/x-www-form-urlencoded'} avec un requests.session(). 2) Je n'ai pas réponse du serveur si je soumet une réponse au premier challenge. J'essaye finir en python les 3 dernières épreuves qui me reste. :)

6 Nov - 8:17 am

Bonjour, un léger problème sur l'épreuve 10 : Une fois réussie, le champ "points earned" indique 72 au lieu de 7 En revanche sur le site le nombre de points comptabilisés est bien 7 Merci pour ce site génial !

21 Oct - 9:48 pm

Équation du challenge 52 corrigée, merci

16 Oct - 8:43 am

Bonjour, il y a aussi un problème d'affichage "invalid equation" dans le challenge 52. Merci

14 Oct - 8:57 pm

Barbapapou l'équation du challenge 29 a été corrigée

4 Oct - 10:30 am

Bonjour, il y a un problème avec l'affichage d'une équation dans le challenge 29

Connexion
Mot de passe oublié

Supportez nousx

Vous aimez µContest ?
Supportez nous en votant (fun et difficulté) pour µContest sur WeChall :)
Si vous ne l'avez pas encore fait, profitez-en pour lier votre compte
Wechall à µContest pour pouvoir voter !

Merci

Forum

You are not logged in.

#1 2015-02-08 10:16:53

Kithyane
New member
Registered: 2013-04-17
Posts: 8

Random Walk

Bonjour,

J'ai trouvé la méthode de résolution de random walk "sur papier", mais j'ai un peu de mal sur la manière de la coder, du coup j'aurais voulu tester mon code sur l'exemple donné dans l'énoncé. Est-ce que sur l'exemple de matrice donné, il faudrait bien retourner 2,1,3,4 (ou 2,3,1,4) (avec A = 1,..., D = 4) ?
D'autre part, si comme dans l'exemple de l'énoncé des villes sont exaequo, peut-on retourner n'importe laquelle des possibilités ?

Mon code retourne bien ça, mais comme je ne valide pas sur un vrai challenge je m'interroge smile

Offline

#2 2015-02-08 14:22:35

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

Bonjour,

comme c'est Eisenheim qui a codé cette épreuve je vais le laisser répondre, mais il me semble que tu as réussi l'épreuve Kithyane puisque tu l'as validée smile

Offline

#3 2015-02-08 22:41:01

Eisenheim
Administrator
Registered: 2011-04-23
Posts: 91

Re: Random Walk

Salut,

effectivement il faut bien trouver 2,1,3,4 ou 2,3,1,4 sur l'exemple.
Pour ce qui est des villes ex-aequo normalement ça ne devrait pas arriver avec les données de l'épreuve, il y a qu'un classement possible.

Offline

#4 2015-02-09 10:06:42

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

Tu peux peut être rajouter cette solution à la description de l'épreuve pour que ce soit clair pour tout le monde

Offline

#5 2015-02-17 00:33:37

thefinder
Member
Registered: 2013-12-31
Posts: 39

Re: Random Walk

Bonsoir, c'est une chaîne de Markov?
J'ai tenté par simulations mais il y a trop de valeurs. ;(
Pour le tips (GG), je pensais à la dichotomie mais je ne vois pas le lien.
Je veux bien un petit indice?
Merci.

Offline

#6 2015-02-18 13:06:32

Eisenheim
Administrator
Registered: 2011-04-23
Posts: 91

Re: Random Walk

Salut thefinder,

oui, tu es dans la bonne direction, et effectivement la simulation n'est pas envisageable compte tenu de la taille de la matrice.

Je sais pas si tu as déjà vu cette page mais ça devrait pouvoir t'aider un peu : .
Après il faut pas trop s'attarder sur tous les détails mathématiques de wikipédia, c'est trop complexe pour ce qui est demandé dans ce challenge, les éléments les plus simples suffisent.

Offline

#7 2015-02-27 09:01:35

Kithyane
New member
Registered: 2013-04-17
Posts: 8

Re: Random Walk

Metatr0n

Bonjour,

comme c'est Eisenheim qui a codé cette épreuve je vais le laisser répondre, mais il me semble que tu as réussi l'épreuve Kithyane puisque tu l'as validée smile

Oui en fait mon erreur était très bête ^^
En fait mon code retourne les villes en ordre croissant, du coup je renvoyais la chaîne de caractère inversée, donc 10 devenait 01... mais comme ça ne se voyait pas sur l'énoncé à 4 villes, je n'ai pas repéré ça tout de suite.

Une inversion de tableau plutôt que de chaîne de caractère et c'était bon !

Offline

#8 2015-02-27 10:15:32

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

D'accord bien joué wink

Offline

#9 2015-04-05 13:33:11

thefinder
Member
Registered: 2013-12-31
Posts: 39

Re: Random Walk

Bonsoir, serait-il possible d'avoir un exemple avec plus de valeurs svp?
Merci.

Offline

#10 2015-04-08 09:30:42

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

Salut thefinder.
C'est mon frère qui s'occupe de cette épreuve et il a pas été sur µContest depuis un moment il a pas mal de choses à faire, ça m'étonnerait que tu aies un exemple avec plus de valeurs avant un bon moment, désolé hmm

Offline

#11 2015-04-08 09:46:37

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

Bon en fait c'est bon je viens de rajouter un exemple, il était nécessaire

Offline

#12 2015-04-08 11:38:06

thefinder
Member
Registered: 2013-12-31
Posts: 39

Re: Random Walk

Merci, c'est beaucoup mieux.

Offline

#13 2015-06-22 17:03:12

thefinder
Member
Registered: 2013-12-31
Posts: 39

Re: Random Walk

Bonsoir,
J'ai utilisé un algo trouvé sur internet.
Ma solution est par rapport à l'exemple:
71,7,97,66,55,47,92,31,5,67,94,36,98,35,50,24,21,78,15,81,70,41,9,10,38,17,100,28,4,37,73,30,26,12,77,14,82,68,60,69,42,76,6,3,11,59,1,89,72,87,58,18,79,63,84,20,39,86,93,40,80,29,96,22,62,54,51,8,13,25,27,91,83,34,64,33,75,19,44,43,52,53,16,2,95,46,88,32,23,56,74,61,57,48,65,85,45,49,90,99

C'est un résultat proche mais inexact.
J'ai pris d=0,85 et nb_itérations=120 qui est largement suffisant.
Qq a-t-il eu le même problème que moi?
Dois-je chercher un algo encore plus complexe?

Merci.

Last edited by thefinder (2015-06-22 17:07:48)

Offline

#14 2015-06-23 09:27:58

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

boris39 tu avais eu le même genre de problème non ?

Offline

#15 2015-06-23 13:45:37

boris39
New member
Registered: 2013-09-08
Posts: 1

Re: Random Walk

En effet, j'ai mis un peu de temps à bien cerner l'utilité des paramètres (notamment le facteur d'amortissement d) à passer à l'algo.
Mais une fois cela fait, et en choisissant leur valeur judicieusement relativement à l'énoncé, la résolution n'a pas posé de problème.

Offline

#16 2015-06-23 18:03:43

thefinder
Member
Registered: 2013-12-31
Posts: 39

Re: Random Walk

Merci, j'ai trouvé grâce à l'explication de Boris.
On trouve les paramètres grâce à l'exemple!
On pourrait les donner dans l'énoncé, non?

Offline

#17 2015-06-28 18:08:10

Eisenheim
Administrator
Registered: 2011-04-23
Posts: 91

Re: Random Walk

Ce challenge peut se résoudre sans utiliser d'algorithme, on peut trouver une solution exacte directement wink.

Offline

#18 2018-04-13 17:34:47

lugdanum
New member
Registered: 2018-04-03
Posts: 5

Re: Random Walk

Hello

Juste pour vous demander si possible une confirmation.
En prenant l'exemple links.txt la "ville" que je trouve en première position n'est pas 71 (d’ailleurs le reste de l'ordre que je trouve n'est pas bon non plus...) mais 91 :

1111101001010001010001001101101011001011110100100101100111101100000000000110000110011001100100000010
ligne numéro :91 //// Nb de 1 :44 //// valeur trouvée :25252295477500022954568206843204795477525229547729570457070479545454545457045457045704570456818182

Alors je pense en fait que je ne dois pas bien m'y prendre ou mal interpréter l’énoncé (pas faute d'avoir recherché de la doc sur Markov et Cie..)

Donc par si j'ai bien compris avec l'exemple donné (qui retourne 2,1,3,4 ou 2,3,1,4) on fait bien pour déterminer cela :
ligne 1 : 100/1
ligne 2 : 1010/2
ligne 3 : 100/1
ligne 4 : 1110/3

?

Merki d'avance !

Offline

#19 2018-04-30 09:51:14

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

Bonjour lugdanum

En fait, les cases de la matrice représentent des probabilités, donc leur valeur est toujours comprise entre 0 et 1 (inclus).
Prenons la ligne 1 : 0 1 0 0 (ces chiffres ne sont pas à coller ensemble pour former 100). Elle veut dire :
- Probabilité d'aller dans la ville A quand on est dans la ville A : 0 %
- Probabilité d'aller dans la ville B quand on est dans la ville A : 100 %
- Probabilité d'aller dans la ville C quand on est dans la ville A : 0 %
- Probabilité d'aller dans la ville D quand on est dans la ville A : 0 %

Donc en fait, la matrice nous dit que quand on est dans la ville A, on va forcément dans la ville B, on ne peut pas faire autre chose. Mais ce n'est pas le cas quand on est dans la ville D.
En effet, dans la ville D, on a 33.3.. % (1/3) de chance d'aller soit dans la A, soit dans la B, soit dans la C.
De même, dans la ville B, on a 50% de chance d'aller dans la A et 50% d'aller dans la C.

Le problème, c'est qu'on ne vous donne pas exactement cette matrice, parce que ce sont des nombres à virgule (0.3333...) et les approximations ainsi obtenues par la représentation binaire faite par les ordinateurs (il est impossible de représenter rigoureusement 1/3 dans une variable) peuvent poser problème.
A la place, on vous donne la même matrice, mais avec des 1 à la place des probabilités non nulles.
Donc la matrice de l'exemple :
0    - 1    - 0    - 0
1/2 - 0    - 1/2 - 0
0    - 1    - 0    - 0
1/3 - 1/3 - 1/3 - 0

devient :
0 - 1 - 0 - 0
1 - 0 - 1 - 0
0 - 1 - 0 - 0
1 - 1 - 1 - 0

Or, comment retrouver la matrice originale à partir de celle ci ? Très simplement en remarquant que dans la matrice de probabilités, la somme des probabilités sur une ligne fait toujours 1 et qu'elles sont toutes égales !
On peut donc compter le nombre de 1 sur chaque ligne, et diviser CHAQUE 1 de cette ligne par la somme obtenue :
                     Nombre de 1 :
0 - 1 - 0 - 0            1
1 - 0 - 1 - 0            2
0 - 1 - 0 - 0            1
1 - 1 - 1 - 0            3

On divise :
0/1 - 1/1 - 0/1 - 0/1            0    - 1    - 0    - 0
1/2 - 0/2 - 1/2 - 0/2      =    1/2 - 0    - 1/2 - 0
0/1 - 1/1 - 0/1 - 0/1            0    - 1    - 0    - 0
1/3 - 1/3 - 1/3 - 0/3            1/3 - 1/3 - 1/3 - 0

On retrouve bien la matrice de départ.
Ça répond à ta question ?

Offline

#20 2018-04-30 23:14:44

lugdanum
New member
Registered: 2018-04-03
Posts: 5

Re: Random Walk

Bonjour

ah oui carrément je te remercie beaucoup pour ton explication, j'étais complètement parti sur autre chose et là tu m'as bien expliqué, c'est clair.

Je vais la retenter, je te remercie encore d'avoir pris du temps pour m'expliquer.

@ bientôt !

Offline

#21 2018-05-02 09:35:39

Metatr0n
Administrator
Registered: 2011-04-24
Posts: 205

Re: Random Walk

De rien, bonne chance wink

Offline

Board footer

Powered by FluxBB