Probablility with arrays

[LMat619]

Hello everyone! I am new to this forum (and C programming) but I hope that I will be able to master C help anyone out with problems in the coming months. But I am having trouble with my own program for an assignment.
I am asked to simulate a user entered number of birthday parties and user entered number of guests at each party. I am supposed to have a function with the prototype int party(int n) that will simulate one party at a time with n guests. I have to assign each guest with a random birthday and have the program check to see if two of the guests have the same birthday. If one party has two guests with the same birthday, the function returns 1. If all the birthdays at one party are different, the function returns 0.
Then main() counts the number of 1's, divides it by the number of parties and prints out a percentage.
I got a little bit into the program and got stuck.

#include <stdlib.h>
#include <time.h>
int party(int g, int p);
main()
{
	int guests;
	float parties, samebday;
	srand(time(NULL));
	party(guests, parties);
    system("PAUSE");	
    return 0;

}

int party(int g, int p)
{
    int guests, count;
    float parties;
   	printf("Enter the number of parties: ");
	scanf("%f", &parties);
	printf("Enter the number of guests: ");
	scanf("%d", &guests);
	for (count = 1; count <= guests; count++)
	{
        //testing with printf to see if loop works
        printf("%d \n", 1 + rand() % 365);
        }
}

Like I said before, I am a complete noob with C programming and any help would be appreciated. Thank you!

[Adak]

Right off the bat, I don't like float data types for parties and bdays. No one has 1/4th of a party, or .01 bdays.

Unless there is a specific need for floats or doubles, don't use them! They have their own subtle problems.

You will need two nested loops:

for(each party)  {
   for(each guest)  {
      assign their bday. maybe put it also into an array of int's
   }
   now all guests have bdays, see if any of them are duplicate days
   maybe sort them out, and they will be adjacent in the sorted list?
   if (number of duplicates you find > 0)
      return 1
   else
      return 0
  }

That kind of idea.

And welcome to the forum! :)

P.S. If you make your outer loop inside the party function, aren't you going to be stuck trying to return something like your assignment requires?

I would move those questions, and that loop, to main, and use party() as a call, inside that loop.

[LMat619]

Right off the bat, I don't like float data types for parties and bdays. No one has 1/4th of a party, or .01 bdays.

Unless there is a specific need for floats or doubles, don't use them! They have their own subtle problems.

well I'm using the float for parties only because I am simulating 1,000,000 parties. I'm not sure why I put bdays there. Must have accidentally left it there when I was trying different things with the program.

[Adak]

Still wrong - use long int, and your range will be no problem.

Seriously, don't use floats EVER if you don't have to. Try to print out ten and one-third to see one reason why, on your double or float.

[LMat619]

Lol, that makes a lot more sense than float. Thank you.

Making the array is one of my problems. I'm not quite sure how to set the value inside the array to the number entered by the user. Every time I try something the compiler gives me an error. And I am also unsure how to scan the random number into the array.

[Adak]

Lol, that makes a lot more sense than float. Thank you.

Making the array is one of my problems. I'm not quite sure how to set the value inside the array to the number entered by the user. Every time I try something the compiler gives me an error. And I am also unsure how to scan the random number into the array.

You make an array like any other variable, but add [SizeYouWant] after the name of the array. This is a static array - not the only kind, btw.

Use the index to the array's elements, to set your bday numbers up

And on further thought, the easier way to do this is with "counting sort".

Follow me closely:

In the array of numbers {1,3,1,4}, I want to know if there are any duplicate numbers.

I make an array

int dupes[5] = { 0 };  //set array to all zero's
//size is one number bigger than the largest value in numbers!

and then do a for loop like this:
for(i = 0; i < 5; i++) {
  dupes[numbers[i]]++;
}
Now, the dupes array will look like:
Index numbers:
   0  1  2  3  4
==============
{ 0, 2, 0, 1, 1 }

Now, in a simple for loop, I can see if any of the dupes array elements have a value greater than 1. If they do, then there was a duplicate in numbers[] (bdays to you).

This is a simple, and very fast programming trick, that you definitely want to remember. It can save you from so much programming, and help solve problems.

Here, it saves you writing a sort function.

You assign your array values just like any other variable value, but include the array[INDEX].

