views:

994

answers:

8

A word is an anagram if the letters in that word can be re-arranged to form a different word.

Task:

  • The shortest source code by character count to find all sets of anagrams given a word list.
  • Spaces and new lines should be counted as characters
  • Use the code ruler

    ---------10--------20--------30--------40--------50--------60--------70--------80--------90--------100-------110-------120

Input:

a list of words from stdin with each word separated by a new line.

e.g.

A
A's
AOL
AOL's
Aachen
Aachen's
Aaliyah
Aaliyah's
Aaron
Aaron's
Abbas
Abbasid
Abbasid's

Output:

All sets of anagrams, with each set separated by a separate line.

Example run:

./anagram < words
marcos caroms macros
lump's plum's
dewar's wader's
postman tampons
dent tend
macho mocha
stoker's stroke's
hops posh shop
chasity scythia
...

I have a 149 char perl solution which I'll post as soon as a few more people post :)

Have fun!

EDIT: Clarifications

  • Assume anagrams are case insensitive (i.e. upper and lower case letters are equivalent)
  • Only sets with more than 1 item should be printed
  • Each set of anagrams should only be printed once
  • Each word in an anagram set should only occur once

EDIT2: More Clarifications

  • If two words differ only in capitalization, they should be collapsed into the same word, and it's up to you to decide which capitalization scheme to use for the collapsed word
  • sets of words only have to end in a new line, as long as each word is separated in some way, e.g. comma separated, or space separated is valid. I understand some languages have quick array printing methods built in so this should allow you to take advantage of that if it doesn't output space separated arrays.
A: 

Python, O(n^2)

import sys;
words=sys.stdin.readlines()
def s(x):return sorted(x.lower());
print '\n'.join([''.join([a.replace('\n',' ') for a in words if(s(a)==s(w))]) for w in words])
codewarrior
This is... incredibly slow. :P It also outputs each set of anagrams multiple times, equal to the number of anagrams in the set.
Amber
(Oh, and it also outputs individual words which aren't anagrams on their own line, which doesn't appear to be part of the specified output.)
Amber
Why ; at end of line, that is not Python!
Tony Veijalainen
+2  A: 

Python, 167 characters, includes I/O

import sys
d={}
for l in sys.stdin.readlines():
 l=l[:-1]
 k=''.join(sorted(l)).lower()
 d[k]=d.pop(k,[])+[l]
for k in d:
 if len(d[k])>1: print(' '.join(d[k]))

Without the input code (i.e. if we assume the wordlist already in a list w), it's only 134 characters:

d={}
for l in w:
 l=l[:-1]
 k=''.join(lower(sorted(l)))
 d[k]=d.pop(k,[])+[l]
for k in d:
 if len(d[k])>1: print(' '.join(d[k]))
Amber
Remove the space between `:` and `print`, and use semicolons. I think you could use `input()`.
KennyTM
This produces case-sensitive results. Compare against Dan Andreatta or my solutions.
Mark Rushakoff
Fixed, now that case-insensitivity was specified as required.
Amber
Python 2.6.1 on my machine claims: "NameError: name 'lower' is not defined"
MtnViewMark
Yeah, that was a mistake on my part, I fixed it (should be `.lower()` instead of `lower(...)`).
Amber
+1  A: 

AWK - 119

{split(toupper($1),a,"");asort(a);s="";for(i=1;a[i];)s=a[i++]s;x[s]=x[s]$1" "}
END{for(i in x)if(x[i]~/ .* /)print x[i]}

AWK does not have a join function like Python, or it could have been shorter...

It assumes uppercase and lowercase as different.

Dan Andreatta
Will this only print out words which are anagrams? Or will it also print out words with no other anagram on their own lines?
Amber
The original version prints everything. Update with the fix.
Dan Andreatta
I think this must be for Gnu awk (gawk) only. Standard awk doesn't have the function asort.
MtnViewMark
@MtnVieweMark: you are correct, this is for `gawk`
Dan Andreatta
+10  A: 

Powershell, 104 97 91 86 83 chars

$k=@{};$input|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)}
$k.Values|?{$_[1]}|%{"$_"}

Update for the new requirement (+8 chars):

