### Write a script to identify an anagram

#### Peter Kim Frank on February 01, 2018

Inspired by this tweet from the always awesome Fermat's Library.
Fermat's Library
@fermatslibrary
Clever algorithm to find out whether or...
[Read Full]

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

In Ruby:

We might want to refactor into two functions

The

`?`

in Ruby is just another character, but it's commonly used in naming comparison methods like this.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. 🙂If we wanted the comparison to work for

`n`

words, we might take an approach like this:This would check if the "unique" array of sorted words is a length of one, indicating they are all the same.

In true Ruby style, we could monkey patch the

`Array`

class, like such:So then we could call:

Looking up methods on the

`Array`

class, I see that I can refactor the above to:This may be less clear to non-Rubyists, but that method is there for a reason for Ruby folks.

Following your train of thought was fun

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.

Hi Ben,

seems to have a small typo in your code (first part).

After "==" should be second_word, no?

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

The common way, written in Scala:

Always happy to provide Clojure answers ;)

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

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

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

^{6}= 10^{12.}It would take 39 bits, or 5 bytes to store (10^{12}/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

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:

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

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

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

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.

My quick PHP one

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!

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

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.

Alternatively,

Edit: Added sort-based solution for Elm.I think the primes thing was actually harder than what I did. Here is my 15-line Elm solution where you could also reuse the breakdown of how many of which letters were used. I could have turned it into 1 long line with the 3 import statements, but I won't do that to you. :)

## Don't take my word for it.

Here is a full program with tests that you can run over at elm-lang.org/try. Paste the code below in the left window and hit the Compile button.

Scheme R5RS using srfi-13:

First we define a LUT of the first 26 primes.

Next we define our function:

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':

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:

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.

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

The solution based on sort:

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

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 sumIt even performs better than sorting

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

In javascript you can do something like this:

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:

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

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.

delete could also be imported from Data.List

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:

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.

Rust way, could be done better.

This just compares the char vector directly after sorting them.

C++

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.

While this happens to work for

`stressed`

and`desserts`

this only checks for words which are reverse copies of each other, notanagrams.`add`

and`dad`

are anagrams (same letters) but this check does not catch it:I feel we need SPOILER warnings for the comments

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

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