[shell] Jeu du pendu

Bonsoir à tous,
J'ai eu un TP en cours qui consiste à faire un jeu du pendu en shell.
N'ayant jamais pratiquer ce langage avant ce tp, je sollicite votre aide pour une erreur que je rencontre avec mon script.

Voici l'énoncé de ma première question :

Écrivez une fonction « motAuHasard » qui affiche un mot tiré au hasard dans le fichier dico.dic, ce mot devra faire 6 caractères ou plus pour être utilisable (la variable système RANDOM permet de générer des nombres aléatoires. Par exemple $(($RANDOM%nombdredelignes)) calcule un nombre au hasard compris entre 0 et nombrelignes.
Attention la variable RANDOM, donne une valeur entre 0 et 32767, le fichiers mots contenant plus de 32767 lignes, il faudra tirer 2 valeurs aux hasard et les multiplier pour obtenir une valeur assez grande et en calculer ensuite le modulo.
Voici ce que j'ai fait

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#!/bin/bash   motAuHasard () { while [$nbcaract < 6] do #calcule des deux aléatoire rdm = $(($RANDOM%32767)) rdmm = $(($RANDOM%32767))   #multiplication des deux aléatoire modulo = expr $rdm \* $rdmm echo $modulo #calcul modulo nbligne= expr $modulo % 50 echo $nbligne #Cherche la ligne du mot mot = sed -n "$nbligne" dico.dic echo $mot #calcule du nombre de caractère nbcaract = ${#mot} echo $nbcaract done }

---

Lorsque je l’exécute j’obtiens l'erreur suivante :
line 6 : 6] : no such file or directory
Merci

Bonjour,