To exclude the words that only differ in capitalization, we could just remove the duplicates (case-insensitvely) from the input list, i.e. $input|sort -u where -u stands for -unique. sort is case-insenstive by default:

$k=@{};$input|sort -u|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)} 
$k.Values|?{$_[1]}|%{"$_"} 

Explanation of the [char[]]$_|%{$_+0}|sort -part

It's a key for the hashtable entry under which anagrams of a word are stored. My initial solution was: $_.ToLower().ToCharArray()|sort. Then I discovered I didn't need ToLower() for the key, as hashtable lookups are case-insensitive.

[char[]]$_|sort would be ideal, but sorting of the chars for the key needs to be case-insensitive (otherwise Cab and abc would be stored under different keys). Unfortunately, sort is not case-insenstive for chars (only for strings).

What we need is [string[]][char[]]$_|sort, but I found a shorter way of converting each char to string, which is to concat something else to it, in this case an integer 0, hence [char[]]$_|%{$_+0}|sort. This doesn't affect the sorting order, and the actual key ends up being something like: d0 o0 r0 w0. It's not pretty, but it does the job :)

Danko Durbić
This Powershell is starting to freak me out ;)
Dan Andreatta
Looks like perl.
Alex
I'm accepting this because 1. it conforms to all the requirements 2. it's the highest voted answer, and 3. I haven't seen much power shell code golfing before :)
Charles Ma
+3  A: 

Ruby, 94 characters

h={};(h[$_.upcase.bytes.sort]||=[])<<$_ while gets&&chomp;h.each{|k,v|puts v.join' 'if v.at 1}
Mark Rushakoff
This is a pretty Perl-ish approach, so I expect that somebody will be able to knock off at least 5-10 characters with a Perl solution.
Mark Rushakoff
+4  A: 

Haskell, 147 chars

prior sizes: 150 159 chars

import Char
import List
x=sort.map toLower
g&a=g(x a).x
main=interact$unlines.map unwords.filter((>1).length).groupBy((==)&).sortBy(compare&).lines

This version, at 165 chars satisifies the new, clarified rules:

import Char
import List
y=map toLower
x=sort.y
g&f=(.f).g.f
w[_]="";w a=show a++"\n"
main=interact$concatMap(w.nubBy((==)&y)).groupBy((==)&x).sortBy(compare&x).lines

This version handles:

  1. Words in the input that differ only by case should only count as one word
  2. The output needs to be one anagram set per line, but extra punctuation is acceptable
MtnViewMark
Just my first attempt -- I'm sure it can be squeezed.
MtnViewMark
It's so nice to see that something close to idiomatic, readable Haskell also scores pretty well in code golf!
Thomas
Agreed, this is probably my favorite answer :)
Charles Ma
A: 

C++, 542 chars

#include <iostream>
#include <map>
#include <vector>
#include <boost/algorithm/string.hpp>
#define ci const_iterator
int main(){using namespace std;typedef string s;typedef vector<s> vs;vs l;
copy(istream_iterator<s>(cin),istream_iterator<s>(),back_inserter(l));map<s, vs> r;
for (vs::ci i=l.begin(),e=l.end();i!=e;++i){s a=boost::to_lower_copy(*i);
sort(a.begin(),a.end());r[a].push_back(*i);}for (map<s,vs>::ci i=r.begin(),e=r.end();
i!=e;++i)if(i->second.size()>1)*copy(i->second.begin(),i->second.end(),
ostream_iterator<s>(cout," "))="\n";}
TC
Notes: (1) Actual count as shown is a little higher because I threw in some newlines for readability (main() can be on a single line) (2) Slightly compressed yet readable version: http://codepad.org/JtB1AHrE
TC
+10  A: 

Perl, 59 characters

chop,$_{join'',sort split//,lc}.="$_ "for<>;/ ./&&say for%_

Note that this requires Perl 5.10 (for the say function).

Michael Carman
MtnViewMark
@MtnViewMark: To protect backward compatibility the features added to Perl in version 5.10 must be explicitly enabled: `perl -M5.010 ana-perl.pl < wordlist` How that should effect golf scores is debatable.
Michael Carman