Top 20

1 0x00h 680 pts
2 boris39 680 pts
3 thefinder 680 pts
4 neoxquick 661 pts
5 maf-ia 643 pts
6 eax 642 pts
7 Lucky92 641 pts
8 nikokks 600 pts
9 benito255 590 pts
10 mego 573 pts
11 madbat2 564 pts
12 plucth 547 pts
13 Mart 535 pts
14 rostale 534 pts
15 Stupefy 515 pts
16 lalba 515 pts
17 tehron 499 pts
18 LouisJ 486 pts
19 Kithyane 484 pts
20 egosum 459 pts

Full ranking

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

Connection
Password forgotten

Support usx

You like µContest ?
Support us by voting (fun and difficulty) for µContest on WeChall :)
If you have not already, take the opportunity to link your Wechall
account to µContest in order to be able to vote !

Thank you

Contests list :: Mathematics :: Random walk (55)

Summary

ID : 55
Points : 16
Validations :
Challenge page
Report a bug

Description


What will be discussed in this challenge made their designers rich and powerful. Sounds interesting no ? Let see what this is about.

We will consider the simpler version of the algorithm. Let us consider a graph of cities with links between some of them :

Imagine now someone who decide to travel among cities randomly. At the beginning he is in a city, and chose one of the possible links to go to a nearby town. All links have the same probability to be chosen which is 1/N with N the number of links. For example, there are three links starting from D so the probability for each link to be chosen is 1/3. Once he arrives to the nearby city he starts the process again. And this indefinitely.

Let define now the best city the most visited by our traveler, the second best the second most visited, etc. The purpose of this challenge is to establish the rank of the cities.

In order to make the description of the graph simple, we describe it with a matrix, called adjacency matrix, representing the probability to go from a city to another. Here is an example with the previous graph :

For example, the red coefficient is the probability for the traveler when he is in B to go to C.

But, to avoid approximations, we just simply put 1 where there is a link :

Then to recover the probability matrix, you just have to divide each row by the number of 1 in the row.

The matrix is coded in the same way as those of the Matrices challenge. For example the above matrix would be coded :
[[0,1,0,0][1,0,1,0][0,1,0,0][1,1,1,0]] in links variable.

The rank has to be sent back in rank variable with the following format when cities are separated with comma, for example :
3,4,1,2,5
Here the city '3' is the best and '5' is the worse. Use numbers (instead of letters) from 1 to n, n standing for the dimension of the links matrix, representing the number of cities.


You have not found what I was talking about in the beginning ? I will give you a hint (select the text) : this algorithm is behind the success of Google when it started. And of course, it is not applied to cities, but I am sure you have guessed what it is !

Example



Let's take an example. For the following links variable value : links
We expect the following answer :
rank = "71,7,97,66,55,47,92,5,31,67,94,36,98,35,50,24,21,78,15,81,70,41,9,10,38,100,17,4,73,28,30,37,77,26,12,14,82,68,60,69,42,
76,6,3,59,11,1,89,72,87,58,18,79,63,84,20,39,86,93,29,40,80,96,22,62,54,51,13,8,25,27,91,34,83,64,75,33,19,44,43,52,53,16,
2,95,46,88,32,23,56,74,61,57,48,65,85,45,49,90,99"


Variables


Name Type Description
Variables to get
linksStringchar*Links matrix
Variables to send back
rankStringchar*Ranking of cities