Thread: anagram program help

  1. #16
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Redemption?
    Code:
    #include <stdio.h>
    #include <string.h> 
    
    struct characters { 
    	int letters[256] ; 
    } ; 
    
    void map(char * s, struct characters * c) { 
    	int i ; 
    	for (i = 0 ; i < sizeof(c->letters) / sizeof(c->letters[0]) ; i++) c->letters[i] = 0 ;  
    	while(*s != 0) { 
    		if (*s != ' ') { 
    			c->letters[(int) tolower(*s)]++ ; 
    		}
    		s++ ; 
    	} 
    } 
    
    int compare( struct characters * c1, struct characters * c2  ) { 
    	return !memcmp( c1, c2, sizeof(struct characters)) ; 
    } 
    
    int main() {
    	struct characters c1 , c2 ; 
    	printf("struct is &#37;d\n", sizeof(c1) ) ; 
    	char s1[] = "Tom Marvolo Riddle" ; 
    	char s2[] = "I am Lord Voldemort" ; 
    	map(s1, &c1) ; 
    	map(s2, &c2) ; 
    	printf("The strings %s Anagrams\n", (compare( &c1, &c2 ) ? "are" : "are not" ) ) ; 
    	return 0 ; 
    }
    Mainframe assembler programmer by trade. C coder when I can.

  2. #17
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Psh... mine was so elegant in its ability not to damage two strings... but alas, I will concede that yours is more streamlined.

    Though...
    Code:
    for (i = 0 ; i < sizeof(c->letters) / sizeof(c->letters[0]) ; i++) c->letters[i] = 0 ; 
    // could become (btw, cheater...)
    memset(c->letters, 0, sizeof(c->letters));
    // Now you aren't a cheater :)
    
    
    // And
    if (!isspace(*s))

  3. #18
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Or better yet
    Code:
    memset(c, 0, sizeof(struct characters));
    And yes, isspace() is better.
    Mainframe assembler programmer by trade. C coder when I can.

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Redemption?
    Not quite, due to lack of const-correctness... also is there any particular need to make the code compatible with C, and thus avoid passing by reference and prefixing struct names with struct?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I'm fairly certain his works. (And for longer cases than you might imagine.)

    Soma

    Code:
    #include <iostream>
    #include <string>
    
    static const unsigned long values[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    
    unsigned long mugprime
    (
      const std::string & f
    )
    {
      unsigned long return_value(0);
      for(std::string::const_iterator cursor(f.begin()), stop(f.end()); stop > cursor; ++cursor)
      {
        std::string::value_type character(*cursor);
        if(isalpha(character))
        {
          return_value += values[static_cast<unsigned long>(toupper(character))];
        }
      }
      return(return_value);
    }
    
    int main()
    {
      const char s1[] = "To be or not to be: that is the question; whether 'tis nobler in the mind to suffer the slings and arrows of outrageous fortune, or to take arms against a sea of troubles and by opposing, end them?";
      const char s2[] = "Is a befitting quote from one of Shakespeare's greatest tragedies. But why won't Hamlet's inspiring motto toss our stubborn hero's tortuous battle for life, on one hand, and death, on another?";
      unsigned long vs1(mugprime(s1));
      unsigned long vs2(mugprime(s2));
      std::cout << "The string are " << ((vs1 == vs2) ? "anagrams" : "not anagrams") << "!\n";
      return(0);
    }

  6. #21
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by phantomotap View Post
    I'm fairly certain his works. (And for longer cases than you might imagine.)
    Taking advantage of prime numbers is clever but I don't think that's correct either. The products of combinations of prime numbers are unique. Their sums need not be. If you used multiplication instead of addition, this would be correct. Of course the values would grow extremely large very quickly.

    You could add the logarithms of the primes instead, for an equivalent solution, but then you'd be using doubles in an anagram program

  7. #22
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Taking advantage of prime numbers is clever but I don't think that's correct either. The products of combinations of prime numbers are unique. Their sums need not be. If you used multiplication instead of addition, this would be correct. Of course the values would grow extremely large very quickly.
    ^_^

    You're right. That was a mistake on my part, but as far that goes, it may not even compile.

    And of course, the primes shouldn't be sequential, in order, nor as small, but I was in a hurry. I'm playing Mario Kart! (Without intentionally manipulation integer wraparound will be less likely to eventually cause a collision with the "right" primes.)

    Soma

  8. #23
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by laserlight View Post
    Not quite, due to lack of const-correctness... also is there any particular need to make the code compatible with C, and thus avoid passing by reference and prefixing struct names with struct?
    Man, tough crowd!!

    When I did my first sample, I wasn't paying attention to which forum I was responding, so C it was.

    How's this?
    Code:
    #include <stdio.h>
    #include <string.h> 
    #include <stdlib.h> 
    
    struct characters { 
    	int letters[256] ; 
    } ; 
    
    void map(const char * s, struct characters * c) { 
    	memset( c, 0, sizeof(struct characters) ) ; 	
    	while(*s) { 
    		if (*s != ' ') { 
    			c->letters[(int) tolower(*s)]++ ; 
    		}
    		s++ ; 
    	} 
    } 
    
    int compare( const struct characters * c1, const struct characters * c2  ) { 
    	return !memcmp( c1, c2, sizeof(struct characters)) ; 
    } 
    
    int main() {
    	struct characters c1 , c2 ; 
    	const char s1[] = "Tom Marvolo Riddle" ; 
    	const char s2[] = "I am Lord Voldemort" ; 
    	map(s1, &c1) ; 
    	map(s2, &c2) ; 
    	printf("The strings %s Anagrams\n", (compare( &c1, &c2 ) ? "are" : "are not" ) ) ; 
    	return 0 ; 
    }
    Mainframe assembler programmer by trade. C coder when I can.

  9. #24
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    my humble submission

    Code:
    #include <math.h>
    __int64 genPhraseVal(const char *phrase)
    {      
            __int64 value=0;
            unsigned int i=strlen(phrase);
            while(i)
            {
                    --i;
                    unsigned int cv = tolower(phrase[i])-97;
                    if(cv<26)
                    {
                            value+=pow(2,cv);
                    }
            }
            return value;
    }
    
    bool anagram(const char *phrase1,const char *phrase2)
    {
            if(genPhraseVal(phrase1)==genPhraseVal(phrase2))
            {
                    return true;
            }
            else
            {
                    return false;
            }
    }
    Last edited by m37h0d; 04-28-2008 at 08:39 AM.

  10. #25
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    m37h0d, why not use int64_t instead of __int64? The former is C99.

    http://en.wikipedia.org/wiki/Stdint.h
    Last edited by robwhit; 04-27-2008 at 11:55 PM.

  11. #26
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    my compiler doesn't recognize that as a datatype. it is from 2002, so that may have something to do with it.

  12. #27
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by m37h0d View Post
    my compiler doesn't recognize that as a datatype. it is from 2002, so that may have something to do with it.
    So use:
    Code:
    typedef __int64 int64_t;
    That way you only have to remove one line when you get a better compiler.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #28
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    i'll consider that, thanks.

    so can anyone find a flaw here? i think the alg is rock solid and should work for strings of, for all intents and purposes, unlimited length.

  14. #29
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
                    unsigned int cv = tolower(phrase[i])-97;
    Why not 'a'?

    Code:
                    if(cv<26)
                    {
                            value+=pow(2,cv);
                    }
    could be written as:
    Code:
                            value+=1LL << cv;
    And of course, your anagram will think that:
    aaaa
    and
    bb
    are anagrams, because both will add up to 4.

    Edit: the last flaw is probably the biggest one.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #30
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    awww crap you're right.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-21-2008, 10: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, 11:17 PM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM