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

[Peter Kim Frank]

Paging @heikodudzus , I feel like you always enjoy these challenges!

[Heiko Dudzus]

Hey, thank you very much! I'm glad you sent me a notice. I will look for some spare time! :)

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

[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

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

[Andrey Kostakov]

def isAnagram(a, b):
    return a == b[::-1]

[Evan Oman]

While this happens to work for stressed and desserts this only checks for words which are reverse copies of each other, not anagrams.

add and dad are anagrams (same letters) but this check does not catch it:

>>> def isAnagram(a, b):   
...     return a == b[::-1]
...                        
>>> isAnagram("dad", "add")
False                      

[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));
    }
}

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

[Daniel Camargo]

In javascript you can do something like this:

function isAnagram(s1, s2){
    return s1.split('').sort().toString() === s2.split('').sort().toString();
}

isAnagram('stressed', 'desserts');
// true
isAnagram('add', 'dad');
// true
isAnagram('happy', 'sad');
// false

[Conor James Giles]

Scheme R5RS using srfi-13:
First we define a LUT of the first 26 primes.

(define primes '(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))

Next we define our function:

(define (isAnagram a b) (let ((mult (lambda (l) (apply * (map (lambda (x) (list-ref primes (- (char->integer x) 97))) (string->list (string-downcase l))))))) (= (mult a) (mult b))))

To break it down, our function takes two string arguments a and b, and applies the internal function 'mult' to both.
Taking a closer look at 'mult':

(mult (lambda (l) (apply * (map (lambda (x) (list-ref primes (- (char->integer x) 97))) (string->list (string-downcase l))))))

It's a lambda expression which takes a string 'l', downcases it, converts it to a list of chars, and maps an anonymous lambda function across that list, then multiplies the resulting list of integers.
Taking a closer look at the anonymous lambda:

lambda (x) (list-ref primes (- (char->integer x) 97))

It quite simply finds the prime number corresponding to the code-point of each character in the list, minus 97 (the code-point for 'a', we can do this because of the earlier downcasing), a number which corresponds to each letter's ordinal value in the alphabet if a corresponds with 0.

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

?>