Discussion :

[abribus]

Bonjour,

Pour un programme perso de solveur de mots-croisés, j'aimerais bien pouvoir mettre un score sur la capacité des mots d'un dictionnaire à bien "croiser".

Pour un premier essai, je prends comme score du dictionnaire la somme du nombre de croisements entre mots pris 2 à 2.

Par exemple pour "HELLO", "CROSS" et "WORLD", le résultat donne 6 car il y a 6 combinaisons de croisements entre mots pris 2 par 2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
          |C|           |W|             |W|             |W|          |W|            |W|        
          |R|           |O|             |O|     |H|E|L|L|O|          |O|        |C|R|O|S|S|    
  |H|E|L|L|O|           |R|             |R|             |R|        |C|R|O|S|S|      |R|        
          |S|       |H|E|L|L|O|   |H|E|L|L|O|           |L|          |L|            |L|        
          |S|           |D|             |D|             |D|          |D|            |D|

Le code en question :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
package com.gitlab.super7ramp.croiseur.dictionary.tools;
 
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;
import java.util.stream.Stream;
 
/**
 * Computes a <em>crossability</em> score for the words of a given dictionary.
 * <p>
 * This score corresponds to the cumulated sum of the number of crossings between words taken 2 by
 * 2.
 * <p>
 * Example: "HELLO", "WORLD" will return 3 because there are three ways to cross these words:
 * <pre>
 *        |W|             |W|             |W|
 *        |O|             |O|     |H|E|L|L|O|
 *        |R|             |R|             |R|
 *    |H|E|L|L|O|   |H|E|L|L|O|           |L|
 *        |D|             |D|             |D|
 * </pre>
 */
public final class Scorer implements Callable<Long> {
 
    /** The number of words to process between each progress print. */
    private static final int WORDS_BETWEEN_EACH_PRINT_PROGRESS = 1_000;
 
    /** The words to compute for which to compute the number of crossings. */
    private final List<String> words;
 
    /**
     * A shared counter incremented each time the crossings of a word with all the other words have
     * been computed.
     */
    private final AtomicInteger counter;
 
    /**
     * Constructs an instance.
     *
     * @param wordsArg the words for which to compute the number of crossings
     */
    Scorer(final List<String> wordsArg) {
        words = wordsArg;
        counter = new AtomicInteger();
    }
 
    @Override
    public Long call() {
        return IntStream.range(0, words.size())
                        .parallel()
                        .mapToLong(i -> IntStream.range(i + 1, words.size())
                                                 .parallel()
                                                 .mapToLong(
                                                         j -> crossings(words.get(i), words.get(j)))
                                                 .sum())
                        .peek(i -> printProgress())
                        .sum();
    }
 
    /**
     * Computes the number of crossings between two given words.
     *
     * @param a a word
     * @param b another word
     * @return the number of crossings between the two given words
     */
    private static int crossings(final String a, final String b) {
        int numberOfCrossings = 0;
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                numberOfCrossings += eq(a.charAt(i), b.charAt(j));
            }
        }
        return numberOfCrossings;
    }
 
    /**
     * Returns 1 if given characters are equal, 0 otherwise.
     *
     * @param a left operand
     * @param b right operand
     * @return 1 if given characters are equal, 0 otherwise
     */
    private static int eq(final char a, final char b) {
        return a == b ? 1 : 0;
    }
 
    /**
     * Prints progress on standard output every {@value WORDS_BETWEEN_EACH_PRINT_PROGRESS} words
     * processed.
     */
    private void printProgress() {
        final int current = counter.incrementAndGet();
        if (current % WORDS_BETWEEN_EACH_PRINT_PROGRESS == 0) {
            final long completionPercentage = (long) ((current * 100.0) / words.size());
            final String progress =
                    String.format("[%d] %d / %d [%d %%]", Thread.currentThread().getId(), current,
                                  words.size(), completionPercentage);
            System.err.println(progress);
        }
    }
 
    /**
     * Usage: {@code scorer path/to/wordlist.txt}.
     *
     * @param args arguments
     * @throws ExecutionException   if computation fails
     * @throws InterruptedException if interrupted while computing
     */
    public static void main(final String[] args) throws ExecutionException, InterruptedException {
 
        if (args.length != 1) {
            System.err.println("Usage: scorer path/to/wordlist.txt");
            System.exit(1);
        }
 
        final Path wordListPath = Path.of(args[0]);
        List<String> words = null;
        try (final Stream<String> lines = Files.lines(wordListPath)) {
            words = lines.distinct().toList();
        } catch (final IOException e) {
            System.err.println("Failed to read " + wordListPath + ": " + e.getMessage());
            System.exit(2);
        }
 
        final ForkJoinPool pool = new ForkJoinPool(16);
        final Long result = pool.submit(new Scorer(words)).get();
 
        System.out.println("score = " + result);
    }
}