Peux-tu déplacer ton post dans la section correspondante (si sous linux, il y a un forum dédier (shell et commande gnu), si sous unix en général, il y a aussi un forum shell et commande posix.

Sinon, en survolant un peu ton programme, quelques remarques:
- Le shebang (#!/bin/bash) doit-être obligatoirement sur la 1ère ligne.
- on voit à la fois une utilisation de expr et une utilisation de $((...)) qui est un peu la même chose...
- la syntaxe sur la valorisation de tes variables n'est pas je pense ce que tu veux, qui je pense est le résultats des commandes que tu passes, donc les 2 syntaxes possibles:

Code:

---

mot = sed -n "$nbligne" dico.dic

---

Doit s'écrire soit:

Code:

---

mot=$(sed -n "$nbligne" dico.dic)

---

ou

Code:

---

mot=`sed -n "$nbligne" dico.dic`

---

comme tu le remarquera, dans un premier temps, j'ai retiré les espaces autour du signe '=' car sinon, le shell considère ta variable comme une commande.
puis j'ai soit englobé ta commande de $(...) ou de backquote (`) qui sont les deux syntaxe pour dire au shell courant que c'est une commande à éxécuter dans un sous-shell.
Cas particulier, cette syntaxe est sous-entendu pour la forme $((...)) mais il ne faut toujours pas mettre d'espace autour du signe '=' pour signifie la valorisation d'une variable.
-Concernant l'erreur que tu rencontres, c'est l'inverse du signe '=', il faut un espace apres '[' et avant ']', donc while [ ... ] .
Après, je te conseilles d'aller dans la session tutoriel, pour compulser ceux concernant les shell...

Merci pour cette réponse.
Cela m'a bien aidé.

Voici le code avec quelque changements notamment au niveau de la boucle while qui n' était pas bonne et du sed pour bien chercher à partir du numéro de ligne. Si je rencontre d'autre problème sur le jeu je viendrai poster ici.

Code:

---

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

#!/bin/bash   motAuHasard () { nbcaract=0 while [ $nbcaract -le 6 ] do #calcule des deux aléatoire rdm=$(($RANDOM%32767)) rdmm=$(($RANDOM%32767)) echo $rdm echo $rdmm #multiplication des deux aléatoire modulo=$(expr $rdm \* $rdmm) echo $modulo #calcul modulo nbligne=$(expr $modulo % 28) echo $nbligne #Cherche la ligne du mot mot=$(sed -n "$nbligne"p dico.dic) echo $mot #calcule du nombre de caractère nbcaract=${#mot} echo $nbcaract done }

---

j'ai demandé à un modo de déplacer le sujet.

Bonjour

Soit un dictionnaire, fichier texte ne contenant qu'un mot par ligne, que nous appelerons 'dico.txt'.

Si un pendu a besoin d'un dico ayant uniquement besoin des mots de 6 lettres ou plus, on peut utiliser l'expression régulière '......' ou '.\{6\}' dans un filtre.

Code:

---

grep '......' dico.txt

---

OU

Code:

---

grep '.\{6\}' dico.txt

---

Donc, dans le programme, le mot serait tiré aléatoirement dans cet extrait:

Code:

---

mot=$(grep '......' dico.txt | sed -n "$nbligne"p )

---

Les tests de longueur deviennent alors inutiles

heu?

Citation:

---

ce mot devra faire 6 caractères ou plus

---

cela suggère que le fichier contient davantage de mots.

il faudrait donc connaître le nombre de mots >=6 lettres, que l'on divisera par deux (plus un pour une partie si le nombre de mots est impair); ces deux parties serviront à calculer les modulos sur RANDOM, qui seront enfin additionnés pour obtenir la ligne qui sera sélectionnée (et donc le mot).
le modulos de Xteise est d'ailleurs inutile, puisqu'il "module" sur le nombre maximum que peut atteindre RANDOM.

Ça me paraît plus efficace que de tirer un nombre au hasard, qui pourrait être supérieur au nombre de lignes du fichiers, et, encore plus, au nombre de mots >=6 lettres

Bonjour,

Citation:

---

Envoyé par N_BaH

il faudrait donc connaître le nombre de mots >=6 lettres, que l'on divisera par deux (plus un pour une partie si le nombre de mots est impair); ces deux parties serviront à calculer les modulos sur RANDOM, qui seront enfin additionnés pour obtenir la ligne qui sera sélectionnée (et donc le mot).

---

Je suis perplexe quant à ce raisonnement -- pas qu'il faille connaître (ou pouvoir obtenir facilement) le nombre de mots >=6 lettres, le reste bien sûr ;-) --.

Citation:

---

Envoyé par N_BaH

le modulos de Xteise est d'ailleurs inutile, puisqu'il "module" sur le nombre maximum que peut atteindre RANDOM.

---

Agreed. Et je comprends encore moins le modulo 50 transformé en modulo 28, par ex. ici nbligne=$(expr $modulo % 28).

J'ai l'impression que pour le choix du mot, ce qu'il faut faire est clairement dit dans l'énoncé : multiplier 2 random d'entiers sur 16 bits pour simuler une distribution uniforme sur 32
j'ai de sérieux doutes sur l'uniformité de la distribution, rien que pour la densité des pairs et impairs, mais bon...

On a alors une distribution qui permet de couvrir des nombres largement au dessus de la centaine de milliers, qui doit correspondre à l'ordre de grandeur de la taille du dico (ou dico modifié par une commande similaire à celle proposées par Flodelarab (à adapter pour >=6, mais bon c'est pas grand chose)).

Reste à prendre le modulo du random vs nombre entrées dico >=6 (qui induit aussi un biais dans l'uniformité de la distribution sur le nbre d'entrées, mais bon, être bien uniformément aléatoire dans un jeu de pendu n'est peut-être pas vital non plus.

Edit: qui plus est, le requis est "au hasard", donc ça doit suffire puisque c'est l'énoncé qui suggère de faire comme ça).

Ou alors suis-je à côté de la plaque ?

Ici, c'est juste pour apprendre le shell d'après ce que j'avais compris, je n'ai donc pas regardé la cohérence de l'algorithme.
Donc, après avoir extrait les mots qui nous interresse (post Flodelarab), on pourrait rajouter un petit sort -R et plus besoin du random (puisque le sort le fait pour nous).

Bonjour,

Merci pour toutes ces réponses.
Effectivement mon code n'est pas très bon
Après avoir lu vos messages j'ai testé plus en profondeur le random. Et effectivement il ne marche pas très bien. Les mots qui sortent avec mon code sont souvent les mêmes. Je pense avoir mal compris le sujet. Je vais donc essayer la solution de xflr6 et je vous posterai le code après.

Pour info le dico fait plus de 300 000 lignes avec des mot de trois à beaucoup de lettres.
Si certain sont intéressé et veulent s'amuser à faire le jeu, je peut le mettre à disposition avec le tp.