Do this in a loop, for every guest, as you get the random number bday:

for(each guest)  //i = 0; i < NumberOfGuests; i++
  bdays[i] = rand() % 365;

[LMat619]

Sorry I didnt reply sooner, I had some personal things to take care of.
I understood a little bit of what you said but I got lost after you said "Follow me closely:" haha. I updated the code a little bit and got it to assign each guest with a birthday.

#include <stdlib.h>
#include <time.h>
int party(int g, int p);
main()
{
      int guests;
      long int parties, samebday;
      srand(time(NULL));
      party(guests, parties);
      system("PAUSE");
      return 0;
}
       
      int party(int g, int p)
{
      int guests, count, i, j, bdays[40];
      long int parties;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      for (j = 1; j <= parties; j++)
      {
       for(i = 0; i < guests; i++)
       {
             bdays[i] = 1 + rand() % 365;
       }
      }
}

All I need to do now is make a loop to check if two+ guests have the same bday and have it return 1 or 0.

[Adak]

After the for loop for each party, you want use the "follow closely" code, to find the elements in dupes, if any, that have a value greater than 1.

Those are your duplicated bdays.

Read that part again, and use that "counting sort" logic, in your program. You'll be glad you did.

[LMat619]

Ok, I understood it a little bit more. I went and edited the code to add it. It compiled fine but when it reaches the loop, the program stops running and wont respond. Can you check what's wrong with it?

int party(int g, int p)
{
      int guests, count, i, j, bdays[40], duplicates[50] = { 0 }, k;
      long int parties;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      for (j = 1; j <= parties; j++)
      {
       for(i = 0; i < guests; i++)
       {
             bdays[i] = 1 + rand() % 365;
       }
      }
      for (k = 0; k <= guests; k++)
       {
           duplicates[bdays[k]]++;
           //printf just to test
           printf("%5d", duplicates[bdays[k]]);
       }
}

[Adak]

Back in a bit.

[Adak]

It was crashing because you were running outside the boundaries of dupes. It has to have 366 elements (0-365). Even though there is no day 0, the arrays in C always start with zero, so that explains the one day extra in this size (I hope). ;)

The program is a bit odd, because the party() function does everything. I did not change that.

#include <stdio.h>


int party(int g, int p)
{
      int guests, count, i, j, duplicates[366] = { 0 }, k, haveDupes = 0;
      int bdays[10] = {209,37,209,151,37,302,8,142,151,209};
      long int parties;
      guests = 10;
/*      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      parties = 1;
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      guests = 10;
      for (j = 0; j < parties; j++)
      {
*/
        for(i = 0; i < guests; i++)
        {
//          bdays[i] = 1 + rand() % 365;
            duplicates[bdays[i]]++;
            if(duplicates[bdays[i]])
              haveDupes = 1;
        }
    //}


      if(haveDupes) {
        printf("\n The Duplicated Birthday Numbers Are: \n");
        for (k = 0; k < 366; k++)
        {
          //printf just to test
          if(duplicates[k] > 1)
             printf("\n%3d: %5d", k, duplicates[k]);
        }
      }
      else
        printf("\n No Duplicated Birthday Numbers Were Found.");

}
int main() {
  int n;
  printf("\n\n");
  n = party(0,0);  

  getch();
  return 0;
}

variables like g, p, and n (in main), are never used and shout that the program needs a bit of a re-design, when you can.

To enable multiple parties, just remove the /* and */ from your code, and be sure the printouts of the duplicates is done for EVERY party.

Adding which party number has the found duplicates, would be a good idea.

[LMat619]

I took the program you made and edited it so the user can enter the parties and guests but it is printing out every party and a random number way more than 365. I'm not sure what it is doing. It's doing something like:
...
30: 1534
31: 1296
32: 840
...

[Adak]

I can't fix code that I can't see. ;)

[LMat619]

Lol, my bad. I talked to my professor and he helped me out a little bit with the little time he had. I cleaned up my code so it returns 1 or 0 and party() doesn't do everything but it's not printing out the number of same and different bdays. Can you spot what's wrong with it?

