Discussion :

[Pombor]

Bonjour,

Je suis quelque peu bloqué dans mon développement, en effet, je cherche à développer un solveur du jeu "Le mot le plus long" dans des chiffres et des lettres.

Actuellement je suis en mesure de trouver l'anagramme quand il y a 10 et 9 lettres. Mais pas quand on descend en-dessous.

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
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
 
var wordFound = ''
var copyArr = []
var lettersChosen = ['A', 'S', 'V', 'T', 'S', 'E', 'A', 'M', 'N', 'T']
 
function isAnagram(stringA, stringB) {
    stringA = stringA.toLowerCase().replace(/[\W_]+/g, "");
    stringB = stringB.toLowerCase().replace(/[\W_]+/g, "");
 
    const stringASorted = stringA.split("").sort().join("");
    const stringBSorted = stringB.split("").sort().join("");
 
    return stringASorted === stringBSorted;
}
 
function checkForEachWord(arr) {
    strLetters = ''
 
    for (i in arr)
        strLetters = strLetters + arr[i]
    for (var i in file) 
        if (isAnagram(strLetters, file[i])) {
            wordFound = file[i]
            return true
        }
    return false
}
 
function getOneOfTheLongestWord() {
    lettersChosen.forEach(letter => {
        copyArr.push(letter)
    })
    var index = 1
    var countLetter = 1
    var position = copyArr.length - index
    var savedArray = []
    var iteration = 0
    var test = checkForEachWord(copyArr)
    if (test == true)
        return true
 
    while (test == false) {
        copyArr.splice(position, 1)
        index++
        if (index > copyArr.length + 1) {
            index = 1
            countLetter++
        }
        console.log(copyArr + ' | ' + position)
        position = copyArr.length - index
        test = checkForEachWord(copyArr)
        copyArr = []
        lettersChosen.forEach(letter => {
            copyArr.push(letter)
        })
    }
 
    return true
}
 
getOneOfTheLongestWord()

Auriez-vous une idée de comment je peux gérer pour le cas où je retire 2 lettres et que je teste toutes les combinaisons possibles jusqu'à trouver un anagramme. Mon objectif de tester toutes les possibilités afin de trouver un anagramme.

[javatwister]

Salut,

J'ai du mal à décoder ton script mais je pense qu'on peut faire plus simple;
Le seul problème est le temps de traitement pour - mettons - 50000 entrées.
J'ai essayé ça, en simulant un dictionnaire (file) et un tirage quelconque, même s'il est trop long:

Code javascript :

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
// dictionnaire
const lettres={
	file:[
	"banane",
	"ban",
	"bonbon",
	"caramel",
	"esquimau",
	"chocolat",
	"bonobo",
	"bon",
	"annoter",
	"anonner",
	"non",
	"tomate",
	"abonne",
	"bonne",
	"boa"],
 
	// fonction de répérage des mots corrects
	mots:(data,draw)=>{
		const res=[];
 
		// pour chaque mot du dictionnaire
		data.forEach(v => {
			// on crée une copie du tirage et un compteur
			let ind=0, bis=draw.slice();
			// pour chaque lettre du mot
			Array.from(v).forEach(w=>{
				// si le tirage contient la lettre
				if(bis.includes(w)){
					// on enlève la lettre du tirage
					bis.splice(bis.indexOf(w),1);
					// et on incrémente le compteur
					ind++;
				}
			});
			// si le compteur correspond au nombre de lettres du mot
			if(ind==v.length){
				// on ajoute le mot dans le tableau des résultats
				res.push(v)
			};
		});
		// on retourne le tableau trié par longueur de mots et par ordre alphabétique
		return res.sort().sort((a,b)=>a.length-b.length).join("\n");
	}
}
 
alert(`Les mots valides sont \n${lettres.mots(lettres.file,"taanonnartie".split(""))}`)

[javatwister]

Ah non, apparemment ça reste relativement rapide: http://javatwist.imingo.net/lmlpl.php

[CosmoKnacki]

