Anagrams: Difference between revisions
No edit summary |
|||
Line 3: | Line 3: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<ada> |
<lang ada> |
||
with Ada.Text_IO; use Ada.Text_IO; |
with Ada.Text_IO; use Ada.Text_IO; |
||
Line 73: | Line 73: | ||
Close (File); |
Close (File); |
||
end Words_Of_Equal_Characters; |
end Words_Of_Equal_Characters; |
||
</ |
</lang> |
||
Sample output: |
Sample output: |
||
<pre> |
<pre> |
||
Line 84: | Line 84: | ||
</pre> |
</pre> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
<cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include <fstream> |
#include <fstream> |
||
#include <string> |
#include <string> |
||
Line 117: | Line 117: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</lang> |
||
Output: |
Output: |
||
abel, able, bale, bela, elba, |
abel, able, bale, bela, elba, |
||
Line 129: | Line 129: | ||
D 1, using Phobos (to download the word list you need the Tango Std Lib). |
D 1, using Phobos (to download the word list you need the Tango Std Lib). |
||
<d> |
<lang d> |
||
import std.stdio, std.stream; |
import std.stdio, std.stream; |
||
Line 143: | Line 143: | ||
writefln(a); |
writefln(a); |
||
} |
} |
||
</ |
</lang> |
||
== {{header|Factor}} == |
== {{header|Factor}} == |
||
Line 204: | Line 204: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
The key to this algorithm is the sorting of the characters in each word from the dictionary. The line <tt>Arrays.sort(chars);</tt> sorts all of the letters in the word in ascending order using a built-in [[quicksort]], so all of the words in the first group in the result end up under the key "aegln" in the anagrams map. |
The key to this algorithm is the sorting of the characters in each word from the dictionary. The line <tt>Arrays.sort(chars);</tt> sorts all of the letters in the word in ascending order using a built-in [[quicksort]], so all of the words in the first group in the result end up under the key "aegln" in the anagrams map. |
||
<java>import java.net.*; |
<lang java>import java.net.*; |
||
import java.io.*; |
import java.io.*; |
||
import java.util.*; |
import java.util.*; |
||
Line 233: | Line 233: | ||
System.out.println(ana); |
System.out.println(ana); |
||
} |
} |
||
}</ |
}</lang> |
||
Output: |
Output: |
||
[angel, angle, galen, glean, lange] |
[angel, angle, galen, glean, lange] |
||
Line 243: | Line 243: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<perl>use LWP::Simple; |
<lang perl>use LWP::Simple; |
||
use List::Util qw(max); |
use List::Util qw(max); |
||
Line 257: | Line 257: | ||
print "@$ana\n"; |
print "@$ana\n"; |
||
} |
} |
||
}</ |
}</lang> |
||
Output: |
Output: |
||
alger glare lager large regal |
alger glare lager large regal |
||
Line 268: | Line 268: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Python 2.5 shell input (IDLE) |
Python 2.5 shell input (IDLE) |
||
<python>>>> import urllib |
<lang python>>>> import urllib |
||
>>> from collections import defaultdict |
>>> from collections import defaultdict |
||
>>> words = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt').read().split() |
>>> words = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt').read().split() |
||
Line 292: | Line 292: | ||
>>> count |
>>> count |
||
5 |
5 |
||
>>></ |
>>></lang> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<ruby>require 'open-uri' |
<lang ruby>require 'open-uri' |
||
anagram = Hash.new {|hash, key| hash[key] = []} # map sorted chars to anagrams |
anagram = Hash.new {|hash, key| hash[key] = []} # map sorted chars to anagrams |
||
Line 311: | Line 311: | ||
p ana |
p ana |
||
end |
end |
||
end</ |
end</lang> |
||
Output: |
Output: |
||
["evil", "levi", "live", "veil", "vile"] |
["evil", "levi", "live", "veil", "vile"] |
Revision as of 15:23, 3 February 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Two or more words can be composed of the same characters, but in a different order. Using the word list at http://www.puzzlers.org/pub/wordlists/unixdict.txt, find the sets of words that share the same characters that contain the most words in them.
Ada
<lang ada> with Ada.Text_IO; use Ada.Text_IO;
with Ada.Containers.Indefinite_Ordered_Maps; with Ada.Containers.Indefinite_Ordered_Sets;
procedure Words_Of_Equal_Characters is
package Set_Of_Words is new Ada.Containers.Indefinite_Ordered_Sets (String); use Ada.Containers, Set_Of_Words; package Anagrams is new Ada.Containers.Indefinite_Ordered_Maps (String, Set); use Anagrams;
File : File_Type; Result : Map; Max : Count_Type := 1;
procedure Put (Position : Anagrams.Cursor) is First : Boolean := True; List : Set renames Element (Position); procedure Put (Position : Set_Of_Words.Cursor) is begin if First then First := False; else Put (','); end if; Put (Element (Position)); end Put; begin if List.Length = Max then Iterate (List, Put'Access); New_Line; end if; end Put;
begin
Open (File, In_File, "unixdict.txt"); loop declare Word : constant String := Get_Line (File); Key : String (Word'Range) := (others => Character'Last); List : Set; Position : Anagrams.Cursor; begin for I in Word'Range loop for J in Word'Range loop if Key (J) > Word (I) then Key (J + 1..I) := Key (J..I - 1); Key (J) := Word (I); exit; end if; end loop; end loop; Position := Find (Result, Key); if Has_Element (Position) then List := Element (Position); Insert (List, Word); Replace_Element (Result, Position, List); else Insert (List, Word); Include (Result, Key, List); end if; Max := Count_Type'Max (Max, Length (List)); end; end loop;
exception
when End_Error => Iterate (Result, Put'Access); Close (File);
end Words_Of_Equal_Characters; </lang> Sample output:
abel,able,bale,bela,elba caret,carte,cater,crate,trace angel,angle,galen,glean,lange alger,glare,lager,large,regal elan,lane,lean,lena,neal evil,levi,live,veil,vile
C++
<lang cpp>#include <iostream>
- include <fstream>
- include <string>
- include <map>
- include <vector>
- include <algorithm>
- include <iterator>
int main() {
std::ifstream in("unixdict.txt"); std::map<std::string, std::vector<std::string> > anagrams;
std::string word; size_t count = 0; while (std::getline(in, word)) { std::string key = word; std::sort(key.begin(), key.end()); // note: the [] operator automatically inserts a new value if key does not exist anagrams[key].push_back(word); count = std::max(count, anagrams[key].size()); }
in.close();
for (std::map<std::string, std::vector<std::string> >::const_iterator it = anagrams.begin(); it != anagrams.end(); it++) if (it->second.size() >= count) { std::copy(it->second.begin(), it->second.end(), std::ostream_iterator<std::string>(std::cout, ", ")); std::cout << std::endl; } return 0;
}</lang> Output:
abel, able, bale, bela, elba, caret, carte, cater, crate, trace, angel, angle, galen, glean, lange, alger, glare, lager, large, regal, elan, lane, lean, lena, neal, evil, levi, live, veil, vile,
D
D 1, using Phobos (to download the word list you need the Tango Std Lib). <lang d> import std.stdio, std.stream;
void main() {
string[][string] anags; foreach (string w; new BufferedFile("unixdict.txt")) anags[w.dup.sort] ~= w.dup; int lmax; foreach (a; anags) lmax = lmax < a.length ? a.length : lmax; foreach (a; anags) if (a.length == lmax) writefln(a);
} </lang>
Factor
"resource:unixdict.txt" utf8 file-lines [ [ natural-sort >string ] keep ] { } map>assoc sort-keys [ [ first ] compare +eq+ = ] monotonic-split dup 0 [ length max ] reduce '[ length _ = ] filter [ values ] map .
{ { "abel" "able" "bale" "bela" "elba" } { "caret" "carte" "cater" "crate" "trace" } { "angel" "angle" "galen" "glean" "lange" } { "alger" "glare" "lager" "large" "regal" } { "elan" "lane" "lean" "lena" "neal" } { "evil" "levi" "live" "veil" "vile" } }
Haskell
import Data.List groupon f x y = f x == f y main = do f <- readFile "./../Puzzels/Rosetta/unixdict.txt" let words = lines f wix = groupBy (groupon fst) . sort $ zip (map sort words) words mxl = maximum $ map length wix mapM_ (print . map snd) . filter ((==mxl).length) $ wix
Sample output:
*Main> main ["abel","able","bale","bela","elba"] ["caret","carte","cater","crate","trace"] ["angel","angle","galen","glean","lange"] ["alger","glare","lager","large","regal"] ["elan","lane","lean","lena","neal"] ["evil","levi","live","veil","vile"]
J
(#~a:~:{:"1)(]/.~/:~&>)<;.2]1!:1<'unixdict.txt' +-----+-----+-----+-----+-----+ |abel |able |bale |bela |elba | +-----+-----+-----+-----+-----+ |alger|glare|lager|large|regal| +-----+-----+-----+-----+-----+ |angel|angle|galen|glean|lange| +-----+-----+-----+-----+-----+ |caret|carte|cater|crate|trace| +-----+-----+-----+-----+-----+ |elan |lane |lean |lena |neal | +-----+-----+-----+-----+-----+ |evil |levi |live |veil |vile | +-----+-----+-----+-----+-----+
Java
The key to this algorithm is the sorting of the characters in each word from the dictionary. The line Arrays.sort(chars); sorts all of the letters in the word in ascending order using a built-in quicksort, so all of the words in the first group in the result end up under the key "aegln" in the anagrams map. <lang java>import java.net.*; import java.io.*; import java.util.*;
public class WordsOfEqChars {
public static void main(String[] args) throws IOException { URL url = new URL("http://www.puzzlers.org/pub/wordlists/unixdict.txt"); InputStreamReader isr = new InputStreamReader(url.openStream()); BufferedReader reader = new BufferedReader(isr);
Map<String, Collection<String>> anagrams = new HashMap<String, Collection<String>>(); String word; int count = 0; while ((word = reader.readLine()) != null) { char[] chars = word.toCharArray(); Arrays.sort(chars); String key = new String(chars); if (!anagrams.containsKey(key)) anagrams.put(key, new ArrayList<String>()); anagrams.get(key).add(word); count = Math.max(count, anagrams.get(key).size()); }
reader.close();
for (Collection<String> ana : anagrams.values()) if (ana.size() >= count) System.out.println(ana); }
}</lang> Output:
[angel, angle, galen, glean, lange] [elan, lane, lean, lena, neal] [alger, glare, lager, large, regal] [abel, able, bale, bela, elba] [evil, levi, live, veil, vile] [caret, carte, cater, crate, trace]
Perl
<lang perl>use LWP::Simple; use List::Util qw(max);
my @words = split(' ', get('http://www.puzzlers.org/pub/wordlists/unixdict.txt')); my %anagram; foreach my $word (@words) {
push @{ $anagram{join(, sort(split(//, $word)))} }, $word;
}
my $count = max(map {scalar @$_} values %anagram); foreach my $ana (values %anagram) {
if (@$ana >= $count) { print "@$ana\n"; }
}</lang> Output:
alger glare lager large regal abel able bale bela elba evil levi live veil vile angel angle galen glean lange elan lane lean lena neal caret carte cater crate trace
Python
Python 2.5 shell input (IDLE) <lang python>>>> import urllib >>> from collections import defaultdict >>> words = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt').read().split() >>> len(words) 25104 >>> anagram = defaultdict(list) # map sorted chars to anagrams >>> for word in words: anagram[tuple(sorted(word))].append( word )
>>> count = max(len(ana) for ana in anagram.itervalues())
>>> for ana in anagram.itervalues():
if len(ana) >= count:
print ana
['angel', 'angle', 'galen', 'glean', 'lange']
['alger', 'glare', 'lager', 'large', 'regal']
['caret', 'carte', 'cater', 'crate', 'trace']
['evil', 'levi', 'live', 'veil', 'vile']
['elan', 'lane', 'lean', 'lena', 'neal']
['abel', 'able', 'bale', 'bela', 'elba']
>>> count
5
>>></lang>
Ruby
<lang ruby>require 'open-uri'
anagram = Hash.new {|hash, key| hash[key] = []} # map sorted chars to anagrams
open('http://www.puzzlers.org/pub/wordlists/unixdict.txt') do |f|
words = f.read.split for word in words anagram[word.split().sort] << word end
end
count = anagram.values.map {|ana| ana.length}.max for ana in anagram.values
if ana.length >= count p ana end
end</lang> Output:
["evil", "levi", "live", "veil", "vile"] ["abel", "able", "bale", "bela", "elba"] ["elan", "lane", "lean", "lena", "neal"] ["alger", "glare", "lager", "large", "regal"] ["angel", "angle", "galen", "glean", "lange"] ["caret", "carte", "cater", "crate", "trace"]