Rangement de mots

[hammana]

J'ai récemment vu le défi suivant: Etant donnés les douze mots ci-dessous

ALE,GIN,MALT,KIR,SIROP,THE,MEDOC,WHISKY,SODA,CAFE,BIERE,PORTO

comment les ranger pour que tous les mots ne soient pris qu'une seule fois, et que deux mots consécutifs n'aient aucune lettre en commun.
Avis aux programmeurs qui voudraient trouver l'algorithme qui permet de trouver toutes les réponses possibles.

[Deliantha]

Un programmeur n'a aucune valeur ajoutée à l'exercice. En effet, un arbre tracé à la main est suffisant.
Il suffit juste remarquer que chacun des 12 mots comprend au moins une voyelle et on déduit les suites.

[C.Ret]

Ce qui est dangereux c'est le mélange de toutes ces boissons ! :we:

Deliantha je n'ai pas compris comment ton arbre portait ses fruits, mais surtout pourquoi il ne produirait que des voyelles ?!? :hein:

Moi j'aurais plutot tendance à utiliser mon potager et y faire pousser de l'adjacence en rang bien aligné et espacé.

[chan79]

J'ai récemment vu le défi suivant: Etant donnés les douze mots ci-dessous

ALE,GIN,MALT,KIR,SIROP,THE,MEDOC,WHISKY,SODA,CAFE,BIERE,PORTO

comment les ranger pour que tous les mots ne soient pris qu'une seule fois, et que deux mots consécutifs n'aient aucune lettre en commun.
Avis aux programmeurs qui voudraient trouver l'algorithme qui permet de trouver toutes les réponses possibles.

