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

[Ben Halpern]

I'd think sorting the characters of the string and comparing them would be a fine solution.

In Ruby:

def is_anagram?(first_word, second_word)
    first_word.chars.sort.join == first_word.chars.sort.join
end

We might want to refactor into two functions

def is_anagram?(first_word, second_word)
    sort_alphabetically(first_word) == sort_alphabetically(second_word)
end

def sort_alphabetically(string)
    string.chars.sort.join
end

The ? in Ruby is just another character, but it's commonly used in naming comparison methods like this.

[Ben Halpern]

Actually, the join step is unnecessary given that the arrays will match or not at that point, but it still seems like an ergonomic step if we are thinking in words. 🙂

[Ben Halpern]

If we wanted the comparison to work for n words, we might take an approach like this:

    def are_anagrams?(words)
        words.map { |w| sort_alphabetically(w) }.uniq.size == 1
    end

This would check if the "unique" array of sorted words is a length of one, indicating they are all the same.

[Ben Halpern]

In true Ruby style, we could monkey patch the Array class, like such:

class Array
  def are_anagrams?
    self.map { |w| sort_alphabetically(w) }.uniq.size == 1
  end
end

So then we could call:

["pots", "post", "stop"].are_anagrams? # true
["pots", "post", "ghost"].are_anagrams? # false

[Ben Halpern]

Looking up methods on the Array class, I see that I can refactor the above to:

def are_anagrams?
    self.map { |w| sort_alphabetically(w) }.uniq.one?
end

This may be less clear to non-Rubyists, but that method is there for a reason for Ruby folks.

[Enrique Jose Padilla]

Following your train of thought was fun

[xelaflash]

Very cool
i'm learning ruby currently and the refactor steps are very clear and easy to follow.
At then end only one line method!
i would have written this in 20 lines probably and in a couple of hours :)

Cool stuff.

[xelaflash]

Hi Ben,

seems to have a small typo in your code (first part).
After "==" should be second_word, no?

[Evan Oman]

Full blown Java implementation of the Prime Product method mentioned in the tweet (Gist for full viewing):

package testing;

import java.math.BigInteger;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class IsAnagramDemo
{
    /* Get the primes we need */
    private static final List<BigInteger> alphaPrimes = primes()
            .limit(26)
            .collect(Collectors.toList());

    /* Int encoding of lowercase a in unicode */
    private static final int A_INT_ENCODING = 97;

    /* Int encoding of lowercase z in unicode */
    private static final int Z_INT_ENCODING = 122;

    /*
        Main method to demonstrate success
     */
    public static void main(String[] args) throws Exception
    {
        assert isAnagram("stressed", "desserts");

        assert !isAnagram("happy", "sad");
    }

    /**
     * Determines if two strings are anagrams using the prime product method
     *
     * @param s1 First input string
     * @param s2 Second input string
     * @return Boolean indicating anagram-ness
     * @throws IllegalArgumentException Thrown when at least one of the input strings is invalid
     */
    public static boolean isAnagram(String s1, String s2) throws IllegalArgumentException
    {
        return primeProduct(s1).equals(primeProduct(s2));
    }

    /**
     * Converts a string to the corresponding product of prime values
     *
     * @param s Input string
     * @return Big integer product of primes
     * @throws IllegalArgumentException Thrown when strong contains chars outside of A-z
     */
    private static BigInteger primeProduct(String s) throws IllegalArgumentException
    {
        /* Convert to lowercase char array */
        char[] chars = s.toLowerCase().toCharArray();

        BigInteger product = BigInteger.ONE;

        for (char c : chars)
        {
            /* Cast char to int */
            int cInt = (int)c;

            /* If the char is out of bounds we must throw an exception */
            if (cInt < A_INT_ENCODING || cInt > Z_INT_ENCODING)
            {
                throw new IllegalArgumentException("Character \"" + c + "\" not valid");
            }
            /* Otherwise we can do the prime lookup */
            else
            {
                /* Prime value corresponding to this char */
                BigInteger primeVal = alphaPrimes.get(cInt % A_INT_ENCODING);

                /* Add this prime to our product */
                product = product.multiply(primeVal);
            }
        }

        /* Return the product */
        return product;
    }

    /**
     * @return Infinite stream of primes
     */
    private static Stream<BigInteger> primes()
    {
        return Stream.iterate(BigInteger.valueOf(2L), n -> n.add(BigInteger
                .ONE)).filter(n -> n.isProbablePrime(10));
    }
}