Ça marche, mais c'est lent pour un gros dictionnaire. Ça m'a pris ~2h pour UKACD (250 000 mots).

Je fais la somme des croisements entre un mot et tous les mots suivants dans la liste, pour chacun des mots de la liste. Ça revient à une complexité en O(n²) si je ne m'abuse. Je me demande s'il n'y a pas moyen de faire mieux.

Peut-être en faisant une première passe pour décomposer les mots en leur nombre de lettres et ensuite en sommant le nombre de combinaisons apportées par chaque lettre comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
HELLO ->           1E + 1H + 2L + 1O                   
CROSS -> 1C +                     1O + 1R + 2S         
WORLD ->      1D +         + 1L + 1O + 1R      + 1W    
---------------------------------------------------    
                             2  + 3  + 1

Si chaque lettre est unique dans un mot, c'est rapide : le nombre de combinaisons apportées par une lettre vaut alors (2 parmi m) où m est le nombre de mots où la lettre apparaît. Par exemple pour la lettre O dans l'exemple au-dessus, ça fait (2 parmi 3) ce que l'on peut calculer directement et qui vaut 3.

Mais dès que les lettres se répètent, je ne vois pas comment faire un calcul rapide.

Est-ce que vous voyez un meilleur algorithme ?

[AbsoluteLogic]

Salut,

Voici ma proposition. Je ne garantie pas qu'elle soit optimale, mais au moins elle est de complexité linéaire par rapport au nombre de mots.

Si je prends l'exemple de la lettre L avec les mots suivants : HELLO, CROSS, WORLD, LIBELLULE
Il y a 7 fois la lettre L en tout.
- HELLO contient 2 L, chacun de ces L va amener (7 - 2) = 5 croisements avec les autre mots. Donc 2 * 5 = 10 croisements en tout.
- CROSS contient 0 L, donc n'amène aucun croisement de L.
- WORLD contient 1 L, qui va amener (7 - 1) = 6 croisements avec les autre mots.
- LIBELLULE contient 4 L, chacun de ces L va amener (7 - 4) = 3 croisements avec les autre mots. Donc 4 * 3 = 12 croisements en tout.
Au total, on a 10 + 0 + 6 + 12 = 28 croisements en considérant les deux sens. Il faut prendre soin de diviser par 2 pour ne considérer chaque paire de mot qu'une fois. Donc 14.

Voilà, il faut donc faire ça pour chaque lettre, pour chaque mot. Donc l'algo:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# On compte le nombre global de chacune des lettres
occurences_lettres_global = {'a':0, 'b':0, ..., 'z':0}
Pour mot dans dictionnaire
  Pour lettre dans mot
    occurences_lettres_global[lettre] += 1
  Fin Pour
Fin Pour
 
score := 0
 
# On compte les croisements
Pour mot dans dictionnaire
  # On compte le nombre de chacune des lettres dans ce mot
  occurences_lettres_mot = {'a':0, 'b':0, ..., 'z':0}
  Pour lettre dans mot
    occurences_lettres[lettre] += 1
  Fin Pour
  # On applique la formule
  Pour (lettre, occurences_lettre_dans_mot) dans occurences_lettres_mot
    score += occurences_lettre_dans_mot * (occurences_lettres_global[lettre] - occurences_lettre_dans_mot)
  Fin pour
Fin Pour
 
Afficher score / 2

[Flodelarab]

Bonjour

Abribus, tu as tout identifié. On peut résumer cela par un compte des lettres. Si les mots sont dans un fichier, on fait cela en une ligne :

Code bash :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
$ awk -F '' '(NR>1){for (i=1;i<=NF;i++) total += nb[$i];} {for (i=1;i<=NF;i++) nb[$i]++;} END{print total;}' fichier.txt 
6

Pour vérifier, j'ai complexifié un peu :

sergent
gens
gegene
granges

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
$ awk -F '' '(NR>1){for (i=1;i<=NF;i++) total += nb[$i];} {for (i=1;i<=NF;i++) nb[$i]++;} END{print total;}' fichier.txt 
40

40. Ça a l'air juste.

