Programming Challenges by Steven Skiena ! A must read ! :)

--PC Heaven

Valve Corporation is an American video game development and digital distribution company based in Bellevue, Washington, United States. Must have heard of games like Counter Strike, Left for Dead, Half Life etc.,right ? Valve has a great 3D game engine titled Source, authored entirely in C++. It is a tool developers use to build games. Read more here at Wikipedia. 

All permutations of a given string.

Finding permutations of a given string is something everyone should know how to do, to tackle various other challenging problems.

Language : C

# include <stdio.h>

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

/* Driver program to test above functions */
int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

Output:


ABC
ACB
BAC
BCA
CBA
CAB

Algorithm Paradigm: Backtracking.

N.B. : not an original code.

Tower of Hanoi using numbers

So, here I come up with a simple problem for you: Tower of Hanoi using numbers.

You have a predefined 1-D array, say A, of size n having numbers from 1 to n occupying positions 0 to n-1. Position 0 is the top of the array.
You have two other 2-D empty arrays, say B and C.
Now, what you have to do:
You have to empty the array A and transfer its elements to the array C such that at the end C has same configuration -> 1 to n, using some VALID STEPS.

Characteristics of a valid step is :
>Removing an number from the top of an array and placing it on the top of another array.
>You have to ensure that you are placing a smaller number on the top of a higher number (i.e. after each step each array should be in ascending order from top to bottom).
Here is a animation of the problem: http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif
You must use only 3 arrays as described above.
Output :
The problem takes (2^n)-1 steps. You have print each step in the following format:
7 is moved from A to C.
6 is moved from B to A.
......
......

Thanks.