Nous n'avons pas le choix de la technique, vu l'énoncé.
La technique du sort -R est vraiment excellente. Surtout pour un pendu. Si on veut tirer 100000 mots au hasard, c'est plus lent.

Code:

---

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

]$ for ((i=0;i<1000;i++));do head -n 30 dico.txt | sort -R | head -1;done |awk 'a[$0]++{} END{for (j in a) print j, a[j]}' AA 35 ABAISSAMES 38 ABAISSAIT 38 ABAISSA 30 ABAISSASSIEZ 42 ABAISSASSES 42 ABAISSABLE 35 ABACA 25 ABAISSASSE 29 AALENIENNES 40 ABACULES 32 ABAISSANT 32 ABACULE 23 AALENIENNE 34 ABACAS 38 AAS 33 ABAISSAS 31 ABAISSANTE 41 ABAISSANTS 28 ABAISSASSIONS 40 ABAISSAIENT 31 ABAISSAI 34 ABAISSANTES 30 AALENIEN 25 ABAISSASSENT 30 AALENIENS 36 ABACOST 37 ABAISSAIS 29 ABACOSTS 27 ABAISSABLES 35

---

Les mots sont tirés à des fréquences équivalentes.

Citation:

---

Envoyé par Flodelarab

La technique du sort -R est vraiment excellente. Surtout pour un pendu. Si on veut tirer 100000 mots au hasard, c'est plus lent.

---

Ce n'est en effet pas ce qui est demandé, mais c'est clair, l'idée est vraiment excellente.
Y compris pour 100000 pendus !
En effet : une fois le sort -R effectué, on a une suite aléatoire de mots qu'il suffit de parcourir, et on est même sûr de ne pas tirer deux fois le même. Pour certaines applications, ça peut carrément être utile.
Mais pour des applications de type tabula rasa où tout doit être remis en jeu à chaque fois, OK, s'il faut faire le sort à chaque fois, ça va devenir long.

Si on laisse de coté le sort -R qui se prête bien au pendu car on peut très bien ne faire qu'un seul tri comme précisé par xflr6, je pense que la méthode pas trop complexe tout en étant (je pense...:)) à peu près équilibré serait pour 300 000 mots environ:

Code:

---

$(((($RANDOM*($RANDOM%10))%$nblignes)+1))

---

Le +1 est juste là pour ne pas avoir zéro car sed compte à partir de 1 ;)

+1 pour le +1.

Après, mieux vaut laisser (($RANDOM*$RANDOM)%$nblignes)+1.

Intuitivement [...] plus c'est immensément grand devant nbligne, plus l'erreur d'uniformité due au modulo a de chance de passer petite et inaperçue lorsqu'on passe à l'échelle dans la stat.
Après, le coup de l'uniformité, c'est un peu du pinaillage compte tenu de la légèreté du sujet -le pendu-, et l'objectif initial du problème (shell et outils associés).

@Flodelarab: Juste un détail concernant le passage par grep, le mieux serait:

Code:

---

grep -m $nblignes '......' | tail -1

---

ou

Code:

---

grep -m $nblignes '......' | sed -n '$p'

---

Mais, bon, je pinaille :)

Déjà, quit à pinailler:

Code:

---

grep -m $nblignes '......' | sed '$!d'

---

;)

Après, je ne suis pas sûr de comprendre pourquoi le nombre maximum de correspondances devrait être fixée (à une valeur, d'ailleurs, qui ne sera pas atteinte, a moins que tout le dico ait des 6_lettres_ou_+). Tout le dico nous intéresse.


Bon. Résumons. Il n'y a pas besoin de script shell. Une ligne suffit:

Code:

---

1 2	$ awk -vrnd=$((RANDOM*RANDOM)) '/....../{nb_mots++;mots[nb_mots]=$0} END{print mots[rnd%nb_mots+1]}' dico.txt ABAISSAIT

---

:lol:

Et la vérif'

Code:

---

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

for ((i=0;i<1000;i++));do awk -vrnd=$((RANDOM*RANDOM)) '/....../{nb_mots++;mots[nb_mots]=$0} END{print mots[rnd%nb_mots+1]}' dico.txt;done | awk 'a[$0]++{} END{for (j in a) print j, a[j]}' ABAISSAIT 56 ABAISSAMES 21 ABAISSASSIEZ 23 ABAISSA 55 ABAISSASSES 46 ABAISSABLE 26 ABACULES 28 ABAISSASSE 26 AALENIENNES 22 ABACULE 24 ABAISSANT 28 AALENIENNE 25 ABACAS 27 ABAISSANTE 74 ABAISSAS 60 ABAISSANTS 28 ABAISSAI 44 ABAISSASSIONS 15 ABAISSAIENT 16 AALENIENS 58 ABAISSASSENT 18 ABAISSANTES 23 AALENIEN 123 ABACOST 32 ABAISSAIS 28 ABACOSTS 44 ABAISSABLES 30

---

:ccool:

Citation:

---

Envoyé par xflr6

+1 pour le +1.

Après, mieux vaut laisser (($RANDOM*$RANDOM)%$nblignes)+1.

Intuitivement [...] plus c'est immensément grand devant nbligne, plus l'erreur d'uniformité due au modulo a de chance de passer petite et inaperçue lorsqu'on passe à l'échelle dans la stat.
Après, le coup de l'uniformité, c'est un peu du pinaillage compte tenu de la légèreté du sujet -le pendu-, et l'objectif initial du problème (shell et outils associés).

---

J'avais forcé un RANDOM modulo 10 car 32767 * 10 est assez proche de 300 000 (qui est la contenance de son dictionnaire).
Pour que le random soit vraiment correcte, il faudrait que l'on tombe sur un facteur du nombre de mots qu'il y a dans le dico sinon, le modulo nbligne force certain mots à avoir une chance supplémentaire à être tiré au sort:

Code:

---

(32767 * 10)%300000=27670

---

ici on aurait donc 27670 mots avec une chance supplémentaire d'apparaitre.

Code:

---

(32767 * 32767)%300000=276289

---

ici on aurait donc 276289 mots avec une chance supplémentaire d'apparaitre.

On pourrait croire que mon choix est donc meilleurs car il y a moins de mots avec une chance suppléméntaire d'être tirer au sort, mais en fait ce n'est pas le cas car:

Code:

---

300000 - 276289=23711

---

on a donc que 23711 mots avec en fait une chance en moins d'être tiré contre 27670 mots avec une chance en plus d'être tiré et tout ça sur une répartition de 300000 mots.

Donc oui, ici $RANDOM*$RANDOM est mieux que $RANDOM*($RANDOM%10).;)

En fait, selon le "pseudo-raisonnement" que je viens de donner, le meilleur choix serait:

Code:

---

($RANDOM%600)*($RANDOM%500)

---

Et qui d'ailleurs n'est autre que le modulo du nombre de mots mais répartie sur l'ensemble des randoms...

Et pour le fun, en builtin bash:

Code:

---

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

$ cat dico1.txt DECFG BCEEE ABAISSAIENT AALENIENS DDFDF ABAISSAIT DEEGG ABAISSABLES CBFFE CCCGE ABAISSASSIEZ ACCEE ABAISSASSES ADDDF ACDDF DBCGG AEDDF ABAISSASSIONS ABACOSTS DBDFH AALENIENNES DBCEE ADEGE BBDGF BBDGF ABAISSANTS ABAISSAS ABACULES CDDDG AALENIENNE ABAISSAMES CBDFH CBDFH DCDFF BDEDH ABAISSA CCCGH ABAISSAIS ABAISSANTES ABAISSABLE CEFFH ABACOST DCCEF ABAISSAI ABACAS CBFGE DEFGF ADEFE AEEEE AECDF ABAISSANTE ABAISSANT AALENIEN ABAISSASSENT ABAISSASSE CEDEE ABACULE

---

Code:

---

1 2	$ unset MAPFILE ; while [ ${#MAPFILE[0]} -lt 6 ]; do mapfile -O 0 -t -s $(($RANDOM)) -n1 -c 1 <dico1.txt ; done ; echo ${MAPFILE[0]} ABAISSAI

---

ou

Code:

---

1 2	$ unset MAPFILE ; while [ ${#MAPFILE[0]} -lt 6 ]; do readarray -O 0 -t -s $(($RANDOM)) -n1 -c 1 <dico1.txt ; done ; echo ${MAPFILE[0]} ABAISSANTES

---

si on connait le nombre de ligne, on peut dans ce cas moduler le random pour gagner du temps, mais ici, c'est juste pour le fun :aie:

Code:

---

1 2	while read -r mot; do ((${#mot} >=6)) && a+=( "$word" ); done <dico.txt echo "${a[RANDOM]}"

---

les double-parenthèses sont inutiles autour de RANDOM.
le $ est facultatif entre double-parenthèses.
réitérer mapfile tant que le premier élément du tableau <6 :aie:

Pour les erreurs concernant la présence des double paranthèse, c'est juste parce qu'à l'origine je fesai un calcul modulo et que j'ai arrêté par la suite...
Après, le $ facultatif dans une double parenthèse, je le savais mais on ne peut pas lutter contre tout ces démons :)
Concernant le mapfile, je ne charge pas la totalité du tableau mais juste une ligne qui ici est bien positionné sur l'index 0 mais je ne lit pas d'autre ligne que la ligne spécifier par le random:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

$ unset MAPFILE $ readarray -t -s1 -n1 -c 1 <dico1.txt $ set | grep MAPFILE MAPFILE=([0]="BCEEE") $ readarray -t -s1 -n2 -c 1 <dico1.txt $ set | grep MAPFILE MAPFILE=([0]="BCEEE" [1]="ABAISSAIENT") $ readarray -t -s1 -n3 -c 1 <dico1.txt $ set | grep MAPFILE MAPFILE=([0]="BCEEE" [1]="ABAISSAIENT" [2]="AALENIENS") $ readarray -t -s1 -n1 -c 1 <dico1.txt $ set | grep MAPFILE MAPFILE=([0]="BCEEE")

---

le fichier est bien relu (ouvert dans sa totalité) à chaque appel de mapfile, non ?

Dans la totalité, peut-être pas, au moins jusqu'a la ligne s + n.
Mais comme je disais c'est pour le fun.

Bonjour,

Citation:

---

Envoyé par disedorgue

J'avais forcé un RANDOM modulo 10 car 32767 * 10 est assez proche de 300 000 (qui est la contenance de son dictionnaire)...

---

C'est malheureusement hors-sujet par rapport au poste initial, mais je n'arrive pas à ne revenir sur le caractère aléatoire d'une distrib calculée avec un modulo.

Supposons une distribution uniforme sur l'intervalle [1:N].
La distribution étant uniforme, chaque entrée a une probabilité 1/N de sortir.

On souhaite maintenant construire une distribution la plus uniforme possible sur un intervalle [1:M], avec M < N.
Dans notre boîte à outils, on ne dispose que d'un générateur aléatoire [1:N] et des opérateurs communs qu'on ne sait utiliser qu'avec des nombres entiers relatifs.
On a par ailleurs N = M * q + r, ou q est le quotient et r le reste de la division euclidienne de N par M.

On construit la distribution comme suit : RANDOM(N)%M+1

Code:

---

1 2 3 4 5 6 7

Soit n issu de RANDOM[1:N], avec 1 <= n <= M probabilité 1/N. On le met dans la distrib [1:M] ---- n ---- -- ------------ ---- M+1 <= n <= 2*M ----------- ---. -- -- --- ---- -- ------- [1:M] [...] [...] [...] ---- n ---- -- ------------ ---- (q-1)*M+1 <= n <= q*M ----------- ---. -- -- --- ---- -- ------- [1:M] ---- n ---- -- ------------ ---- q*M+1 <= n <= N=q*M+r ----------- ---. -- ------ ---- -- ------- [1:r]

---

Donc pour la distribution [1:M], les nombres [1:r] ont une probabilité de sortir de (q+1)/N, et les nombres compris entre [r+1:M] ont une probabilité de sortir de q/N.
C'est à dire :
Les nombres m <= r ont (q+1)/q = 1 + 1/q fois plus de chances que les autres de sortir, ce qui n'est pas très uniforme... Mais plus q est grand, soit plus N est immense devant M, plus l'erreur est moindre.

Si on prend un N trop juste mais dont on a l'impression qu'il est plus calibré pour le problème, tel que M < N < 2M par exemple, comme tu l'avais suggéré, on a q=1. Ca veut dire que les nombres compris entre [1:r] ont... 2 fois plus de chances de sortir que les autres. Peu importe leur nombre au sein de la distribution, l'erreur sur l'uniformité est énorme lors du passage à l'échelle, et si l'aléatoire que l'on met dans le problème est important, c'est rédhibitoire.

Si N > 1000 * M, c'est franchement pas top non plus si l'aléatoire est important, mais au moins, 1.001 fois plus de chances est mieux que 2 fois plus...
En conclusion, il faut raisonner sur l'erreur relative d'uniformité dans la distribution, et non la proportion des cas "non canoniques" de la distribution. En effet, qu'il y en ai peu ou beaucoup, si l'erreur est grande, lors du passage à l'échelle (nombre de tirage -> infini), les problèmes vont se voir plus que le nez au milieu de la figure (même avec un gros nez).
Et pour contrôler au mieux les problèmes d'erreur, réaliser les étapes biaisantes le plus tard possible pour ne pas avoir à réfléchir à la propagation des biais. Donc ici, prendre le modulo une seule fois à la fin.

Pour le pendu, osef, je suis bien d'accord.

Après, si on a vraiment besoin de l'aléatoire, on prend le problème au sérieux et on utilise autre chose que la fonction de RANDOM qui retourne des entiers signés de 16 bits... Et on prend encore moins une distribution obtenue en multipliant deux entiers randoms sur 16 pour simuler une distrib uniforme sur 32 bits (enfin sur 31 bits, car on a un bit de signe dans chaque distrib sur 16 bits, donc un bit de perdu par rapport à des entiers sur 32 bits signés...) (bah oui car, en dehors de la densité odd/even, quid par exemple des nombres premiers supérieurs à l'entier le plus grand codé sur 16 bits ? il n'y en a pas par définition (!), vu qu'on obtient ces nombre par multiplication)

Je retiens ta dernière objection qui est très bonne.
Le mot d'indice 100213 (par exemple) n'est jamais tiré au sort.
Il faudrait une concatenation textuelle des écritures bianires ou hexadécimales des deux RANDOM pour atteindre l'objectif, ce qui est facile en bash ou awk.


Pour le reste, je crois que tu te compliques la vie. Avec une distribution uniforme sur [1:N] et M<N, il suffit d'ignorer les tirages au-delà de M. Ou qM.
Ainsi tu as une distribution uniforme.

La probabilité de ne tirer que des nombres de [M+1:N] (respectivement [Mq+1:N]) est nulle.

Citation:

---

Envoyé par Flodelarab

Je retiens ta dernière objection qui est très bonne.
Le mot d'indice 100213 (par exemple) n'est jamais tiré au sort.
Il faudrait une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM pour atteindre l'objectif, ce qui est facile en bash ou awk.

---

Tout à fait.

Citation:

---

Envoyé par Flodelarab

Pour le reste, je crois que tu te compliques la vie. Avec une distribution uniforme sur [1:N] et M<N, il suffit d'ignorer les tirages au-delà de M. Ou qM.
Ainsi tu as une distribution uniforme.

La probabilité de ne tirer que des nombres de [M+1:N] (respectivement [Mq+1:N]) est nulle.

---

Je critiquais l'utilisation du modulo qui est souvent utilisée pour des distributions d'entiers, et qui n'est pas une bonne méthode. Je soulignais les cas où elle était plus ou moins méchante. Plus particulièrement, je faisais une mise au point sur le raisonnement de disedorgue de 13h26 qui ne me convient pas. Et suis complètement d'accord sur la méthode de rejet (qui est straightforward !).

Bref, j'ai voulu faire un aparté en disant ce qui faisait plus ou moins mal dans l'usage du modulo. J'aurais pu avoir un peu moins la tête dans le guidon et ne pas me limiter à ça en disant ce qu'il était bien de faire en effet...
Avec ton post, c'est chose faite :ccool:.

Je suis conscient de mon erreur sur l'erreur de faire le modulo avant la multiplication.
Pour l'histoire de la distribution, je comprend le raisonnement, mais mon propos était plus pour essayer d'expliquer mon erreur sur le RANDOM*(RANDOM%10)...

Je ne comprends pas ce que vous voulez dire par "une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM" et surtout comment on peut la réduire à la taille du dico.

Citation:

---

Envoyé par disedorgue

Je ne comprends pas ce que vous voulez dire par "une concaténation textuelle des écritures binaires ou hexadécimales des deux RANDOM"

---

RANDOM1 + RANDOM2 * 2^15 fait la concaténation en binaire il me semble. Après j'ai acquiescé un peu vite pour "concaténation textuelle ..."

Citation:

---

Envoyé par disedorgue

et surtout comment on peut la réduire à la taille du dico.

---

On a 0 <= N <= 2^30-1=NMAX, M le nombre de mots du dico
on pose Nm = ((int)(NMAX/M))*M = q*M
Si N >= Nm, on rejette le tirage
Sinon, nbligne=N%M+1, et on a une distrib uniforme, comme l'a proposé Flodelarab. (les rejets n'interviennent pas dans les stats, donc on a q/Nm proba pour chaque nombre).

• Pardon pour ma réponse. J'avais sans doute lu trop vite.
  
• De plus, mea culpa, mon exemple est mauvais. Certes, 100213 est premier, mais modulo 300000, il y a 400213 qui se factorise :D
  Donc le mot peut être tiré. (par les cheveux, aussi)
  
• En ce qui concerne le tirage aléatoire:
  
  On tire r1 et r2, 2 randoms, entre 0 et 32767 = 2**15-1
  La multiplication ne fonctionne pas car elle ne donne pas tous les entiers entre 0 et 2**30-1. Il manque les nombres premiers.
  
  La concaténation n'est ni la multiplication, ni l'addition, mais le fait d'écrire à la suite l'un l'autre (d'où la commande cat)
  
  10011
  11100
  ->
  1001111100
  
  Dans ce cas, tous les nombre sont atteints de manière uniforme.
  C'est facile à imaginer.
  Il n'y avait aucunement de réflexion sur ce qu'on n'en fait après.
  
  Par contre, je suis allé vite en disant que c'était facile à programmer, car écrire une variable en binaire n'est pas forcément facile.
  (C'est du binaire/héxa vers le décimal qui est facile)
  
  Code:

  ---

  1 2	$ echo $((2#11100)) 28

  ---

  De plus, il y a un bit de signe a faire sauter.

A ce que je comprend, on peut faire ceci (puisque l'hexa et le binaire, c'est un peu la même chose et la conversion en hexa se fait simplement):

Code:

---

1 2	$ printf "%X%X" $RANDOM $RANDOM 52E57884

---

et pour revenir en décimal:

Code:

---

1 2	$ echo $((16#$(printf "%X%X" $RANDOM $RANDOM))) 1685206995

---

Merci disedorgue! C'est exactement ce que je pensais mais mon neurone broutait au moment de trouver la syntaxe.
N_BaH avait déjà donné cette façon de convertir avec printf, si je ne m'abuse.

OK pour la concaténation, mais en quoi r1 + r2*2^15 = r1 + r2*32768 ne serait-il pas tout simplement suffisant pour faire ce taf ?
Plus besoin de s'occuper du bit de signe ni rien.

Citation:

---

Envoyé par Flodelarab

N_BaH avait déjà donné cette façon de convertir avec printf, si je ne m'abuse.

---

Exact, plusieurs fois même (ainsi que pour la conversion de l'heure en format hexa) :ccool:

Citation:

---

Envoyé par xflr6

OK pour la concaténation, mais en quoi r1 + r2*2^15 = r1 + r2*32768 ne serait-il pas tout simplement suffisant pour faire ce taf ?
Plus besoin de s'occuper du bit de signe ni rien.

---

Ici, je ne comprends pas tout mais si le but est de trouver le même résultat que la concat, la formule est du type:
r1*2^16 + r2 = r1*65536 + r2 que l'on peut ecrire en bash:

Code:

---

$(((r1<<16)+r2))

---

Si on doit laisser le bit manquant du quartet le plus à gauche, dans ce cas on doit bien utiliser ta formule qui en bash donnerait donc au final:

Code:

---

$(((RANDOM<<15)+RANDOM))

---

Citation:

---

Envoyé par disedorgue

Code:

---

1 2	$ printf "%X%X" $RANDOM $RANDOM 52E57884

---

et pour revenir en décimal:

Code:

---

1 2	$ echo $((16#$(printf "%X%X" $RANDOM $RANDOM))) 1685206995

---

---

Euh.... ici, il y a une grave erreur ici, la concat sera fausse si la valeur du random est inférieur à 16. donc la bonne syntaxe est:

Code:

---

echo $((16#$(printf "%02X%02X" $RANDOM $RANDOM)))

---

Euh... non mais en fait, seul la solution de xflr6 fonctionne.
Il faut le faire numériquement.

Le second random doit prendre la place des 16 bits (ce qu'il ne fera pas pour un petit nombre).
Et même si on le force, il y aura des espaces.
Et même si on remplit de 0, il y aura un bit en trop (signe).

Et si on ne fait rien, il va tirer plusieurs fois le même nombre (12 13 = 1213 = 1 213 = 121 3)

Une bonne petite galère.

Bon, donc on corrige et on synthétise:
concat textuel (comme on est sur 16 bit):

Code:

---

$ N=$((16#$(printf "%X%04X" $RANDOM $RANDOM)))

---

ou numériquement qui reste comme précédemment:
concat textuel

Code:

---

$ N=$(((RANDOM<<16)+RANDOM))

---

concat binaire:

Code:

---

$ N=$(((RANDOM<<15)+RANDOM))

---

Pour calculer le M,et Nm:

Code:

---

1 2	$ M=$(grep -c '......' dico.txt) $ Nm=$(((((1<<30)-1)/M)*M))

---

Reste plus qu'à vérifier que N ne soit pas >= Nm car sinon, on calcul un nouveau N.
Et on calcul:

Code:

---

$ nblignes=$(((N%M)+1))

---

Puis l'on récupère la ligne en conséquence par un truc du genre:

Code:

---

$ grep -m $nblignes '......' | sed '$!d'

---

Bon, bien sur, M et Nm ne se calcul qu'une seule fois sauf si le dico change.

Juste pour information, il est possible de faire une concatenation binaire sur des nombre de 15 bits en passant uniquement par la conversion de base:
Exemple par le calcul:

Code:

---

1 2	$ echo -e $(((25<<15)+33)) 819233

---

Le même par la conversion de base:

Code:

---

1 2	$ echo -e $[8#$(printf "%05o%05o\n" 25 33)] 819233

---

[CHIPOTAGE (une fois n'est pas coutume...)]

Citation:

---

Envoyé par disedorgue

En fait, selon le "pseudo-raisonnement" que je viens de donner, le meilleur choix serait:

Code:

---

($RANDOM%600)*($RANDOM%500)

---

Et qui d'ailleurs n'est autre que le modulo du nombre de mots mais répartie sur l'ensemble des randoms...

---

Citation:

---

Envoyé par xflr6

J'ai l'impression que pour le choix du mot, ce qu'il faut faire est clairement dit dans l'énoncé : multiplier 2 random d'entiers sur 16 bits pour simuler une distribution uniforme sur 32
j'ai de sérieux doutes sur l'uniformité de la distribution, rien que pour la densité des pairs et impairs, mais bon...

---

Comme l'a très justement fait remarquer xflr6, j'ai aussi de sérieux doutes quant à la parité du résultat:
La formule $RANDOM%600 fournit, en moyenne, autant d'entiers pairs que d'entiers impairs.
La formule $RANDOM%500 fournit, en moyenne, autant d'entiers pairs que d'entiers impairs.
Or (et non "hors" (comme je le vois trop souvent écrit)) il suffit que l'un des 2 entiers soit pair pour que leur produit le soit aussi!
Le produit de ces 2 entiers aléatoires est donc 3 fois plus souvent pair qu'impair!

On peut par ailleurs remarquer que, si les nombres premiers inférieurs à 400 sont susceptibles d'être tirés (lorsque l'un des 2 randoms est "1"), je ne vois pas très bien comment les nombres premiers supérieurs à 400 auraient la moindre chance d'être tirés!!!

Pour ma part (en temps que mathématicien chipoteur), je préfèrerais une formule du genre:

Code:

---

(($RANDOM%600)*600)+($RANDOM%500)

---

qui a l'avantage de permettre le tirage de tous les nombres entre 0 et 299999
tout en n'oubliant pas qu'il reste quand même un léger biais du fait que $RANDOM%600 n'est pas complètement uniforme sur [0 .. 599] (comme l'a très clairement indiqué Disedorgue post #15)
[/CHIPOTAGE]

Edit:
Oops! J'arrive un peu après la bataille (je n'avais pas vu qu'il y avait une 2ème page et j'ai donc zappé les messages #21 à #34...) :oops:

Ouf, sauvé, je ne dis pas que des bêtises :lol: