Programming Challenge: Anagram checking.

(\f x y -> f x == f y) (sort . map toLower . filter isAlpha)

Haskell is pretty cool :)

This was fun! I'm doing this one in go. I'm fairly new to go, so if I'm making any obvious mistakes feel free to point them out :)

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	one := testAnagram([]string{"yes", "no"})
	two := testAnagram([]string{"HoSe", "shoE"})
	fmt.Println(one, two)
}

func testAnagram(str []string) bool {

	for i := range str {
		str[i] = strings.ToLower(str[i])
		temp := strings.Split(str[i], "")
		sort.Strings(temp)
		str[i] = strings.Join(temp, "")
	}

	return str[0] == str[1]
}

Edited with /u/Emerald_Knight's findings.

A C solution that counts characters:

bool is_anagram_of(char *a, char *b)
{
    size_t counts[256] = {0};
    for (; *a; ++a)
        counts[tolower(*a)] += (bool)isalpha(*a);
    for (; *b; ++b)
        counts[tolower(*b)] -= (bool)isalpha(*b);
    for (int i = 0; i < 256; ++i) {
        if (counts[i] != 0)
            return false;
    }
    return true;
}

def anagram(*words):
    normalized = [sorted(word.lower()) for word in words]
    return all(word == normalized[0] for word in normalized)

I always feel icky writing functions like this that work on specifically two inputs. So I've generalized the code to work with 0 or more strings (providing 0 or 1 string will always result in a True return value).

Edit:

O(n * m) runtime! :D (where the average word length is n and there are m words).

from collections import Counter

def anagram(*words):
    normalized = [Counter(word.lower()) for word in words]
    return all(word == normalized[0] for word in normalized)

Rust

I've only just started learning Rust and have only coded as a hobby. How'd I do?

fn main() {
    let s1 = "anagram".to_string();
    let s2 = "nag a ram".to_string();
    assert!(anagram(s1, s2)); // True
}

fn anagram(s1: String, s2: String) -> bool {
    let sorted_s1 = sort_string(s1);
    let sorted_s2 = sort_string(s2);
    sorted_s1 == sorted_s2
}

fn sort_string(mut s: String) -> Vec<u8> {
    s.retain(|c| !c.is_whitespace());
    let mut sorted_s = s.to_lowercase().into_bytes();
    sorted_s.sort_unstable();
    sorted_s
}

Edit: cargo bench puts it at 572 ns/iter (+/- 11) to run the function anagram():

mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn count_letters_bench(b: &mut Bencher) {
        b.iter(|| anagram("nag a ram".to_string(), "anagram".to_string()))
    }

}

Late, but here's a pure Bash 4+ solution:

#!/usr/bin/env bash

shopt -s nocasematch
set -- "${1//[[:space:]]}" "${2//[[:space:]]}"
string=$2

