My first code contest

Programming challenges are fun! It’s one of those things that you get better with practice and suddenly you are addicted to it. That mental click that make twenty lines of codes shrink to four, finally seeing a O(log(n)) solution in a O(n2) approach, watching your friends struggle to solve that same problem…

My first fair set of exercises was during Data Structures for Engineering class by professor Imre Simon. Several years later, another list that gave a hard time was Joel’s proposed exercises for the Microsoft interview loop. After this list I realized that I was only at the tip of the iceberg.

So I decided to give it a try. You can easily find dozens of programming contest websites by searching “programming contest” and you can join a local Coding DOJO sessions for a fast ramp-up.

My first one was the Polish SPOJ website. I found it from one of RicBit’s tweets about the Traversing Grid shorten challenge. The goal here is to write the smallest source code. That’s right, it’s ranked by the number of characters at the submitted code. The time to run and memory usage are also considered, but being concise is what they want. The nice thing about SPOJs is that they compile your code online. Nice training sessions.

Give a look at https://www.spoj.pl/SHORTEN/problems/TR_GRID/.

My entry in C has 105 chars, but there is a contestant that reached 78 chars! Note that I’m comparing C language solutions… The PERL winner has only 41 bytes. See results here. I will describe the steps that I went through, but bear in mind that I’m a novice here and there are many tricks that are still to be discovered.

You may want to try at home first before continuing…

The algorithm

Don’t start by coding. Try to visualize the solution first. This TR_GRID problem could be wrongly solved by actually visiting each cell using four or five loops. The time to solve it would be proportional to the number of cells in the grid. Imagine a 1,000,000 x 1,000,000 grid… The problem statement says the dimension can be up to 10^9!

I preferred a heuristics approach to find the result as a function of the grid dimensions. Some people may picture it quickly, but I needed some drawings to understand it easier:

The algorithm as I saw it (given a grid with dimensions N x M) was:

if N <= M
___if N is odd
______result = R (right)
___else
______result = L (left)
___else (N > M)
______if M is odd
_________result = D (down)
______else
_________result = U (up)

Much simpler, right?

The first implementation

So my first naive implementation was:

#include<iostream>

using namespace std;

int main()
{
	int  T;
	int* N;
	int* M;

	cin >> T;
	N = new int[T];
	M = new int[T];

	for (int i = 0; i < T; ++i)
	{
		cin >> N[i] >> M[i];
	}

	for (int i = 0; i < T; ++i)
	{
		if (N[i] > M[i])
		{
			if (M[i] & 1)
				cout << "D" << endl;
			else
				cout << "U" << endl;
		}
		else
		{
			if (N[i] & 1)
				cout << "R" << endl;
			else
				cout << "L" << endl;
		}
	}

	delete[] N;
	delete[] M;

	return 0;
}

So we read the number of grids, allocate memory for all the dimensions, read them and then loop through the array to process each case. Ok, you may submit it just to check if you got the algorithm right, but a little optimization wouldn’t get it too much obfuscated.

The first optimization

Let’s start by compacting the obvious, using the ternary conditional operator and pre-allocating the vectors (it was given that T < 10001):

#include<iostream>

using namespace std;
int main()
{
	int T, N[10000], M[10000];

	cin >> T;

	for (int i = 0; i < T; ++i)
		cin >> N[i] >> M[i];
	for (int i = 0; i < T; ++i)
		cout << ((N[i] > M[i]) ? (M[i] & 1 ? "D" : "U") : (N[i] & 1 ? "R" : "L")) << endl;

	return 0;
}

Compressing it to suppress white spaces and line breaks, you would get:


#include <iostream>
using namespace std;int main(){int T,N[10000],M[10000];cin>>T;for(int i=0;i<T;++i)cin>>N[i]>>M[i];for(int i=0;i<T;++i)cout<<((N[i]>M[i])?(M[i]&1?"D":"U"):(N[i]&1?"R":"L"))<<endl;return 0;}

Hard to read, isn’t it? But still 207 characters… let’s keep moving.

Keep shrinking

Why was I using two loops? The SPOJ engine does not care about the moment I output the result. Let’s just print as we read the input. Merging them:

#include <iostream>
using namespace std;
int main()
{
	int T, N[10000], M[10000];

	cin >> T;

	for (int i = 0; i < T; ++i)
	{
		cin >> N[i] >> M[i];
		cout << ((N[i] > M[i]) ? (M[i] & 1 ? "D" : "U") : (N[i] & 1 ? "R" : "L")) << endl;
	}
	return 0;
}

Down to 189 chars. But then, as we does not need to read it all before writing, allocating arrays is now unnecessary.

#include <iostream>
using namespace std;
int main()
{
	int T, N, M;

	cin >> T;

	while(T--)
	{
		cin >> N >> M;
		cout << ((N > M) ? (M & 1 ? "D" : "U") : (N & 1 ? "R" : "L")) << endl;
	}
	return 0;
}

Great improvement… 147 chars. Let’s try to eliminate using namespace std, add std:: here and there, substitute std::cout and std::endl with a printf, use ASCII code to save a quote, remove some parenthesis…

