Vouter sel anagrammes.

Cette semaine, c'est Damien qui vous propose un #KataOfTheWeek : Anagrammes

Briefing du Kata : Étant donné en input un fichier texte 'dictionary' avec un mot par ligne, ton but est de grouper dans un fichier 'output' les mots par ligne d'anagrammes, séparés par une virgule.

Par exemple, pour le dictionnaire suivant :

dictionary

is
real
lief
sith
this
lear
si
eth
het
hits
file
the
earl
rale
hist
life

Un résultat possible serait :

output

is,si
this,sith,hits,hist
the,eth,het,
real,lear,earl,rale
life,lief,file

Attention, pour la suite, les majuscules et caractères spéciaux suivants ne devraient pas poser de problème ;)

dictionary

Crusty's
crustys
aAäáåâàÅ
aaaaaaaa
cCç
ccc
eEéèëê
eeeeee
iIíîï
iiiii
nNñ
nnn
oOöóôøÖ
ooooooo
uUüûùúÜ
uuuuuuu

output

Crusty's,crustys
aAäáåâàÅ,aaaaaaaa,
cCç,ccc,
eEéèëê,eeeeee
iIíîï,iiiii
nNñ,nnn
oOöóôøÖ,ooooooo
uUüûùúÜ,uuuuuuu

Facile ? Essaye un peu avec ce dictionnaire (attention, le fichier est encodé en ISO88591).

Maintenant, le vrai challenge consiste à optimiser ton algorithme pour avoir le résultat le plus rapide possible.

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

Une partie intuitive de la solution est de calculer pour chaque mot un hash qui serait le même pour deux anagrammes, puis stocker pour chaque hash la liste des anagrammes correspondants. Bref, en admettant que le hash sera (spoiler alert) un Integer, en Java 8+, ça donnerait quelque chose comme l'interface HashComputer.

Reste à déterminer un calcul de hash pertinent et efficace, et je te propose pour cela de profiter des propriétés intéressantes des nombres premiers. En effet, d'après la réciproque du théorème fondamental de l'arithmétique, tout produit de nombres premiers unique à l'ordre près des facteurs est égal à un nombre entier strictement positif unique.

Pour revenir à nos moutons, une solution efficace à notre problème serait d'assigner à chaque caractère un nombre premier et de calculer le hash d'un mot comme étant le produit des coefficients associés à chacun de ses caractères. Traduit en Java :

interface HashComputer {
    int compute(String word);
}

public Map<Integer, List<String>> groupByHash(HashComputer hashComputer, Stream<String> words) {
    return words.collect(Collectors.groupingBy(hashComputer::compute));
}

HashComputer hashComputer = new HashComputer() {

    private int getCoefficient(char c) {
        switch (c) {
            case 'a':
            case 'A':
            case 'ä':
            case 'á':
            case 'å':
            case 'â':
            case 'à':
            case 'Å':
                return 3;
            case 'b':
            case 'B':
                return 5;
            case 'c':
            case 'C':
            case 'ç':
                return 7;
            ...
            default:
                return 1;
        }
    }

    @Override
    public int compute(String word) {
        int hash = 1;
        String remaining = word;

        while (!remaining.isEmpty()) {
            char c = remaining.charAt(0);
            int coefficient = getCoefficient(c);
            hash *= coefficient;
            remaining = remaining.substring(1);
        }

        return hash;
    }

}

Votre équipe TakiVeille