#include <stdlib.h>
#include <time.h>
int party(int g);
main()
{
      int guests, j;
      long int parties, samebday, diffbday, count;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      srand(time(NULL));
      samebday == 0;
      diffbday == 0;
      for (j = 1; j <= parties; j++)
      {
      count = party(guests);
      if (count = 1)
         samebday++;
      else
          diffbday++;
      }
      printf("%d \n", samebday);
      printf("%d \n", diffbday);
      system("PAUSE");
      return 0;
}
       
      int party(int g)
{
      int i, j, bdays[50];
      long int parties;
       for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
       for (j = 0; j < g; j++)
       {
          if (bdays[i] = bdays[j])
             return 1;
             else
                 i - 1;
             if (i = 0)
                return 0;
       }
       }
}

[Adak]

Assignment of a value to a variable, uses just ONE = sign.

Comparison of one variable with a number, requires TWO == signs.

So this needs correcting in your code:

samebday == 0;  //***
      diffbday == 0;    //***
      for (j = 1; j <= parties; j++)
      {
      count = party(guests);
      if (count = 1)    //***
         samebday++;
      else
          diffbday++;
      }

All the one's with //*** on that line, need correcting.

Check the rest of your program over for more of the same. I did not do that.

[0x69]

All I need to do now is make a loop to check if two+ guests have the same bday and have it return 1 or 0.

I optimized a bit calculation of duplicates - main idea is that when guest count is less than 365 -> we should iterate through guests and not through year days. In that case we win some CPU cycles. Theoretically speed-up factor would be 365/guestCount. If you simulate 1,000,000 parties then this is important thing :)
Code:

int HasDuplicates(int bornedThisDay[], int bdays[], int guestCount ) {
	int byGuests = (guestCount < 365);
	int until = (byGuests)? guestCount:365;
	int skipThisDay[365];
	int duplicates = 0;
	
	for (int i=0; i < until; i++) {
		if (byGuests) {
			if (!skipThisDay[bdays[i]]) {
				duplicates = bornedThisDay[bdays[i]];
				skipThisDay[bdays[i]] = 1;
			}
		}
		else {
			duplicates = bornedThisDay[i];
		}
		if (duplicates > 1)
			break;
	}
	return (duplicates > 1);
}

int bornedThisDay[365] -> this is aka. duplicates[] array as in Adak example.

Good luck !

[Adak]

Another point I did not mention, but is very likely to cause errors, is if you re-use the dupes array, after one party, without resetting the elements of that array to zero!

That would give you VERY large numbers, after a bunch of parties. So set it to zero's, using a for loop, after every party has been all reported.

[LMat619]

Ok, well the code is doing exactly what i want it to do except for one minor thing. It is always returning 1. I'm thinking there is something wrong with the for loop when I am comparing bday and bday[j].

#include <stdlib.h>
#include <time.h>
int party(int g);
main()
{
      int guests, j;
      long int parties, samebday, diffbday, count;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      srand(time(NULL));
      samebday = 0;
      diffbday = 0;
      for (j = 1; j <= parties; j++)
      {
      count = party(guests);
      if (count == 1)
         samebday++;
      else
          diffbday++;
      }
      printf("%d \n", samebday);
      printf("%d \n", diffbday);
      system("PAUSE");
      return 0;
}
       
      int party(int g)
{
      int i, j, bdays[g];
      long int parties;
       for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
       for (j = 0; j < g; j++)
       {
          if (bdays[i] == bdays[j])
             return 1;
             else
                 i - 1;
             if (i == 0)
                return 0;
       }
       }
}

[WaltP]

for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
             for (j = 0; j < g; j++)
            {
                  if (bdays[i] == bdays[j])
                        return 1;
                   else
                       i - 1;
                 if (i == 0)
                       return 0;
             }
       }

This loop makes no sense at all. Your first step is to format the entire code because it's really hard to see what's going on. I reformatted the loop and it still is senseless.

i and j both start at 0. So your IF is always true since bdays[0] will always be equal to itself.
If the IF wasn't true though, you execute i - 1 which does nothing. Then you test if i is zero, which it is, so you return.

[Adak]

Ok, well the code is doing exactly what i want it to do except for one minor thing. It is always returning 1. I'm thinking there is something wrong with the for loop when I am comparing bday and bday[j].

