A look at Code Jam 2018

 Published on 2018-06-01

I enjoy participating in programming competitions. That is not true for everyone though. A lot of people seem to hate them, because competitions (may) take a lot of time, are hard at first, and appear unrelated to the job we do as software developers. I disagree. Programming competitions are a great way to practice and test your knowledge in data structures and algorithms – and those concepts are key to being a good developer. For example, using lists where we need hash maps (dictionaries) leads to slow applications that visit all stored elements even though we can jump to the required one much quicker (think of databases with indexes).

Also, coding when you have a clock ticking is pretty challenging (because most competitions in informatics last for a couple of hours), so competing really improves your ability to write code faster; and with less issues and bugs.

I’ll begin with a look at the Qualification Round of Google Code Jam 2018. A person needed to earn 25 points to advance from this round, and I’ll show you how (little) knowledge was required to do just that (we’ll actually present 3 tasks here, worth 68 points). Hopefully, this will motivate you to try participating in a programming competition. There are a lot of them online – both for beginners, and experienced competitors. For example, Codeforces groups tasks into 3 divisions (Div 1, Div 2 and Div 3), so (if you’re new) just start by participating in Division 3.

Trouble sort

In this problem, we’re given a “broken” sorting algorithm, and we need to read an array/list of integers. If the algorithm would sort the array correctly, we are required to print “OK”. Otherwise, we need to print the index (position) of the first sorting error. The “Trouble” sort algorithm looks like this:

TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