#include <iostream>
int main()
{
	int T, N, M;

	std::cin>>T;

	while(T--)
	{
		std::cin>>N>>M;
		printf("%c\n", N > M ? M & 1 ? 68 : 85 : N & 1 ? 82 : 76);
	}
	return 0;
}

Weird, but now we are at 128 chars. What about wrapping the while in a for?

#include <iostream>
int main()
{
	int T, N, M;

	for(std::cin>>T; T--; printf("%c\n", N > M ? M & 1 ? 68 : 85 : N & 1 ? 82 : 76))
		std::cin>>N>>M;

	return 0;
}

124 chars now… All that trouble for just only 4 chars. Can we twist it a little bit more? Let’s index a static text:

#include <iostream>
int main()
{
	int T, N, M;

	for(std::cin>>T; T--; printf("%c\n", "UDLR"[N > M ? M & 1 : 2 + (N & 1)]))
		std::cin>>N>>M;

	return 0;
}

Nope, just got the same 124 chars. Wait, what is that #include <iostream> there? Let’s leave C++ and move to C. In this case, GCC will also allow us to declare main() as void.

void main()
{
	int T, N, M;

	for(scanf("%d",&T); T--; printf("%c\n", "UDLR"[N > M ? M & 1 : 2 + (N & 1)]))
		scanf("%d%d",&N,&M);

}

The final submitted code was:

void main(){int T,N,M;for(scanf("%d",&T);T--;printf("%c\n","UDLR"[N>M?M&1:2+(N&1)]))scanf("%d%d",&N,&M);}

A fellow programmer tipped me to use #define‘s, but I went back to 113 chars with this approach:


#define S(x) scanf("%d",&x)
void main(){int T,N,M;for(S(T);T--;printf("%c\n","UDLR"[N>M?M&1:2+(N&1)]))S(N),S(M);}

Unless there are some pre-configured defines that I’m unaware of…

According to this rules page, we don’t need a new line character to separate outputs. A single space will do. So my code now has 104 chars!

void main(){int T,N,M;for(scanf("%d",&T);T--;printf("%c ","UDLR"[N>M?M&1:2+(N&1)]))scanf("%d%d",&N,&M);}

A short while after my post, Raphael Amorim, another contestant entered a 99 chars solutions! I cannot see his solution, but I bet he also figured out that “void” is not necessary. Good catch! My new submission:

main(){int T,N,M;for(scanf("%d",&T);T--;printf("%c ","UDLR"[N>M?M&1:2+(N&1)]))scanf("%d%d",&N,&M);}

The same contestant, Raphael Amorim, gave me a tip about the variable declarations. Believe or not, the code main() { int X,Y,Z; } is equal to main(X,Y,Z) { }!!! I could not find much info about that, only some uses on obfuscated coding. So the new code became:

main(T,N,M){for(scanf("%d",&T);T--;printf("%c ","UDLR"[N>M?M&1:2+(N&1)]))scanf("%d%d",&N,&M);}

That 94 chars now… My next effort was to get rid of the T variable to control the loop. So I tried to use the return value from scanf():

main(N,M)
{
    for(
        scanf("%d",&N);
        scanf("%d%d",&N,&M);
        printf("%c ","UDLR"[N>M?M&1:2+(N&1)])
    );
}

But it failed to detect EOF and it never stopped. I forgot the EOF returned by scanf() is not zero, but a negative number. This time, the problem-proposer, Kokosek, gave me the tip to use the tilde unary operator.

Great change. This resulted 90 chars:

main(N,M){for(scanf("%d",&N);~scanf("%d%d",&N,&M);printf("%c ","UDLR"[N>M?M&1:2+(N&1)]));}

One thing that always bothered me is the first scanf(). I don’t really need that value, I only need to read the first input.
So I replaced it for the most infamous gets() to shorten it even more:

main(N,M)
{
    for(
        gets(&N);
        ~scanf("%d%d",&N,&M);
        printf("%c ","UDLR"[N>M?M&1:2+(N&1)])
    );
}

Which resulted in:

main(N,M){for(gets(&N);~scanf("%d%d",&N,&M);printf("%c ","UDLR"[N>M?M&1:2+(N&1)]));}

Which has 84 chars only! My best shot so far, but still 6 to go…

This entry was posted in C++, English. Bookmark the permalink.

7 Responses to My first code contest

  1. Pingback: Tweets that mention My first code contest | { Daniel Landi; } -- Topsy.com

  2. kokosek says:

    challenger is my account – I shorten users’ codes and submit them so that them still feel rivalry. In this case I can tell You that:
    -declaration – 3 characters (You – 10 chars)
    -reading input – 26 chars (You – 36 chars)
    -printing answer – 33 chars (You – 37 chars)
    Good luck! :-)

  3. kokosek says:

    You can still shorten the declaration by 2 characters, though. ;-)

  4. kokosek says:

    Congratulations. :-)
    You can shorten reading by 2 chars and printing by 4 chars. ;-)
    Good luck. ;-]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>