On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Damien en début de semaine !

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;
    }

}

A bientôt pour un nouveau #KataOfTheWeek !