Graphical Editor – Programming Challenges
In my previous post, I wrote about the website includes programming problems. I aimed to emphasize the importance of careful problem text reading.
After that post, I should be more careful. However, I spent last 3 hours to find out what was wrong with my solution. I had checked every line again and again. I even implemented same functionality in different ways. I had submitted 30 times and received the 'wrong answer' every time.
I found the problem only ten minutes ago (BTW, time is about 2.25 am). Here is the problem that took 3 hours...
The problem text says "Create a new M x N image with all pixels initially colored white (O)". Yes, color white is capital letter O, not 0 (Zero). My last 3 hours and 30 submits included 0 (zero) instead O. 
Programming Challenges
I discovered a new website while I was reading 'The Algorithm Design Manual' from Steve Skiena (I have read only one chapter so far. However, I can say it is worth to read all).
On that website, You can find hundreds of problems that are like the ones used during programming contests. You can submit your solutions in C/C++, Java and Pascal.
This is really interesting opportunity to the developers who haven't got many challenging tasks at work and to who like to solve puzzles. I am some more lucky, my company develops real time billing systems on Unix/Linux. Therefore, I do much more interesting than reading/writing database. However, even in my company, the most challenging parts are already developed and they are put to the libraries. Therefore, I don't face challenging problems every day. I mostly don't do more than calling library functions in order or fixing cheesy bugs. Fortunately there are times that I am asked to develop tough projects.
I have solved only two of the problems so far. I received 'wrong answer' for one of them due to the '\n' character at the end of the file. The code printing one less '\n' character is accepted. The results are checked by a software and every byte of the output is important. If you receive 'wrong answer' as a result and you are sure about your solution, you should read the problem text carefully for the output format.
The Algorithm Design Manual
Peterson’s n-Process Protocol
Peterson's Solution is a classic software based solution to the critical-section problem. Peterson's original formulations works for 2 processes. However, it is possible to implement it for more than 2 processes.
The following code works for 2 processes and it can be found easily on the Internet.
#define TRUE 1
int turn;
int interested[2];
void enterRegion(int process)
{
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (interested[other] == TRUE && turn == process)
;
}
void leaveRegion(int process)
{
interested[process] = FALSE;
}
Unfortunately, there aren't many resources about n-Process Peterson solution. I think one of the good explanation can be found in "Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)".
I just like to show the following implementation of Peterson's n-Process Protocol.
#define N 10 /* First process is indicated with 1, not 0 */
int turn[N];
int stage[N + 1];
void enterRegion(int process)
{
int i, j;
for (i = 1; i <= N - 1; i++) {
stage[process] = i;
turn[i] = process;
for (j = 1; j <= N; j++) {
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process)
;
}
}
}
void leaveRegion(int process)
{
stage[process] = FALSE;
}
Note: There are N processes from 1 to N. Therefore we need a turn array with size N - 1 and we need a stage array with size N. However, I declared the turn and the stage arrays with sizes N and N + 1 respectively. It is just because I like to keep the code clean. I don't want to subtract 1 like turn[i - 1]. I ignore the first elements -turn[0] and stage[0]- and never access them.
