anagram program help

This is a discussion on anagram program help within the C++ Programming forums, part of the General Programming Boards category; i need to write a program that takes two strings of at most a length of 500, and outputs whether ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    37

    anagram program help

    i need to write a program that takes two strings of at most a length of 500, and outputs whether or not they are anagrams

    Example of an anagram :
    Tom Marvolo Riddle
    I am Lord Voldemort


    i'm not sure how i would go about doing this. do i need to see if both strings equal each other as far as letters go? how would i even accomplish that?

  2. #2
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    839
    i'm not sure how i would go about doing this.
    well there's your problem. you haven't identified what you need to do!

    what makes an anagram?

    the same quantity of the same letters...

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    You need to keep a count every character (except blanks) and ignore case.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  4. #4

    Join Date
    Apr 2008
    Location
    USA
    Posts
    76
    Each letter in the first string (except spaces) should have exactly one counterpart in the second string (keeping in mind that a letter can be repeated in a word).

    So, you could loop through each letter in the first string, then loop through each letter in the second string until you get a match, making sure you don't count the same letter twice from the second string.

    To satisfy case insensitivity, you can just make both strings all lowercase.
    Last edited by rudyman; 04-24-2008 at 05:40 PM.

  5. #5
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    Write an http client that feeds an anagram web server and parses the results.

    Just kidding. The others have given you a good start. Post your first attempt at code when you are ready.

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,252
    Sort both strings, then check if they are equal.

  7. #7

    Join Date
    Apr 2008
    Location
    USA
    Posts
    76
    Quote Originally Posted by brewbuck View Post
    Sort both strings, then check if they are equal.
    Clever, but don't forget to remove all spaces first.

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    I just wrote one to add up the non-blank, lowercase value of each ascii character in each string. Works great. 20 lines of code.



    Todd
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  9. #9
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76
    I did something simmilar way back, hope it helps:
    INPUT FILES - space counts as character

    input.txt - Anagrams
    3
    ant
    4
    t an


    input1.txt - Anagrams
    3
    ant
    3
    tan


    input2.txt - NOT Anagrams
    3
    ast
    3
    tan


    input3.txt - Empty File - Recive Error Message


    input4.txt - Anagrams
    14
    do your own
    13
    word on you


    input5.txt - NOT Anagrams
    14
    do your own
    13
    word on yyu


    input6.txt - NOT Anagrams
    14
    do your own


    input7.txt - NOT Anagrams
    40
    The quick brown fox jumps over a lazy do
    41
    The quick brown fox jumps over a lay dog.


    input8.txt - NOT Anagrams
    4
    clasp
    5
    scalp


    input9.txt - NOT Anagrams
    3
    3
    tan

    Code:
    #include <fstream>
    #include <iostream>
    #include <stdlib.h>
    #include <string>
    #include <vector>
    #include <sstream>
    #include <algorithm>
    
    
    
    using namespace std;
    
    
    //functions prototypes
    void make_upcase (string input_string[] , int size , int count) ; // converts letters to upper case
    int count_words ( int string_number , string input_string[]) ; // counts words on a line
    bool are_anagrams (string input_string[] , int string_lenght[] , int position);
    void swap (char &first_char , char &next_char);
    
    ////////////////////////////////////////////////////////////////////////////////
    
    int main()
    {
         ifstream input_data;
         input_data.open ("input.txt");
         if (! input_data) // File was no found
         {
              cout << "File \"input.txt\" not found" << endl << endl;
              system ("pause");
              exit(1);
         } 
         else // File was found
         {
              cout << "File \"input.txt\" found" <<  endl;
              int temp_num;  // temporary int for storing number of chars
              int size = temp_num; // size of input string
              int count = 0; // counter for loop
    
              // read data from file and move it to the input_string dynamic array
              string * input_string = new string [size] ; // dynamic allocated array
              
              cout << "This file looks like:"  << endl;
              
              while (!input_data.eof()) 
              {
                   getline(input_data, input_string [count] ) ;   
                   cout << input_string[count] << endl;  // show original input file
                   count ++;
              } // end while loop
              
             input_data.close(); // close ifstream
    
             if (count == 1)  //File is empty
             {
                  cout << "File \"input.txt\" is empty" << endl << endl;
                  system ("pause");
                  exit(1);
             }  // end if
       
            // splitt array --- take numbers and put it into new array   
            int * string_lenght = new int[size];
            int convert;
            for ( int i = 0 , j = 0; i < count ; i+=2)
            {         
                 convert = atoi(input_string[i].c_str()); // c_str() converts 
                                                              // string into char[]
                                                              // atoi converts 
                                                              // char[] into int
                 string_lenght[j] = convert; // moves numbers form input_num array 
                                             // to string_lenght array
                 j++;
                 convert++; 
             } // end for loop
       
             cout << endl << endl;
       
            // function calls
       
            // function to convert letters to upper case
            make_upcase (input_string , size , count) ;
            // precondition: input_string ia s array of strings from input.txt file,
            //               where each element is a single word. Size is the size
            //               of array. Count is the number of lines in file   
            // postcondition: letters are converted to upper case
    
            // ****************************************************************** //
    
            // function to count number of words in each sentence function is called
            // only for odd elements of input_string since the even represent count
            for ( int string_number = 1  ; string_number < count ; string_number+=2)
            {
                 int num =  count_words (  string_number , input_string) ; 
                 // precondition: string_number is number of string (only odd)
                 //               input_string is a array of strings from file   
                 // postcondition: returns number of words in each sentence
                 cout << "String " << input_string[string_number]<< endl << 
                 "  has: " << num << " word(s), " << input_string[string_number-1] 
                 << " characters"<< endl;
            } // end for loop
    
            // ****************************************************************** //
    
            // function to check is 2 sentences are anagrams of each other
           int position = 0;
           bool anagrams = are_anagrams ( input_string ,  string_lenght , position);
           // precondition: string_number is number of string (only odd)
           //               string_lenght is the number of characters in each line
           //               after they were converted into intigers from a string 
           //               position coresponds to the index of an array
           // postcondition: returns true if two strings are anagrams and false if 
           //                they are not anagrams    
           if (anagrams != false)
           {
                cout << endl << "They are anagrams." << endl << endl;
                system ("pause");
                exit(1);
            }    
           else
           {
                cout << endl << "They are not anagrams." << endl << endl; 
                system ("pause");
                exit(1);
            }
                     
    }  // end if/else
    
      system ("pause");
      return 0;
    }
    
    
    // FUNCTIONS
    
    // converts all letters into upper case
    void make_upcase (string input_string[] , int size , int count) 
    {
         string * words = new string[size]; // new array to hold uppercase words
         for ( int i = 1 , j = 0 ; i < count ; i+=2)
         {                      
              strupr((char *) input_string[i].c_str()); // Function converts to upper case
              words[j] = input_string[i]; // move words from input_string array to words array
              j++;
         }  // end for loop
    } // end function
    
    ////////////////////////////////////////////////////////////////////////////////
    
    // counts words on a line
    int count_words (int string_number , string input_string[]) 
    {
         int word_count = 0;
         string temp_string = input_string[string_number];
         string buffer; // Create a buffer string
         stringstream string_stream (temp_string); // Insert temp_string into a stream
       
         while (string_stream >> buffer)
              word_count++;  
    
         return word_count;
    } // end function
    
    ////////////////////////////////////////////////////////////////////////////////
    
    // checks if 2 sentences are anagrams
    bool are_anagrams (string input_string[] , int string_lenght[] , int position )
    {
         // each element will hold one char from input_string 
         vector <char> text; 
         vector <char> text1; 
    
         // convert each string (element in array) into array of chars
         const char *char_text = input_string[1].c_str(); 
         const char *char_text1 = input_string[3].c_str();    
    
         // puts each char as seperate element into vector 
         for (int i = 0 ;i < string_lenght[0] ; i++)
              text.push_back (char_text[i]); 
    
         // puts each char as seperate element into vector 
         for (int i = 0 ;i < string_lenght[1] ; i++)
              text1.push_back (char_text1[i]); 
    
         // Sort vector holding first set of chars alphabeticly 
         for (int i = 0; i < string_lenght[position]; i++)   	
         {							      
              for (int j = i; j < string_lenght[position]; j++)
                   if (text [i] > text [j])
                        swap (text[i], text[j]);  
         } // end for loop
        
         // Sort vector holding next set of chars alphabeticly 
         for (int i = 0; i < string_lenght[1]; i++)   	
         {							      
              for (int j = i; j < string_lenght[1]; j++)
                   if (text1 [i] > text1 [j])
                        swap (text1[i], text1[j]);  
         } // end for loop
    
         int x = text.size();
         int x1 = text1.size();
    
         // removes empty elements from vector
         for (int i = 0; i < text.size() ; i++)
         {
              if (text[i] == ' ') 
              {
                   for (int erase = i; erase < text.size()-1; erase++)
                        text[erase ] = text[ erase+1 ] ;
                   text.pop_back() ; 
               } // end if
          } // end for loop
         
         // removes empty elements from vector
         for (int i = 0; i < text1.size() ; i++)
         {
              if (text1[i] == ' ')
              {
                   for (int erase = i; erase < text1.size()-1; erase++)
                        text1[erase ] = text1[ erase+1 ] ;
                   text1.pop_back() ;
              } // end if
          } // end for loop
    
         // compare each element of the 2 vectors, if they are equal return true
         // since the strings are anagrams of each other, else return false  
          if (text == text1)
               return true;                                     
          else
               return false;
               
    } // end function
    
    ////////////////////////////////////////////////////////////////////////////////
    
    // swaps characters for sorting chars alphabeticly
    void swap (char &first_char , char &next_char)
    {
      char temp = first_char; 
      first_char = next_char;
      next_char = temp;    
    } // end function

  10. #10
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Code:
    input8.txt - NOT Anagrams
    4
    clasp
    5
    scalp
    Interesting test case.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  11. #11
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76
    yeah, they both contain same letters but since only 4 are read from the first string and 5 from next, these words are not anagrams

  12. #12
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Ah. I understand your test cases now.

    Here's my solution.

    Code:
    #include <stdio.h>
    
    int count( char * s ) { 
    	int i = 0 ; 
    	int length = 0 ; 
    	while(*s != 0) { 
    		if (*s != ' ') { 
    			i += tolower(*s) ; 
    			length++ ; 
    		}
    		s++ ; 
    	} 
    	return i+length ; 
    } 
    
    int main() {
    	char s1[] = "Tom Marvolo Riddle" ; 
    	char s2[] = "I am Lord Voldemort" ; 
    	printf("The strings &#37;s Anagrams\n", (count(s1)==count(s2) ? "are" : "are not" ) ) ; 
    	return 0 ; 
    }
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  13. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,252
    Quote Originally Posted by Todd Burch View Post
    Ah. I understand your test cases now.

    Here's my solution.
    Your solution is nowhere near correct. According to that, "Tom Marvolo Riddle" is an anagram of "zxhcheiughfkhzya"

  14. #14
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Fix:
    Code:
    #include <stdio.h>
    #include <string.h>
    
    size_t count(const char * s ) {
        size_t length = 0;
    
        do {
            if(!isspace(*s))
                ++length;
         } while(*++s);
    
         return length; 
    } 
    
    int strcpy_nospaces(char *dst, const char *src)
    {
        for(;*src;++src)
            if(!isspace(*src))
              *dst++ = toupper(*src);
        *dst = '\0';
    }
    
    /*
      * s1: The first string
      *
      * s2: The second string
      *
      * Returns: This will return 1 if the strings evaluate as an anagram, or zero if they do not.
      *
      * If an error occurs -1 is returned.
      */
    int anagram(const char *s1, const char *s2)
    {
        size_t length[2];
        char *s[2];
        int comparison;
    
        if(!s1 || !s2)
            return -1;
    
        length[0] = count(s1);
        length[1] = count(s2);
    
        s[0] = malloc(length[0]+1);
        if(!s[0])
            return -1;
    
        s[1] = malloc(length[1]+1);
        if(!s[1])
        {
            free(s[0]);
            return -1;
        }
    
        strcpy_nospaces(s[0], s1);
        strcpy_nospaces(s[1], s2);
    
        qsort(s[0], length[0], sizeof(char), strcmp);
        qsort(s[1], length[1], sizeof(char), strcmp); 
    
        comparison = strcmp(s[0], s[1]);
    
        free(s[0]);
        free(s[1]);
    
        return (comparison == 0)?1:0;
    }
    
    int main() {
            char *booleans[] = {"are not","are"};
    	char s1[] = "Tom Marvolo Riddle" ; 
    	char s2[] = "I am Lord Voldemort" ; 
    	printf("The strings &#37;s Anagrams\n", booleans[anagram(s1, s2)]) ; 
    	return 0 ; 
    }
    Last edited by master5001; 04-26-2008 at 07:32 PM.

  15. #15
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Quote Originally Posted by brewbuck View Post
    Your solution is nowhere near correct. According to that, "Tom Marvolo Riddle" is an anagram of "zxhcheiughfkhzya"
    Son of a gun.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

Page 1 of 4 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-21-2008, 09:39 AM
  2. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  3. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 10:17 PM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21