Sélections de lettres parmi 7 lettres n'offrant aucune solution

**BBouille** · 05/08/2023, 15h51

Bonjour les amis,
Passionné de Scrabble je viens vous soumettre une nouvelle requête.
Je suis sûr que notre ami TBC92 avec sa logique pourra y répondre et vous aussi bien sûr.
Au Scrabble parmi les 15 premiers coups il faut au moins 2 voyelles et 2 consonnes.
Mais là il s'agit du premier coup où il faut trouver les tirages de sept lettres stériles c'est-à-dire ceux qui n'offrent aucune solution même de 2 lettres.
Faire 7 boucles me semble trop lourd, si quelqu'un avait une idée merci.

**tbc92** · 06/08/2023, 11h09

Je ne vois pas comment éviter 'plusieurs' boucles.
Soit 7 boucles.
Soit un peu moins, mais sans certitude que ça améliore réellement la performance.
On fait 2 boucles, on a 26x26=676 combinaisons de 2 lettres. On élimine toutes les combinaisons qui sont des mots existants. On élimine aussi les combinaisons de type XX ou ZZ, c'est à dire toutes les combinaisons de 2 fois une lettre qui est unique dans le jeu (les lettres très chères). Combien de combinaisons ça élimine ? Plus cette proportion est élevée, plus la piste est efficace.
Admettons qu'il nous reste 400 combinaisons (donc mon hypothèse, c'est qu'il existe 270 mots de 2 lettres à peu près, et 6 ou 7 lettres qui sont uniques)
On croise donc ces 500 x 500 combinaisons. Et on élimine toutes les combinaisons qui peuvent former des mots de 3 ou 4 lettres. On élimine aussi les combinaisons impossibles (celles avec 2 Z ou 3 H ou ... )
On recroise ça avec nos 500 combinaisons de 2 lettres, et on élimine toutes les combinaisons qui peuvent former des mots de 5 ou 6 lettres. On élimine aussi les combinaisons impossibles (celles avec 2 Z ou 3 H ou ... )
Et enfin, on recroise ça avec les 26 lettres et on élimine tous les mots de 7 lettres.

En réalité, ça complique pas mal la programmation, pour un bénéfice qui n'est pas garanti du tout.
Comme en plus, ce n'est pas un programme qu'on va faire tourner tous les jours, on se moque un peu d'économiser 5% ou 10% sur les temps de traitement.

Par curiosité, quand on regarde toutes les combinaisons de 2 lettres, combien on supprime de combinaisons parce que ça forme un mot de 2 lettres ? et combien on en supprime parce que on ne peut pas tirer XX ou ZZ ...
Et pareil quand on regarde toutes les combinaisons de 3 lettres.

**Flodelarab** · 06/08/2023, 14h58

Bonjour

Envoyé par BBouille

Faire 7 boucles me semble trop lourd.

Ben, c'est dommage. Il n'y a que 2.281.335 tirages possibles. Ensuite, il suffit d'élaguer. Il y a 81 mots de 2 lettres. Ils éliminent pas mal de tirages, de sorte qu'il n'en reste déjà plus que 460.282. Il ne reste plus qu'à éliminer les 3 lettres, 4 lettres, etc. Pense à enlever les 2-lettres des 3-lettres avant de les enlever des tirages puisque tu les as déjà filtrés.

tirages bruts :

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
A A A A A A A
A A A A A A B
A A A A A A C
A A A A A A D
A A A A A A E
A A A A A A F
A A A A A A G
A A A A A A H
A A A A A A I
A A A A A A J
A A A A A A K
A A A A A A L
A A A A A A M
A A A A A A N
A A A A A A O
A A A A A A P
A A A A A A Q
A A A A A A R
A A A A A A S
A A A A A A T
(...)
U U U U W X Z
U U U U W Y Z
U U U U X Y Z
U U U V V W X
U U U V V W Y
U U U V V W Z
U U U V V X Y
U U U V V X Z
U U U V V Y Z
U U U V W X Y
U U U V W X Z
U U U V W Y Z
U U U V X Y Z
U U U W X Y Z
U U V V W X Y
U U V V W X Z
U U V V W Y Z
U U V V X Y Z
U U V W X Y Z
U V V W X Y Z

