## 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("Ångström") == sorted("Ångström"))  # => False
print(signature("Ångström") == signature("Ångström")) # => True
print(signature("Ångström")) # => agmnorst
print(signature("Ἀχιλλεύς")) # => αειλλςυχ
print(signature("H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝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: “Ångström”, “Ἀχιλλεύς”, “H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ”

8. matthew said

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