Tävlingsprogrammering/Uppgifter/Anagram

ANAGRAM

Ett ord är anagram till ett annat ord, om bokstäverna i det första har kastats om i det senare. adrenalin är anagram till ledarinna och läsekrets är anagram till stärkelse för att ta två ganska långa ord som exempel. Men ibland kan ett ord ha flera anagram, som till exempel speldator, ledarpost datorspel och repsoldat. Vi säger att vi funnit en grupp bestående av 4 anagram. Skriv ett program, som för givna ord tar reda på den största gruppen av anagram.

Programmet ska läsa listan med ord från filen anagram.dat. Filen inleds med ett tal n, (n ≤ 30000), som anger antalet ord. Därefter följer n rader med ett ord på varje rad. Varje ord innehåller ≤ 16 bokstäver valda bland versalerna A. . . Z. Programmet ska först skriva ut hur många anagram den största gruppen innehåller, och därefter själva orden, i godtycklig ordning.

Körningsexempel:

Filen anagram.dat med innehållet 
14 
VELA 
LEVT 
ELEV 
AVEL 
LEVE 
LAVE 
ALV 
ELVA 
VAL 
LEVA 
VALL 
LAV 
VALE 
TELE 

ska ge svaret: 

Den största gruppen innehåller 6 ord. 
ELVA 
AVEL 
VALE 
VELA 
LEVA 
LAVE

Lösning

En enkel och i min uppfattning också elegant lösning är att använda tabeller. Nycklarna utgörs av de sorterade bokstäverna från orden. I körningsexemplet ovan skulle ELVA och AVEL båda hamna under nyckeln AELV.

Kodningen blir enkel i tex Perl:

open(INFILE, "anagram.dat") or die "\nkan inte öppna anagram.dat\n";
chomp($n=<INFILE>);
$big=0;
while ($n>0) {
	$n--;
	chomp($x=<INFILE>);
	$k=join('', sort(split(/ */,$x)));
	push @{$h{$k}}, $x;	
	$b=scalar(@{$h{$k}});
	if ($b>$big) {
		$big=$b;
		$bigKey=$k;
	}
}
print "\nDen största gruppen innehåller $big ord.\n";
foreach (@{$h{$bigKey}}) {
	print "$_\n";
}

Lösningsexempel i Java. Tricket är som sagt att sortera bokstäverna i orden.

import java.util.*;
import java.io.*;

public class Anagram
{
	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen anagram.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\anagram.dat"));

		//Antalet ord.
		int nr = scan.nextInt();

		//HashMap där vi sparar orden med deras bokstäver sorterade som nyckel.
		HashMap <String, LinkedList<String>> map = new HashMap <String, LinkedList<String>> ();

		//Läser in alla orden.
		for(int i = 0; i<nr; i++)
		{
			//Läser in ordet.
			String s = scan.next();

			//Sorterar bokstäverna i ordet.
			char [] bokstaver = s.toCharArray();
			Arrays.sort(bokstaver);

			//Skapar ett sorterat ord.
			String sorted = new String(bokstaver);

			//Hämtar listan över tidigare ord som innehåller samma bokstäver.
			LinkedList <String> ord = map.get(sorted);

			//Om listan inte fanns, så skapar vi den.
			if(ord==null)
			{
				ord = new LinkedList <String> ();

				//Lägger till listan med ord med det sorterade ordet som söknyckel.
				map.put(sorted, ord);
			}

			//Lägger till ordet i listan.
			ord.add(s);
		}

		//Iterator för alla ordgrupperna.
		Iterator <LinkedList<String>> it = map.values().iterator();

		//Den största anagram-gruppen.
		LinkedList <String> biggest = it.next();

		//Går igenom alla ordgrupperna och kollar vilken som är störst.
		while(it.hasNext())
		{
			LinkedList<String> list = it.next();

			if(list.size()>biggest.size())
			{
				biggest = list;
			}
		}

		//Skriver ut svaret.
		System.out.println("Den största gruppen innehåller " + biggest.size() + " ord.");

		//Skriver ut alla orden.
		for(String s : biggest) System.out.println(s);
	}
}

Lösning i Haskell.

-- Anagram
module Main where
import IO
import Data.List
import Data.Foldable (sequenceA_)

main = do {
	ih <- openFile "anagram.dat" ReadMode;
		
	content <- hGetContents ih;
	
	rader <- return $ lines content;
	svar <- return $ (getAns $ tail rader);
	
	putStrLn $ "Den storsta gruppen innehaller " ++ (show $ length svar) ++ " ord.";
	sequenceA_ [putStrLn s | (_,s) <- svar];
	
	hClose(ih)
}

getAns :: [String] -> [(String,String)]
getAns s = snd $ maximum $ map (\x -> (length x, x) ) $ groupBy eqFst $ sort $ map (\x -> (sort x, x)) s
	where eqFst a b = (fst a) == (fst b)