Anagram program implentation

#include 
using namespace std;

#include "anaword.h"

static const int ALPH_SIZE = 26;

Anaword::Anaword(const string & word)
    : myWord(word),
      myCounts(ALPH_SIZE,0)
// postcondition: constructed    
{
    normalize();
}

Anaword::Anaword()
    : myWord(""),
      myCounts(ALPH_SIZE,0)
{
    
}

void Anaword::normalize()
// postcondition: myCounts represents the letter signture of myWord
{
    
}

string Anaword::toString() const
// postcondition: return "bagel" or "gable", regular form of string
{
    return myWord;
}

ostream & operator << (ostream & out, const Anaword & a)
// postcondition: a printed t stream out, out returned    
{
    out << a.toString();
    return out;
}

bool Anaword::equal(const Anaword & rhs) const
// postcondition: returns true if and only if *this == rhs
//                canonical/normalized form of word used for comparisons    
{
    return false;
}

bool operator == (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs == rhs
{
    return lhs.equal(rhs);
}

bool operator != (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs != rhs
{
    return ! lhs.equal(rhs);
}


bool Anaword::less(const Anaword & rhs) const
// postcondition: returns true if and only if *this < rhs
//                canonical/normalized form of word used for comparison    
{
    return false;
}

bool operator <  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this < rhs    
{
    return lhs.less(rhs);
}

bool operator <=  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this <= rhs
{
    return ! rhs.less(lhs);
}

Anagram class

#ifndef _ANAWORD_H
#define _ANAWORD_H

#include 
#include 
using namespace std;
#include "tvector.h"

// Used for finding anagrams: words with the same letters
// but which are different words, e.g., "bagel" a "gable"
// author: Owen Astrachan
//
// an Anaword object prints as a regular string, but
// compares using a normalized (also called canonicalized) form
//
// Example: the Anaword version of the string "bagel"
//          prints as bagle, but will be compared with
//          other Anawords as a vector of counts
//          of one 'a', one 'b', one 'e', one 'g', one 'l'
//          Since the counts for "gable" are the same, "gable"
//          and "bagel" will be equal when compared using operator ==
//
// basically an Anaword takes a string and converts it to a twenty-six
// digit number based on the counts of a's, b's, c's, ... z's so that
// aardvark is represented as:
//
//  3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0
//
//
// operations:
//
// Anaword(const string & word)      -- construct from a string
//
// bool equal(const Anaword & rhs)   -- compare rhs for equality
// bool operator == (lhs, rhs)       -- compare Anawords lhs == rhs
//
// bool less(const Anaword & rhs)    -- compare rhs for inequality <
// bool operator < (lhs,rhs)         -- compare Anawords lhs < rhs
// bool operator <= (lhs,rhs)        -- compare Anawords lhs <= rhs
//
// string toString()                 -- returns uncanonicalized "bagel"
// ostream & << operator(ostream,    -- print using <<
//                       Anaword)

class Anaword
{
  public:
    Anaword(const string & word);             // construct from string
    Anaword();                                // default (for vector)
    bool equal(const Anaword & rhs) const;    // compare for ==
    bool less(const Anaword & rhs)  const;    // compare for <    
    string toString()               const;    // return "bagel" or "gable"

  private:  

    void normalize();                         // helper function, sorts
    string myWord;                            // regular string: "bagel"
    tvector myCounts;                    // canonicalized form
};

bool operator == (const Anaword & lhs, const Anaword & rhs);
bool operator != (const Anaword & lhs, const Anaword & rhs);
bool operator <  (const Anaword & lhs, const Anaword & rhs);
bool operator <= (const Anaword & lhs, const Anaword & rhs);
ostream & operator << (ostream & out,  const Anaword & a);

#endif 

#include 
#include 
#include 
using namespace std;

#include "anaword.h"
#include "prompt.h"
#include "tvector.h"
#include "sortall.h"



void FindAnagrams(tvector& list)
// pre: list contains list.size() elements
// post: all anagrams in list printed, one set of anagrams per line
{
    QuickSort(list,list.size());
}

int main(int argc, char * argv[])
{
    tvector list;
    ifstream input;
    string filename,word;
    // use command line argument if it exists, else prompt user
    
    if (argc > 1)
    {
 filename = argv[1];
    }
    else
    {
 filename = PromptString("enter file name "); 
    }
    
    input.open(filename.c_str());
    if (input.fail())
    {
 cerr << "could not open " << filename << endl;
 exit(1);
    }

    while (input >> word)
    {
 list.push_back(Anaword(word));
    }
    cout << endl << "read " << list.size() << " words" << endl;

    FindAnagrams(list);

    return 0;
}
 

Do not run the program as it is (without implementing) Anaword::equal and Anaword::less since the call to QuickSort will cause an infinite loop.

Program Description

You'll write a program, part of which is given to you, that reads a file of words and generates as output all the anagrams in the file. Each line of output should contain words that are anagrams of each other, for example:
gazer graze gases sages heals leash shale heaps phase shape hares hears share shear earth hater heart haste hates heats haves shave arise raise lakes leaks Your program should deal with words that contain punctuation. You can ignore these words, but your program should not die/stop if such a word is encountered. You should make your own small test files, but check your final program with the input file words accessible on acpub as ~ola/data/words. (This file is /usr/dict/words from Linux.)

Coding and Algorithm

You must use the class Anaword whose declaration is given in the file anaword.h. You will need to write the implementation of this class in the file anaword.cpp although this has been started for you. An Anaword object is constructed from a string, and prints as the string, but is compared using a normalized or canonical form created by counting the number of times each letter in the word occurs (more on this below). For example, the code fragment below prints the two lines of output shown. <br> Anaword a("bagel");<br> Anaword b("gable");<br><br> cout << a << " " << b << endl;<br> if (a == b) cout << "they're ananagrams!" << endl;<br> Output as shown:
bagel gable they're anagrams! The objects a and b are equal because the operator == is overloaded for Anaword objects and returns true for "bagel" and "gable" since both words have the same normalized/canonical form of letter-signature: 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 which indicates one 'a', one 'b', one 'e', one 'g', and one 'l'. The signature of aardvark, for example, is 3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 You must implement the member functions declared and described in anaword.h so that the real word (e.g., "bagel") is used for printing, but the canonical/normal form of the letter-signature is used for comparison using == and <
To do this you'll need to implement all the functions declared in anaword.hthat are not implemented in the anaword.cpp file you're given. This includes

• Anaword::normalize which creates the signature for an Anaword
• Anaword::equal which determines if two Anawords are equal
• Anaword::less which determines if one Anaword is less than another.

For your program to run efficiently your implementations of Anaword::equal and Anaword::less should return true/false after making the minimal number of comparisons possible. Treat the vector myCounts as a 26-digit number so that, for example, "egg" > "ego" since the signatures are
egg: 00001020000000000000000000 ego: 00001010000000100000000000 The determination that "egg" is larger can be made after seven comparisons (the count of g's in egg is greater than the count of g's in ego and 'g' is the seventh letter of the alphabet).

A Working Program

You'll need to add code to doana.cpp to yield a working anagram program. This requires completing the function FindAnagrams using the idea below

1. Sort the vector of Anaword objects using quicksort. You can do this with &lt;br&gt; QuickSort(list, list.size());&lt;br&gt; because Anaword ojbects can be compared using <, ==, and <=. Access to QuickSort is via #include "sortall.h".
   
2. All anagrams are now adjacent in the vector. Make one pass over the elements looking for adjacent elements that are equal. You must write code to determine when two or more adjacent words are equal and print anagrams one set per line as shown at the beginning of this assignment.

Faster Anagrams

You'll now develop another method of canonicalizing an Anaword that's faster than the letter-signature method. First, when you've got the program working, you should add code to time how long it takes to find and print all anagrams in ~ola/data/words which is words, a file of 45,402 words. Write down the name of the machine you used and the time it takes and include these in your README file you submit. You should then create copies of both anaword.h and anaword.cpp by typing cp anaword.h anawordfinger.h cp anaword.cpp anawordfinger.cpp Now you have a copy of your (hopefully) correct Anaword class and implementation. You'll be re-implementing Anaword using another technique, but you'll need to submit both versions so you must make a copy. Instead of using the letter-signature method you'll store a sorted form of the word and use this to compare Anawords. For example, the sorted form of "bagel" and "gable" is the same, it's the string "abegl". This string is used for relational comparisons. To do this you'll need to make a few changes:

1. Remove the declaration below from the private section of Anaword. &lt;br&gt; tvector&amp;amp;lt;int&amp;amp;gt; myCounts; // canonicalized form&lt;br&gt; Then you'll add a new declaration for the sorted word: &lt;br&gt; string mySortedWord; // canonicalized form&lt;br&gt;
   
2. The function Anaword::equal is now one line: &lt;br&gt; return mySortedWord == rhs.mySortedWord;&lt;br&gt;
   
3. The function Anaword::less is similar: &lt;br&gt; return mySortedWord &amp;amp;lt; rhs.mySortedWord;&lt;br&gt;
   
4. The only other change needed is the function Anaword::normalize In this function you should sort the letters in mySortedWord which is a copy of myWord. To sort, use the code from selection sort which can be found in both the Sedgwick and Astrachan texts.
   
5. Be sure to change the comments in anaword.h to reflect the new method used.

When the program works, time it again on the same machine you timed the original program. Write the time in the README file you create. You should also write a paragraph or explaining why you think the timings are different.

Grading

This assignment is worth 15 points. Style of the code/program counts for 5/15, correctness is 8/10 and the README is 2/10.

Submit

You'll submit a README that describes the timings of both versions of the program, includes information about how much time you spent on the assignment, and a list of people with whom you discussed the program. Submit all .h and .cpp files and the README file. You do not need to submit the Makefile unless you modified it.
To submit use
submit_cps100 anagram README *.h *.cpp If submit_cps100 doesn't work, try ~ola/bin/submit100

Extra Credit

This is worth four points. Instead of sorting using < and == for Anawords, create a different ordering so that when anagrams are printed shorter words are printed first and longer words printed last. To do this, create a function object as described in pages 543-549 of the Tapestry text. This object will be used when sorting the vector of Anawords, e.g., you'll write &lt;br&gt; AnaLenComparer analen;&lt;br&gt; ...&lt;br&gt; QuickSort(list,list.size(), analen);&lt;br&gt;
The struct/class AnaLenComparer should compare two Anaword objects, using the length of the strings in the objects as the first criteria of comparison, and using Anaword::less only if the strings have the same length. For example: &lt;br&gt; Anaword a("tear");&lt;br&gt; Anaword b("ace");&lt;br&gt; Anaword c("race");&lt;br&gt; Here we want b to be "less" than a since it has fewer characters, but c is less than a since although they have the same number of characters, the canonicalized forms show that "acer" < "aert".

c program without main

/* prog_without_main.c */
_start()
{
_exit(my_main());
}
int my_main(void)
{
printf(“Hello\n”);
return 42;
}
And use this command (% is command prompt) to compile:
%gcc -O3 -nostartfiles prog_without_main.c

Try compiling this example:
#include
#define decode(s,t,u,m,p,e,d) m##s##u##t
#define begin decode(a,n,i,m,a,t,e)
void begin()
{
printf(“hello”);
}
here is how it works once we say define we need to understand that
#define x y
then ‘x’ ix replaced by ‘y’
similarly in this case
#define begin decode(a,n,i,m,a,t,e)
decode(a,n,i,m,a,t,e) is replaced by m##a##i##n
bcoz s is replaced by a,t by n,u by i and so on
s->a
t->n
u->i
m->m
p->a
e->t
d->e
now the statement becomes
void m##a##i##n
And u must be knowing that ## is used for string concatenation so it becomes
“main”
finally the code crops down to
void main()
{
printf(“hello”);
}

Here we are using preprocessor directive #define with arguments to give an impression that the program runs without main.But in reality it runs with a hidden main function.

The ‘##‘ operator is called the token pasting or token merging operator.That is we can merge two or more characters with it.

NOTE: A Preprocessor is program which processess the source code before compilation.

Look at the 2nd line of program-

#define decode(s,t,u,m,p,e,d) m##s##u##t

What is the preprocessor doing here.The macro decode(s,t,u,m,p,e,d) is being expanded as “msut” (The ## operator merges m,s,u & t into msut).The logic is when you pass (s,t,u,m,p,e,d) as argument it merges the 4th,1st,3rd & the 2nd characters(tokens).

Now look at the third line of the program-

#define begin decode(a,n,i,m,a,t,e)

Here the preprocessor replaces the macro “begin” with the expansion decode(a,n,i,m,a,t,e).According to the macro definition in the previous line the argument must de expanded so that the 4th,1st,3rd & the 2nd characters must be merged.In the argument (a,n,i,m,a,t,e) 4th,1st,3rd & the 2nd characters are ‘m’,'a’,'i’ & ‘n’.

So the third line “int begin” is replaced by “int main” by the preprocessor before the program is passed on for the compiler.That’s it…

The bottom line is there can never exist a C program without a main function.Here we are just playing a gimmick that makes us beleive the program runs without main function, but actually there exista a hidden main function in the program.Here we are using the proprocessor directive to intelligently replace the word begin” by “main” .In simple words int begin=int main.

c program without main

/* prog_without_main.c */
_start()
{
_exit(my_main());
}
int my_main(void)
{
printf(“Hello\n”);
return 42;
}
And use this command (% is command prompt) to compile:
%gcc -O3 -nostartfiles prog_without_main.c

Try compiling this example:
#include
#define decode(s,t,u,m,p,e,d) m##s##u##t
#define begin decode(a,n,i,m,a,t,e)
void begin()
{
printf(“hello”);
}
here is how it works once we say define we need to understand that
#define x y
then ‘x’ ix replaced by ‘y’
similarly in this case
#define begin decode(a,n,i,m,a,t,e)
decode(a,n,i,m,a,t,e) is replaced by m##a##i##n
bcoz s is replaced by a,t by n,u by i and so on
s->a
t->n
u->i
m->m
p->a
e->t
d->e
now the statement becomes
void m##a##i##n
And u must be knowing that ## is used for string concatenation so it becomes
“main”
finally the code crops down to
void main()
{
printf(“hello”);
}

Here we are using preprocessor directive #define with arguments to give an impression that the program runs without main.But in reality it runs with a hidden main function.

The ‘##‘ operator is called the token pasting or token merging operator.That is we can merge two or more characters with it.

NOTE: A Preprocessor is program which processess the source code before compilation.

Look at the 2nd line of program-

#define decode(s,t,u,m,p,e,d) m##s##u##t

What is the preprocessor doing here.The macro decode(s,t,u,m,p,e,d) is being expanded as “msut” (The ## operator merges m,s,u & t into msut).The logic is when you pass (s,t,u,m,p,e,d) as argument it merges the 4th,1st,3rd & the 2nd characters(tokens).

Now look at the third line of the program-

#define begin decode(a,n,i,m,a,t,e)

Here the preprocessor replaces the macro “begin” with the expansion decode(a,n,i,m,a,t,e).According to the macro definition in the previous line the argument must de expanded so that the 4th,1st,3rd & the 2nd characters must be merged.In the argument (a,n,i,m,a,t,e) 4th,1st,3rd & the 2nd characters are ‘m’,'a’,'i’ & ‘n’.

So the third line “int begin” is replaced by “int main” by the preprocessor before the program is passed on for the compiler.That’s it…

The bottom line is there can never exist a C program without a main function.Here we are just playing a gimmick that makes us beleive the program runs without main function, but actually there exista a hidden main function in the program.Here we are using the proprocessor directive to intelligently replace the word begin” by “main” .In simple words int begin=int main.

How can we sum the digits of a given number in single statement?

int sum=0;

  for(;num>0;sum+=num%10,num/=10);  // This is the "single line".

A program to print numbers from 1 to 100 without using loops

Method1 (Using recursion)


void printUp(int startNumber, int endNumber)
{
  if (startNumber > endNumber)
    return;
 
  printf("[%d]\n", startNumber++);
  printUp(startNumber, endNumber);
}




Method2 (Using goto)


void printUp(int startNumber, int endNumber)
{
start:

    if (startNumber > endNumber)
    {
       goto end;
    }
    else
    {
       printf("[%d]\n", startNumber++);
       goto start;
    }

end:
    return;
}

Finding whether 2 arrays are intersecting

Here are 2 arrays:
A1   1 8 7 5 6
A2   0 9 6 4 2

These two are intersecting at 6.
Complexity? 


Solution:
This can be solved using Hash Tables.
Take 1 Hash Table.
Insert elements from A1 in Hast Table as key and put value in front of them
(In case elemente get repeated increment the value count).
Now traverse the second array A2 and check for element as a key.If you find
it decrement the value and put it in array else continue to next element in
A2.

How to add two numbers without using the plus operator?

Actually,
SUM   = A XOR B
CARRY = A AND B
Recursive:
int add(int a, int b){
            if (!a) return b;
            else
                 return add((a & b) << 1, a ^ b);
      }

Iterative

unsigned long add(unsigned long integer1, unsigned long integer2)
{
    unsigned long xor, and, temp;

    and = integer1 & integer2; /* Obtain the carry bits */
    xor = integer1 ^ integer2; /* resulting bits */

    while(and != 0 ) /* stop when carry bits are gone */
    {
        and <<= 1; /* shifting the carry bits one space */
        temp = xor ^ and; /* hold the new xor result bits*/
        and &= xor; /* clear the previous carry bits and assign the new
carry bits */
        xor = temp; /* resulting bits */
    }
    return xor; /* final result */

} 

On a wicked note, you can add two numbers wihtout using the + operator as follows
a - (- b)

Other way is to use ++ operator:
           int a=10,b=20;
          while(b--) a++;
           printf("Sum is :%d",a);  

C progam to convert from decimal to any base (binary, hex, oct etc...)

#include 

int main()
{
  decimal_to_anybase(10, 2);
  decimal_to_anybase(255, 16);
  getch();
}

decimal_to_anybase(int n, int base)
{
  int i, m, digits[1000], flag;
  i=0;
 
  printf("\n\n[%d] converted to base [%d] : ", n, base);
 
  while(n)
  {
     m=n%base;
     digits[i]="0123456789abcdefghijklmnopqrstuvwxyz"[m];
     n=n/base;
     i++;
   }

   //Eliminate any leading zeroes
   for(i--;i>=0;i--)
   {
     if(!flag && digits[i]!='0')flag=1;
     if(flag)printf("%c",digits[i]);
   }  
}

Given an array of n integers from 1 to n with one integer repeated

#include
#include
#include

int i,j=0,k,a1[10];

main()
{
     printf("Enter the array of numbers between 1 and 100(you can repeat the numbers):");
     for(i=0;i<=9;i++)
     {
         scanf("%d",&a1[i]);
     }
    
     while(j<10)
     {
        for(k=0;k<10;k++)
        {
            if(a1[j]==a1[k] && j!=k)
            {
                printf("Duplicate found!");
                printf("The duplicate is %d\n",a1[j]);
                getch();
            }
        }
        j=j+1;
    }
   
    getch();
    return(0);
}

How to find out if a machine is 32 bit or 64 bit?

n = sizeof(void *);


if n==8, than 64 bit 
if n==4, than 32 bit.

Given an eight-bit bitmap graphics file, devise an algorithm to convert the file into a two-bit ASCII approximation

Assume that the file format is one byte for every pixel in the file, and that the approximation will produce one ASCII character of output for each pixel. This problem is easier to solve than it sounds. This is one of the tricks used in technical interview questions. Problems may be obscured or made to sound difficult. Don't be fooled! Take the time to think about the core of the problem. In this case, all you want is an algorithm for reading the values in a file and outputting characters based upon those values.
Eight-bit numbers can be in the range from 0 to 255. Two-bit numbers are in the range from 0 to 3. Basically, we want to divide the 256 numbers specified by an eight-bit number into four ranges, which can be indicated by a two-bit number. So, divide the range of 0 to 255 uniformly into four separate ranges: 0 to 63, 64 to 127, 128 to 191, and 192 to 255.
You then have to assign an ASCII character to each of those four ranges of numbers. For example, you could use "_", "~", "+", and "#". Then, the algorithm is as follows:

1. Open the file.
2. For every byte in the file:
a. Read in one byte.
b. If the value is in the range 0..63, we'll print '_'.
c. If the value is in the range 64..127, we'll print '~'.
d. If the value is in the range 128..191, we'll print '+'.
e. If the value is in the range 192..255, we'll print '#'.
3. Close the file.

Devise an algorithm for detecting whether a given string is a palindrome

For the sake of this problem, assume that the string has been stripped of punctuation (including spaces), and has been converted to a single case. The most efficient way to detect whether a string is a palindrome is to create two pointers. Set one at the beginning of the string, and one at the end. Compare the values at those locations. If the values don't match, the string isn't a palindrome. Otherwise, move each pointer inward and repeat the comparison. Stop when the pointers are pointing to the same position in the string (if its length is an odd-number) or when the pointers have "crossed" (if the string's length is an even-number).

Given the time, devise an algorithm to calculate the angle between the hour and minute hands of an analog clock

The important realization for this problem is that the hour hand is always moving. In other words, at 1:30, the hour hand is halfway between 1 and 2. Once you remember that, this problem is fairly straightforward. Assuming you don't care whether the function returns the shorter or larger angle.

routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.

Let

(x ^ 2 + y ^2 = r ^ 2)...................................1 

The basic idea is to draw one quadrant and replicate it to other four quadrants.
Assuming the center is given as (a,b) and radius as r units, then start X from (a+r) down to (a) and start Y from (b) up to (b+r). In the iteration, keep comparing is the equation (1) is satisfied or not within an error of one unit for a and b. If not then re-adjust X and Y.

Swapping 2 variables without 3rd variable

Method1 (The XOR trick)

a ^= b ^= a ^= b;


Although the code above works fine for most of the cases, it tries to modify variable 'a' two times between sequence points, so the behavior is undefined. What this means is it wont work in all the cases. This will also not work for floating-point values. Also, think of a scenario where you have written your code like this



swap(int *a, int *b)
{
  *a ^= *b ^= *a ^= *b;
}


Now, if suppose, by mistake, your code passes the pointer to the same variable to this function. Guess what happens? Since Xor'ing an element with itself sets the variable to zero, this routine will end up setting the variable to zero (ideally it should have swapped the variable with itself). This scenario is quite possible in sorting algorithms which sometimes try to swap a variable with itself (maybe due to some small, but not so fatal coding error). One solution to this problem is to check if the numbers to be swapped are already equal to each other.


swap(int *a, int *b)
{
  if(*a!=*b)
  {
    *a ^= *b ^= *a ^= *b;
  }
}




Method2

This method is also quite popular


 a=a+b;
 b=a-b;
 a=a-b;


But, note that here also, if a and b are big and their addition is bigger than the size of an int, even this might end up giving you wrong results.