for (( i = 0; i < ${#1}; i++ )); do
	string=${string/"${1:i:1}"}
done

(( i == ${#2} && ${#string} == 0 ))
exit

I wanted to try it without doing a sort, so here's a questionably-readable solution in JavaScript (ES6) that compares the strings by counting instances of each character.

const getCharCountObject = string =>
  [...string.toLowerCase().replace(/[^a-z]/g, "")].reduce(
    (accumulator, letter) => ({
      ...accumulator,
      [letter]: (accumulator[letter] || 0) + 1
    }),
    {}
  );
const charCountObjectsEqual = (cc1, cc2) => {
  const firstKeys = Object.keys(cc1);
  return (
    firstKeys.length === Object.keys(cc2).length &&
    firstKeys.every(key => cc1[key] === cc2[key])
  );
};
const isAnagram = ([...strings]) =>
  strings.every(string =>
    charCountObjectsEqual(
      getCharCountObject(strings[0]),
      getCharCountObject(string)
    )
  );

Quick tests:

> isAnagram(['Madam Curie', 'Radium came', 'Radium came.'])
< true
> isAnagram(['Edward Gorey', 'Ogdred Weary', 'Regera Dowdy',  'E. G. Deadworry'])
< true
> isAnagram(['Madam Curie', 'Rdium came'])
< false

Julia version, it might be possible to do a non-allocating version, but I'm not sure how.

sorted_split(s) = lowercase(s) |> s->split(s,"") |> sort 

anagram(s1,s2) = all( s1 == s2 for (s1,s2) in zip(sorted_split(s1),sorted_split(s2)) )

@assert anagram("yes","no") == false
@assert anagram("restful","fluster") == true
@assert anagram("Madam Curie", "Radium came") == true

function test(s)
    f = [anagram(s1,s2)  for (s1,s2) in s]
    mean(f)
end

s = [(randstring(3),randstring(3)) for i=1:10_000]

Main> @time test(s)
0.022325 seconds (290.42 k allocations: 15.129 MiB, 25.91% gc time)   
0.0004

I've made version without any sorting, so I think, I might have one of the fastest versions here. Time complexity is linear, memory complexity is constant.

I've used python, which I've started with few days ago.

first = [ "abc", "def", "ghi" ]
second = [ "cab", "DeF", "ihg" ]

def encodeString(string):
    string = string.lower()
    total = 0
    for ch in string:
        val = ord(ch) - ord('a')
        # Now I have value of all letters. 
        # 'a' is 0, 'b' is 1, etc... Now, I can set the value to 2^x
        # so 'a' is 1, 'b' is 2, 'c' is 4... This will generate unique number
        # for each word. "ab" is 3, "bc" is 6, "abc" is 7, etc
        total += 2 ** val

    return total



def areStringsAnagrams(string1, string2):
    return len(string1) == len(string2) and encodeString(string1) == encodeString(string2)


for i in range(0, 3):
    for j in range(0, 3):
        print(areStringsAnagrams(first[i], second[j]))

^{Edit: Added syntax highlighting}

Figured I'd try something stupid and convoluted, so I came up with the idea to create two temporary directories, inside which, create a file for each letter in each word, then simply compare the two directories.

#!/bin/bash
t1=$(mktemp -d) && echo $1 | sed -e "s|.|touch $t1/\L&\n|g" | bash
t2=$(mktemp -d) && echo $2 | sed -e "s|.|touch $t2/\L&\n|g" | bash
diff $t1 $t2 && { echo Anagrams; }

By the time I finished I realized the flaw of course is that it doesn't account for repeating characters. "foo" and "oooooooooof" are considered anagrams. Oh well. And of course this has numerous other problems as well. Can't deal with spaces or a lot of punctuation. Probably exploitable by directory traversal attacks etc.

still in my kotlin comfort zone, heavily leaning on the stdlib

fun testAnagram(input1: String, input2: String) = input1.length == input2.length
    && input1.toLowerCase().toSortedSet() == input2.toLowerCase().toSortedSet()

I wanted to try my hand at this. I did something a little different, since the most reasonable approach I can think of in C appears to be here already. lazyGram does a few checks that should work in almost all cases, but it's probably still possible to confuse it and get a wrong result. That said, I haven't yet managed to mess it up yet, but maybe someone here can find a good test case.

int lazyGram(char *str1, char *str2)
{
  int sum1 = 0;
  int sum2 = 0;
  int count1 = 0;
  int count2 = 0;
  int anagram = 1;
  for(int i = 0 ; i < 256 ; i++)
  {
    sum1 += tolower(*(str1+i));
    sum2 += tolower(*(str2+i));
    if(*(str1+i))
    {
      count1++;
    }
    if(*(str2+i))
    {
      count2++;
    }
  }
  if(sum1 != sum2)
  {
    anagram = 0;
  }
  else if(count1 != count2)
  {
    anagram = 0;
  }
  else
  {
    for(int i = 0 ; i < count1 ; i++)
    {
      int found = 0;
      for(int j = 0 ; j < count2 ; j++)
      {
        if(tolower(*(str1+i)) == tolower(*(str2+j)))
        {
          found = 1;
        }
      }
      if(!found)
      {
        anagram = 0;
      }
    }
  }
  return anagram;
}

Second time submitting a solution. Yuss!

In Python:

word1=list(input('Gimmie a word!\n'))
word2=list(input('Gimmie another word!\n'))

word1.sort()
word2.sort()

word1s=''.join(word1)
word2s=''.join(word2)

if len(word1)==len(word2):
    if word1s.lower()==word2s.lower():
        print("S'an anagram, bruh.")
    else:
        print("S'not an anagram, bruh.")

Saw this pop up and thought it was this week's. Oops! Posting anyways since I already did it. Did mine in ruby:

def anagram_check(x, y)
	x.gsub(/\W/, '').downcase.chars.sort == y.gsub(/\W/, '').downcase.chars.sort
end

puts "Enter first word or phrase to check: "
word1 = gets.chomp
puts "Enter second word or phrase to check: "
word2 = gets.chomp

puts anagram_check word1, word2

Don't have a laptop on me right now and I'm a newbie but I'd sort them(not sure if sort functions would work on a string, so I'd probably assaign numbers to letters) and then compare both arrays

Write the worst--but still working--implementation that you can conceive of.

Here’s some ugly, ugly bash:

$ function sortstr () {
    tr [A-Z] [a-z] | grep -o . | sort | tr -d "\n"
    echo ""
}
$ function anagrams () {
    count="$(while read w1 w2; do sortstr <<< $w1; sortstr <<< $w2; done | sort | uniq | wc -l | tr -d ' ')"
    [[ $count = 1 ]] && echo 'anagrams' || echo 'not anagrams'
}
$ echo 'foo foo' | anagrams
anagrams
$ echo 'foo Foo' | anagrams
anagrams
$ echo 'foo oof' | anagrams
anagrams
$ echo 'foo off' | anagrams
not anagrams