[Evan Oman]

The common way, written in Scala:

scala> def isAnagram(s1: String, s2: String): Boolean = s1.sorted.equalsIgnoreCase(s2.sorted)
isAnagram: (s1: String, s2: String)Boolean                                                   

scala> isAnagram("stressed", "desserts")                                                     
res1: Boolean = true                                                                         

scala> isAnagram("sad", "happy")                                                             
res2: Boolean = false

[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.

[Michael Ho]

You don't need sort or multiply or any fancy stuff

int[26] wordcount; //array containing encounter count of each character.

for each char:
    charnum <- ConvertCharToNum(char)
    wordcount[charnum]++

return wordcount

Check if the wordcount array of the two strings.

Computation
Does not require to sort, which is nlogn. This only requires a single pass to create wordcount array, thus n.
You can also optimize on aborting upon first index mismatch with this solution (You could also do this with the prime hashing, by aborting on first division yielding a decimal number).

Memory
The 26th prime is 97. Assume it's 100, 6 'z's would be 100⁶ = 10^12. It would take 39 bits, or 5 bytes to store (10¹² /log2). This is much less efficient to store a hash. If you want to be stricter, you could store only 1 wordcount, and have the second string count down instead of up.

Feature extension
If I want to accept numbers, the 36th prime is 367 (See Memory). With the array, it's just allocating another 10 index. It is also possible to add this feature without redeploying code, by replacing a specifically allocated array with a map of char to count

[Heiko Dudzus]

This is good. I adapted it to Haskell, recording letter frequencies in Maps/dictionaries. The Map data structure is already an instance of the Eq typeclass, so it was a one-liner to add the equality check:

import qualified Data.Map.Strict as M

-- incrementor for Map entries (used by Map's alter function)

inc Nothing = Just 1
inc (Just x) = Just (x+1)

-- produces a Map containing frequencies of elements in a given list (or Foldable)
-- e.g. a Map of frequencies of characters in a given word

frequencies :: (Foldable t, Ord k, Num a) => t k -> M.Map k a
frequencies = foldr (M.alter inc) M.empty

-- equality is already defined for Maps :)

isAnagram word1 word2 = frequencies word1 == frequencies word2

[MTD]

Best answer here. The prime trick is nice but as you said it gets way too expensive very fast.

[Ali Spittel]

In Python, I've always used the builtin Counter collection!

from collections import Counter

def isAnagram(word, check_word):
    return Counter(word) == Counter(check_word)

[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.

[Richard Orelup]

My quick PHP one

<?php

function isAnagram($word1, $word2) {
  $word1Array = str_split($word1);
  $word2Array = str_split($word2);
  sort($word1Array);
  sort($word2Array);

  return $word1Array === $word2Array;
}

var_dump (isAnagram("test","etst")); //returns bool(true)
var_dump (isAnagram("test","ftst")); //returns bool(false)

?>

[Ryan Palo]

Not super practical maybe, but using binary XOR is a sneaky way of checking for exact pairs of things (or finding an odd one out!). :) No sorting, and it works with punctuation!

# Detects whether two words are anagrams or not
def is_anagram?(word1, word2)
  (word1 + word2).chars.reduce(0) { |acc, curr| acc ^ curr.ord } == 0
end

puts "stressed is an anagram of desserts: #{is_anagram?('stressed', 'desserts')}"
# => true
puts "happy is an anagram of sad: #{is_anagram?('happy', 'sad')}"
# => false
puts "banana? is an anagram of b?naana: #{is_anagram?('banana?', 'b?naana')}"
# => true

[Ben Halpern]

Wouldn't "hello" and "hellooo" be a false positive here? I like the feel of this approach though.

[Ryan Palo]

Oh, good point. This is probably better suited to a “find the one unique letter” type problem. I like the solution that uses ‘uniq’ the best so far, I think.

[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.