Salut
Si on veut trouver des solutions "à la main", il me semble qu'on a intérêt à placer d'abord ceux qui ont au moins un E. (d'accord, il y a 5!=120 façons). Ensuite, il y a assez peu de possibilités.... ?
Il faut intercaler au moins un mot entre ceux qui ont un E.
Exemple (ceux qui ont du E sont en rouge)
Le premier à placer est PORTO (une seule possibilité), puis SIROP, ...

SODA BIERE MALT WHISKY CAFE PORTO GIN ALE SIROP THE KIR MEDOC
Sinon, ça ne devrait pas résister longtemps aux programmeurs du forum :zen:

[hammana]

Salut
Si on veut trouver des solutions "à la main", il me semble qu'on a intérêt à placer d'abord ceux qui ont au moins un E. (d'accord, il y a 5!=120 façons). Ensuite, il y a assez peu de possibilités. Il faut intercaler au moins un mot entre ceux qui ont un E.
Exemple (ceux qui ont du E sont en rouge)
Le premier à placer est PORTO (une seule possibilité), puis SIROP, ...

SODA BIERE MALT WHISKY CAFE PORTO GIN ALE SIROP THE KIR MEDOC
Sinon, ça ne devrait pas résister longtemps aux programmeurs du forum :zen:

Il y a plus de 8000 combinaisons qui répondent à la question. On ne va pas très loin à la main.

[chan79]

Il y a plus de 8000 combinaisons qui répondent à la question. On ne va pas très loin à la main.

Ca ne m'étonne pas. Tout ce qu'on peut faire à la main, c'est en trouver quelques unes. Ca peut donner des idées pour l'algorithme.

[acoustica]

On pourrait les placer sur un cercle et s'autoriser une seule anomalie. On coupera ensuite à cet endroit-là.

[chan79]

On peut noter que si la BIERE a deux voisins, ce sont forcément MALT et SODA

[C.Ret]

Bonjour,

Il y a plusieurs algorithmes pour énumérer et afficher toutes les combinaisons possibles; les premiers qui viennent à l'esprit sont ceux qui utilisent plus ou moins la force brute pour lister de façon systématique toutes les combinaisons.

A partir d'un tel algorithme, on peut ensuite l'optimiser ou le simplifier. Effectivement en étudiant les solutions possibles pour le mot suivant. Mais il y a d'autres axes, comme pré-calculer les liaisons possibles. Par exemple en utilisant une matrice d'adjacence.

On a donc alors le moyen d'optimiser l'algorithme (en diminuant le nombre de calculs, la table d'adjacence étant par ces propriétés plus facile à exploiter qu'une fonction de contrôle qui rechercherait à chaque pas les éventuelles lettres communes entre les deux mots qui se suivent), mais aussi en cherchant à mémoization.

En effet, même en utilisant une table d'adjacence, notre algorithme reste malgré tout un compteur (ce qui n'est pas loin d'un simple algo par force brute).
Il n'est donc pas très efficace, il va essayer un grand nombre de combinaisons avant d'en trouver une qui permet d'enchainer les 12 mots.

Il va y avoir un effort de calcul non négligeable pour trouver une position pour par exemple les 6 premiers. Une fois cette première partie de l'enchainement trouvé, il va y avoir un second effort (=nombre de calculs et de test) pour tenter de placer les 6 suivants.
La boucle de recherche (même si elle prend du temps) va trouver aucune, une ou plusieurs combinaisons possibles et l'es affichera et comptabilisera.

Après avoir parcours les 6 mots inférieurs, elle modifiera l'ordre des 6 premiers. Et ainsi de suite.

Imaginons se qui arrive si l'ordre des 6 premier est alors modifier, mais que se soit toujours les 6 mêmes mots qui se trouve dans le première partie de notre palindrome.
Tel qu'elle est envisagée, notre recherche va refaire une nouvelle fois exactement les mêmes calculs et le même test pour lister (énumérer ou afficher) les positions possibles pour les 6 derniers mots.

Et il en sera ainsi, notre algorithme (uniquement optimisé par adjacence et de bonnes tables pré-calculées) refera toutes la série de calculs à chaque nouvelle combinaison des 6 premiers.

Et pour être clair, je n'es partagé la liste qu'en deux, mais en réalité la remarque vaut pour tout sous-ensemble de mots.
On économiserait un nombre non négligeable de calcul en mémorisant la liste (éventuellement vide) des combinaisons possibles lorsqu'il reste à placer 2, 3, 4, etc. mots.
En mémorisant les combinaisons possible, il serait alors facile de la afficher/comptabiliser sans refaire à l'infini les calculs de recherche des combinaisons.

Toute l'astuce est alors de trouver le moyen de facilement reconnaitre une situation déjà rencontrée au cours de recherche. C'est exactement la méthode que l'on emploie lors du calcul récursif de par exemple la suite de Fibonacci. On mémorise dans une table les valeurs de la suite au fur et à mesure du calcul récursif de façon à ne pas avoir à refaire toutes cette branche de l'arbre de calcul lors d'une prochaines évaluation. Ce qui fait vite économiser des efforts.

Pour la suite de Fibonacci, reconnaitre une situation déjà rencontrée est trivial, il suffit de que F(n) n'est pas déjà dans la table, l'indice n suffit à vérifier cela (avec peut-être une astuce pour marquer les valeurs calculées ou encore inconnue de la table !).

Ici, c'est un peu plus compliqué, la clef est un mot (par exemple THE) mais cela ne suffit pas à déterminer si la situation a déjà était rencontrée. Il nous faut aussi tenir compte des mots qu'il reste à placer (per exemple BIERE, KIR, MALT et SODA).

Pour caractériser cette situation, il me faut établir une table de correspondance à deux entrée, la première identifie l'indice du mot à placer et la seconde un code caractérisant le sous ensemble restant à placer.

Pour ma part, j'ai indexé numériquement les mots en fonction de leur position en mémoire (ordre alphabétique en fait):
Pour lister les façon de placer THE sera dans ma table de mémoziation placer aux coordonnées ( 11 , 1124 )
10 = Index de THE
562 = #1000110010_b = 2^9+2^5+2^4+2^1 = { BIERE, KIR, MALT, SODA }

Si cette liste de combinaison est déjà mémoriser, je l'ajoute/affiche.
Sinon, je la calcule sans oublier une fois toutes les combinaisons déterminées et de les mémoriser.

Pour déterminer les combinaisons possibles à partir de THE, j'utilise la table d'adjacence qui a deux rôles : donner pour chaque mot le(s) suivant(s) possible(s) et aussi éviter d'utiliser deux fois les mêmes mots (en mémorisant les mots déjà utilisé).

Code: Tout sélectionner

          BIERE  KIR MALT SODA
THE    :       x    o    x    o


Comme on peut le constater, il n'y a que deux suivants possible à partir de THE.
La boucle commence par essayer KIR
THE (KIR) , il convient donc de vérifier que le cas KIR, { BIERE+MALT+SODA } n'a pas déjà était rencontré; vérifier la table à la position ( 4, 546 ).

par chance, celle-ci a déjà été rencontrée, il y a deux combinaisons possible: on comptabilise et affiche et les mémorise déjà dans la table à la position ( 10, 562) c'est à dire pour THE, {BIERE+KIR+MALT+SODA}.
: ~~ THE (KIR) MALT BIERE SODA.
: ~~ THE (KIR) SODA BIERE MALT.

PAr contre pour le second suivant SODA la table de mémoziation est vide position ( SODA, {BIERE+KIR+MALT} ) :
~~ THE (SODA)

On utilisera donc la table d'adjacence, mais cette fois en étudiant la ligne concernant SODA
et ainsi de suite

Code: Tout sélectionner

          BIERE  KIR MALT
SODA   :       o    o    x


On gagnera du temps si la table de mémoziation contient les chaines élémentaires contenant deux ou trois mots seulement. il peut être facile d'ajouter ces situation lors de la construction de la table d'adjacence.
Il est important aussi de noter les impasses. C'est à faire au fur et à mesure, mais aussi lors de préparation de la tables d'adjacence.

Il faut également faire attention, on attend plusieurs milliers de combinaisons possible, les tables doivent être construire de façon à gérer convenablement la mémoire, de même qu'en cas d'appel par récurrence il faut s'attendre à une profondeur de recherche non négligeable.
Mais là cela dépend des systèmes et du langage de programmation.

Pour ma part, comme la mémorisation se fait par ajout des combinaisons pour chaque mot suivant possible, je profite qu'une grande partie de l'enchainement des mots en le même d'un rang à l'autre.

Ainsi, ma table de mémoziation ne contient pas les chaines (car cela multiplie de façon inutile et de façon importante les répétitions), mais point vers une table de hachage qui elle même pointe vers une table d'indexation des mots.
Le liste des mots n'est donc en pratique en mémoire qu'une seule fois dans la mémoire du système, les combinaisons sont obtenues par un indexage indirect, indexage qui est appelé par la table de mémoziation avec un décalage en fonction de la "profondeur".


En conclusion je rappelle les grande ligne de mon algorithme :

Code: Tout sélectionner

 - Saisir et mémoriser des MOTS,
 - Construire la table d'adjacence,
 - Construire les situations de base (un deux ou trois MOTs) de la table de mémoziation,
 - Initialiser l'indexation des combinaisons en fonction des situations de bases (rien de tel qu'un bon début pour une indexation efficace)
 - Initialiser la boucle de recherche, (piles et indicateurs indexés par le niveau de profondeur pour éviter d'utiliser des appels récursif)
 - Initialiser avec ALE au niveau 1
 - Boucle de recherche/affichage des combinaisons
       Pour le niveau en cours, 
         - vérifier si la situation est déjà mémorisée (table de mémoziation)
         - Sinon rechercher dans table d'adjacence les mots suivants
               Pour chacun des éventuels mots suivants les tester au niveau supérieur.
               Mémoriser les combinaisons (ou marquer l'absence de combinaison)
         - Afficher et compter les combinaisons trouvées
               Si nécessaire les ajouter à la table de mémoziation du mot en cours
    Si tous les mots ont été essayés pour le niveau 1, sortir de la boucle


Evidemment, ce n’est pas la seule façon de faire. On peut aussi envisager d’autres approches. En particulier, construire l’arbre des combinaisons en partant du bas. Peut être une excellente idée. Mais je n’ai pas essayé. En tout cas cela évitera mon approche « itérative » du problème.

Car même s’il est bien compliqué, mon algo n’est en fait qu’un compteur et en cela je le classe dans la catégorie des « recherche par force brute » même s’il est un peu optimiser.

Un stratégie par « diviser pour conquérir » doit aussi pouvoir monter son efficacité, l’idée étant de décomposer le problème des 12 MOTS en un sous-groupe plus facile à résoudre et ensuite d’associer en les permutant les différents sous-groupe de combinaison.

[hammana]

Bonjour,

Il y a plusieurs algorithmes pour énumérer et afficher toutes les combinaisons possibles; les premiers qui viennent à l'esprit sont ceux qui utilisent plus ou moins la force brute pour lister de façon systématique toutes les combinaisons.

A partir d'un tel algorithme, on peut ensuite l'optimiser ou le simplifier. Effectivement en étudiant les solutions possibles pour le mot suivant. Mais il y a d'autres axes, comme pré-calculer les liaisons possibles. Par exemple en utilisant une matrice d'adjacence.

On a donc alors le moyen d'optimiser l'algorithme (en diminuant le nombre de calculs, la table d'adjacence étant par ces propriétés plus facile à exploiter qu'une fonction de contrôle qui rechercherait à chaque pas les éventuelles lettres communes entre les deux mots qui se suivent), mais aussi en cherchant à mémoization.

En effet, même en utilisant une table d'adjacence, notre algorithme reste malgré tout un compteur (ce qui n'est pas loin d'un simple algo par force brute).
Il n'est donc pas très efficace, il va essayer un grand nombre de combinaisons avant d'en trouver une qui permet d'enchainer les 12 mots.

Il va y avoir un effort de calcul non négligeable pour trouver une position pour par exemple les 6 premiers. Une fois cette première partie de l'enchainement trouvé, il va y avoir un second effort (=nombre de calculs et de test) pour tenter de placer les 6 suivants.
La boucle de recherche (même si elle prend du temps) va trouver aucune, une ou plusieurs combinaisons possibles et l'es affichera et comptabilisera.

Après avoir parcours les 6 mots inférieurs, elle modifiera l'ordre des 6 premiers. Et ainsi de suite.

Imaginons se qui arrive si l'ordre des 6 premier est alors modifier, mais que se soit toujours les 6 mêmes mots qui se trouve dans le première partie de notre palindrome.
Tel qu'elle est envisagée, notre recherche va refaire une nouvelle fois exactement les mêmes calculs et le même test pour lister (énumérer ou afficher) les positions possibles pour les 6 derniers mots.

Et il en sera ainsi, notre algorithme (uniquement optimisé par adjacence et de bonnes tables pré-calculées) refera toutes la série de calculs à chaque nouvelle combinaison des 6 premiers.

Et pour être clair, je n'es partagé la liste qu'en deux, mais en réalité la remarque vaut pour tout sous-ensemble de mots.
On économiserait un nombre non négligeable de calcul en mémorisant la liste (éventuellement vide) des combinaisons possibles lorsqu'il reste à placer 2, 3, 4, etc. mots.
En mémorisant les combinaisons possible, il serait alors facile de la afficher/comptabiliser sans refaire à l'infini les calculs de recherche des combinaisons.

Toute l'astuce est alors de trouver le moyen de facilement reconnaitre une situation déjà rencontrée au cours de recherche. C'est exactement la méthode que l'on emploie lors du calcul récursif de par exemple la suite de Fibonacci. On mémorise dans une table les valeurs de la suite au fur et à mesure du calcul récursif de façon à ne pas avoir à refaire toutes cette branche de l'arbre de calcul lors d'une prochaines évaluation. Ce qui fait vite économiser des efforts.

Pour la suite de Fibonacci, reconnaitre une situation déjà rencontrée est trivial, il suffit de que F(n) n'est pas déjà dans la table, l'indice n suffit à vérifier cela (avec peut-être une astuce pour marquer les valeurs calculées ou encore inconnue de la table !).

Ici, c'est un peu plus compliqué, la clef est un mot (par exemple THE) mais cela ne suffit pas à déterminer si la situation a déjà était rencontrée. Il nous faut aussi tenir compte des mots qu'il reste à placer (per exemple BIERRE, KIR, MALT et SODA).

Pour caractériser cette situation, il me faut établir une table de correspondance à deux entrée, la première identifie l'indice du mot à placer et la seconde un code caractérisant le sous ensemble restant à placer.

Pour ma part, j'ai indexé numériquement les mots en fonction de leur position en mémoire (ordre alphabétique en fait):
Pour lister les façon de placer THE sera dans ma table de mémoziation placer aux coordonnées ( 11 , 1124 )
10 = Index de THE
562 = #1000110010_b = 2^9+2^5+2^4+2^1 = { BIERRE, KIR, MALT, SODA }

Si cette liste de combinaison est déjà mémoriser, je l'ajoute/affiche.
Sinon, je la calcule sans oublier une fois toutes les combinaisons déterminées et de les mémoriser.

Pour déterminer les combinaisons possibles à partir de THE, j'utilise la table d'adjacence qui a deux rôles : donner pour chaque mot le(s) suivant(s) possible(s) et aussi éviter d'utiliser deux fois les mêmes mots (en mémorisant les mots déjà utilisé).

Code: Tout sélectionner

          BIERRE  KIR MALT SODA
THE    :       x    o    x    o


Comme on peut le constater, il n'y a que deux suivants possible à partir de THE.
La boucle commence par essayer KIR
THE (KIR) , il convient donc de vérifier que le cas KIR, { BIERRE+MALT+SODA } n'a pas déjà était rencontré; vérifier la table à la position ( 4, 546 ).

par chance, celle-ci a déjà été rencontrée, il y a deux combinaisons possible: on comptabilise et affiche et les mémorise déjà dans la table à la position ( 10, 562) c'est à dire pour THE, {BIERRE+KIR+MALT+SODA}.
: ~~ THE (KIR) MALT BIERRE SODA.
: ~~ THE (KIR) SODA BIERRE MALT.

PAr contre pour le second suivant SODA la table de mémoziation est vide position ( SODA, {BIERRE+KIR+MALT} ) :
~~ THE (SODA)

On utilisera donc la table d'adjacence, mais cette fois en étudiant la ligne concernant SODA
et ainsi de suite

Code: Tout sélectionner

          BIERRE  KIR MALT
SODA   :       o    o    x


On gagnera du temps si la table de mémoziation contient les chaines élémentaires contenant deux ou trois mots seulement. il peut être facile d'ajouter ces situation lors de la construction de la table d'adjacence.
Il est important aussi de noter les impasses. C'est à faire au fur et à mesure, mais aussi lors de préparation de la tables d'adjacence.

Il faut également faire attention, on attend plusieurs milliers de combinaisons possible, les tables doivent être construire de façon à gérer convenablement la mémoire, de même qu'en cas d'appel par récurrence il faut s'attendre à une profondeur de recherche non négligeable.
Mais là cela dépend des systèmes et du langage de programmation.

Pour ma part, comme la mémorisation se fait par ajout des combinaisons pour chaque mot suivant possible, je profite qu'une grande partie de l'enchainement des mots en le même d'un rang à l'autre.

Ainsi, ma table de mémoziation ne contient pas les chaines (car cela multiplie de façon inutile et de façon importante les répétitions), mais point vers une table de hachage qui elle même pointe vers une table d'indexation des mots.
Le liste des mots n'est donc en pratique en mémoire qu'une seule fois dans la mémoire du système, les combinaisons sont obtenues par un indexage indirect, indexage qui est appelé par la table de mémoziation avec un décalage en fonction de la "profondeur".


En conclusion je rappelle les grande ligne de mon algorithme :

Code: Tout sélectionner

 - Saisir et mémoriser des MOTS,
 - Construire la table d'adjacence,
 - Construire les situations de base (un deux ou trois MOTs) de la table de mémoziation,
 - Initialiser l'indexation des combinaisons en fonction des situations de bases (rien de tel qu'un bon début pour une indexation efficace)
 - Initialiser la boucle de recherche, (piles et indicateurs indexés par le niveau de profondeur pour éviter d'utiliser des appels récursif)
 - Initialiser avec ALE au niveau 1
 - Boucle de recherche/affichage des combinaisons
       Pour le niveau en cours, 
         - vérifier si la situation est déjà mémorisée (table de mémoziation)
         - Sinon rechercher dans table d'adjacence les mots suivants
               Pour chacun des éventuels mots suivants les tester au niveau supérieur.
               Mémoriser les combinaisons (ou marquer l'absence de combinaison)
         - Afficher et compter les combinaisons trouvées
               Si nécessaire les ajouter à la table de mémoziation du mot en cours
    Si tous les mots ont été essayés pour le niveau 1, sortir de la boucle


Evidemment, ce n’est pas la seule façon de faire. On peut aussi envisager d’autres approches. En particulier, construire l’arbre des combinaisons en partant du bas. Peut être une excellente idée. Mais je n’ai pas essayé. En tout cas cela évitera mon approche « itérative » du problème.

Car même s’il est bien compliqué, mon algo n’est en fait qu’un compteur et en cela je le classe dans la catégorie des « recherche par force brute » même s’il est un peu optimiser.

Un stratégie par « diviser pour conquérir » doit aussi pouvoir monter son efficacité, l’idée étant de décomposer le problème des 12 MOTS en un sous-groupe plus facile à résoudre et ensuite d’associer en les permutant les différents sous-groupe de combinaison.

Merci pour ce pasage en revue des différentes approches du problème.
Après une semaine de reflexion j'ai eu la conviction qu'on ne peut pas éviter de passer par une sorte de force brute. J'ai trouvé un algorithme simple, qui ressemble un peu au vôtre . Je programme en Liberty Basic qui est relativemment lent, j'obtiens les 8000 et quelques réponses en 5 secondes. J'attend de voir d'autres idées sur la question.

[C.Ret]

Actuellement je teste mon algorithme en Microsoft BASIC v7.0 sur Commodoe C128D.

Evidemment, je n'obtiendrais pas les 8000 et quelques solutions en 5 s. ! :we:

[Dlzlogic]

Actuellement je teste mon algorithme en Microsoft BASIC v7.0 sur Commodoe C128D.

Evidemment, je n'obtiendrais pas les 8000 et quelques solutions en 5 s. ! :we:

Bonjour,
J'ai retrouvé un manuel de référence GwBasic pour Commodor. J'ai peut-être encore les disquettes, mais plus la machine depuis longtemps.

[C.Ret]

Bonjour,
J'ai retrouvé un manuel de référence GwBasic pour Commodor. J'ai peut-être encore les disquettes, mais plus la machine depuis longtemps.

Merci ! :we:

Mais l'avantage du BASIC sur le Commodore C128D est qu'il réside dans la ROM.
On allume l'écran, on allume le Commodre, on s'assoit et ça y est on peut saisir la première instruction (ou première ligne d'instruction). Même mon téléphone portable met plus de temps à démarrer !


En photo comme cela il ressemble à un ordinateur comme ceux d'aujourd'hui. Mais ça n'a rien à voir.


Et une disquette; on en a besoin que si l'on veut enregistrer son programme ou ses données. Mais on puet aussi utiliser une K7 audio. Ca marche aussi.

[Dlzlogic]

Magnifique.
Le Comodore que j'avais appartenait en fait à mon fils, (moi j'avais pas le temps de faire de l'informatique à la maison), puis un jour son alimentation est tombée en panne, le pauvre commençait à criser, naturellement pas possible de le faire réparer, mais j'ai fini pas me souvenir que j'avais acheté une machine du genre Alice (HS) et qu'il y avait donc une alime disponible. Je viens d'ouvrir mon armoire pleine de pièces diverses, et le crois bien qu'il est toujours, ainsi que l'alime, sous un tas de claviers et de câbles.
Ce serait effectivement amusant de le ressortir.

[chan79]

Magnifique.
Le Comodore que j'avais appartenait en fait à mon fils, (moi j'avais pas le temps de faire de l'informatique à la maison), puis un jour son alimentation est tombée en panne, le pauvre commençait à criser, naturellement pas possible de le faire réparer, mais j'ai fini pas me souvenir que j'avais acheté une machine du genre Alice (HS) et qu'il y avait donc une alime disponible. Je viens d'ouvrir mon armoire pleine de pièces diverses, et le crois bien qu'il est toujours, ainsi que l'alime, sous un tas de claviers et de câbles.
Ce serait effectivement amusant de le ressortir.

Ah, la nostalgie !
Tiens, je viens de retrouver le PC1500 de SHARP, avec son basic intégré. Je m'étais bien amusé avec ça, au début des années 80.
[img][IMG]http://imageshack.us/a/img35/7333/pc1500.gif[/img][/IMG]

[C.Ret]

J'ai fait mes premiers programmes sur la petite soeur de ce PC-1500; j'avais pas les moyen d'avoir un équipement aussi puissant !

Mon SHARP PC-1211 fonctionne toujours (ainsi que son interface/imprimante), mais hélas l'écran commence à se dégrader, il s'y développe une huile noire qui va bientôt masquer entièrement l'affichage.

Sinon concernant la recherche des enchaînements de mots; j'ai renoncé à faire afficher toutes les combinaisons, par contre, je les compte.

Pour le moment je peux affirmer qu'il y a au-moins
757 enchainements commençant par ALE,
1520 enchainements commençant par BIERE,
757 enchainement commençant par CAFE,
...

Les autres résultats vont bientôt arriver.

L'inconvénient de mon approche par mémoziation des combinaisons est qu'il y a un temps non négligeable de pré-calcul. En suite, lors des premiers dénombrements, le système apprend plus qu'il ne compte, c'est assez long.

Par contre, l'avantage est que le comptage est de plus en plus rapide (même sur un système à 2MHz et 8bits) on obtient le premier comptage en moins de 4h, puis moins de 2h, ...

J'ai dû interrompre mes travaux, mais je vais reprendre cela, c'est interessant de voir comment le système "apprend" les combinaisons.

j'ai vu aussi quelques répétitions et incohérences dans mon système. Je vais revoir cela et surtout modifier le code pour obtenir un horodatage, ce peut être interrssant de convenablement "quantifier" l'accélération du comptage au fur et à mesure de l'apprentissage.

[chan79]

J'ai fait mes premiers programmes sur la petite soeur de ce PC-1500; j'avais pas les moyen d'avoir un équipement aussi puissant !

Mon SHARP PC-1211 fonctionne toujours (ainsi que son interface/imprimante), mais hélas l'écran commence à se dégrader, il s'y développe une huile noire qui va bientôt masquer entièrement l'affichage.

Sinon concernant la recherche des enchaînements de mots; j'ai renoncé à faire afficher toutes les combinaisons, par contre, je les compte.

Pour le moment je peux affirmer qu'il y a au-moins
757 enchainements commençant par ALE,
1520 enchainements commençant par BIERE,
757 enchainement commençant par CAFE,
...

Les autres résultats vont bientôt arriver.

L'inconvénient de mon approche par mémoziation des combinaisons est qu'il y a un temps non négligeable de pré-calcul. En suite, lors des premiers dénombrements, le système apprend plus qu'il ne compte, c'est assez long.

Par contre, l'avantage est que le comptage est de plus en plus rapide (même sur un système à 2MHz et 8bits) on obtient le premier comptage en moins de 4h, puis moins de 2h, ...

J'ai dû interrompre mes travaux, mais je vais reprendre cela, c'est interessant de voir comment le système "apprend" les combinaisons.

j'ai vu aussi quelques répétitions et incohérences dans mon système. Je vais revoir cela et surtout modifier le code pour obtenir un horodatage, ce peut être interrssant de convenablement "quantifier" l'accélération du comptage au fur et à mesure de l'apprentissage.

salut
Evidemment, en basic, ça va moins vite...
J'ai distingué les cas suivants:
BIERE est en position 1 (à gauche)
BIERE est en position 2
BIERE est en position 3
BIERE est en position 4
BIERE est en position 5
BIERE est en position 6
Je dissocie chacun de ces cas en deux, car il n'y a que deux voisins possibles pour bière
J'ajoute ces 12 résultats et je multiplie le résultat par 2, compte tenu de la symétrie des solutions, pour trouver 9600. J'ai fait aussi un tableau disons de voisinage (12 x 12) avec 1 pour voisinage autorisé, 0 sinon.
Je suis en train d'ingurgiter la syntaxe du langage C. Je suis dans les headers et les prototypes ...

[Dlzlogic]

Bonjour,
Et les pointeurs ça donne quoi ?

[chan79]

Bonjour,
Et les pointeurs ça donne quoi ?

Salut Dlzlogic
Ben les pointeurs, c'est le chapitre suivant
Pour les boucles, les conditions ( if, while ...) même principe que le basic pour l'instant, pas trop dépaysé

[Dlzlogic]

Salut Dlzlogic
Ben les pointeurs, c'est le chapitre suivant
Pour les boucles, les conditions ( if, while ...) même principe que le basic pour l'instant, pas trop dépaysé

Tout à fait exact. Il y a une instruction qui n'existait pas en basic, c'est le switch. Elle existait en Fortran (ancien) sous la forme GO TO (et1, et2, ... etn), c'est une alternative très intéressante au if.
Bonne continuation.