tirages sans 2 lettres :

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
A E E E E E E                                                                                                                                                                 
A E E E E E G                                                                                                                                                                 
A E E E E E O                                                                                                                                                                 
A E E E E E P                                                                                                                                                                 
A E E E E E Q                                                                                                                                                                 
A E E E E E W                                                                                                                                                                 
A E E E E E Z                                                                                                                                                                 
A E E E E G G                                                                                                                                                                 
A E E E E G P                                                                                                                                                                 
A E E E E G Q                                                                                                                                                                 
A E E E E G W                                                                                                                                                                 
A E E E E G Z                                                                                                                                                                 
A E E E E O O                                                                                                                                                                 
A E E E E O P                                                                                                                                                                 
A E E E E O Q                                                                                                                                                                 
A E E E E O W                                                                                                                                                                 
A E E E E O Z                                                                                                                                                                 
A E E E E P P                                                                                                                                                                 
A E E E E P Q                                                                                                                                                                 
A E E E E P W                                                                                                                                                                 
(...)                                                                                                                                                                         
T T T V V X Z                                                                                                                                                                 
T T T V V Y Z                                                                                                                                                                 
T T T V W X Y                                                                                                                                                                 
T T T V W X Z                                                                                                                                                                 
T T T V W Y Z                                                                                                                                                                 
T T T V X Y Z                                                                                                                                                                 
T T T W X Y Z                                                                                                                                                                 
T T V V W X Y                                                                                                                                                                 
T T V V W X Z                                                                                                                                                                 
T T V V W Y Z                                                                                                                                                                 
T T V V X Y Z                                                                                                                                                                 
T T V W X Y Z                                                                                                                                                                 
T V V W X Y Z                                                                                                                                                                 
U U U U U U X                                                                                                                                                                 
U U U U U U Y                                                                                                                                                                 
U U U U U U Z
U U U U U X Y
U U U U U X Z
U U U U U Y Z
U U U U X Y Z

**BBouille** · 06/08/2023, 15h45

tbc92: C'est un peu ce que j'essaie de faire mais dès qu'on insère des requêtes SQL dans des boucles ça devient très lourd et lent.
Flodelarab: Comment parviens-tu à 2.281.335 tirages possibles?
En exagérant et en faisant 7 boucles de 26 lettres chacune on obtient 8*031*810*176 tirages.
Dans ces boucles on peut éliminer les tirages comprenant AA (comme ce mot existe), BBB, CCC, ... WW, XX, YY, ZZ.
Ça fera déjà beaucoup moins de tirages mais je ne sais pas encore combien, ça tourne.
Ensuite je comptais vérifier qu'il y avait au moins 2 voyelles ou 2 consonnes dans les tirages.
Puis on vire les tirages comprenant un mot de 2 lettres, 3, etc.
Mais je n'ose déjà pas imaginer le temps que ça prendrait avec des requêtes SQL.

**Flodelarab** · 06/08/2023, 16h13

En exagérant et en faisant 7 boucles de 26 lettres chacune on obtient 8*031*810*176 tirages.

Tu ne peux pas tirer UUUUUUU car il n'y a que 6 U. Donc 26^7 est surévalué.
tirages.sans.blanc.awk :

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#!/usr/bin/awk -f
 
 
{
	q[NR]=$2;
}
 