#include <stdlib.h>
#include <time.h>
int party(int g);
main()
{
      int guests, j;
      long int parties, samebday, diffbday, count;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      srand(time(NULL));
      samebday = 0;
      diffbday = 0;
      for (j = 1; j <= parties; j++)
      {
      count = party(guests);
      if (count == 1)
         samebday++;
      else
          diffbday++;
      }
      printf("%d \n", samebday);
      printf("%d \n", diffbday);
      system("PAUSE");
      return 0;
}
       
      int party(int g)
{
      int i, j, bdays[g];
      long int parties;
       for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
       for (j = 0; j < g; j++)
       {
          if (bdays[i] == bdays[j])
             return 1;
             else
                 i - 1;
             if (i == 0)
                return 0;
       }
       }
}

As WaltP has alluded to, the party() loops are off.

I think you were thinking about the nested loops needed in main:

1) for the parties, and 2) for the guests.

But in the party() function, there is no need for nested loops. There is only "guests" data from one party at a time, present.

So the for loop with j as the iterator, should be removed, completely.

...//your other code in party() up here, 

    for(i = 0; i < g; i++)  //assign the bdays random day numbers
    {
          bdays[i] = 1 + rand() % 365;
    }
     //let the previous loop finish, completely
    //now start the loop to test if there is a duplicate

/* 
Can't do the test, because you removed the code that would do the counting sort!

Crap!
*/
          
}

LMat, you need to find someone that you can trust to follow their advice on this matter, and follow it.

Right now, you're wasting my time, and I'm wasting yours.

[LMat619]

Yeah, maybe you're right. My professor wants me to have the program check if any birthdays are the same without assigning all of the guests with b-days first, unless all the b-days are different by the time it reaches the end (which would return 0).
Well, thanks for all your help. I probably wouldn't have even gotten this far if it wasn't for you.

[Adak]

Oh says the smart student, I could put that counting sort code just before the assignment of the random number bday!

Brilliant!

if(counting sort finds a duplicate)
return value to indicate a duplicate was found
else
assign bday number to the guest

return value to indicate no dupes were found

You could do a binary search instead, before the bday assignment, but that's about 800% slower. A sequential search would be Number of guests * 100 % slower. < eek! >

[0x69]

Ok, well the code is doing exactly what i want it to do except for one minor thing. It is always returning 1. I'm thinking there is something wrong with the for loop when I am comparing bday and bday[j].

#include <stdlib.h>
#include <time.h>
int party(int g);
main()
{
// bla bla bla
      int party(int g)
{
      int i, j, bdays[g];
      long int parties;
       for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
       // why you iterating util guestCount here ?
      // it doesn't make sense here, because
      // rest bdays with j > i will be empty.
     // Besides this will repair your error when you
    // was comparing guest birthday with himself (i==j)
    // so =>
       for (j = 0; j < i  /*g*/; j++)
       {
          if (bdays[i] == bdays[j])
             return 1;
             else
                 i - 1;
             if (i == 0)
                return 0;
       }
       }
}

Also there are some nonsensical code here - what is this ?

else
   i - 1;

??
But i dont like brute-force search as I said before, because it will perform slow. So you should try to search for duplicates as in my example before OR at least:
1. Sort bdays array with QSORT function.
2. Then search that bdays array in acending order with only one loop, something like

// sort bdays
qsort(bdays,...);
// search for duplicates
// (this only do AFTER you generate ALL guest birthdays)
for (j = 0; j < g-1 ; j++) {
   if (bdays[j]==bdays[j+1]) {
    // duplicate found
    return 1
   }
}
// there are no duplicates
return 0;

In this case sorting array + 1 loop should perform faster than performing 2 loops as in your code. But ... as you wish.

Good luck!

[Adak]

Also there are some nonsensical code here - what is this ?

else
   i - 1;

??
But i dont like brute-force search as I said before, because it will perform slow. So you should try to search for duplicates as in my example before OR at least:
1. Sort bdays array with QSORT function.
2. Then search that bdays array in acending order with only one loop, something like

// sort bdays
qsort(bdays,...);
// search for duplicates
// (this only do AFTER you generate ALL guest birthdays)
for (j = 0; j < g-1 ; j++) {
   if (bdays[j]==bdays[j+1]) {
    // duplicate found
    return 1
   }
}
// there are no duplicates
return 0;

