Rangement de mots

[C.Ret]

salut
Evidemment, en basic, ça va moins vite...

Dans le cas du Commodore C128D, c'est pas le BASIC (ou le fait qu'il soit uniquement interprété) qui pose problème, c'est plutôt la vitesse globale du système et la capacité limité du processeur:

La fréquence n'est que de 1 ou 2 MHz et comme comme les registres internes de son porcesseur sont de 8 bits, rien que pour déplacer (ou additionner) un nombre réel (4 octets), il faut au minimum 5 cycles (sur la page "0") ou 11 cycle (si changement hors de la plage mémoire iniitale) ou 33 cycles (si changemtn de banque mémoire).

Cela fait très vite quelques dizaines de µs, soit le temps qu'un multi-core actuel à 4 GHz met pour faire la même opération sur 33000 ou 66000 nombres réels du même type pour chacun des 'cores'. Donc un 4-core "calcul" entre 40000 et 264000 x plus vite !!!

Bon, en même temps, les système actuel font 2000 à 4000 trucs inutiles à chaque instant (système d'exploitation actuels obligent !), alors le rapport de force n'est pas aussi catastrophique. Mais quand-même cela donne à réflèchir !


Quand à ton idée de partager, les cas en fonction de la position du MOT le plus contraignient, c'est une excellente approche; elle fait partie des algorithme type "partager pour conquérir", ou comment découper de façon récursive le problème en sous-problèmes plus facile à résoudre !

[fatal_error]

Hello,

j'ai pas trop le temps de pondre le code, mais en partant du bas.
on considère la matrice d'adjacence (booléenne) A qui donne la liaison entre deux mots.
On remarque que A est symétrique.

On considère maintenant la matrice M d'adjance, dont les éléments sont des WordsList.
par exemple l'élément M(i,j) est composé de


avec GIL correspondant à mot(i) et ARBRE à mot(j)

l'idée principale c'est que en prenant le produit M*M on définit les relations (un peu à la Chasles) pour chaque trajet début/fin.
la multiplication de WordsList est donc définie par

Code: Tout sélectionner

WL1*WL2==
si WL1.empty ou WL2.empty, return emptyWordList
sinon
newWordsList;
pour toutes les listes de WL1 as l_1
 pour toutes les listes de WL2 as l_2
  si intersection de l_1 et l_2 vide
    l_1.concatenate(l_2) //il faut enlever le premier mot de l_2 qui est déjà le dernier mot de l_1
  finsi
 finpour
finpour
return newWordsList

Comme l_1 est au début de longueur 1, le produit de M donnera des chemins de longueur au moins 2 puis 4 etc...
donc M^4 devrait suffire pour lister toutes les possibilités. Bon ici, ca sent un peu, à voir....

Concernant l'optimisation:
comme M est symétrique, il n'est pas nécessaire de calculer les wordsList de la partie inférieure. Il faut juste remarquer que tous les chemins à prendre
pour M(i,j) sont les chemins reverse de M(j,i)

après ya éventuellement les optim de stockage comme encoder les string en int et toussa, mais je pense pas que ca soit bien utile (du moins sur les machines évoluées :lol3: )

[C.Ret]

Code: Tout sélectionner

ale...     757
biere...  1520
cafe...    757
gin...     362
kir...     410
malt...    504
medoc...  1538
porto...  1040
sirop...   656
soda...    640
the...     948
whisky...  468

TOTAL:    9600


Bizarrement, le nombre total de combinaisons est un nombre bien rond ??
Y aurait-il un calcul qui donne le résultat directement ?

[chan79]

Code: Tout sélectionner

ale...     757
biere...  1520
cafe...    757
gin...     362
kir...     410
malt...    504
medoc...  1538
porto...  1040
sirop...   656
soda...    640
the...     948
whisky...  468

TOTAL:    9600


Bizarrement, le nombre total de combinaisons est un nombre bien rond ??
Y aurait-il un calcul qui donne le résultat directement ?

Salut
Si on enlève le PORTO (pardon aux Portuguais !) on arrive à 3200

[C.Ret]

Salut
Si on enlève le PORTO (pardon aux Portuguais !) on arrive à 3200

Je confirme :

Code: Tout sélectionner

00:15'51"--------  ale     400     
00:33'41"--------  biere   508
00:42'49"--------  cafe    400
00:51'39"--------  gin     112
00:55'26"--------  kir     112
00:59'41"--------  malt    192
01:04'33"--------  medoc   576
01:09'40"--------  sirop   164
01:14'12"--------  soda    248
01:16'12"--------  the     360
01:20'46"--------  whisky  128
01:20'46"=======  total : 3200


[hammana]

Je confirme :

Code: Tout sélectionner

00:15'51"--------  ale     400     
00:33'41"--------  biere   508
00:42'49"--------  cafe    400
00:51'39"--------  gin     112
00:55'26"--------  kir     112
00:59'41"--------  malt    192
01:04'33"--------  medoc   576
01:09'40"--------  sirop   164
01:14'12"--------  soda    248
01:16'12"--------  the     360
01:20'46"--------  whisky  128
01:20'46"=======  total : 3200


Devant la difficulté de construire à titre individuel les combinaisons de mots acceptables j'ai opté pour la méthode suivante:

Représenter chaque mot par une lettre de A à L.

Commencer par établir une table de 12 lignes donnant pour chaque mot les mots qui peuvent le suivre ce qui permet de faire le test uniquement pour ces mots.

Etabir une table tb2() contenant toutes les combinaisons acceptables de 2 mots, elle a 56 lignes.

A partir de tb2() etablir une table t3() contenant toutes les combinaisons de 3 mots (208 lignes),
de même pour tb4(), tb5, etc. jusqu'à tb12() qui a 9600 lignes.

Chaque combinaison de mots est représentée par une chaîne de caractères. Voilà à titre d'exemple un extrait de la table tb12() qui contient toutes les combinaisons possibles:

GHLJBADCEFIK
GHLJBADCKIFE
GHLJBADFECKI
GHLJBADFIKCE
GHLJBADIFECK
GHLJBADIKCEF
GHLJBAECDFIK
GHLJBAECKIDF
GHLJBAECKIFD
GHLJBAEFDCKI

Le programme en Liberty Basic se déroule en 6 secondes. Je peux en fournir le listing à ceux qui le désirent.

[fatal_error]

bon, 3-4s pour moi. 9600combi
c'est un peu l'idée de hammama (donc avec matrice adjacence).
la seule astuce en plus c'est
m2=m*m;//M2
m8=m2*m2;//M4
m8=m8*m8;//M8
m8=m8*m2*m;//M11
ou m représente la matrice dont j'avais parlé au poste précédent.
du coup on stocke tout et on progresse sans avoir à tout recalculer.

les 3-4 peuvent être grandement améliorées je pense, je fais tout par copie de valeur :ptdr:

[C.Ret]

ou m représente la matrice dont j'avais parlé au poste précédent.
du coup on stocke tout et on progresse sans avoir à tout recalculer.

C'est une bonne méthode, je l'ai implémenté sur mon 8bit/2MHz et ça marche très bien. Il y a juste un souci, c'est qu'avec les 64ko de base, comme toutes les combinaisons doivent être mémorisé, je n'arrive pas au résultat final (OUT OF MEMROY ERROR en calculant le dernier produit matriciel.
Il va falloir que je "compresse" en utilisant une méthode de mémorisation plus efficace (par paresse j'ai pour l'instant une méthode de mémorisation des enchainemetn qui prend beaucoup de mémoire pour rien. Ce week-en, si j'ai le temps je tenterai de remédier à cela - ce n'est pas les solutons qui manquent !)

En fait, cette idée de considérer chaque étape comme un produit de matrice a l'énorme avantage d'exploiter au mieu la matrice d'adjacence; en organisnt les chose en pseudo-ligne et colonne, seul les "croisement" possible sont considéré.
Ce qui fait gagner un temps précieux, la méthode par force brute perdant un temps immense à tenter des "produits" impossibles.

[fatal_error]

outre le fait de compresser, on peut remarquer que m est "antisymetrique" dans le sens ou m(j,i) contient les chemins dans le sens inverse de m(i,j).

On peut alors se passer de stocker les coefficients m(j,i).
au lieu de stocker un chemin s, on peut stocker un chemin ordonne [s, order] ou order vaut 1 ou -1 (dans m(i,j) )

De fait en prenant le produit matriciel du genre

Code: Tout sélectionner

pour chaque ligne i
 pour chaque colonne c
  pour chaque colonne k de la matrice resultat, k>i
   si ji
   m(i,k)=m(i,j)*m(k,j,-1)
   finsi
finpour
finpour
finpour

ou m(k,j,-1) signifie prendre m(k,j) mais en reverse.
du coup ya pas besoin de stocker explicitement ces chemins reverse, on utilise plus que (n^2-n)/2 elements, et on gagne meme en temps puisque on calcule moitien moins de cellules

[LeJeu]

Ce qui fait gagner un temps précieux, la méthode par force brute perdant un temps immense à tenter des "produits" impossibles.

Bonjour, ici la force brutale...

Je suis parti bêtement sur une fonction récursive qui choisit le 1° mot puis se rappelle pour le 2° mot...

Pour ce genre de problème et de dimension : ca marche très bien: j'ai testé par exemple le nombre de façons de ranger 12 nombres ( sans aucune contrainte), ce qui donne donc 12! solutions
On trouve 479 0001 600 en 51 s.
Bien sûr le programme construit la liste, compte, mais n'imprime pas la solution trouvée !

Dans le cas qui nous intéresse , j'ai bien sûr utilisé la matrice 12*12 d'adjacence (construit bêtement sans même considérer la symétrie... j'ai honte)

Ensuite le programme construit les listes en regardant à chaque mot posé si c'est autorisé
Le nombre de contraintes étant énorme - ce n'est pas 12! tests qui sont nécessaires mais seulement
425 282 ( consultation d'une valeur de la matrice)

Code: Tout sélectionner

ellapsed time 0:00:00
Nombre  de solutions : 9600
Nombre  d'essais     : 425282


Je dois avoir un vieil ordi, il n'arrive pas bien à mesurer le temps passé

[EDIT]
J'oubliais, le programme ne nécessite pas de mémoire, il n'y a pas de stockage nécessaire des listes trouvées,

[C.Ret]

Merci.

Effectivement sur les machines actuelles la méthode de recherche par force brute est tout à fait envisageable.
C'est bien pour cela que je me suis amusé à faire l'excercice sur un ordinosuare.

avec 4 Ghz, 32 bits et 2 Go de RAM, code compilé, c'est quelque(s) seconde(s), le même principe appliqué à 1 MHz, 8 bits et 64 ko de RAM , code interprété, c'est .... beaucoup plus.

Rien que le nombre 4790001600 , c'est déjà toute une sinécure pour l'obtenir sans arrondi !

[LeJeu]

Merci

avec 4 Ghz, 32 bits et 2 Go de RAM, code compilé, c'est quelque(s) seconde(s), le même principe appliqué à 1 MHz, 8 bits et 64 ko de RAM , code interprété, c'est .... beaucoup plus.

Rien que le nombre 4790001600 , c'est déjà toute une sinécure pour l'obtenir sans arrondi !

J'ai bien compris le défi esthétique que tu te lançais sur ton ordinosaure.
Mais tu sais que même avec des htz en plus on retrouve la même problématique un peu plus loin ....

Le cran d'apres, pour 13, sans contrainte , on attaque les 10 minutes, les nombres d'essais se rapprochent de 2^32 ca devient dur de les compter.. il faut envisager la retenue sur un mot de 32 bit high....

Sinon si ça intéresse quelqu'un je suis en train de faire un petit benchmark pour savoir le prix d'un test, d'une affectation, d'un compteur, d'un appel de fonction, de la récurrence elle même , le tout en C compilé comme l'a bien entrevu C Ret.

C pur & dur ( pas C++) un poil au dessus de l'assembleur, Microsoft en l'occurence mais pas bien loin du Lattice utilisé par Dlzlogic.
Pas si loin de ton très cher PDP11-70 !!!!

[fatal_error]

salut leJeu,

tu pourras pas, t'as la boucle for qui traine dans les parages.
Ce que tu peux faire en revanche, c'est voir le code assembleur généré.

Tu peux également regarder comment fonctionne ton ALU.

Sinon pour ma part, je suis en train de tester le polymorphisme (sur les chemins (que je compose de sous chemins)) voir si ca améliore les perfs ou pas.

Et il reste bien sûr la fine question de pouvoir dénombrer de manière sexy. Parce que faire M*M...M 13 fois en mettant les diago à zéro, c'est pas très smart.

[Dlzlogic]

Bonsoir,
J'ai pas regardé le truc au début, mais ça commence à m'intéresser.
Si je le traite, j'utiliserai des listes et non pas des matrices d'adjacence, là ça commencera à être intéressant de comparer des méthodes très différentes.
J'ai pas tout suivi, donc l'hypothèse est bien toujours celle de départ, mais d'où vient 13, on suppose une treizième boisson ?
Pour l'évaluation des prix de test etc, ça m'intéresse. J'ai déjà fait ce genre de truc, mais c'était ponctuel, pour un point particulier.

[LeJeu]

Bonsoir,
J'ai pas regardé le truc au début, mais ça commence à m'intéresser.
Si je le traite, j'utiliserai des listes et non pas des matrices d'adjacence, là ça commencera à être intéressant de comparer des méthodes très différentes.
J'ai pas tout suivi, donc l'hypothèse est bien toujours celle de départ, mais d'où vient 13, on suppose une treizième boisson ?
Pour l'évaluation des prix de test etc, ça m'intéresse. J'ai déjà fait ce genre de truc, mais c'était ponctuel, pour un point particulier.

Matrice d'adjacence, c'est un grand mot ... c'est juste pour dire que l'on a pré-calculé à l'avance les voisins possibles (une demi matrice - car symétrique- hors diagonale - pour stocker les possibles)

13, oui c'était pour malmener les algos, comme si on rajoutait un nouveau mot, j'ai bien vu que C-ret est au bout des possibilités de son ordinosaure, je tente de même de pousser mes giga hertzs dans les cordes pour voir au final ce que l'algorithmique peut amener comme soluces

Reste aussi, la question de Fatal error est-ce que 9600 peut-être sexy ?

[Dlzlogic]

Salut Le_Jeu.
Ok, j'ai compris. Je m'y mets demain.
Je crois que l'intérêt de la manipe sera de voir si la méthode des listes, peut être sans limitation (ou presque), c'est ça qui me parait intéressant.
Donc, je résume pour être sûr : "calculer pour chaque mot, le nombre de solutions étant donné les hypothèses de départ. Je propose comme 13è boisson "WATER".

[C.Ret]

Donc, je résume pour être sûr : "calculer pour chaque mot, le nombre de solutions étant donné les hypothèses de départ. Je propose comme 13è boisson "WATER".

Bonne idée ça d'ajouter le même mot, comme cela nous pourrons confronter nos résultats :lol3: !


Sinon l'idée des listes me parait également une solution interessante. En lisant, j'ai tout de suite pensé à l'utilisation de "listes chainées".

Il faut juste régler la contrainte qu'un mot ne peut apparaitre qu'une seule fois. Donc, la composition du début de la liste influe de façon prépondérante sur les mots suivants possibles.
Est-dce que la facilité que procurrent les pointeurs pour chainer la liste de mot ne va pas être pénalisant pour obtenir le résultat et surtout le comptage. Si à chaque pointeurs, on doit faire un calcul monstrueux, ... ?
Je n'ai pas la réponse, mais c'est interessant de creuser le problème et j'attends avec impatience de voir quelle astuce ^(à laquelle je n'ai pas pensée) va être utilisée !

[LeJeu]

Bonne idée ça d'ajouter le même mot, comme cela nous pourrons confronter nos résultats :lol3: !

J'ai donc mis de l'eau dans mon wisky !

Code: Tout sélectionner

WATER ---> 362 solutions

ellapsed time 0:00:00
Nombre de solutions : [B]724[/B]

Je ne pense pas que l'utilisation de listes chainées soit une bonne idée ?
J'ai préféré garder un simple tableau des 13 indices sur le tableau des mots, et une matrice 13*13 des suivants possibles.....


[edit]- je corrige le temps

[fatal_error]

Est-dce que la facilité que procurrent les pointeurs pour chainer la liste de mot ne va pas être pénalisant pour obtenir le résultat et surtout le comptage. Si à chaque pointeurs, on doit faire un calcul monstrueux, ... ?

Théoriquement, le seul inconvénient de la liste chainée, c'est pour accéder à un élément en particulier.
Concaténer deux listes, c'est immédiat (il suffit de garder l'info: un pointeur vers l'élément de fin de la liste)

Ensuite, itérer sur la liste, c'est doublement plus couteux (à vu de nez, j'ai pas fait de comparaisons), parce qu'il faut lire une variable, et faire un saut. (avec un vecteur, il suffit de faire le saut), mais ca reste complètement néligeable face à un accès file I/O.

L'avantage en revanche, c'est que il n'y a pas besoin d'allouer une nouvelle zone mémoire pour un vecteur (qui va devenir plus gros et aura pe pas assez de mem contigue).

De toute façon, rien n'empêche de se créer des vecteurs de taille 13 directement. quitte à supprimer la mémoire après

[C.Ret]

J'ai donc mis de l'eau dans mon wisky !

Code: Tout sélectionner

WATER ---> 362 solutions

ellapsed time 0:00:00
Nombre de solutions : [B]724[/B]

J'ai fait de même, à ma grande surprise ce mot supplèmentaire réduit considérablement le nombre de solution. Ce que la mémoziation détecte immédiatement et j'ai ontenu rapidement la liste des 724 combinaisons.

De plus, toutes commenceNT par WATER GIN ... OU finisseNT par ... GIN WATER. Ce qui parait évident car GIN et le seul mot qui peut se lier à WATER !

Code: Tout sélectionner

      ALE BIERE CAFE GIN KIR MALT MEDOC PORTO SIROP SODA THE WATER WHISKY
ALE     \     x    x   o   o    x     x     o     o    x   x     x      o
BIERE   x     \    x   x   x    o     x     x     x    o   x     x      x
CAFE    x     x    \   o   o    x     x     o     o    x   x     x      o
GIN     o     x    o   \   x    o     o     o     x    o   o     o      x
KIR     o     x    o   x   \    o     o     x     x    o   o     x      x
MALT    x     o    x   o   o    \     x     x     o    x   x     x      o
MEDOC   x     x    x   o   o    x     \     x     x    x   x     x      o
PORTO   o     x    o   o   x    x     x     \     x    x   x     x      o
SIROP   o     x    o   x   x    o     x     x     \    x   o     x      x
SODA    x     o    x   o   o    x     x     x     x    \   o     x      x
THE     x     x    x   o   o    x     x     x     o    o   \     x      x
WATER   x     x    x   o   x    x     x     x     x    x   x     \      x
WHISKY  o     x    o   x   x    o     o     o     x    x   x     x      \

01:01'   31:ALE    ... GIN WATER    31
02:30'   73:BIERE  ... GIN WATER    42
03:32'  104:CAFE   ... GIN WATER    31
     '     :GIN                    none
04:57'  116:KIR    ... GIN WATER    14
05:13'  140:MALT   ... GIN WATER    24
07:19'  220:MEDOC  ... GIN WATER    80
08:04'  268:PORTO  ... GIN WATER    48
09:37'  290:SIROP  ... GIN WATER    22
09:59'  306:SODA   ... GIN WATER    24
11:49'  348:THE    ... GIN WATER    42
12:43'  710:WATER GIN ...          362
13:28'  724:WHISKY ... GIN WATER    14

 TOTAL  724  COMBINAISONS           2188017  CONSULTATIONS MAT.ADJACENCE


Comme les enchainements sont symétriques, c'est normal d'avoir autant de WATER BIN ... que de de ... BIN WATER, il suffit juste d'inverser l'ordre des mots !

362 = 31 + 41 + 31 +14 + 24 + 80 + 48 + 22 + 24 + 42 + 14 = 724/2 :we: