Results of March Monthly Contest

[PJYelton]

Here is Micko's 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.

[PJYelton]

Here are both Lithorian's and JaWiB's code, included together since they essentially used the exact same algorithm.

JaWib:

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:

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.

[PJYelton]

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!

[Micko]

Congratulations JaWib. Good job!

[Welshy]

Well done guys, congrats JaWib

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

[Lithorien]

Congratulations JaWib.

[treenef]

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?

[PJYelton]

Read the end of my last post, it gives information about the next contest.

[treenef]

oh ok missed that.