Elysian Shadows

this is one that i struggled with quite alot because my data structure sucked.

there are many solutions but the key to a good solution is in the data structure.

the program is like a social network. facebook, myspace. myface. whatever.
so you have a node that represents a person and he has friends

node: andre
|
---> friends: 1 --> 2 --> 3 --> 4 //each number representing a friend.

its fairly easy to write a function that you see if a node has a particular friend. but how would you write a function that you say is node X connected to node Y in any ways. and if so return the connection

example if node 1 has friends 2, 3
and node 2 has frindd 1,3,4
node 3 has friends 1,2
and node 4 has frinds 2.

if you said does node 1 have a connection with node 4, then the answer would be yes. 4 knows 2 who knows 1.


this is a really nice and rewarding challenge. at least i felt that way about it. give it a try.

note that the goal also is to be as efficient as possible. having each node have an entire map of the network is not logical.
ps: there are some theories in networking that actually help with this problem.

Is there an upper limit to how many friends can you have?
Do we know what is the average number of friends one person has?
What is the maximum number of links a person can have before a connection is deemed invalid?
What is the target language?

In response to the language question: Avansc usually doesn't care what language these are done in. I also like it that way, so that I can see how people use different approaches with different languages to get the job done.

So PHP and MySQL?

Added question, is it assumed that if A is friends with B, then B is friends with A?

bugmenot wrote:Added question, is it assumed that if A is friends with B, then B is friends with A?

Although I can't answer that, I would assume yes.

IIRC, a logical language like Prolog would probably be best for this type of question. Shame I can't remember any of it :/

Is there an upper limit to how many friends can you have?
- no, i would suggest using a linked list to represent the friends

Do we know what is the average number of friends one person has?
[you dont really have a average for a single number. person A has 10 friends. you cant have a average of 10 friends, unless you had multiple sets of friends.
person A has 10 friends in set 1 and 12 friends in set 2, so a avarage of 11 friends over sets {1,2}]
- im not sure what you exactly mean, but you could keep a counter of the number of friends if you wanted to.

What is the maximum number of links a person can have before a connection is deemed invalid?
- in practice you could make a link limit. but lets make it that it just looks to see if there is any kind of link.

What is the target language?
- any language, but i mean its not really a challenge if the language has this functionality built in.

yeah. when you add B to A's list of friends you also add A to B's list of friends.

here is a little hint: be careful for infinite loops.

also, and this is a big one. read up about tree traversal, preorder, inorder, and postorder, and see which one you need and how you can adapt it.
recursion works well here.

Hm. As a starting point, I am currently thinking along the lines of a breadth first graph traversal and making nodes as 'dirty' so I don't traverse through the same nodes twice. Unfortunately, it is still pretty brute force.

I think this app could also be used to solve Six Degrees to Kevin Bacon, cool.

bugmenot wrote:Hm. As a starting point, I am currently thinking along the lines of a breadth first graph traversal and making nodes as 'dirty' so I don't traverse through the same nodes twice. Unfortunately, it is still pretty brute force.

yeah this is one of those challenges where you are questioned whether to go breadth or depth first. and i guess it all matters on how big the network is.
its a very interesting challenge with alot of solutions. some more nifty than others.

Hm. An alternative solution is to cache all possible connections as friends are added to each person. Disadvantages is that it requires more memory and the performance hit on added friends but the search time is dramatically reduced. Whether this is better then doing the search each time really does depend on the frequency of changes to the data set vs the number of queries though.

My first thought was something along the lines of iterative deepening. Has all the advantages of breadth first and depth first with negligible calculation time increase. Keep a vector of visited nodes.

each person keeps a list of their own friends,
you can search 2 ways. breadth first or depth first. (up to you and) (i'll do depth first, although its not technically depth first entirely )

then have a list that you can add "already visited" people.

go to the first person on the list (the first time it will be your list).
then look of the target on the current node's list, if not there, go to its first node one its list..
keep this cycle going till you have have list depleted. you will also not follow links that have been traversed already.
this method can be implemented recursively quite easily.

note: if the network is small this will work fine. but is not ideal if the network is large.

another way could be to have the network host keep a list in this form.

andre,jack
jack,andre

it can be sorted, and an algorithm can be be devised that can sort through it.

i love this challenge because there are many solutions some which are better than others, but not one that ideal.