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.
Kernighan’s Law
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it."
Tower of Hanoi
The tower of Hanoi is a mathematical game invented by French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs.
The objective is to transfer entire tower A to the peg B, moving only one disk at a time and never moving a larger one onto a smaller one.
The algorithm to transfer n disks from A to B in general: We first transfer n - 1 smallest disks to peg C, then move the largest one to the peg B and finally transfer the n - 1 smallest back onto largest (peg B).
The number of necessary moves to transfer n disks can be found by
Tn = 2^n - 1
Here is the sample solution in C:
void hanoi(int n_disks, char source, char destination, char temp)
{
static n_move = 0;
if (n_disks == 1) {
printf("%d - Move disk 1 from %c to %cn", ++n_move, source, destination);
} else {
hanoi(n_disks - 1, source, temp, destination);
printf("%d - Move disk %d from %c to %cn", ++n_move, n_disks, source, destination);
hanoi(n_disks -1, temp, destination, source);
}
}
int main(int argc, char *argv)
{
int n_disk = 8;
char source = 'A';
char destination = 'B';
char temp = 'C';
hanoi(n_disk, source, destination, temp);
return 0;
}