Write a script to identify an anagram

Inspired by this tweet from the always awesome Fermat's Library.

Challenge

In the language of your choice, write a script that will determine if two strings are an anagram for each other. You can use the approach outlined in the tweet, or — for bonus points — come up with your own solution 🤓.

Via Wikipedia:

An anagram is word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

For our challenge, we'll use the strict definition — each letter must be used exactly once.

Expected Behavior:

isAnagram(stressed, desserts) // TRUE
isAnagram(happy, sad) // FALSE

Have fun!

Comments

[Lyon]

I feel we need SPOILER warnings for the comments

[Simon Proctor]

So there was a perl6 version of the using this method posted on twitter. But it had a wee bug (it was summing not multiplying the value). Here's the fixed version:

sub ana(*@words) {
    state %primes = 'A'..'Z' Z=> (^Inf).grep(*.is-prime);
    [==] @words.map({ [*] %primes{$_.comb} });
}

I realise any version of Perl can look like line noise so I'll break it done.

Firstly the *@words indicates that all the arguments passed into the function should be put into an Array called @words.

state %primes state variables are defined once and then reused each time the function is called so the first time you call the ana function the primes hash is populated.

(^Inf).grep(*.is-prime) this gives a lazy list of integers from 0 to Infinity (but then only returns those that are prime).

'A'..'Z' gives the Range of characters from A to Z (inclusive).

The Z meta operator applies the infix operator on it's right (in this case the => Pair constructor) to each element in the Positional objeect on it's left and right until one is used up. (That important, don't use a Z operator on a couple of lazy lists... it won't go well).

So that gives us a hash starting { A => 2, B => 3, C => 5 ... and so on.

@words.map applies the code block inside the map call to each item in @words. Inside the block $_ is assign the current value.

$_.comb splits the word into individual characters and %primes{$_.comb} references each of the characters and gets it's value in the prime array.

[*] and [==] are cases of applying the [] meta operator to an infix operator. It acts like taking the list on the right and putting the operator between each item.

So for the string "ABC" %primes{$_.comb} returns the list (2 3 5) and then you have [*] (2 3 5) which can be thought of as 2 * 3 * 5 or 30.

The [==] takes our list of products and puts == between them. In this case it makes use of Perl6 operator chaining which allow you to write something like 30 == 30 == 30 or 5 < 10 > 7 in both the cases each individual Boolean check is made and then these are all combined into a sets of AND checks.

Hope that makes sense. Note that this function only works on uppercase strings. It would be easy enough to make it case insensitive and to also add any Unicode characters for accents found in the expected strings.

[Vinay Pai]

This algorithm is actually an excellent illustration of why clever algorithms aren't always better.

In fact the clever algorithm here is worse in basically every way imaginable. It's more complicated, limited in scope, error prone, can fail in unexpected ways, and possibly less efficient than the obvious solution.

• You need to store a lookup table of letters to primes. For the 26 letters, this 26 element lookup table is already more code than it would take to iterate over the characters and increment values in a map.
• If you typo one of the values you'll get wrong answers all the time. Or you need code to compute the first n primes which comes with its own performance penalty and extra code.
• The list of primes gets pretty huge if you want to support any kind if i18n and you're dealing with more than just 26 letters.
• In most languages on modern processors integers are 64 bits long. The 26th prime is 101. In the worst case you could overflow the integers in as few as 10 letters. Integer overflow is DEFINITELY an issue if you're dealing with i18n and therefore more characters and larger primes, or if you want to support phrases rather than individual words, and therefore longer input. Once you overflow and wrap around you could get false positives. Or you could use arbitrary precision arithmetic, but that's drastically less efficient.

[Osaetin Daniel]

I'm surprised that no one has talked about using ord in python (It Returns the Unicode code point for a string) and comparing the sum

>>> sum(map(ord, 'stressed')) == sum(map(ord, 'desserts'))
True

It even performs better than sorting

>>> timeit.timeit("sorted('stressed') == sorted('desserts')")
1.3272779149992857

>>> timeit.timeit("sum(map(ord, 'stressed')) == sum(map(ord, 'desserts'))")
1.2404647049988853

[Vinay Pai]

It performs better but it's wrong. Comparing sums can give you false positives.

>>> sum(map(ord, 'false positive'))
1438
>>> sum(map(ord, 'farce positivo'))
1438
>>>

[Jay]

Rust way, could be done better.
This just compares the char vector directly after sorting them.

fn is_anagram(a: &str ,b : &str) ->  bool {
    if a.len() != b.len() {    // Length check 
        return false;
    }
    let mut a:Vec<char> = a.chars().collect();
    a.sort();
    let mut b:Vec<char> = b.chars().collect();
    b.sort();
    if a == b {
        return true
    }
    false
}

[John Selbie]

C++

using namespace std;
bool isAnagram(const string& s1, const string& s2)
{
    unordered_map<string::value_type, int> themap;
    if (s1.size() != s2.size())
        return false;
    for (auto c : s1)
        themap[c] += 1;
    for (auto c : s2)
        themap[c] -= 1;
    for (auto& p : themap) {
        if (p.second != 0)
            return false;
    }
    return true;
}

[Heiko Dudzus]

I like the solution to "subtract" all characters of the shorter word from the (possibly) longer word, and check if there is some character left:

import Data.List(delete,sortBy)
import Data.Function(on)

-- deletes the first character of word from str
del str word = delete (head word) str

-- deletes all chars of word from str
str `without` word = foldl del str (map (:[]) word)

-- are there any remaining characters? 
isAnagram word1 word2 = null $ longer `without` shorter
  where [shorter,longer] = sortBy (compare `on` length) [word1,word2]

Ok, this is more fun, but it somehow reimplemented the library function ( \ \ ) (which can be read as the difference operation in set theory)

import Data.List((\\),sortBy)
import Data.Function(on)
isAnagram word1 word2 = null $ longer \\ shorter
  where [shorter,longer] = sortBy (compare `on` length) [word1,word2]

[Heiko Dudzus]

I'm sorry, it took me a dinner out to see, this was unnecessarily complicated. :) The delete functions perfectly fits a right fold. And if the words aren't of equal length, they are not anagrams.

-- deletes the first occurance of element x from a list
delete _ [] = []
delete x (y:ys) = if x == y then ys else y : delete x ys

-- deletes all elements of the second list from the first
without :: Eq a => [a] -> [a] -> [a]
without = foldr delete

-- are there any remaining characters? 
isAnagram word1 word2 = null $ word1 `without` word2

delete could also be imported from Data.List

[Heiko Dudzus]

This is close to cheating and must have terrible space and runtime complexity:

import Data.List(permutations)
isAnagram word1 word2 = word1 `elem` permutations word2

The solution based on sort:

import Data.List(sort)
isAnagram word1 word2 = sort word1 == sort word2

The library functions sort and permutations seem to be such an integral part of the solution, they should be implemented, here. :)

[Heiko Dudzus]

I stick with mappings to prime numbers. Haskell, without considerations of performance:

import Data.Char(toLower)
import Data.List(lookup)

primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

charToPrime c = lookup c $ zip ['a'..'z'] primes

eval word = product <$> sequence (map (charToPrime . toLower) word)

isAnagram word1 word2 = eval word1 == eval word2

lookup and charToPrime return a Maybe value, without catching the eye. Umlauts or digits result in a Nothing value for the character and in a product of 1 for the word. The handling of those cases could be improved.

[Josha von Gizycki]

Always happy to provide Clojure answers ;)

(defn anagram? [w1 w2]
  (= (sort w1) (sort w2)))

And of course I snooped the algorithm from all the other answers here.