Anagrams, Again

October 18, 2019

The previous exercise showed a probabilistic method for determining if two strings are anagrams, and some users pointed out collisions in the method that falsely concluded two strings were anagrams when in fact they were not.

Your task is to write a program that recognizes anagrams without possibility of error. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

8 Responses to “Anagrams, Again”

  1. Paul said

    In Python. These functions work for ascii and for unicode.

    from collections import Counter
     
    def is_anagram(a, b):
        return sorted(a) == sorted(b)
     
    def is_anagram(a, b):
        return Counter(a) == Counter(b)
    
  2. Zack said

    Here is my take on this, using Julia 1.1.1, without any dependencies: https://pastebin.com/9LgUHJr8

    Have a nice weekend!

  3. Daniel said

    Here’s a solution in C.

    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    bool check_anagrams(char* s1, char* s2) {
      int diff[256] = {0};
      for (char* s = s1; *s != '\0'; ++s) {
        ++(diff[(unsigned char)(*s)]);
      }
      for (char* s = s2; *s != '\0'; ++s) {
        --(diff[(unsigned char)(*s)]);
      }
      for (int i = 0; i < 256; ++i) {
        if (diff[i]) return false;
      }
      return true;
    }
    
    int main(int argc, char* argv[]) {
      if (argc != 3) return EXIT_FAILURE;
      bool anagram = check_anagrams(argv[1], argv[2]);
      printf("%d\n", anagram);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./a.out programming praxis
    0
    
    $ ./a.out praxis xsairp
    1
    
  4. Daniel said

    Here’s a sorting-based solution in C.

    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int compare(const void* a, const void* b) {
      char a_ = *((char*)a);
      char b_ = *((char*)b);
      return (a_ > b_) - (a_ < b_);
    }
    
    // destructive
    bool check_anagrams(char* s1, char* s2) {
      qsort(s1, strlen(s1), 1, compare);
      qsort(s2, strlen(s2), 1, compare);
      return strcmp(s1, s2) == 0;
    }
    
    int main(int argc, char* argv[]) {
      if (argc != 3) return EXIT_FAILURE;
      bool anagram = check_anagrams(argv[1], argv[2]);
      printf("%d\n", anagram);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./a.out programming praxis
    0
     
    $ ./a.out praxis xsairp
    1
    
  5. matthew said

    @Paul: you need to be a bit careful with this approach with Unicode. Here’s an attempt to deal with combining characters, equivalences & casing:

    import unicodedata
    
    def signature(s):
        # Apply compatibility decomposition
        s = unicodedata.normalize('NFKD',s)
        # Include: Letter, Number, Symbol.
        # Exclude: Mark, Punctuation, Separator, Other
        s = [c.lower() for c in s if unicodedata.category(c)[0] in "LNS"]
        s = "".join(sorted(s))
        return(s)
    
    print(sorted("Ångström") == sorted("Ångström"))  # => False
    print(signature("Ångström") == signature("Ångström")) # => True
    print(signature("Ångström")) # => agmnorst
    print(signature("Ἀχιλλεύς")) # => αειλλςυχ
    print(signature("H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ")) # => ceehmos
    
  6. matthew said

    I’m a bit disappointed that Chrome on my Android phone can’t cope with the combining characters in that last post at all, FF on Linux seems to manage though.

  7. matthew said

    Just trying something: “Ångström”, “Ἀχιλλεύς”, “H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ”

  8. matthew said

    OK, Chrome on Android just seems to have problems when displaying with its code font.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: