A Quine Program in C

A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output. 

The program given below is a quine program in C.

char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

Figure below shows the output of the program

Click here to download the C program.

Backtracking Algorithms : Explaining Cindy's Puzzle with a C++ Program

Classic text books in Algorithm Analysis like Cormen, Leiserson and Rivest, Sedgewick and Flajolet, etc. often neglect or give least preference to the algorithm development technique called backtracking. Even those textbooks discussing backtracking only discuss few selected problems. A classic problem discussed along with backtracking is the eight queens puzzle. Often this problem is unappreciated by persons not well versed in the game of Chess. Here I am trying to explain backtracking using a very simple game often called ‘Cindy’s puzzle’.

The game Cindy’s puzzle involves n Red marbles, n Green marbles and a playing board which consists simply of a line of 2n+1 spaces to put the marbles in. Start with the Red marbles all at one end (say, the left), the Green marbles all at the other end, and a free space in between. For n=2, the initial arrangement on the board is shown below.

To denote this position we use the notation |R|R| _ |G|G| is used.

The aim of the puzzle is to reverse the positions of the marbles as shown below.

So the solution for the puzzle can be denoted as |G|G| _ |R|R|.

The movements of the marbles are restricted by the following rules.

The Red marbles can only move to the right, and the Green marbles can only move to the left (no backing up). At each move, a marble can either

• Move one space ahead, if that space is clear, or
• Jump ahead over exactly one marble of the opposite color, if the space just beyond that marble is clear.

I am trying to develop a backtracking algorithm to solve this puzzle. The algorithm will be able to produce one particular solution to this puzzle. For example for n=2, the solution steps are given below.

           |R|R| _ |G|G|

        |R|R|G| _ |G|

        |R| _ |G|R|G|

        | _ |R|G|R|G|

        |G|R| _ |R|G|

        |G|R|G|R| _ |

        |G|R|G| _ |R|

        |G| _ |G|R|R|

        |G|G| _ |R|R|

Of course this is an ideal solution where no backtracking is used but in the proposed backtracking algorithm, if non winnable situation arises backtracking is applied to go back to a previous state and continue the search for a solution. 

 Click here to download the C++ Program.

C Program to Find the Endianness of a Machine

Endianness is the ordering or sequencing of bytes of a word of digital data in computer memory storage or during transmission. Words may be represented in big-endian orlittle-endian manner. Big-endian systems store the most-significant byte of a word at the smallest memory address and the least significant byte at the largest. Little-endian system, in contrast, stores the least-significant byte at the smallest address.

In this post I have given a C program to find out the Endianness of your system. The program is given below.

int main()

{

    int x = 1;

    if(*(char *)&x == 1)

    {

        printf("little-endian\n");

    }

    else

    {

        printf("big-endian\n");

    }

    return 0;

}

The program finds the Endianness by using the size of integer variables and a character variables. The integer variable holds the value 1. Then this integer variable is cast into a character and if the value of this character  is 1 you have a little-endian machine. If the character    is 0 then you have a big-endian machine. What is the working principle of this program? When you cast an integer to char the lowest addressed byte of the integer is used a char variable. If this lowest addressed byte contains the value 1 then the machine is little-endian, otherwise it is a big-endian machine. Why so? The integer 1 is represented as 00000000 00000000 00000000 00000001 in a 4 byte int. When you cast this int variable as a char the lowest address contains 00000001 in little-endian and 00000000 in big-endian. Hence if the value of the character variable is 1 you have a little-endian system and if the value of the character variable is 0 you have a big-endian system.

Click here to download the C program.

Operator Overloading in C++ : PART 2 ([ ] Operator)

  Array subscript operator [ ] used for array indexing can also be overloaded in C++. In this post I have added a program in which the array subscript operator [ ] is overloaded. The program illustrates an overloaded array subscript operator.

The program also offers a solution to the C++ puzzle question given below.

Floating Point Number in Array Subscript

Write a C++ program in which the following statement compiles without an error.

cout << a[0.123];

The difficulty in solving this puzzle arises from the fact that array subscript should be an integer.  

If you pass a float value to a normal array subscript you will get the following error "Invalid type for array subscript". 

One possible solution is to overload the array subscript operator.

Click here to download the C++ program solving the puzzle.

There might be some other solutions to this puzzle. If you know any other solution please share them here. 

   

Operator Overloading in C++ : PART 1 (++ Operator)

 I am now teaching under graduate students C++ programming. I thought I will share the programs I have prepared so that it benefits everyone.

Overloading ++ Operator

In this post I have added sample programs overloading the ++ Operator. In C++ we have preincrement and postincrement operators. For example ++a is preincrement whereas a++ is postincrement. So in order to handle these two situations there should be two versions of the operator++( ) function. The two versions are shown below. 

    void operator++(int y);  // for postincrement

   // The call a++; will invoke this version

   // The call a++; is same as the call a.operator++();
   

   void operator++( );        // for preincrement

   // The call ++a; will invoke this version

   // The call ++a; is same as the call a.operator++(0);

Click here to download the C++ program. 

Overloading ++ Operator with Friend Function

In C++ we can overload the ++ operator by using friend function.  Here also we need two versions to manage the preincrement and postincrement versions of the ++ operator. The two versions are given below.

   void operator++(A, int);  // for postincrement

   // The name of the Class is A

   // The call a++; will invoke this version

   // The call a++; is same as the call operator++(a);
   

   void operator++(A);        // for preincrement
   //The name of the class is A 

   // The call ++a; will invoke this version

   // The call ++a; is same as the call operator++(a,0);

Click here to download the C++ program.