On représente chaque lettre par un plage de bits.
Par exemple, on alloue à la lettre A une plage de 5 bits (car il n'y a pas de mots dans le dictionnaire sélectionné avec plus de 5 lettres A). Un mot comme CHAT donnera donc la plage 00001 pour la lettre A, un mot comme HAMAC la plage 00011 (et non 00010 car on additionne pas, on décale et on ajoute 1, on verra pourquoi plus tard), ANANAS 00111, TARATATA 01111, ABRACADABRA 11111.

L'intérêt de cette représentation par plages est qu'avec elle il est très simple de contrôler si un groupe de lettres contient le nombre suffisant de lettres A pour satisfaire un autre mot. Si mon groupe de lettres contient 3 A, sa plage de bits pour A sera 00111, et avec l'opération sur les bits AND (&), je vérifie que MOT & MONGROUPE === MOT:

• CHAT: 00001 & 00111 = 00001 vrai
• HAMAC: 00011 & 00111 = 00011 vrai
• ANANAS: 00111 & 00111 = 00111 vrai
• TARATATA: 01111 & 00111 = 00111 faux
• ABRACADABRA: 11111 & 00111 = 00111 faux

Histoire de ne pas faire ce genre de tests lettre par lettre, à partir du dictionnaire choisi, on dresse une liste des 26 lettres triées en fonction du nombre de mots dans lesquels elles sont présentes, puis pour chacune d'elles on note le nombre maximal d'apparitions dans un mot afin de déterminer la taille des plages. Ensuite on répartit ces lettres en 5 groupes hétérogènes (c'est à dire que chaque groupe doit contenir des lettres fréquentes et peu fréquentes).
Chaque groupe correspond à un entier dans lequel chaque lettre appartenant à ce groupe a une plage de bits qui lui est allouée.

Code Javascript :

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
const encoder = {
 
    alphabet: new Map([
        ['W', { position:  0, width: 2, group: 0 }], ['Q', { position:  2, width: 2, group: 0 }],
        ['B', { position:  4, width: 3, group: 0 }], ['C', { position:  7, width: 4, group: 0 }],
        ['N', { position: 11, width: 5, group: 0 }], ['E', { position: 16, width: 6, group: 0 }],
 
        ['K', { position:  0, width: 3, group: 1 }], ['V', { position:  3, width: 3, group: 1 }],
        ['G', { position:  6, width: 3, group: 1 }], ['U', { position:  9, width: 4, group: 1 }],
        ['R', { position: 13, width: 4, group: 1 }],
 
        ['J', { position:  0, width: 2, group: 2 }], ['Z', { position:  2, width: 3, group: 2 }],
        ['D', { position:  5, width: 3, group: 2 }], ['L', { position:  8, width: 4, group: 2 }],
        ['I', { position: 12, width: 6, group: 2 }],
 
        ['X', { position:  0, width: 2, group: 3 }], ['H', { position:  2, width: 3, group: 3 }],
        ['P', { position:  5, width: 3, group: 3 }], ['O', { position:  8, width: 5, group: 3 }],
        ['A', { position: 13, width: 5, group: 3 }],
 
        ['Y', { position:  0, width: 2, group: 4 }], ['F', { position:  2, width: 3, group: 4 }],
        ['M', { position:  5, width: 4, group: 4 }], ['T', { position:  9, width: 5, group: 4 }],
        ['S', { position: 14, width: 7, group: 4 }]
    ]),
 
    proceed: function(letters) {
 
        let result = [0, 0, 0, 0, 0];
 
        for (const letter of letters) {
            const bitsRange = this.alphabet.get(letter);
            const mask = (2**bitsRange.width - 1) << bitsRange.position; // 2**5 - 1 => 11111 << 3 => 11111_000
 
            // on extrait la plage de bits de la lettre grâce au masque: 0111_00011_001 & 11111_000 = 00011_000
            let range = result[bitsRange.group] & mask;
 
            // on décale d'un bit vers la gauche et on "allume" le 1er bit: 00011_000 => 00110_000 => 00111_000
            range = (range << 1) | (1 << bitsRange.position);
 
            // par sécurité on applique de nouveau le masque pour éliminer un éventuel bit sortant de la plage
            // suite au décalage: 0000_11111_000 => 0001_11110_000 => 0001_11111_000 & 11111_000 = 0000_11111_000
            range &= mask;
 
            // on met à jour la plage avec la nouvelle via un OR: 0111_00011_001 | 00111_000 = 0111_00111_001
            result[bitsRange.group] |= range;
        }
 
        return result;
    }
};

Pourquoi 5 groupes? D'une part cela évite de dépasser les 32bits par groupe, d'autre part ces groupes "hétérogènes" sont à la fois communs a beaucoup de mots et en même temps assez discriminants pour pouvoir constituer un arbre de recherche efficace et pas trop profond:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const tree = {
    branches: new Map(),
 
    insert: function (w) {
        let current = this;
 
        for (const code of w.code) {
            if ( !current.branches.has(code) )
                current.branches.set(code, { branches: new Map() });
 
            current = current.branches.get(code);
        }
 
        delete current.branches;
 
        if ( !current.hasOwnProperty('leaves') )
            current.leaves = new Set();
 
        current.leaves.add(w.word);
    },
 
    find: function (code, current = this, level = 0) {
        if ( current.hasOwnProperty('leaves') )
            return current.leaves;
 
        let result = new Set();
 
        for (const branch of current.branches.keys()) {
            if ( (code[level] & branch) !== branch )
                continue;
 
            result = new Set([
                ...result,
                ...this.find(code, current.branches.get(branch), level + 1)
            ]);
        }
 
        return result;        
    } 
}

Les branches de premier niveau (celles qui partent du tronc) de cet arbre sont constituées du premier groupe, le deuxième groupe pousse sur le premier, le troisième sur le deuxième, etc.
Les feuilles, c'est les mots du dictionnaire!
À noter qu'avec cette arbre si une branche du niveau 5 comporte plusieurs mots, ces mots sont des anagrammes car les signatures que constituent ces groupes ne tiennent pas compte de l'ordre des lettres (et donc lors de la recherche on les chope toutes d'un coup).
Autre chose, dans la méthode find le résultat de la recherche est stocké dans une instance de Set, c'est pratique si on veut vérifier que tel ou tel mot est présent dans le résultat mais sinon ce n'est pas vraiment nécessaire, un simple tableau suffit.

Donc si la variable dico contient un tableau avec les mots du dictionnaire (en majuscule sans accent), voici comment on l'utilise:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
console.time('buildTree');
for (const word of dico) {
    tree.insert({ 'word': word, 'code': encoder.proceed(word) });
}
console.timeEnd('buildTree');
 
console.time('find');
let res = tree.find(encoder.proceed('LOUUXICNSNEASYKP'));
console.timeEnd('find');
 
console.log(res.size + ' result(s)');
 
// console.log(res);

La recherche est super rapide, quant à la construction de l'arbre, j'obtiens ~750 ms avec NodeJS et ~2700 ms avec Firefox, mais bon, la construction de l'arbre on la fait qu'une seule fois (on peut d'ailleurs le transformer en JSON et le recharger pour le reconstruire sans avoir du coup à charger le dictionnaire, mais c'est un autre sujet).

Pièce jointe: dictionnaire.js.gz.