In this case sorting array + 1 loop should perform faster than performing 2 loops as in your code. But ... as you wish.

Good luck!

As it turns out, the assignment requires LM to NOT have duplicate bdays checked after they've been assigned to all the guests.

I thought it would simplify the program a bit to do it that way. Also, it just seemed odd to check bdays BEFORE they were assigned to the guests.

Bottom line is, it will be done (with the next version), using a very fast counting sort look up, BEFORE the bdays are assigned. So it will be way faster than Quicksort or any other sorting algorithm.

If you haven't run across the simplicity and speed of counting sort, you might want to stay tuned. It's a very worthwhile trick to know. You can't use it all the time, but when you can - it sets the guitars on fire! ;)

[LMat619]

I think I might have made a breakthrough! Here is my new code, and it is actually returning both 1's and 0's! If you notice anything wrong with it, let me know but I think I got it to work.

#include <stdlib.h>
#include <time.h>
int party(int g);
main()
{
      int guests, j;
      long int parties, samebday, diffbday, count, result;
      printf("Enter the number of parties: ");
      scanf("%ld", &parties);
      printf("Enter the number of guests: ");
      scanf("%d", &guests);
      srand(time(NULL));
      samebday = 0;
      diffbday = 0;
      for (j = 1; j <= parties; j++)
      {
      party(guests);
      count = party(result);
      printf("%d \n", count);
      if (count == 1)
         samebday++;
      if (count == 0)
          diffbday++;
      }
      printf("%d \n", samebday);
      printf("%d \n", diffbday);
      system("PAUSE");
      return 0;
}
       
      int party(int g)
{
      int i, j, bdays[g], matches;
      long int parties, hold;
      matches = 0;
       for(i = 0; i < g; i++)
       {
             bdays[i] = 1 + rand() % 365;
       }
             for (j = i-1; j >= 0; j--)
             {
                 if (bdays[j] == bdays[i])
                    matches = 1;
             }
             return matches;
}

CRAP! I just realized that it assigns all the birthdays first, then checks if any are the same. I tried moving the } down to the bottom but the code didn't work. SOOOO FREAKING CLOSE!!

[Adak]

"So freakin' close!"

Yep! ;)

I see you're determined to do this the simple and slow way <sigh >

int party(int g) {
  int i, j, bdnum; 
  int bdays[g] = { 0 };
  long int parties, hold;
  for(i = 0; i < g; i++)  {
    bdnum = 1 + rand() % 365;
    for(j = 0; j <= i; j++)  {
      if(bdnum == bdays[j])  
        return 1;
    }
     //assign bdnum to bdays[i], here 
  }
  return 0;
}

[LMat619]

It keeps showing me an error for this line:

int bdays[g] = { 0 };

[Adak]

It keeps showing me an error for this line:

int bdays[g] = { 0 };

How this is handled, depends on what version of the Standard for C, you're compiler is supporting.

Usually, g would need to be a constant int, declared before that line (of course), or a (capitalized by convention):
#define G 300

(for the number, pick one about twice the size of what you expect your largest number of guests to be.)

located just below your #include files lines of code (also by convention).

You CAN allocate the exact size of array you want with malloc, but your class hasn't got there yet - otherwise you wouldn't be showing me this error.

Then make it:
int bdays[G] = { 0 };

and remember to keep the lower case g, for whatever the user inputs as the number of guests.

So the teacher's intention is to show malloc to you, later. I would use #define G 300 for now.

[LMat619]

SUCCESS!!! I got it to work! Thank you so much!! I'm sorry I caused you so much trouble. C is very new to me so I kinda suck at it right now. I really appreciate all your help. Thanks again!

[Adak]

You're quite welcome. Odd thing about this bit of birthdays being on the same day - if you have a group of 50 people, the odds are VERY high that two of them will share the same bday.

Very un-intuitive! Google "Birthday paradox".

When I was in high school, I tried to explain this in an oral presentation to the class.

The presentation went well - but they didn't get it, at all.

Got me so mad, I went out to the field across the street, and kicked a brontosaurus in the butt, and ran like hell.

Ah, the good ol' days! ;)