[edit]
Je l'ai appliqué sur un dictionnaire français :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
$ time awk -F '' '(NR>1){for (i=1;i<=NF;i++) total += nb[$i];} {for (i=1;i<=NF;i++) nb[$i]++;} END{print total;}' dico.txt 
424637607956
 
real    0m0,803s
user    0m0,788s
sys     0m0,012s

Je ne sais pas si c'est interprétable
[/edit]

[anapurna]

salut

le plus simple est de creer un tableau de lettre du dictionnaire contenant les occurence de tout les mots
sans controle de doublon ou autre dans un mots on arrive a un algorithme simpliste comme celui-ci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
  // on genere le dictionnaire
   TabLettre[1..255] of integer
  POUR Mots IN Dicho  FAIRE
      POUR Lettres IN Mots FAIRE
         TabLettre[Ord(lettre)] := TabLettre[Ord(lettre)]  +1 
      FINPOUR 
  FINPOUR  
 
   // Traitement du mots rechercher
   POUR   Lettre IN MotsChercher 
       TabCpt[Ord(lettre)] := TabCpt[Ord(lettre)]+TabLettre[Ord(lettre)] - 1 ;
   FINPOUR  
 
   // Affichage
   POUR Lettre IN TabCpt 
     SI TabCpt[Ord(lettre)] <> 0 FAIRE
        Ecrire('nb occurence possible de croissement pour '+Lettre+ ' est '+TabCpt[Ord(lettre)] )
     FIN SI 
   FINPOUR

il y a des amelioration a faire c'est certain

[abribus]

Bonjour à tous,

Voilà, il faut donc faire ça pour chaque lettre, pour chaque mot. Donc l'algo:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# On compte le nombre global de chacune des lettres
occurences_lettres_global = {'a':0, 'b':0, ..., 'z':0}
Pour mot dans dictionnaire
  Pour lettre dans mot
    occurences_lettres_global[lettre] += 1
  Fin Pour
Fin Pour
 
score := 0
 
# On compte les croisements
Pour mot dans dictionnaire
  # On compte le nombre global de chacune des lettres
  occurences_lettres_mot = {'a':0, 'b':0, ..., 'z':0}
  Pour lettre dans mot
    occurences_lettres[lettre] += 1
  Fin Pour
  Pour (lettre, occurences_lettre_dans_mot) dans occurences_lettres_mot
    score += occurences_lettre_dans_mot * (occurences_lettres_global[lettre] - occurences_lettre_dans_mot)
  Fin pour
Fin Pour
 
Afficher score / 2

Merci ! C'est ce que je cherchais et que je ne voyais pas

On peut résumer cela par un compte des lettres. Si les mots sont dans un fichier, on fait cela en une ligne :

Code bash :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
$ awk -F '' '(NR>1){for (i=1;i<=NF;i++) total += nb[$i];} {for (i=1;i<=NF;i++) nb[$i]++;} END{print total;}' fichier.txt 
6

Super, en une seule boucle, merci ! j'ai repris mon code avec cette idée du coup :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
/**
 * For a given word list, computes a score corresponding to the capability of the
 * words to cross with each other: A <em>crossability</em> score.
 * <p>
 * This score corresponds to the cumulated sum of the number of crossings between words taken 2 by
 * 2.
 * <p>
 * Example: "HELLO", "CROSS", "WORLD" will return 6 because there are 6 ways to cross these
 * words 2-by-2:
 *
 * <ul>
 * <li>HELLO and CROSS:
 * <pre>
 *             |C|
 *             |R|
 *     |H|E|L|L|O|
 *             |S|
 *             |S|
 * </pre>
 * </li>
 * <li>HELLO and WORLD:
 * <pre>
 *        |W|             |W|             |W|
 *        |O|             |O|     |H|E|L|L|O|
 *        |R|             |R|             |R|
 *    |H|E|L|L|O|   |H|E|L|L|O|           |L|
 *        |D|             |D|             |D|
 * </pre>
 * </li>
 * <li>CROSS and WORLD:
 * <pre>
 *        |W|            |W|
 *        |O|        |C|R|O|S|S|
 *      |C|R|O|S|S|      |R|
 *        |L|            |L|
 *        |D|            |D|
 *
 * </pre>
 * </li>
 * </ul>
 */
public final class Scorer implements Callable<Long> {
 
    /** The words for which to compute the number of crossings. */
    private final List<String> words;
 
    /**
     * Constructs an instance.
     *
     * @param wordsArg the words for which to compute the number of crossings
     */
    Scorer(final List<String> wordsArg) {
        words = wordsArg;
    }
 