Please, notice how this is very similar to Bubble sort (though, it wasn't necessary to remember that algorithm). However, compared to the real sorting algorithm, with Trouble sort we're comparing and swapping positions that are at a distance of 2 (instead of swapping adjacent elements). Because we always swap positions which are at a distance of 2, we will be looking at a group of elements on odd positions, and a group of elements on even positions (and never between those groups). For example, if we had the starting list “3 100 2 200 1”, the trouble sort algorithm will end up with “1 100 2 200 3”, where the elements at the even positions (0, 2, 4) are sorted correctly between them (1, 2, 3), and the elements at the odd positions (1, 3) are sorted correctly between them (100, 200). But, the complete array/list is clearly not sorted correctly – it’s equal to “1 100 2 200 3” instead of “1 2 3 100 200”.

Of course, during the competition, you are able to experiment with this algorithm and get to those conclusions yourself. In this post, I’m just (quickly) trying to explain that no special knowledge or training is needed to tackle some tasks at Google Code Jam.

So, to solve this task, we can separately sort the elements on the even positions, and those on the odd positions (because “Trouble sort” sorts those two parts correctly, as it’s basically equal to Bubble sort), and then we can just find the first position where we have a problem between the even and odd parts. It’s also possible that such a position doesn’t exist (for example, in “1 2”), so in that case, we can just output “OK”. Here is the implementation of the solution in C++:

void solve()
{
	int N;
	cin >> N;

	vector<int> odd, even;
	for (int i=0; i<N; i++)
	{
		int value;
		cin >> value;

		if (i%2 == 1)
			odd.push_back(value);
		else
			even.push_back(value);
	}

	sort(odd.begin(), odd.end());
	sort(even.begin(), even.end());

	int firstError = -1;
	for (int i=0; i+1<N; i++)
	{
		//half of the elements are in "odd" and half are in "even"
		int current = (i%2 == 1 ? odd[i/2] : even[i/2]);   //i'th element
		int next = ((i+1)%2 == 1 ? odd[(i+1)/2] : even[(i+1)/2]); //(i+1)'th element

		if (current > next)
		{
			//we found the first error
			firstError = i;
			break;
		}
	}

	if (firstError == -1)
		cout << "OK" << endl;
	else
		cout << firstError << endl;
}

Saving the Universe

The second task on the Qualification Round was called “Saving the Universe Again”, and it featured a bad alien robot programmed to execute a series of instructions (that we want to hack), and a shield that can withstand a certain damage. The instructions on the robot are ‘C’ for charge, and ‘S’ for shoot, where C doubles the strength of the following shots, and S does the actual damage. The only way to hack (without the robot noticing) is to swap adjacent instructions. I won’t paste the entire text here (you can find it on Google if you want to). Let’s just summarize that we need to write a program that will calculate the smallest possible number of hacks that are needed in order to ensure that the robot does no more than D total damage to the shield.

For example, the series of instructions “SCCS” will do a total damage of 5, because we have an “S” instruction on the start (doing damage 1), then the strength doubles twice (to 2, and then 4), and then there is another shot with that strength (doing damage 4). However, if we reorder the instructions by swapping the third and fourth instruction (“SCCS” to “SCSC”), and then by swapping the second and third instruction (“SCSC” to “SSCC”), then the total damage that the robot will make is 2 (1+1, i.e. two shots with strength 1). Here, we made two hacks (swaps).

This task is actually not that difficult (the biggest difficulty is probably understanding what you need to program). However, once you understand the problem, the solution is actually quite easy. You should just notice that the only way to lower the damage with one hack (swap), is to swap two adjacent elements where the left one is ‘C’ (charge), and the right one is ‘S’ (shoot), because then that particular shot will make half the damage that it used to make (because we moved the ‘C’ charge instruction that doubles the strength of a shot to the right). So, if the series contains “CS”, we should replace it with “SC”. However, we need to make the least number of hacks, so which appearances of “CS” should we replace first? The best approach is to replace the latest appearances first, because those ‘S’ shots are the most powerful (doing the most damage), given the count of ‘C’ (charge) instructions that appear before them. For example, in “CSCS”, the first shot does 2 damage, while the last shot does 4 damage (it has two charge instructions before it). If the shield strength is equal to D=5, we can make just one hack (“CSCS” to “CSSC”), because the robot would then make damage equal to 4 (2+2), which the shield can withstand.

These ideas lead to the following greedy algorithm: while the damage made by the series of instructions is bigger than D, find the latest appearance of “CS” and replace it with “SC”. That’s it. If we somehow make all possible replacements and the shield still can’t withstand the damage, we will print “IMPOSSIBLE” (for example, imagine D=1, and the series of instructions having two ‘S’ shots).

Here is the solution (in C++):

int damage(string instructions)
{
	int totalDamage = 0, strength = 1;
	for (char op : instructions)
	{
		switch (op)
		{
			case 'C': strength *= 2; continue;
			case 'S': totalDamage += strength;
		}
	}

	return totalDamage;
}

void solve()
{
	int D;
	string instructions;
	cin >> D >> instructions;

	int hacksCount = 0;
	while (damage(instructions) > D && instructions.rfind("CS") != string::npos)
	{
		hacksCount++;
		int position = instructions.rfind("CS");
		instructions = instructions.replace(position, 2, "SC");
	}

	if (damage(instructions) > D) 
	{
		cout << "IMPOSSIBLE" << endl;
	} else 
	{
		cout << hacksCount << endl;
	}
}

Gopher

The last task that we’re going to see in this blog post is interactive. This means that our program needs to communicate with another one (instead of reading all the data at the start). The point of the task is to draw a rectangle, by making sure you completely fill all the area inside the rectangle (see image 1), and by making sure you don’t draw anything outside the rectangle (see image 2).

So, we have a rectangular grid, and we need to fully draw a rectangle inside it. We need to draw a 20x10 rectangle in (at most) 1000 operations, where the only allowed operation is giving an order to a bot to draw on a certain location inside the grid. In a normal world, we can do this with 200 operations (we just need to draw on 20x10 positions inside the grid to create the 20x10 rectangle). However, the complication in this task is that the bot (once we tell him which field to populate/fill in the grid), will either populate that field, or will populate (at random) one of the 8 fields immediately around it (top-left, top, top-right, left, bottom-left, bottom, bottom-right, or right).

So, since we have randomness here, how do we make sure we fill in the entire rectangle, but don’t get to fill anything outside it? This is actually pretty simple: we should just make sure that we don’t ask the bot to draw anything on the top or bottom row of the rectangle, or on the leftmost or rightmost column. That’s because we don’t want the bot to fill anything outside the rectangle, but if we ask it to fill something on the topmost row (for example), it may (due to the randomness) fill something above it, which we clearly don’t like. However, if we only ask the bot to fill things inside the rectangle, excluding the topmost, leftmost, bottommost and rightmost row/column, we will still fill/populate all 20x10 fields – for example, the topmost row of the rectangle will be filled because we’ll ask the bot to fill/populate positions in the second row, and because of the randomness, that will cause the top row to be eventually filled. Imagine we ask the bot to populate the field at position (2, 2) ten times. The bot will (at random) fill either that field, or the one above it, the one below it, etc. Because we ask it to populate a field 10 times, it will likely fill something on the top row on one of those tries (if not, we'll try again until it does).

This is the basic idea that we should implement to solve this task. We’re going to repeat the following procedure until the entire 20x10 rectangle is filled: choose a position that has the highest number of unfilled neighboring cells/fields (including the cell itself), and ask the bot to fill it. That’s it. We should just make sure that we don’t choose a position on the top, left, right or bottom row/column.

void solve()
{
	int A;
	cin >> A; //how big of a rectangle should we draw? (can be 20 or 200)

	int rows = (A == 20 ? 5 : 20);    //rows=5, cols=4 if A=20 (5*4=20)
	int cols = (A == 20 ? 4 : 10);    //rows=20, cols=10 if A=200 (20*10=200)

	bool grid[100][100];
	memset(grid, false, sizeof(grid));

	while (true)
	{
		int chosen_row = 2, chosen_col = 2;
		int chosen_position_unfilled = count_unfilled(grid, chosen_row, chosen_col);

		//we don't fill the edges
		//row=1 or row=rows
		//col=1 or col=cols
		for (int row=2; row < rows; row++)
			for (int col=2; col < cols; col++)
			{
				int unfilled_neighbours = count_unfilled(grid, row, col);
				if (unfilled_neighbours > chosen_position_unfilled)
				{
					chosen_row = row;
					chosen_col = col;

					chosen_position_unfilled = unfilled_neighbours;
				}
			}

		//tell the bot where to draw
		cout << chosen_row << " " << chosen_col << endl;

		//read the position that the bot actually filled
		int actual_filled_row, actual_filled_col;
		cin >> actual_filled_row >> actual_filled_col;
		grid[actual_filled_row][actual_filled_col] = true;

		if (actual_filled_row == 0 && actual_filled_col == 0)
		{
			//the task description says that once the rectangle has
			//been drawn, we're going to get the message "0 0", so we're done
			break;
		}
	}
}


int count_unfilled(bool grid[100][100], int row, int col)
{
	int unfilled = 0;
	if (grid[row][col] == false) unfilled++;    //cell
	if (grid[row][col-1] == false) unfilled++;  //left
	if (grid[row][col+1] == false) unfilled++;  //right

	if (grid[row-1][col-1] == false) unfilled++;  //top-left
	if (grid[row-1][col] == false) unfilled++;    //top
	if (grid[row-1][col+1] == false) unfilled++;  //top-right

	if (grid[row+1][col-1] == false) unfilled++;  //bottom-left
	if (grid[row+1][col] == false) unfilled++;    //bottom
	if (grid[row+1][col+1] == false) unfilled++;  //bottom-right

	return unfilled;
}

I tried to present the tasks in as little words as possible. For example, before presenting the solution, I never mentioned that we should break when the bot responds with “0 0”. Of course, in the actual task description on Google Code Jam, that fact is clearly written and presented with examples.

Final thoughts

Programming competitions are fun – at least for me. They make me think about the simplest way to implement something, how to code without introducing bugs, and more. Of course, the tasks I presented above didn't require a lot of knowledge in data structures or algorithms. As you progress through the Code Jam rounds (Qualification round, Round 1, Round 2, etc), you will get harder and harder tasks, including some where it’s actually important to choose a correct data structure or algorithm. During the Qualification round (because it’s introductory, and it lasts for 24+ hours), the only thing that mattered is to use some logic and play with the system (which actually tells you if your solution earned points or not).

Opinions

Similar posts

Cool apps