• [^] # Re: un petit peu plus (de divisions)

    Posté par (site web personnel, Mastodon) . En réponse au journal résoudre "trouve 24". Évalué à 3.

    Comme tu verras plus loin, avec l'implémentation en Python, il y a le cas intéressant de 1 4 5 6 pour lequel le script shell ne trouve pas de solution non plus ([...]) Du coup, le défi suivant est de lui faire trouver l'élégante solution ([...])

    On remet l'œuvre sur l'établi, et on fait la vérification en amont de la procédure d'affichage. Normalement le calcul doit se dérouler sans accroc parce que les cas tordus (pour l'instant les zéros et je n'en vois pas d'autres) ont été éliminés juste avant. On va faire appel à un programme externe pour quasiment tous les calculs, histoire qu'ils se fassent dans \mathbb{D} et non plus \mathbb{N}.
    Comme je le craignais, lancer des processus a un certain coût qui est quand même important sur la machine où j'ai travaillé. Ainsi, par exemple pour 8 3 2 1 avec juste l1, je note que real/user/sys passe

    • de 0m0.109s/0m0.073s/0m0.040s (ancienne version)
    • à 0m4.503s/0m2.242s/0m3.984s (nouvelle version)
    • soit 41/30/99 fois plus de temps...

    Ceci dit, ça reste intéressant car il faut moins d'une minute pour lister toutes les solutions possibles sur les pistes explorées. Le fait de changer de domaine de calcul ramène plus de résultats... (cela me fait penser à la programmation linéaire, sauf que c'est dans l'autre sens ; c'est peut-être une forme d'optimisation de production qui sait ? Mais revenons à nos moutons...)

    id type formule 1 2 3 8 1 2 7 7 1 4 5 6
    b1 Ax(ByC)zD 10/1296 0/1320 0/1296
    b2 (AxB)y(CzD) 10/1488 0/1480 0/1488
    b3 AxByCzD 8/1536 2/1536 0/1536
    l1 (AxB)yCzD 8/1536 2/1536 0/1536
    l2 (AxByC)zD 8/1536 2/1536 0/1536
    r1 AxBy(CzD) 10/1536 0/1520 0/1536
    r2 Ax(ByCzD) 8/1530 0/1520 1/1524
    all totaux 62/10458 6/10448 1/10452

    Plus de résultats mais pas mal de duplications... Arriver à les anticiper et donc ne pas calculer inutilement (ce qui aurait quand même été le cas si on stockait les résultats pour au final n'en afficher que les occurrences uniques...) C'est une piste d'amélioration qui pourrait impacter positivement le temps d'exécution.
    Si on prend le cas soumis par le_poney, il n'y a qu'une seule solution qui est trouvée dans deux branches branches mais en deux ou quatre fois pour chacune...

    $ trouve24.sh 7 7 1 2
7*7=49; 49-1=48; 48/2=24; b3
7*7=49; 49-1=48; 48/2=24; l1
7*7=49; 49-1=48; 48/2=24; l1
7*7=49; 49-1=48; 48/2=24; b3
7*7=49; 49-1=48; 48/2=24; l1
7*7=49; 49-1=48; 48/2=24; l1
Found 6 solutions for 10448 computations.

    La solution de le_poney est la seule possible... C'est une r2 qui se présente comme suit chez moi :

    5/4=1.25; 1.25-1=.25; 6/.25=24; r2

    Mission accomplie ; la solution en shell semble l'emporter sur les autres ;-) Plus qu'à l'optimiser.
    (p.s. Je mettrai à jour le snippet plus tard)

    "It is seldom that liberty of any kind is lost all at once." ― David Hume