Results of March Monthly Contest

This is a discussion on Results of March Monthly Contest within the Contests Board forums, part of the Community Boards category; Here is Micko's code: Code: class Micko { enum { w = 0, g }; struct element { int num; ...

  1. #16
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Here is Micko's code:
    Code:
    class Micko  
    {
    	enum
    	{
    		w = 0,
    		g
    	};
    	struct element
    	{
    		int num;
    		unsigned int check :1;
    	};
    	 public:
          string originalNecklace(int, int, int);
    	  int find_first(element*, int, int);
    };
    
    string Micko::originalNecklace(int W, int G, int K)
    {
    	int i;
    	element* e = new element[W + G];
    
    	for (i = 0; i < W; i++)
    	{
    		e[i].num = w;
    		e[i].check = 0; 
    	}
    	for (i = W; i < W + G; i++)
    	{
    		e[i].num = g;
    		e[i].check = 0; 
    	}
    	/* Now initialization is finished*/
    
    	/*************************************/
    	
    	/* Now starting hard work*/
    
    	int start = 0;
    	int end;
    	int end_loop = 0;
    	while (end_loop != G)
    	{
    		i = start;
    		end = start + K;
    
    		while(i < end)
    		{
    			if (i == W + G)
    			{
    				i %= (W + G);
    				end -= (W + G);
    			}
    			
    			if (e[i].check == 1)
    				end++;
    			
    			i++;
    		}
    		start = i;
    
    		i--;
    
    		if ((e[i].num == g) && (e[i].check == 0))
    		{
    			e[i].check = 1;
    			end_loop++;
    		}
    		else
    		{
    		int index = find_first(e, i + 1, W + G -1);
    		swap(e[i].num, e[index].num);
    		e[i].check = 1;
    		end_loop++;
    		}
    
    	}
    	string s;
    	for (i = 0; i < W + G; i++)
    	{
    		if(e[i].num == g)
    			s += "g";
    		else
    			s +="w";
    	}
    
    	delete [] e;
    	return s;
    }
    
    int Micko::find_first(Micko::element* e, int l, int r)
    {
    	for (int m = l; m <= r; m++)
    	{
    		if ((e[m].num == g) && (e[m].check == 0))
    			return m;
    	}
    	return 0;
    }
    Excellent job as this produces the correct result for every test case I tried. I admit it took awhile to understand the logic behind how it works but essentially it does more or less exactly what my code does just in a different manner. It starts with a full string of white and gold pearls, and as it loops through it swaps the first 'k' white pearl with the first unmoved gold pearl.

    My score: 10 points for correct answers + 1 snazzy point for solving in a unique way for a grand total of 11 points.

  2. #17
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Here are both Lithorian's and JaWiB's code, included together since they essentially used the exact same algorithm.

    JaWib:
    Code:
    class JaWiB
    {
        public:
            std::string originalNecklace(int numwhite, int numgold, int k)
            {
              int total=numwhite+numgold;
              std::string ret;
              ret.reserve(total); //reserve space for string
              ret.assign(total,'w'); //fill string with w's
              int h=1; //used to see if gold pearl needs to be added
              for (int i=0,j=0;i<numgold;h++)
              {
                if (ret[j]=='g') //hit a gold pearl
                {
                  --h; 
                  if (++j==total) //skip this pearl
                   j=0;
                  continue;
                }  
                if(h%k) //add a gold every k times; this is not a k time...
                {  
                  ret[j]='w';
                }
                else
                {
                  ret[j]='g';
                  ++i; //increment gold pearl counter
                }
                
                if (++j==total) //move on to next pearl, is it highest index?
                 j=0; //if so, go back to first pearl
              }
            
              return ret;   
            }
    };
    Lithorien:
    Code:
    class Lithorien
    {
    	public:
    		std::string originalNecklace(int numWhite, int numGold, int k)
    		{
    			char *tArry = new char[numWhite + numGold]; // Dynamically allocate the char array.
    			
    			// Initalize every array element to NULL.
    			
    			for (int q = 0; q <= (numWhite + numGold); q++)
    			{
    				tArry[q] = '\0';
    			}
    			
    			// Algorithm.
    			
    			int x = 1, z = 0; // Counter for the inner for() loop, 'g' counter.
    			
    			if (numGold > 0)
    			{
    				while (z < numGold) // While there aren't enough 'g's..
    				{
    					for (int y = 0; y < (numWhite + numGold); y++) // Go through the array..
    					{
    						if ((x == k) && (tArry[y] != 'g') && (z < numGold)) // If x is the next k, and the array ISN'T on a 'g' already..
    						{
    							tArry[y] = 'g'; // Make the array element g.
    							x = 1; // Make our 'counter' move back to 1.
    							z++; // Increment our 'g' counter.
    						}
    						
    						else if (tArry[y] != 'g') // Assume w if not on a 'g' currently.
    						{
    							tArry[y] = 'w';
    							x++; // Increment our x.
    						}
    						
    						// If the counter is on a g already, there's no need to do anything. So we skip it, and we don't update x. This lets us keep a constant 'k' without having to shift arrays.
    					}
    				}
    			}
    			
    			else // If all whites are inputted, we need to handle that. Otherwise the program'd hang.
    			{
    				for (int r = 0; r < numWhite; r++)
    				{
    					tArry[r] = 'w';
    				}
    			}
    			
    			// Return a string.
    			
    			std::string s(tArry); // Make our string the char array. This is why we initalized to NULL - It ensures that this string will be null terminated. If we didn't, originalNecklace(9, 13, 11) would output garbage characters.
    			return(s);
    		}
    };
    Both produced correct results for every test case and more or less used the same algorithm I described above with only minor modifications. Both I give 10 points for correct solution, and + 2 snazzy points for nice concise algorithm. This was a tough call, but if we need a winner I'll award an extra .5 points to JaWib since his algorithm automatically handles the special case where there are no gold pearls.

  3. #18
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    So the final results for the easy problem are:

    JaWib: 12.5 points
    Lithorien: 12 points
    Micko: 11 points
    Brain Cell: 8 points

    Congratulations JaWib! Everybody give this man some well deserved rep!

    I hope everybody had fun doing this, even if the results were a little late. I plan to do another contest beginning of May with some minor tweaks, most notably an easier problem set. There will be a question easier than the first one this time, a question the same difficulty as the easy one this time, and one a little more difficult. Thanks for participating!

  4. #19
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Congratulations JaWib. Good job!
    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

  5. #20
    Let's do some coding! Welshy's Avatar
    Join Date
    Mar 2005
    Location
    Staffordshire University, UK
    Posts
    168
    Well done guys, congrats JaWib

    Hey PJYelton, are you making more of these contests? ill have to have a go at the next one

  6. #21
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    Congratulations JaWib.

  7. #22
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Looking forward to the next context. Have you any ideas as to what it is going to be about and when you are going to unveil it. Or are you still busy and stuff?

  8. #23
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Read the end of my last post, it gives information about the next contest.

  9. #24
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    oh ok missed that.

Page 2 of 2 FirstFirst 12
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, 10:14 AM
  2. May Monthly Contest Results
    By PJYelton in forum Contests Board
    Replies: 28
    Last Post: 05-27-2005, 02: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, 12:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21