    @Override
    public Long call() {
        long score = 0;
        final Map<Character, Long> countedCharacters = new HashMap<>();
        for (final String word : words) {
            for (int i = 0; i < word.length(); i++) {
                score += countedCharacters.getOrDefault(word.charAt(i), 0L);
            }
            for (int i = 0; i < word.length(); i++) {
                countedCharacters.merge(word.charAt(i), 1L, Long::sum);
            }
        }
        return score;
    }
 
    /**
     * Usage: {@code scorer path/to/wordlist.txt}.
     *
     * @param args arguments
     */
    public static void main(final String[] args) {
        if (args.length != 1) {
            System.err.println("Usage: scorer path/to/wordlist.txt");
            System.exit(1);
        }
        final Path wordListPath = Path.of(args[0]);
        try {
            final List<String> words = Files.readAllLines(wordListPath);
            final Long result = new Scorer(words).call();
            System.out.println(result);
        } catch (final IOException e) {
            System.err.println("Failed to read " + wordListPath + ": " + e.getMessage());
            System.exit(2);
        }
    }
}

(Je pourrais utiliser un long[] plutôt qu'une Map<Character, Long> pour éviter le boxing char -> Character, long -> Long, et je pourrais faire le calcul à mesure que je lis le fichier plutôt que de construire la liste et ensuite itérer dessus, mais le résultat est déjà immédiat.)

Je l'ai appliqué sur un dictionnaire français :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
$ time awk -F '' '(NR>1){for (i=1;i<=NF;i++) total += nb[$i];} {for (i=1;i<=NF;i++) nb[$i]++;} END{print total;}' dico.txt 
424637607956
 
real    0m0,803s
user    0m0,788s
sys     0m0,012s

Je ne sais pas si c'est interprétable

Je vais appliquer le calcul sur les quelques dictionnaires que j'ai pour voir si quelque chose en ressort

[CosmoKnacki]

Il est possible d'accélérer les choses en construisant un tableau à 2 dimensions (caractère, occurrence) dont les valeurs sont donc le nombre de mots qui ont n fois le caractère c. L'avantage c'est que c'est trés rapide, et que ça n'utilise rien en mémoire.

Implémentation en PHP:

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/usr/bin/php8.2
<?php
 
$path = 'dico.txt';
 
if (false !== $handle = fopen($path, 'r')) {
 
    $result = 0;
 
    $chrMap = array_fill_keys(
        range(ord('A'), ord('Z')),
        [0,0,0,0,0,0,0,0] 
    );
 
    while (false !== $word = stream_get_line($handle, 128, "\n")) {
        foreach(count_chars($word, 1) as $chrByte => $chrCount) {
            $chrMap[$chrByte][$chrCount]++;
        }
    }
 
    fclose($handle);
 
    foreach($chrMap as $chr) {
        $chrSum = array_reduce(
            array_keys($chr),
            fn($carry, $index) => $carry + $chr[$index] * $index,
            0
        );
 
        foreach($chr as $occurrences => $wc) {
            $result += $occurrences * $wc * ($chrSum - $occurrences);
        }
    }
 
    $result /= 2;
 
    echo PHP_EOL, number_format($result, 0, '', ' ');
}

PHP facilite pas mal les choses avec sa fonction count_chars qui dans son mode 1 (ils auraient pu pondre une constante quand même!) renvoie un tableau dont les clefs sont les octets des caractères présents et les valeurs, le nombre d'occurrences du caractère.

(Je suis partie sur un dictionnaire type scrabble, tout en majuscules et sans accents, mais c'est facilement adaptable pour prendre en compte différentes casses ainsi que les espaces, les quotes et les tirets présents dans UKACD).

J'ai tenté de le transposer en awk, mais le résultat est décevant (4-5 fois plus lent), je donne le code tout de même:

Code awk :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/gawk -f
 
BEGIN {
    FS=""
}
 
{
    delete tmp
 
    for(i=1;i<=NF;i++) {
        tmp[$i]++
    }
 
    for(key in tmp) { 
        chrMap[key][tmp[key]]++
    }
}
 
END {
    for(chr in chrMap) {
        chrSum = 0
        for(occ in chrMap[chr]) {
            chrSum += occ * chrMap[chr][occ]
        }
        for(occ in chrMap[chr]) {
            result += occ * chrMap[chr][occ] * (chrSum - occ)
        }
    }
    printf("%'d", result/2)
}