[Problem Solving #2] Sharing is Caring

[wolfsinner]

Problem #2 - Sharing is Caring

 

So here's Problem #2 of the series. I'm not sure if the description is lacking, if it is please ask for further explanation. I cannot overstate that!
 
Problem Description:
David loves chocolate. He loves it so much that he engineered a chocolate machine which can produce infinite amounts of chocolate out of thin air!
He was so happy about this magnificent discovery that he decided to share the machine's blueprints with all his friends.
His friends heard about it, and shared the blueprint with their friends (who hadn't heard of the machine yet) the following day.

This behavior is repeated, until everyone in David's social network is aware of the blueprints.

Your goal is to determine:
- The "maximum sharing day" size, which represents the largest number of people that, on a single day, hear about the machine's blueprint for the first time. Note that David does not count.
- The first day during which maximum sharing is achieved.

 

So an example of this process would be:
David tells Anne and Joe about the machine (2 people in day 1).
Anne tells it to Laura, and Joe to Carl and Manny (3 people in day 2).
They have no more friends.
In this case, the "maximum sharing day" size would be 3 and the first day would be 2.

Input:
The input is given in the following format:
The first line of input contains the number P of people in David's social network (including David).
After that line, there are P lines which specify the group of friends of a person (from person 0 to person P-1).
Each of these P lines starts with an integer N, which represents the number of friends that person has, followed by N distinct integers, which identify each friend, separated by a single space.
The last line contains an integer D which represents David (a value between 0 and P-1).

You can download a zip file containing all 5 input files here.

Example input:
6
2 2 4
4 1 4 3 5
3 2 5 0
3 0 5 2
2 0 3
3 3 2 1
1

 

6

2 1 2

2 3 4

3 0 4 5

1 4

0

2 0 2

4

 

 

Too large to show. Download zip file.

 

Too large to show. Download zip file.

 

Too large to show. Download zip file.

 

Too large to show. Download zip file.

 
Output:
The output consists of 2 lines. At the end of every line there must be a line break.
The first line is the "maximum sharing day" size.
The second line is the first day of maximum sharing.
If no one, but David, hears about the machine, then both values should be 0.

Example output:
3
1

 
How to test your solution:
I have updated the gateway to allow for multiple tests.

To submit your output solutions you need to run your code with each of the input files provided in the zip file, and place your output in the appropriate text box.

So your program's output with input from file "input1.txt" should be placed in the "Output 1" box.

 

I recommend downloading the zip file, and using command-line input redirection to send the file contents into the standard input stream of your program. In Windows, Linux or Mac OS, you would do something like:

You can submit your output solutions through the problem solving gateway here.

 
Final notes:

• Create your account at the gateway with the same username as the one you use at the forums.
• Include your code in spoiler tags, so that the thread isn't cluttered with code.
• If you're having trouble solving the problem, ask the community for help! You may learn a lot from them.
• Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it.
• Please don't share the output solution if you've solved the problem.
• If the problem description isn't clear, please ask for further explanation!

[command to run your program] < inputN.txt

[AlwaysFSX]

Your text blends in really well with the background for the night theme...

[Fred Castellum]

I can read a thing with night theme on a tablet. =/

[wolfsinner]

I can read a thing with night theme on a tablet. =/

I'm not sure what the night theme is. Did my edit fix it? I'm sorry, I really have no idea what it is. haha

 

EDIT: Ok, I just saw it. Seems ok now, someone please confirm. That's what I get for copying the text directly from the gateway.

[Maximation]

So far I have always had difficulty with inputstreams. What is the correct way of implementing input stream readers?

Interesting problem

[fizzlesticks]

Always hated graph problems

and had the output lines flipped on my first try

edit: Updated code to use sets, increasing speed by about 25x

class Vertex:    def __init__(self,name,neighbors):        self.neighborNames = neighbors        self.name = name        self.neighbors = []    def addNeighbor(self,v):        self.neighbors.append(v)    def __str__(self):        return "{}, {}".format(self.name,self.neighborNames)        def __repr__(self):        return self.__str__()def main():    graph = []    maxSharingDay = 0    maxSharingCount = 0    david = None    numPeople = int(input())    for i in range(0,numPeople):        line = input().rstrip().split(" ")        neighbors = [int(x) for x in line[1:]]        vert = Vertex(i,neighbors)        graph.append(vert)    for v in graph:        for n in v.neighborNames:            v.addNeighbor(graph[n])    davidNum = int(input())        david = graph[davidNum]    visited = set()    visited.add(david)    newNodes = set(david.neighbors)    day = 0        while newNodes:        day += 1                count = len(newNodes)        if count > maxSharingCount:            maxSharingCount = count            maxSharingDay = day        for v in newNodes:            visited.add(v)        newNodes = set()        for v in visited:            for n in v.neighbors:                if n not in visited:                    newNodes.add(n)            print(maxSharingCount)    print(maxSharingDay)if __name__ == "__main__":    from timeit import Timer    t = Timer(lambda: main())    print(t.timeit(number=1))

[wolfsinner]

So far I have always had difficulty with inputstreams. What is the correct way of implementing input stream readers?

Interesting problem

 

You can use Scanner, which is a wrapper class that encapsulates an input stream. 

Scanner in = new Scanner(System.in); //System.in is the standard inputint x = in.nextInt(); //this will read the next integer in the input stream

Scanner is slow though. I also solved this with Java, and I wrote a simple class which reads input much faster than Scanner, and is used in an equivalent way.

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.util.StringTokenizer; public class FastReader {    private StringTokenizer tokenizer;    private BufferedReader breader;     public FastReader(InputStream stream) {        tokenizer = new StringTokenizer("");        breader = new BufferedReader(new InputStreamReader(stream));    }     public String next() throws IOException {        while (!tokenizer.hasMoreTokens()) tokenizer = new StringTokenizer(breader.readLine());        return tokenizer.nextToken();    }     public int nextInt() throws IOException {        return Integer.parseInt(next());    }}

[Ciccioo]

in the sample input, good ol' David is friend of himself

that's really sad

[Maximation]

The way David shares his blueprints is unclear to me. He shares the blueprints with all of his friends on the first day, then all of his friends know about it. So when they want to tell their friends about the blueprints (day 2) their friends already know about it because David told them about it the first day. This is how I understand it. Because they are all part of David's social network, aren't they?

 

Also, how can David be included in this:

6
2 2 4
4 1 4 3 5
3 2 5 0
3 0 5 2
2 0 3
3 3 2 1
1

 

According to this input there are 6 people in David's social network, after the first line follow 6 lines representing all 6 of his friends in his social network (he can not be included because there are already six friends, right?). How should I try to understand the inputs?

Mh, interesting problem. I hope I will still be able to solve it

[Ciccioo]

(he can not be included because there are already six friends, right?).

Input:

The input is given in the following format:

The first line of input contains the number P of people in David's social network (including David).

the input is not the list of David's friends. it's the list of people on the social network

 

 

The way David shares his blueprints is unclear to me. He shares the blueprints with all of his friends on the first day, then all of his friends know about it. So when they want to tell their friends about the blueprints (day 2) their friends already know about it because David told them about it the first day. This is how I understand it. Because they are all part of David's social network, aren't they?

David is not friend of all the people on the list, he is one person in the list, and you can see there who are his friends

you know which one is David by reading the last line

in the sample input, David's friends are 1, 4, 3, 5

[Ciccioo]

alright, i never really studied graph theory at school, so i just went the way i know

it's pretty much a breadth-first-search

 

this is my solving code:

 

maybe i can learn something from other user's solutions

 

edit: memory leaks D:

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef enum{    false,    true}bool;typedef struct{    bool visited;    size_t nFriends;    size_t* friends;}person;person* readInput(size_t* P, size_t* David){    scanf("%zu", P);    person* facebook = malloc(*P * sizeof *facebook);    size_t i;    for(i = 0; i < *P; i++){        facebook[i].visited = false;        scanf("%zu", &(facebook[i].nFriends));        facebook[i].friends = malloc(facebook[i].nFriends * sizeof(size_t));        size_t j;        for(j = 0; j < facebook[i].nFriends; j++)            scanf("%zu", facebook[i].friends + j);    }    scanf("%zu", David);    facebook[*David].visited = true;    return facebook;}void freeInput(person* facebook, size_t P){    while(P--)        free(facebook[P].friends);    free(facebook);}int main(){    size_t P, David;    person* facebook = readInput(&P, &David);    size_t maxSharingDay = 0;    size_t maxSharing = 0;    size_t friendsLeft = P;    size_t queueSize = facebook[David].nFriends;    size_t* queue = malloc(queueSize * sizeof *queue);    memcpy(queue, facebook[David].friends, queueSize * sizeof *queue);    size_t sharingDay = 0;    while(queueSize && friendsLeft > maxSharing){        sharingDay++;        size_t i, friendsToQueue = 0;        for(i = 0; i < queueSize; i++)            if(!facebook[queue[i]].visited)                friendsToQueue += facebook[queue[i]].nFriends;        size_t sharing = 0;        size_t* newQueue = malloc(friendsToQueue * sizeof *newQueue);        size_t queuePosition = 0;        for(i = 0; i < queueSize; i++){            person* guy = facebook + queue[i];            if(!guy -> visited){                guy -> visited = true;                friendsLeft--;                sharing++;                memcpy(newQueue + queuePosition, guy -> friends, guy -> nFriends * sizeof *newQueue);                queuePosition += guy -> nFriends;            }        }        free(queue);        queue = newQueue;        queueSize = friendsToQueue;        if(sharing > maxSharing){            maxSharing = sharing;            maxSharingDay = sharingDay;        }    }    freeInput(facebook, P);    printf("%zu\n%zu\n", maxSharing, maxSharingDay);    return 0;}

[Maximation]

the input is not the list of David's friends. it's the list of people on the social network

 

 

David is not friend of all the people on the list, he is one person in the list, and you can see there who are his friends

you know which one is David by reading the last line

in the sample input, David's friends are 1, 4, 3, 5

 

Aha, that explains it. Good, thank you very much. I think I can solve this now, I will have another try.

[Maximation]

Good. So I now have this :

 

The lines of all the people in David's network are stored in an array. Now I have to get all the different numbers from the line representing David and his friends, how should I do this with the string. I can get it from the array, but how should I let all his friends know about the blueprint?

 

I'm sorry if my newbish questions annoy you, but ehh.. well let me ask you, how did you learn? Did you learn without asking questions?

import java.util.Scanner;public class Main {	private static int socialNetworkSize;	private static int indexDavid;	private static String[] socialNetwork;	private static int day;	public static void main(String[] args){		Scanner in = new Scanner(System.in);		/*		 *	gets the size of david's social network (first integer on the first line)		 */		socialNetworkSize = Integer.parseInt(in.nextLine());		/*		 *	puts every member of the social network in a String array		 */		socialNetwork = new String[socialNetworkSize];		for (int i = 0; i < socialNetworkSize; i++)			socialNetwork[i] = in.nextLine();		/*		 *	gets last integer of the input file (index of David)		 */		indexDavid = Integer.parseInt(in.nextLine());	}}

[Ciccioo]

well let me ask you, how did you learn? Did you learn without asking questions?

I think i'm more of a sit-down-and-try type, and i think that that's a good approach, because when you have to get a job done, it's not sure that there will be someone there to ask questione to

With that said, i'm not telling you to stop asking, absolutely no, but i think you should try [much] harder

You have an array with a string, and you need the numbers in it

I really don't think that you're not capable of doing this, or that you can't find any hint in google

[wolfsinner]

alright, i never really studied graph theory at school, so i just went the way i know

it's pretty much a breadth-first-search

 

maybe i can learn something from other user's solutions

 

Breadth-First Search is the way to do it. It IS a graph search algorithm.

 

 

Good. So I now have this :

 

The lines of all the people in David's network are stored in an array. Now I have to get all the different numbers from the line representing David and his friends, how should I do this with the string. I can get it from the array, but how should I let all his friends know about the blueprint?

 

I'm sorry if my newbish questions annoy you, but ehh.. well let me ask you, how did you learn? Did you learn without asking questions?

 

You don't need those Integer.parseInt calls though. Scanner has a nextInt() function which does exactly what you need.

Don't store the strings, store the integers. Create some data structure which represents "A person's friends", and store them there.

 

Use nextInt() to get the number of people P. Then do a loop P times which reads each person.

Again, use nextInt() instead of nextLine(). Read the N at the start of each line, then you're guaranteed (by the input) that you need to read N integers after it.

At the end, read one last integer which will be David.

You'll never need to use nextLine().

[Ciccioo]

Breadth-First Search is the way to do it. It IS a graph search algorithm.

oh

*facepalm*

well, i'm good then

 

when i said that though, i was more thinking about the way to solve the problem itself, particular graph data structure or stuff like that

[Maximation]

I think i'm more of a sit-down-and-try type, and i think that that's a good approach, because when you have to get a job done, it's not sure that there will be someone there to ask questione to

With that said, i'm not telling you to stop asking, absolutely no, but i think you should try [much] harder

You have an array with a string, and you need the numbers in it

I really don't think that you're not capable of doing this, or that you can't find any hint in google

 

Mh yes, I think you're right. I should try harder myself. But sometimes I just do not know how to handle a specific situation, or what methods are available to solve something. You can not figure out all the useful methods and classes the standard java libraries provide to you by just "sit-down-and-try".

 

And btw, I do not use Google, but I know what you mean.

[fizzlesticks]

And btw, I do not use Google

Well there's your problem.

[Maximation]

Breadth-First Search is the way to do it. It IS a graph search algorithm.

 

 

 

You don't need those Integer.parseInt calls though. Scanner has a nextInt() function which does exactly what you need.

Don't store the strings, store the integers. Create some data structure which represents "A person's friends", and store them there.

 

Use nextInt() to get the number of people P. Then do a loop P times which reads each person.

Again, use nextInt() instead of nextLine(). Read the N at the start of each line, then you're guaranteed (by the input) that you need to read N integers after it.

At the end, read one last integer which will be David.

You'll never need to use nextLine().

 

Good. I have some problems with storing the friends of all the people in the social network. I have tried to store it in arrays in an array but that didn't worked very well, I believe. How should I store all of these numbers?

[Maximation]

Well there's your problem.

 

I use "duckduckgo" instead, so I still use a search engine, and it works amazing

[wolfsinner]

Good. I have some problems with storing the friends of all the people in the social network. I have tried to store it in arrays in an array but that didn't worked very well, I believe. How should I store all of these numbers?

 

Usually graphs are stored (when they can) as either arrays of lists/arrays (to save memory and faster iteration), or in a VxV matrix (faster random access).

 

Since you'll only be iterating through the friends, a simple structure is:

//this is an array of listsList<Integer> [] people = new LinkedList[P];//you would then create a Linked List for each person (when necessary), which would contain their friendspeople[n] = new LinkedList<Integer>();  //you could then access person n's friends through the list at people[n]List<Integer> friendsOfN = people[n];//-----------------------------------------------------------------------------//you can alternatively create an array people[P][N of p]int [][] people = new int[P][];//then for each person you would create an array with the integers corresponding to the person's friends (given by the input), an example is:int [] friends = {0, 2, 5};people[n] = friends; //and set it to the appropriate index

Another alternative, albeit less efficient, is making a PxP matrix of booleans, and place true on the indexes that correspond to a person's friend.

boolean [][] people = new int[P][P]; //adding friend 2 to person 1 would meanpeople[1][2] = true;

Either way, you get a data structure that fits all your needs for storing this information (I recommend using the lists/array of arrays).

I hope I wasn't confusing!

[Ciccioo]

You can not figure out all the useful methods and classes the standard java libraries provide to you by just "sit-down-and-try".

I use "duckduckgo" instead, so I still use a search engine, and it works amazing

you can just type in what you need, and the internet will serve it to you on a unicorn

just think "i need a function that takes x as a parameter and gives me back y", formulate it somehow good and type it in the search engine

[fizzlesticks]

@Ciccioo What compiler/standard do you use? I tried using gcc (Windows version) with a bunch of different standards but your code either output:

zu

zu

 

or

 

0

0

 

for all the inputs.

[Ciccioo]

@Ciccioo What compiler/standard do you use?

Hm weird

I used gcc for linux, i compiled via command line without particular options so it should be C89

Try just casting the output vars to int, and print them with %d, i think i read that %zu for printing size_t isn't portable for some reason, but i didn't try it on windows yet

And i actually wasn't able to run your code, but i don't know python so i didn't try much

I ran it with python 2.7 on linux, and it gave some kind of error on the input parsing code

[fizzlesticks]

Hm weird

I used gcc for linux, i compiled via command line without particular options so it should be C89

Try just casting the output vars to int, and print them with %d, i think i read that %zu for printing size_t isn't portable for some reason, but i didn't try it on windows yet

And i actually wasn't able to run your code, but i don't know python so i didn't try much

I ran it with python 2.7 on linux, and it gave some kind of error on the input parsing code

Hmm interesting, changing everything to %d works. but the z modifier was added in c99 wasn't it? I'll just blame it on Windows.

 

I use Python 3.3, the input function changed a bit in 3.0 but anything 3+ should work.