Computer Science Canada

Making A Facebook Type Program "Degrees Of Separation"
Author:  SkaterDrummer678 [ Sun Apr 19, 2009 2:13 pm ]
Post subject:  Making A Facebook Type Program "Degrees Of Separation"
I need help with this program or at least instructions/suggestions on how to finish this program.




code:
/*
~Pseudocode~

//FRIENDSHIPS
-Bruce(2) is only friends with (6)
-Chris(1) is only friends with (6)
-Abby(6) is friends with (2)(1)(3)(4)(5)and(7)
-George(7) is friends with (6)and(8)
-Ali(8) is friends with (7)and(9)
-Natalie(5) is friends with (6)(4) and (3)
-Stephen(4) is friends with (6)(5) and (3)
-Zoey(3) is friends with (6)(4)(5) and (15)
-Alberto(15) is friends with (3) and (13)
-Kara(9) is friends with (8)(12) and (10)
-Nomar(10) is friends with (9) and (11)
-Siobahn(11) is friends with (10) and (12)
-Jeff(13) is friends with (15)(12) and (14)
-Terry(14) is friends with (13)
-Kim(16) is friends with (17) and (18)
-Trevor(18) is friends with (17) and (16)
-Richard(17) is friends with (16) and (18)
*/

//DEGREE OF SEPARATION
/* Degree of separation for Chris
~(1)~
-(2)= 2 ; (6)-(2)
-(3)= 2 ; (6)-(3)
-(4)= 2 ; (6)-(4)
-(5)= 2 ; (6)-(5)
-(6)= 1 ; (6)
-(7)= 2 ; (6)-(7)
-(8)= 3 ; (6)-(7)-(8)
-(9)= 4 ; (6)-(7)-(8)-(9)
-(10)= 5 ; (6)-(7)-(8)-(9)-(10)
-(11)= 6 ; (6)-(7)-(8)-(9)-(10)-(11)
-(12)= 5 ; (6)-(7)-(8)-(9)-(12)
-(13)= 4 ; (6)-(3)-(15)-(13)
-(14)= 6 ; (6)-(3)-(15)-(13)-(14)
-(15)= 3 ; (6)-(3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Bruce
~(2)~
-(1)= 2 ; (6)-(1)
-(3)= 2 ; (6)-(3)
-(4)= 2 ; (6)-(4)
-(5)= 2 ; (6)-(5)
-(6)= 1 ; (6)
-(7)= 2 ; (6)-(7)
-(8)= 3 ; (6)-(7)-(8)
-(9)= 4 ; (6)-(7)-(8)-(9)
-(10)= 5 ; (6)-(7)-(8)-(9)-(10)
-(11)= 6 ; (6)-(7)-(8)-(9)-(10)-(11)
-(12)= 5 ; (6)-(7)-(8)-(9)-(12)
-(13)= 4 ; (6)-(3)-(15)-(13)
-(14)= 6 ; (6)-(3)-(15)-(13)-(14)
-(15)= 3 ; (6)-(3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Zoey
~(3)~
-(1)= 2 ; (6)-(1)
-(2)= 2 ; (6)-(2)
-(4)= 1 ; (4)
-(5)= 1 ; (5)
-(6)= 1 ; (6)
-(7)= 2 ; (6)-(7)
-(8)= 3 ; (6)-(7)-(8)
-(9)= 4 ; (6)-(7)-(8)-(9)
-(10)= 5 ; (6)-(7)-(8)-(9)-(10)
-(11)= 4 ; (15)-(13)-(12)-(11)
-(12)= 3 ; (15)-(13)-(12)
-(13)= 2 ; (15)-(13)
-(14)= 3 ; (15)-(13)-(14)
-(15)= 1 ; (15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Stephen
~(4)~
-(1)= 2 ; (6)-(1)
-(2)= 2 ; (6)-(2)
-(3)= 1 ; (3)
-(5)= 1 ; (5)
-(6)= 1 ; (6)
-(7)= 2 ; (6)-(7)
-(8)= 3 ; (6)-(7)-(8)
-(9)= 4 ; (6)-(7)-(8)-(9)
-(10)= 5 ; (6)-(7)-(8)-(9)-(10)
-(11)= 5 ; (3)-(15)-(13)-(12)-(11)
-(12)= 4 ; (3)-(15)-(13)-(12)
-(13)= 3 ; (3)-(15)-(13)
-(14)= 4 ; (3)-(15)-(13)-(14)
-(15)= 2 ; (3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Natalie
~(5)~
-(1)= 2 ; (6)-(1)
-(2)= 2 ; (6)-(2)
-(3)= 1 ; (3)
-(4)= 1 ; (4)
-(6)= 1 ; (6)
-(7)= 2 ; (6)-(7)
-(8)= 3 ; (6)-(7)-(8)
-(9)= 4 ; (6)-(7)-(8)-(9)
-(10)= 5 ; (6)-(7)-(8)-(9)-(10)
-(11)= 5 ; (3)-(15)-(13)-(12)-(11)
-(12)= 4 ; (3)-(15)-(13)-(12)
-(13)= 3 ; (3)-(15)-(13)
-(14)= 4 ; (3)-(15)-(13)-(14)
-(15)= 2 ; (3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Abby
~(6)~
-(1)= 1 ; (1)
-(2)= 1 ; (2)
-(3)= 1 ; (3)
-(4)= 1 ; (4)
-(5)= 1 ; (5)
-(7)= 1 ; (7)
-(8)= 2 ; (7)-(8)
-(9)= 3 ; (7)-(8)-(9)
-(10)= 4 ; (7)-(8)-(9)-(10)
-(11)= 5 ; (7)-(8)-(9)-(10)-(11)
-(12)= 4 ; (7)-(8)-(9)-(12)
-(13)= 3 ; (3)-(15)-(13)
-(14)= 4 ; (3)-(15)-(13)-(14)
-(15)= 2 ; (3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for George
~(7)~
-(1)= 2 ; (6)-(1)
-(2)= 2 ; (6)-(2)
-(3)= 2 ; (6)-(3)
-(4)= 2 ; (6)-(4)
-(5)= 2 ; (6)-(5)
-(6)= 1 ; (6)
-(8)= 1 ; (8)
-(9)= 2 ; (8)-(9)
-(10)= 3 ; (8)-(9)-(10)
-(11)= 4 ; (8)-(9)-(10)-(11)
-(12)= 3 ; (8)-(9)-(12)
-(13)= 4 ; (8)-(9)-(12)-(13)
-(14)= 5 ; (8)-(9)-(12)-(13)-(14)
-(15)= 3 ; (6)-(3)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Ali
~(8)~
-(1)= 3 ; (7)-(6)-(1)
-(2)= 3 ; (7)-(6)-(2)
-(3)= 3 ; (7)-(6)-(3)
-(4)= 3 ; (7)-(6)-(4)
-(5)= 3 ; (7)-(6)-(5)
-(6)= 2 ; (7)-(6)
-(7)= 1 ; (7)
-(9)= 1 ; (9)
-(10)= 2 ; (9)-(10)
-(11)= 3 ; (9)-(10)-(11)
-(12)= 2 ; (9)-(12)
-(13)= 3 ; (9)-(12)-(13)
-(14)= 4 ; (9)-(12)-(13)-(14)
-(15)= 4 ; (9)-(12)-(13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Kara
~(9)~
-(1)= 4 ; (8)-(7)-(6)-(1)
-(2)= 4 ; (8)-(7)-(6)-(2)
-(3)= 4 ; (8)-(7)-(6)-(3)
-(4)= 4 ; (8)-(7)-(6)-(4)
-(5)= 4 ; (8)-(7)-(6)-(5)
-(6)= 3 ; (8)-(7)-(6)
-(7)= 2 ; (8)-(7)
-(8)= 1 ; (8)
-(10)= 1 ; (10)
-(11)= 2 ; (10)-(11)
-(12)= 1 ; (12)
-(13)= 2 ; (12)-(13)
-(14)= 3 ; (12)-(13)-(14)
-(15)= 3 ; (12)-(13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Nomar
~(10)~
-(1)= 5 ; (9)-(8)-(7)-(6)-(1)
-(2)= 4 ; (9)-(8)-(7)-(6)-(2)
-(3)= 4 ; (9)-(8)-(7)-(6)-(3)
-(4)= 4 ; (9)-(8)-(7)-(6)-(4)
-(5)= 4 ; (9)-(8)-(7)-(6)-(5)
-(6)= 3 ; (9)-(8)-(7)-(6)
-(7)= 2 ; (9)-(8)-(7)
-(8)= 1 ; (9)-(8)
-(9)= 1 ; (9)
-(11)= 1 ; (11)
-(12)= 2 ; (11)-(12)
-(13)= 3 ; (11)-(12)-(13)
-(14)= 4 ; (11)-(12)-(13)-(14)
-(15)= 4 ; (11)-(12)-(13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Siobahn
~(11)~
-(1)= 5 ; (10)-(9)-(8)-(7)-(6)-(1)
-(2)= 6 ; (10)-(9)-(8)-(7)-(6)-(2)
-(3)= 4 ; (12)-(13)-(15)-(3)
-(4)= 5 ; (12)-(13)-(15)-(3)-(4)
-(5)= 5 ; (12)-(13)-(15)-(3)-(5)
-(6)= 5 ; (10)-(9)-(8)-(7)-(6)
-(7)= 4 ; (10)-(9)-(8)-(7)
-(8)= 1 ; (10)-(9)-(8)
-(9)= 1 ; (10)-(9)
-(10)= 1 ; (10)
-(12)= 1 ; (12)
-(13)= 2 ; (12)-(13)
-(14)= 3 ; (12)-(13)-(14)
-(15)= 3 ; (12)-(13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Ricardo
~(12)~
-(1)= 5 ; (9)-(8)-(7)-(6)-(1)
-(2)= 5 ; (9)-(8)-(7)-(6)-(2)
-(3)= 3 ; (13)-(15)-(3)
-(4)= 4 ; (13)-(15)-(3)-(4)
-(5)= 4 ; (13)-(15)-(3)-(5)
-(6)= 4 ; (9)-(8)-(7)-(6)
-(7)= 3 ; (9)-(8)-(7)
-(8)= 2 ; (9)-(8)
-(9)= 1 ; (9)
-(10)= 2 ; (11)-(10)
-(11)= 1 ; (11)
-(13)= 1 ; (13)
-(14)= 2 ; (13)-(14)
-(15)= 2 ; (13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Jeff
~(13)~
-(1)= 4 ; (15)-(3)-(6)-(1)
-(2)= 4 ; (15)-(3)-(6)-(2)
-(3)= 2 ; (15)-(3)
-(4)= 3 ; (15)-(3)-(4)
-(5)= 3 ; (15)-(3)-(5)
-(6)= 3 ; (15)-(3)-(6)
-(7)= 4 ; (12)-(9)-(8)-(7)
-(8)= 3 ; (12)-(9)-(8)
-(9)= 2 ; (12)-(9)
-(10)= 3 ; (12)-(11)-(10)
-(11)= 2 ; (12)-(11)
-(12)= 1 ; (12)
-(14)= 1 ; (14)
-(15)= 1 ; (15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Terry
~(14)~
-(1)= 5 ; (13)-(15)-(3)-(6)-(1)
-(2)= 5 ; (13)-(15)-(3)-(6)-(2)
-(3)= 3 ; (13)-(15)-(3)
-(4)= 4 ; (13)-(15)-(3)-(4)
-(5)= 4 ; (13)-(15)-(3)-(5)
-(6)= 4 ; (13)-(15)-(3)-(6)
-(7)= 5 ; (13)-(12)-(9)-(8)-(7)
-(8)= 4 ; (13)-(12)-(9)-(8)
-(9)= 3 ; (13)-(12)-(9)
-(10)= 4 ; (13)-(12)-(11)-(10)
-(11)= 3 ; (13)-(12)-(11)
-(12)= 2 ; (13)-(12)
-(13)= 1 ; (13)
-(15)= 2 ; (13)-(15)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Alberto
~(15)~
-(1)= 3 ; (3)-(6)-(1)
-(2)= 3 ; (3)-(6)-(2)
-(3)= 1 ; (3)
-(4)= 2 ; (3)-(4)
-(5)= 2 ; (3)-(5)
-(6)= 2 ; (3)-(6)
-(7)= 3 ; (3)-(6)-(7)
-(8)= 4 ; (13)-(12)-(9)-(8)
-(9)= 3 ; (13)-(12)-(9)
-(10)= 4 ; (13)-(12)-(11)-(10)
-(11)= 3 ; (13)-(12)-(11)
-(12)= 2 ; (13)-(12)
-(13)= 1 ; (13)
-(14)= 2 ; (13)-(14)
-(16)= Not Connected
-(17)= Not Connected
-(18)= Not Connected
*/

/* Degree of separation for Kim
~(16)~
-(1)= Not Connected
-(2)= Not Connected
-(3)= Not Connected
-(4)= Not Connected
-(5)= Not Connected
-(6)= Not Connected
-(7)= Not Connected
-(8)= Not Connected
-(9)= Not Connected
-(10)= Not Connected
-(11)= Not Connected
-(12)= Not Connected
-(13)= Not Connected
-(14)= Not Connected
-(15)= Not Connected
-(17)= 1 ; (17)
-(18)= 1 ; (18)
*/

/* Degree of separation for Richard
~(17)~
-(1)= Not Connected
-(2)= Not Connected
-(3)= Not Connected
-(4)= Not Connected
-(5)= Not Connected
-(6)= Not Connected
-(7)= Not Connected
-(8)= Not Connected
-(9)= Not Connected
-(10)= Not Connected
-(11)= Not Connected
-(12)= Not Connected
-(13)= Not Connected
-(14)= Not Connected
-(15)= Not Connected
-(16)= 1 ; (16)
-(18)= 1 ; (18)
*/

/* Degree of separation for Trevor
~(18)~
-(1)= Not Connected
-(2)= Not Connected
-(3)= Not Connected
-(4)= Not Connected
-(5)= Not Connected
-(6)= Not Connected
-(7)= Not Connected
-(8)= Not Connected
-(9)= Not Connected
-(10)= Not Connected
-(11)= Not Connected
-(12)= Not Connected
-(13)= Not Connected
-(14)= Not Connected
-(15)= Not Connected
-(16)= 1 ; (16)
-(17)= 1 ; (17)
*/


Java:
// The "CompSciS3" class.
import java.awt.*;
import hsa.Console;

public class Project2009
{
    static Console c;           // The output console

    public static void main (String[] args)
    {
        c = new Console ();
       
        c.println ("Commands: ");
        c.println ("i x y - make person x and person y friends. If they are already friends no change needs to be made. If either x or y is a new person, add them.");
        c.println ("d x y - delete the friendship between person x and person y");
        c.println ("n x - output the number of friends that person x has");
        c.println ("f x - output the number of 'friends of friends' that person x has. Notice that x and direct friends of x are not counted as 'friends of friends'.");
        c.println ("s x y - output the degree of separation between x and y.");
        c.println ("q - quit program");
        c.println ("_______________________________________________________________________________");
        c.println ("                ");



Mod Edit: Remember to use syntax and code tags! Thanks Smile
code:
[syntax="java"]Code Here[/syntax]
Author:  saltpro15 [ Sun Apr 19, 2009 2:26 pm ]
Post subject:  RE:Making A Facebook Type Program "Degrees Of Separation"
this was s3 of this year's CCC contest, a sample solution can be found here
Author:  Tony [ Sun Apr 19, 2009 2:27 pm ]
Post subject:  RE:Making A Facebook Type Program "Degrees Of Separation"
shortest path in a graph.
Author:  SkaterDrummer678 [ Sun Apr 19, 2009 6:34 pm ]
Post subject:  Re: RE:Making A Facebook Type Program "Degrees Of Separation"
saltpro15 @ Sun Apr 19, 2009 2:26 pm wrote:
this was s3 of this year's CCC contest, a sample solution can be found here


Thanks man but for some reason everytime i try to load the page is says "Page Load Error" so i tried doing the whole Google and Cached way of viewing the page but theres no way to see the actual S3 problem.

And the code i posted was as far as i got in the competition Cool hahaha
Author:  saltpro15 [ Sun Apr 19, 2009 6:55 pm ]
Post subject:  RE:Making A Facebook Type Program "Degrees Of Separation"
uh-oh, I guess that milliken mills teacher is slacking Wink jk of course, but like Tony said, it's a shortest path in a graph problem, I think it can be solved with a BFS algorithm. Honestly, I never coded it during the CCC, I ran out of time
Author:  Analysis Mode [ Sun Apr 19, 2009 8:05 pm ]
Post subject:  Re: Making A Facebook Type Program "Degrees Of Separation"
yeah, BFS works, but because the graph had at most 100 vertices, you shold use Floyd-Warshall's ALgorithm. IT's kind of hard to code a four-line algorithm wrong.
Author:  saltpro15 [ Sun Apr 19, 2009 8:17 pm ]
Post subject:  RE:Making A Facebook Type Program "Degrees Of Separation"
oh right, thanks Analysis, I forgot about Floyd-Warshall

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy