Option 1: Facebook Degrees of Separation Using a language of your choice and the

Question

Option 1:

Facebook Degrees of Separation Using a language of your choice and the Facebook API, write a program that accepts two unique user IDs as input and attempts to determine whether there is a chain of friends between them. Examples are provided below: Input: edsger.djikstra, alan.turing Output: edsger.djikstra à charles.babbage à grace.hopper à alan.turing Input: edsger.djikstra, ada.lovelace Output: There is no friends path between edsger.djikstra and ada.lovelace.

Option 2:

The Turing Games Katy Evergreen is competing in the 75th Annual Turing Games. The arena is rectangular and surrounded on all sides by impassable walls. The arena is also filled with numerous impassable obstacles. Katy must capture the flag to win the Turing Games. Write a program in a language of your choice that helps Katy reach the flag by finding the shortest path there. The rules of the Turing Games are as follows: The input for your program will be a file read from standard input. The first line of input will contain two floating point numbers: the arena’s width (or maximum x dimension) and the arena’s length (or maximum y dimension). The second line of input will contain two floating point numbers: (x, y) coordinates showing Katy’s starting point. The third line of input will contain two floating point numbers: (x, y) coordinates showing where the flag is located. The flag will be located within the arena and will not be within the bounds of an obstacle. Next will be 1 to infinity lines containing series of (x, y) coordinate pairs. Each line will contain at least three pairs. These pairs represent the coordinates of the corners of the various obstacles in the arena. Each obstacle is an impassable convex polygon with at least three sides. Input will end with EOF.

Below is a sample input file (bold text is explanatory only and will not be in the file):

1024 4096 arena’s boundaries

110 19 (x, y) coordinates of Katy’s starting point

1023 4090 (x, y) coordinates of the flag

1000 900 1000 1000 800 900 triangle-shaped obstacle (3 pairs)

501 600 501 700 423 650 423 600 four-sided obstacle

Explanation / Answer

providing a solution for option1 :

I think solution is might to start a BFS from both nodes simultaneously.

pseudo code :

nodes1 = (A);

nodes2 = (B);

d = 1;

loop{

nodes1 = neighbours(nodes1);

if(intersects (nodes1, nodes2)){

return d; }

d += 1;

nodes2 = neighbours(nodes2);

if(intersects (nodes2, nodes1)){

return d; }

d += 1;

}

}

Here node1 and node2 is the two unique ids taken from the GUI.

let me know if you have any query regarding this.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.