Thread: Results of March Monthly Contest

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Results of March Monthly Contest

    Ok everyone, I am going to post the results as well as my solutions in this thread. I'll start with the medium since noone posted code for that one, then the hard one, then tomorrow I'll post the results of the easy problem.

    Medium Problem

    Like I said when I posted this problem, I was a little torn about the difficulty of this problem. Since nobody posted code I now know it should have been listed as difficult, but once you see how this problem can be solved in only a couple of lines you'll see why I thought it might be easy.

    Solving the number of combinations can be very difficult if you try to brute force it. You could recursively try every combination of animals but you'll soon find that you'll quickly max out your time. It turns out this problem can be solved very easily using a technique called dynamic programming. I'm not gonna lecture on it so if interested I'd recommend reading up on it, but its a powerful way to solve seemingly impossible problems. Its similar to recursion in that you break the problem up into smaller and smaller parts, but you use an intuitive data storage to prevent recalculating the same results over and over again.

    Heres an example thats similar to my problem. How many different ways can you combine US coins to equal 17 cents? Again you could try every possible combination of coins but thats far too much work. Heres how to do it with dynamic programming:

    Start off with an array of zeros of size n+1 where n is your target number. In this case we are looking for 17 cents, so our array would be size 18. Now what does this array represent? At each index, its the total number of combinations to get to that point. So index 10 is the number of combinations to 10 cents, etc. What we care about is index 17 or the last index. At this point everything is zero since we haven't calculated anything yet. First thing is to set index 0 to 1 since we automatically know that theres only one combination to get zero cents, and thats no coins at all. So our array looks like this:
    Code:
    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    Now you loop through the array with each coin type. Now heres the tricky part, at each spot in the array you know how many combinations it takes to get there since its the value of the index you are at. So if you are array[7] and the value is 5, then you know that there are five different combinations that get you to there. Now say you are looping through with pennies, if you know theres five ways to get where you are now, then add a penny to each of those and you know that theres five combinations to get to array[8]. If array[8] already had 3 combinations of its own, you now know theres 5+3 combinations to get to array[8]. Get the idea? So heres the basic algorithm:
    Code:
    // target is value we are shooting for
    int howMany(int target)
    {
    	int coins[5]={1,5,10,25,50}; // coin values
    	int combinations[500]={0};  // big array to keep the combos :D
    	combinations[0]=1;
    	
    	for (int i=0; i<5; i++)
    		for (int j=0; j<target; j++)
    			combinations[j+coins[i]]+=combinations[j];
    			
    	return combinations[target];
    }
    It can be optimized further but you get the idea. So after pennies our array looks like this:
    Code:
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    After nickels:
    Code:
    1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4
    After dimes:
    Code:
    1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6
    And no reason to do quarters or half dollars. So returning array[17] gives us 6 which is the correct number of combination of coins to 17 cents.

    So if you can understand this one, it should be easy to figure out how to solve my problem. Since we need to know the number of combinations of feet AND heads, we now use a two dimensional array, where array[h][f] is the number of combinations that have h heads and f feet.

    Heres my code to solve the problem (again which could be optimized further but no real need):
    Code:
    // target is value we are shooting for
    int numberCombinations(int maxAnimals, int maxFeet, vector<int> animals)
    {
       int combinations[500][500]={0}; // again lazy, could be dynamically created
       combinations[0][0]=1;
    
       for (int i=0; i<animals.size(); i++)
          for (int curHeads=0; curHeads<=maxAnimals; curHeads++)
             for (int curFeet=0; curFeet<=maxFeet; curFeet++)
                combinations[curHeads+1][curFeet+animals[i]]+=combinations[curHeads][curFeet];
    
       return combinations[maxAnimals][maxFeet];
    }
    Last edited by PJYelton; 03-24-2005 at 09:54 PM.

  2. #2
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    Ok, that big font's really ........ing me off.

  3. #3
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by jverkoey
    Ok, that big font's really ........ing me off.
    +1


    ...

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>Ok, that big font's really ........ing me off.<

    Sorry, if you mean the long lines, I shortened them. If not, let me know whats wrong.

  5. #5
    customized user title!
    Join Date
    Mar 2005
    Posts
    24
    It's not the line length, it's the size of the font.

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    The font size is no different than normal for me... I'll take the size tags off of the problem header and see if that helps. Let me know.

  7. #7
    customized user title!
    Join Date
    Mar 2005
    Posts
    24
    It's back to a readable size, thanks.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Hard Problem

    I tried hard to find an elegant solution to this one but it appears that brute force is needed. The problem is that calculating every possibility for even the simple examples would easily time out, so one must still find some method for pruning the search tree. Turns out one such method exists which greatly reduces the running time.

    If someone is picking after you theres no way to narrow down the numbers to choose from and will have to test them all, but what if you are the last to choose? Do you still have to try every number? Nope. For example, if this is the graph of peoples choices so far and you are last to choose:
    Code:
    ------X--------X-------X-----X-X-----
    the ONLY spots you need to check are:
    Code:
    -----OXO-------XO------XO----XOXO----
    So your choice of moves is very limited when you or anyone else chooses last. This might not seem like it helps out a lot but lets choose an example. Say you have approximately 1000 numbers to check and you have one person after you and one person who picked before you. For each of your 1000 moves your opponant has 999 moves, to check each combo would result in 1000*999 possibilities or 999000 states to check. Now use the above trick, you'll only need to check 3 places in the last level, so for each of your 1000 moves the last player has 3 choices, resulting in only 3000 possibilites to check. 999000 vs 3000 is a HUGE difference!

    So the algorithm basically goes, recursively try every solution except on the last level where you only choose based off of the above trick. To compute the score for any move, its basically the score above + the score below your number + 1.

    For the score below, if you are the lowest number than the score is simply your number - 1. If not, then its (your number-previous number-1)/2. For the score above, if you are the highest number than its (range-your number) and if not its (next number-your number-1)/2.

    Only one person submitted code and thats Karthur. Unfortunately I wasn't able to get his code to compile in MSVC++ due to several errors which I'm assuming are compiler dependant. His method appears to compute the correct answer although many items would time out.

    So for Karthurs score I give a 9/10 with 1 point being deducted for the timeouts, plus an extra 10 snazzy points for being the only one brave enough to submit an entry for a grand total of 19 points and the contest winner for the hard solution. Congratulations! I highly encourage everyone to give this man some well deserved rep for his hard work!

    My solution and his code are attached, let me know if you have any questions, and I'll have the last problem graded and reviewed very soon.

  9. #9
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    And the easy problem, PJ...?

  10. #10
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Quote Originally Posted by PJYelton
    and I'll have the last problem graded and reviewed very soon.
    And that was on 03-25-2005....
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Sorry guys, I feel really bad considering this is a March contest and its April I took on this contest because my work wasn't giving me anything to code and I had lots of extra time, then mid march they suddenly slapped a huge project on me thats taken up all of my free time. But I am finishing with that today so tomorrow night I can guarantee I can finish this contest. Thanks for your patience!

  12. #12
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    Quote Originally Posted by PJYelton
    Sorry guys, I feel really bad considering this is a March contest and its April I took on this contest because my work wasn't giving me anything to code and I had lots of extra time, then mid march they suddenly slapped a huge project on me thats taken up all of my free time. But I am finishing with that today so tomorrow night I can guarantee I can finish this contest. Thanks for your patience!
    Understood. Thanks for the update.

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    All right, only a month late but the results for the easy problem are now in. This was a very tough call with three people turning in code that produced correct results every single time.

    First off, here is my solution to the problem. At first it seems like this problem will require some kind of nasty backtracing to recreate the necklace from scratch. Turns out theres a much easier solution. Since you know how many pearls the original necklace had, by simply retracing her exact steps as she plucked the gold pearls out you can easily tell where the gold pearls were. And if you know where they were, then you know all the rest must be white and viola you have your necklace. So simply start with a necklace consisting of (numWhite+numGold) pearls, keep counting to k and mark that pearl as gold. Continue around and around the necklace until there are no more gold pearls left making sure NOT to count pearls you've already marked since they are no longer on the string, and when done, mark the rest as white. Or even easier, make the entire necklace white to begin with and just change the marked ones to gold. Here is my code:
    Code:
    string neck(int numWhite, int numGold, int k)
    {
    	string s(numWhite+numGold, 'w'); // string is now all white
    
    	int p=-1;  // placeholder value, where we are in the necklace
    	int c=0;   //  our counter
    	int x=0;   //  number of golds we have placed so far
    
    	while (x<numGold)   // while we still have golds left
    	{
    		p++;   // increment placeholder
    		p%=(numGold+numWhite);   // circle to beginning
    		if (s[p]=='g')  // DON'T count this pearl if its gold
    			continue;
    		
    		c++;   // increase our count
    		if (c==k)  // if we've reached k, mark this pearl as gold
    		{
    			s[p]='g';
    			c=0;   // reset count
    			x++;
    		}
    
    	}
    
    	return s;
    }
    Everyone's code and my score are to follow in a couple of seconds.

  14. #14
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Here is Karthur's code:
    Code:
    class Karthur {
    	
    #include <stdio.h>;
    
    int test_main ( void )
    {
        originalNecklace(1,0,6); printf("should return \"w\"\n");
        originalNecklace(0,1,6); printf("should return \"g\"\n");
        originalNecklace(5,4,4); printf("should return \"wwggwwwgg\"\n");
        originalNecklace(4,3,1); printf("should return \"gggwwww\"\n");
        originalNecklace(0,7,25); printf("should return \"ggggggg\"\n");
        originalNecklace(9,13,11); printf("should return \"ggggwgwgwwggwggwwwwggg\"\n");
        originalNecklace(21,31,4);
        originalNecklace(333,667,23);
        originalNecklace(500,500,23);
        originalNecklace(500,500,22);
        originalNecklace(666,334,23);
        originalNecklace(23,29,101);
        printf("Completed.");
        return 0;
    }
    
    struct _bead {
        struct _bead* next;
        struct _bead* prev;
        int color;
    } BEAD;
    
    #define WHITE 0
    #define GOLD  1
    
    void originalNecklace ( int white, int gold, int jump )
    {
        BEAD* first;
        BEAD* added;
        BEAD* latest;
        int i = 0;
        int j = 0;
        int k = 0;
    
      // printf("originalNecklace(%d,%d,%d)\n",white,gold,jump);
      // if ((white < 1 && gold < 1) || jump < 1) return;
        
      try {
        for (; i < white ;i++) { // BUILD ALL-WHITE CHAIN
            added = (BEAD*)malloc(sizeof(BEAD);
    	if (!added) throw("Out of Memory");
            added->color = WHITE;
            if (i) {                   // TACK ONTO END
                latest->next = added;
                added->prev = latest;
            } else {                   // or PICK UP FIRST BEAD (WHITE)
                first = added;
                added->next = added;
            }
            latest = added;
        }
        if (white > 0) { // TIE ENDS TOGETHER
            latest->next = first;
            first->prev = latest;
        }
      } catch (Exception e) {
        printf("WHITE %s\n",e);
      }
    
      try {
    
        for (j = 0; j < gold ;j++) { // INSERT GOLD BEADS
            added = (BEAD*)malloc(sizeof(BEAD);
    	if (!added) throw("Out of Memory");
            added.color = GOLD;
            if (i+j >= 1) {                   // INSERT BEFORE CURRENT
                latest->next->prev = added;
                added->next = latest->next;
                latest->next = added;
                added->prev = latest;
            } else {                          // or PICK UP FIRST BEAD (GOLD)
                first = added;
                added->next = added;
            }
            latest = added;
            if (i) {
                for (k = 0; k < jump ;k++) {  // JUMP BACK TO NEXT INSERTION POINT
                    latest = latest->prev;
                }
            }
            if (white == 0) { // TIE ENDS TOGETHER
                latest->next = first;
                first->prev = latest;
            }
        }
      } catch (Exception e) {
        printf("GOLD %s\n",e);
      }
    
      try {
        first = latest->next;
        latest->next = null; // DISCONNECT CHAIN FOR SIMPLE TERMINATION
        for (latest=first; latest ;latest=latest->next)
            printf("%c",(latest->color == WHITE) ? 'W' : 'G');
        printf("\n");
      } catch (Exception e) {
        printf("PRINTING %s\n",e);
      }
    
      /*************** NOW TRY TO REMOVE THE GOLD ONES ***************/
      try {
        first->prev->next = first; // TIE ENDS BACK TOGETHER
        latest = first->prev;
        while (gold--) {
             for (int n = 0; n < k ;n++)         // COUNT TO NEXT BEAD
                  latest = latest->next;
             if (latest->color != GOLD) {        // MSG & QUIT ON ERROR
                 printf("** error **\n");
                 break;
             }
             latest->prev->next = latest->next;  // REMOVE GOLD BEAD
             latest->next->prev = latest->prev;
        }
        // Note: if all-gold, last one still remains as "first" and "latest"
        // latest = latest->next;
        // if (!white)
          //   latest = null;
        // first = latest;
      } catch (Exception e) {
        printf("CHECKING %s\n",e);
      }
      /**************************************************  *************/
    }
    
    };
    Unfortunately I couldn't get it to compile, even after I tried changing a few things and the logic of his code eluded me. Perhaps you can explain it to us Karthur?

  15. #15
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Here is Brain Cells code:
    Code:
    char * originalNecklace(int numWhite, int numGold, int k)
    {
    	int length = numWhite + numGold;
    	
    	char * str = new char[length+1];
    
    	for(int i=0; i<length; i++)
    		str[i] = 'w';
    
    	str[i] = '\0';
    
    	for(int step = k; numGold!=0; step+=k, numGold--)
    	{
    		while(step > length)
    			step -= length;
    			
    		if(str[step-1] == 'g')
    		{
    			numGold++; step++;
    		}
    		else
    			str[step-1] = 'g';
    
    
    	}
    
    	return str;
    }
    Instead of incrementing by one his loop increments by k everytime. Unfortunately the problem with this is that it makes it nearly impossible to "skip" gold pearls when looping back through the necklace. Anytime it runs out of gold pearls before looping and hitting a gold it produces correct results, but doesn't for any more than that.

    My score: 7/10 for semi-correct results, +1 snazzy point for realizing you can initialize the entire beginning string as white for a total of 8 points.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Contest Results - Snake Numbers
    By pianorain in forum Contests Board
    Replies: 4
    Last Post: 06-22-2006, 09:14 AM
  2. May Monthly Contest Results
    By PJYelton in forum Contests Board
    Replies: 28
    Last Post: 05-27-2005, 01:43 AM
  3. New Monthly Contest!
    By PJYelton in forum Contests Board
    Replies: 50
    Last Post: 03-22-2005, 08:27 PM
  4. Obfuscated Code Contest: The Results
    By Stack Overflow in forum Contests Board
    Replies: 29
    Last Post: 02-18-2005, 05:39 PM
  5. Results for *easy* contest:
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 07-27-2002, 11:35 AM