END{
 
	for (l[1]=1;l[1]<=26;l[1]++)
	{
		n[l[1]]++;
		if (n[l[1]]>q[l[1]])
		{
			n[l[1]]--;
			continue;
		}
		for (l[2]=l[1];l[2]<=26;l[2]++)
		{
			n[l[2]]++;
			if (n[l[2]]>q[l[2]])
			{
				n[l[2]]--;
				continue;
			}
			for (l[3]=l[2];l[3]<=26;l[3]++)
			{
				n[l[3]]++;
				if (n[l[3]]>q[l[3]])
				{
					n[l[3]]--;
					continue;
				}
				for (l[4]=l[3];l[4]<=26;l[4]++)
				{
					n[l[4]]++;
					if (n[l[4]]>q[l[4]])
					{
						n[l[4]]--;
						continue;
					}
					for (l[5]=l[4];l[5]<=26;l[5]++)
					{
						n[l[5]]++;
						if (n[l[5]]>q[l[5]])
						{
							n[l[5]]--;
							continue;
						}
						for (l[6]=l[5];l[6]<=26;l[6]++)
						{
							n[l[6]]++;
							if (n[l[6]]>q[l[6]])
							{
								n[l[6]]--;
								continue;
							}
							for (l[7]=l[6];l[7]<=26;l[7]++)
							{
								n[l[7]]++;
								if (n[l[7]]>q[l[7]])
								{
									n[l[7]]--;
									continue;
								}
								for (ind=1;ind<=7;ind++)
									printf("%c%s",64+l[ind],((ind==7)?"\n":" "));
								n[l[7]]--;
							}
							n[l[6]]--;
						}
						n[l[5]]--;
					}
					n[l[4]]--;
				}
				n[l[3]]--;
			}
			n[l[2]]--;
		}
		n[l[1]]--;
	}	
 
}

Code :

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

./tirages.sans.blanc.awk lettres.scrabble.frequences.txt > tirages.bruts.sans.blanc.txt

Mais je n'ose déjà pas imaginer le temps que ça prendrait avec des requêtes SQL.

Il faut se restreindre et ne compter que les quantités de lettres. les mots AH et HA du dictionnaire ont le même pouvoir éliminatoire sur les tirages. Donc, analyse ton dictionnaire, et compare le dictionnaire aux tirages de réglettes possibles. Si tu as testé "MU", ce n'est pas la peine de tester "MOU" et encore moins "MOULIN".

**BBouille** · 06/08/2023, 18h05

Ouille ouille ouille, c'est clair pour toi mais pas du tout pour mon petit cerveau.
Je sais que c'est surévalué, j'écartais les 7U, etc mais j'ai interrompu mon programme, il était parti pour quelques heures et j'atteignais un nombre de tirages astronomique.
Déjà je ne comprends pas la première ligne

Code :

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

q[NR]=$2

et je ne comprends pas non plus le tableau n que tu incrémentes et décrémentes.
Et enfin

Code :

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

for (l[3]=l[2];l[3]<=26;l[3]++)

tu pars de la lettre précédente si c'est ça pourquoi?

**Flodelarab** · 06/08/2023, 19h25

Envoyé par BBouille

Ouille ouille ouille, c'est clair pour toi mais pas du tout pour mon petit cerveau.

C'est le problème du forum Algorithmie. Chacun vient avec son langage.

"q" est un tableau associatif qui donne la quantité de chaque lettre dans le scrabble (somme : 100). La ligne que tu cites sert juste à charger le fichier. q["E"]=15, par exemple.
"l" est le tableau des 7 lettres du tirage. Pour "A B C D E F G", l[6]=F, par exemple.
"n" est le tableau associatif qui donne le nombre d'occurrence d'une lettre sur la réglette. Pour "A A A B E E F", n["A"]=3, par exemple.

tu pars de la lettre précédente si c'est ça pourquoi?

Si je parcours de 1 à 26 pour les 7 lettres, je vais écrire AB.... et BA.... mais c'est le même tirage ! Donc je pars de la lettre précédente et non de "1". Comme ça, pas de doublon. Et le tableau "n" est là pour éviter d'en piocher plus qu'il n'y en a dans le sac.

Quand la boucle commence, j'incrémente la quantité de la lettre. Et quand la boucle se termine, je décrémente pour laisser la place propre. Si on a dépassé le quota, je décrémente en urgence avant de passer la main au tour de boucle suivant.

Au cœur des 7 boucles, tu mets le code que tu veux. Ici, je ne fais qu'un affichage.

Un bon exercice d'algorithmie serait de faire la même chose sans 7 boucles "for". (avec un indice flottant).

Sélections de lettres parmi 7 lettres n'offrant aucune solution

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager