Un p'tit challenge de code

[niahoo]

Yo !

Je profite d'être en vacances pour remettre à jour mon blog. J'ai encore changé d'engine (c'est ça qui est bon !) mais cette fois-ci j'ai gardé les articles d'il y a un an !).

Bref.

Du coup nouvel article et c'est un challenge de code, alors pitètre qu'il vous plaira.

Le but est de créer une fonction random [0; 7[ avec comme seule possibilité de tirer des nombres aléatoires une fonction random [0; 5[.

Plus d'infos sur mon article : https://ooha.in/blog/the-spolsky-rng-challenge/

Perso j'ai vraiment pas trouvé ça de suite, même si au final c'est plutôt simple et ma méthode est générique. Postez-vos réponses ici si vous jouez

[Meraxes]

Alors moi j'ai un peu triché (en tout cas je pense que c'est pas très optimisé comme code et pas très joli).

Mon code (en blanc) :
function rand7(){

    
    let n = rand5()*5 + rand5();
    
    if(n>=21) {
        return rand7();
    }
    
    return Math.trunc(n/3);
}

window.rand7Factory = function(rand5){
  return function() {
   
    return rand7();
  }
}

Mais du coup, est-ce qu'on a le droit d'ignorer certains tirages et rappeler la fonction récursivement quand c'est le cas ?

En tout cas c'est la première idée qui m'est venue ; pour le coup presque immédiatement et j'obtiens bien un graphe équilibré.

[Xenos]

[niahoo]

@Meraxes Oui c'est valide, tant que tu n'utilises pas d'autre générateur de nombres aléatoires que rand5.
Du coup c'est pas mal du tout. J'avoue que ma nullité en math m'empêche de piger ce qu'il se passe, mais oui c'est correct.

@Xenos ça peut être fun aussi d'implémenter des solutions bancales pour les partager, c'est justement là qu'est le fun du graphique.

Je vais ajouter la possiblité de contrôler le nombre d'itérations via une variable GET.

Edit: voilà pour 100 itérations : http://localhost:8000/blog/the-spolsky-r...enge?i=100 comme ça si tu veux faire une fonction vraiment bourrine, tu peux commencer avec 1 seule itération

[Sephi-Chan]

Je reposte vu que j'ai posté en même temps que Niahoo.

Ma solution : créer un nombre en binaire sous forme d'une chaîne de 3 bits (0 ou 1) et la convertir en base décimal.
Pour produire un bit, je tire un nombre entre 1 et 4 (pour ça je fais un rand5 et si c'est 0 je recommence) et je prends son modulo 2.
Je concatène ces 3 bits pour faire un nombre en binaire entre 000 et 111, si c'est 111 (7 en décimal) je recommence (oui ma solution est un peu bruteforce :p).

Code :

window.rand7Factory = function(rand5){
function randomBit() {
    const number = rand5();
    if (number === 0) return randomBit();
    return number % 2;
}

function random7() {
   const bits = [ randomBit(), randomBit(), randomBit() ].join("");
   const number = parseInt(bits, 2);
   if (number === 7) return random7();
   return number;
}

return random7;
}

J'ai pas regardé la vidéo mais j'ai plutôt mis 15 minutes.

[niahoo]

Mouah ha ha c'est génial (et immonde), j'adore. Par contre, étrangement il faut monter à 100 000 itérations sur ma machine pour que ça ait l'air stable.

[Sephi-Chan]

Sur ton outil c'est stable, mais je ne sais pas combien d'itérations il tente. :p

[Xenos]

Statistiquement, les différentes solutions tombent dans le travers qu'on peut attendre indéfiniment le nombre en question (ie: si on tire toujours "5" dans l'algo de Meraxes, 0 dans celui de Sephi.

Et le dernier des miens n'est pas équiprobable pour la partie "parité" car sur deux tirages de [0;5[ on a 12 chances sur 25 d'avoir la même parité... donc, pas 1 chance sur 2 :\

Rah, je suis persuadé qu'avec cette petite matrice de nombres de 5x7, on trouve une solution finie

[niahoo]

@Sephi 10k itérations. Tu peux mettre ?i=100000 dans l'url si tu en veux plus.

Je donne ma solution :

Code :

window.rand7Factory = function(rand5) {
    function bit() {
        var n = rand5()
        if (n > 1) return bit() // ici le modulo de Sephi améliorerait les perfs
        return n
    }

    return function rand7() {
        switch (rand5()) {
            case 0: return bit()
            case 1: return 2 + bit()
            case 2: return 4 + bit()
            case 3: if (bit()) return 6
        }
        return rand7()
    }
}

J'aime pas trop tous les if/else (habilement cachés sous forme de switch), ça fait un peu trop "manuel". Mais ça marche. Pour le coup, la récursion potentiellement infinie ne me gêne pas.


edit: @Meraxes ci-dessous, Ok !

[Meraxes]

@Niahoo

En fait mon code, c'est simplement un tirage uniforme sur 5*5=25 qu'on découpe en 7 parts égales (de 3, ce qui fait 21/25 cas) et dont on ignore le reste (i.e. 4/25 cas). On pourrait faire la même chose par exemple avec 5*5*5=125 qu'on découpe en 7 parts égales (de 17, ce qui fait 119/125 cas) et dont on ignore le reste (i.e. 6/125 cas).

L'idée m'est venue du fait que pour certains jeu de rôles (et notamment les livres dont vous êtes le héros), on demande souvent de tirer 2 dés ce qui donne des résultats en loi normale autours de 7 ce qui n'est pas toujours pratique et il y avait une astuce pour avoir un tirage uniforme sur 12 avec deux dés (en réalité ça correspondait à faire un tirage uniforme sur 6*6=36 qu'on découpe en 3 parts de 12
; i.e. faire : ceil(((dé1-1) * 6 + dé2) / 3) .

On pouvait aussi faire, par exemple (il y a d'autres façons puisque 12 a plein de diviseurs), comme ça :
- si le 1er dé donne 1 à 3, prendre le résultat du 2nd dé
- si le 1er dé donne 4 à 6, prendre le résultat du 2nd dé + 6


@Xenos
En fait, j'ai quand même un doute sur le fait que l'on puisse trouver un moyen de "tomber juste".