Défi: le compte est bon

Discutez d'informatique ici !
Avatar de l’utilisateur
anthony_unac
Habitué(e)
Messages: 1115
Enregistré le: 30 Juin 2007, 01:31

Re: Défi: le compte est bon

par anthony_unac » 10 Nov 2016, 23:44

Ah ouais, c'est carrément dans la création de l'algo que tu prends ton pied ben314 !
Tu as travaillé sur beaucoup d'algo ?
Quelles sont ceux qui te laissent les meilleurs souvenirs et qui ont pu apporté un vrai plus aux gens.



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 13 Oct 2017, 21:43

Je fais un up des familles... chaque année.

En cherchant programmation dynamique sur le net, je suis tombé sur http://www.enseignement.polytechnique.f ... .java.html
en implémentant plus ou moins la même idée, j'ai donc (en js mal codé)

Code: Tout sélectionner
function store(o, val, sign, lOp, rOp, goal){
    //o[val] = '('+lOp+')'+sign+'('+rOp+')';
    o[val] = '';
    if(val == goal){
        console.timeEnd('start')
        console.log('GOOOOOOAL ', o[val]);
        process.exit(0);
    }
}
/*
for given arr
    generate all left|right parts
    process all possible results between left and right recursively
    dic: partition -> [value->op]
    let simplify op as string for now. Later as concatenation of pointer postfix
 */
function dyn(arr, mask, dic, goal){
    if(dic[mask])return;
    var n = arr.length;
    //2^n possibility
    //right must contain at least one 1
    //that is: ignore 11111
    for(var left = 1; left<Math.pow(2, n)-1; ++left){
        var right = left^(Math.pow(2,n)-1);
        var subl = left & mask;
        var subr = right & mask;
        if(subl && subr && subl>=subr){ //the partition<left, right> lies in mask
            dyn(arr, subl, dic, goal)
            dyn(arr, subr, dic, goal)
            dic[mask] = {};
            Object.keys(dic[subl]).forEach(k=>{
                const v = dic[subl][k];
                Object.keys(dic[subr]).forEach(l=>{
                    const w = dic[subr][l];
                    k = parseInt(k);
                    l = parseInt(l);
                    store(dic[mask], k+l, '+', v, w, goal);
                    store(dic[mask], k*l, '*',v, w, goal);
                    if(k>l){
                        store(dic[mask], k-l, '-',v, w, goal);
                        if(k % l == 0){
                            store(dic[mask], k/l, '/',v, w, goal);
                        }
                    }else{
                        store(dic[mask], l-k, '-',w, v, goal);
                        if(l % k == 0){
                            store(dic[mask], l/k, '/',w, v, goal);
                        }
                    }
                   
                })
            })
        }
    }
}
/**
 * @param  {[type]} arr [description]
 * @param  {[type]} dic
 * @return {[type]}     [description]
 */
function solve(arr, goal){
    var n = arr.length;
    var dic = {};
    //on every items of arr, add a bit position
    for(var i = 0; i<n; ++i){
        var mask = Math.pow(2, i);
        dic[mask] = {[arr[i]]:arr[i]};
    }
    console.time('start');
    dyn(arr, (Math.pow(2,n)-1), dic, goal)

}
solve([1 ,2, 213, 8 ,9, 18, 107, 82, 90, 12], 1000000)


Qui donne une solution en resp 79s et 54s (commentant les string ou pas) sur mon A10
Je pense qu'on peut faire mieux que .keys..forEach
Pas sûr que la cond subl>subr gêne, car doit yavoir branche prédiction (à tester)
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Défi: le compte est bon

par Ben314 » 13 Oct 2017, 22:30

Je le redit (je l'avais déjà dit avant...), mais a mon sens (les gouts et les couleurs...), je ne trouve pas ça joli du tout de ne pas utiliser l'associativité du + et du * dans R qui font que ça sert à rien de "tester" à la fois ((a+b)+c) puis aussi (a+(b+c)).
Et je rajouterais même que si on prenait un nombre de plaque un peu plus important, ça se sentirait plus que drastiquement au niveau de la vitesse d'exécution du programme qu'il faut absolument utiliser cette associativité pour éviter la multiplication des cas.
Comme toujours, tu perd effectivement pas mal de temps à dénombrer le nombre de façon de regrouper les n plaques en "paquets" sur lesquels les opération vont être globalement faites (i.e. on va pas faire juste des sommes ou produit d'élément 2 par 2 mais paquet par paquet).
Mais cette "perte de temps" a pour but de diminuer la base de l'exponentielle qui "pilote" la complexité de l'algo.
Bref, on va passer d'une complexité style 5*2^p où p est le nombre de plaque à un truc du style 50*(1.8)^p.
Le coeff. plus gros (5 -> 50) signifiant que le temps de traitement d'un "cas" est pas mal plus long, mais avec une base d'exponentielle plus petite (2 -> 1.8).
Et en temps que matheux, j'ai évidement une préférence pour le 50*(1.8)^p vu que asymptotiquement parlant, il est bien plus petit que le 5*2^p (mais bien entendu, pour de "petites" valeur de p, le 5*2^p est plus petit que le 50*(1.8)^p)

P.S. : Ton algo, il met combien de temps à énumérer TOUT les cas (si tu t'arrête dès que tu as une solution, je pense pas que ce soit bien pertinent en terme de complexité vu que ça peut être un "coup de bol", sans parler du fait que, s'il y a pas de solution alors il faudra TOUT passer en revue)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 13 Oct 2017, 23:56

P.S. : Ton algo, il met combien de temps à énumérer TOUT les cas (si tu t'arrête dès que tu as une solution, je pense pas que ce soit bien pertinent en terme de complexité vu que ça peut être un "coup de bol", sans parler du fait que, s'il y a pas de solution alors il faudra TOUT passer en revue)


Je viens d'implem en c++, au bout de 9min et 154 solutions, l'os m'a killé XD

Dans ts les cas, je pense pas que tenter de bénéficier de l'associativité soit opposé à l'approche dynamique (somme toute de la mémoisation)
En particulier, lorsque je "cache" pour un paquet l'ensemble des valeurs générées, je peux décider de ne pas stocker une valeur pour laquelle elle est obtenu à partir d'opération ou j'ai pas utilisé l'asso
(ex: a+b+c seulement valide si a > b > c)
la vie est une fête :)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 14 Oct 2017, 20:42

bon...
je me rends compte que je sais même pas différencier la commutativité de l'associativié.. cf mon dernier poste...

Pour la commut c'est bon.
Pour l'associativité je peine encore à cutter:

J'ai un arbre de gauche, un arbre de droite.
Je veux savoir si l'addition de ces "deux arbres" est correcte pour l'associativité.
J'ai un peu de mal à fixer une règle pour assurer qu'infine en remontant dans la récursion, on aie l'unicité...(les autres groupes formés sont droppés)

Actuellement je représente qqch comme:
dans mon arbre j'ai un tableau dont les éléments sont des entiers qui représentent la valeur des termes.
(idem: si j'ai 3*4+5 dans mon arbre, larbre contient [12,5])
pour la commutativté, j'impose: le dernier nombre (5) est supérieur que le premier nombre de l'arbre de droite.

Mais pour l'asso.. j'y réfléchis encore
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Défi: le compte est bon

par Ben314 » 14 Oct 2017, 22:12

Perso, la façon dont j'avais résolu le bidule, c'est de considérer des arbres bien plus compliqué que de simples arbres binaires.
Les sommets (non terminaux) de l'arbre, ils étaient uniquement de deux types : soit +- , soit */ (et pas de 4 types + ; - ; * ; /)
Et de chaque sommet partait un certain nombre d'arêtes (au moins deux) avec deux types d'arêtes : des arrêtes + et des arrêtes - pour les sommets de type +- et des arrêtes * et des arrêtes / pour les sommets de type */.
Avec ça comme convention, tu peut imposer que toutes les arrêtes partant d'un sommet de type +- aillent vers des sommets de type */ et réciproquement.
Bien entendu, comme dans le cas des arbres binaires avec juste 2 paramètres à chaque opération, il faut se débrouiller pour que "l'ordre" dans lequel sont les arrêtes en dessous d'un sommet considéré n'ait pas d'importance.
J'ai pas calculé combien il y a d'arbres de ce type avec exactement 10 feuilles, mais ça doit être calculable (avec l'ordi). J'ai pas vraiment regardé non plus si plusieurs de ces arbres correspondaient au même résultat final, mais je pense que formellement (i.e. en appelant les 10 plaque A,B,C,... et en regardant le résultat formel du calcul avec des A,B,C,...) je pense que deux arbres différents codent des résultat différents (donc dans la théorie, y'a aucune redondance des calculs).
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 15 Oct 2017, 00:55

en fait, j'ai somme toute la même typo d'arbre (mais ils sont binaires):
Code: Tout sélectionner
function Tree(op,left,right){
    this.op = op;
    this.left = left;
    this.right = right;
    this.adders = [];
    this.multipliers = [];
    if(this.op >=0){this.adders=[op];this.multipliers=[op];}
    else{
        if(this.op == opMap.PLUS){
            this.adders = left.adders.concat(right.adders);
            this.multipliers = [this.valadd()];
        }else if(this.op == opMap.SUBS){
            this.adders = left.adders.concat(right.adders.map(x=>-x).reverse());
            this.multipliers = [this.valadd()];
        }else if(this.op == opMap.TIME){
            this.multipliers = this.left.multipliers.concat(this.right.multipliers);
            this.adders = [this.valmul()];
        }else if(this.op == opMap.DIVI){
            this.multipliers = left.multipliers.concat(right.multipliers.map(x=>-x).reverse());
            this.adders = [this.valmul()];
        }else{
            throw "learn how to code";
        }
    }
}

simplement je store pas des pointeurs mais simplement la valeur "aggrégée"

Je pense avoir l'unicité (quasi) avec les règles:
lleft, op, rightTre
pour rightTree, maximum un element (+ à gauche > à droite pour la commutativité)
cqui fait que (je pense, mais jai un peu de mal) ya l'unicité.

par contre, c'est pas plus rapide (...) jvais porter en C++ pour voir, mais bon...
-----EDIT -----
implem en C++:
Code: Tout sélectionner
#define PLUS_OP -1
#define TIME_OP -2
#define SUBS_OP -3
#define DIVI_OP -4
#include <vector>
#include <map>
#include <sstream>
#include <iostream>
#include <chrono>
#include <bitset>

auto T1_START = std::chrono::high_resolution_clock::now();
class Tree{
public:
    Tree(int op, int val=0, const Tree* left=NULL, const Tree* right=NULL):
        _op(op),
        _val(val),
        _left(left),
        _right(right){
        if(op >= 0){
            _val = op;
            _rightVal = op;
        }else{
            _val = val;
            if(op == SUBS_OP || op == DIVI_OP){
                _rightVal = -val;
            }else{
                _rightVal = val;
            }
        }
    }
    int _op;
    size_t _val;
    int _rightVal;
    const Tree* _left;
    const Tree* _right;
    std::string toString()const{
        if(_op >= 0){
            std::stringstream oss;
            oss<<_op;
            return oss.str();
        }
        std::stringstream oss;
        char symbol;
        if(_op==-1){
            symbol = '+';
        }else if(_op==-2){
            symbol = '*';
        }else if(_op==-3){
            symbol = '-';
        }else if(_op==-4){
            symbol = '/';
        }
        oss<<"("<<_left->toString()<<")"<<symbol<<"("<<_right->toString()<<")";
        return oss.str();
    }
    bool isMul()const{
        return _op >= 0 || _op == TIME_OP || _op == DIVI_OP;
    }
    bool isAdd()const{
        return _op >= 0 || _op == PLUS_OP || _op == SUBS_OP;
    }
    static bool isAddOk(const Tree*a, const Tree*b){
        return a->_rightVal >= b->_val && b->isMul();
    }
    static bool isMulOk(const Tree*a, const Tree*b){
        return a->_rightVal >= b->_val && b->isAdd();
    }
    static bool isSubOk(const Tree*a, const Tree*b){
        return a->_rightVal >= -b->_val && b->isMul();
    }
    static bool isDivOk(const Tree*a, const Tree*b){
        return a->_rightVal >= -b->_val && b->isAdd();
    }
};
typedef std::map<size_t, std::map<size_t, Tree*>> Dic;
void dump(const std::string& s, const Dic &d){
    std::cout<<s<<std::endl;
    for(const auto& p: d){
        std::cout<<p.first<<std::endl;
        for(const auto& v: p.second){
            std::cout<<"\t"<<v.first<<":"<<v.second->toString()<<std::endl;
        }
    }
}
void dump(const std::string& s, const size_t &l){
    std::bitset<sizeof(l)> b(l);
    std::cout<<s<<" "<<b<<std::endl;
}
void print_goal(const std::string& s){
    auto t2 = std::chrono::high_resolution_clock::now();
      std::cout<<(std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - T1_START).count()/1000000)
      << " ms:"
      << s
      <<std::endl;
}
void store_plus(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    if(!Tree::isAddOk(l.second,r.second)){
        return;
    }
    const auto& res = l.first+r.first;
    m[res] = new Tree(PLUS_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_time(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first*r.first;
    if(!Tree::isMulOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(TIME_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_subs(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first-r.first;
    if(!Tree::isSubOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(SUBS_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_divi(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first/r.first;
    if(!Tree::isDivOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(DIVI_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
size_t MAX_CALLS = 0;
void dyn(const std::vector<size_t>& v, size_t mask, Dic& dic, size_t goal){
//mp("dyncall", mask);
    if(dic.find(mask)!=dic.end())return;
//X_CALLS++;
//(MAX_CALLS==5){throw std::string("caca");}
    dic[mask];
    const auto& n = v.size();
    size_t ones = (1<<n)-1;;
    size_t umask = mask^ones;
    for(size_t left = 1; left<ones; ++left){
        size_t right = left^(ones);
        size_t subl = left & mask;
        size_t subr = right & mask;
        if(subl && subr && (umask&left)==0){ //the partition<left, right> lies in mask
            dyn(v, subl, dic, goal);
            dyn(v, subr, dic, goal);
            //dump("bl", subl);
            //dump("br", subr);
            for(const auto& l: dic[subl]){
                for(const auto& r: dic[subr]){
                    store_plus(dic[mask], l,r,goal);
                    store_time(dic[mask], l,r,goal);
                    if(l.first>r.first){
                        store_subs(dic[mask], l,r,goal);
                        if(r.first!=0 && l.first % r.first == 0){
                            store_divi(dic[mask], l,r,goal);
                        }
                    }
                }
            }
        }
    }

}

void solve(const std::vector<size_t>& v, const int &goal){
    Dic dic;
    for(size_t i=0;i<v.size(); ++i){
        size_t mask = 1 << i;
        dic[mask][v[i]] = new Tree(v[i]);
    }
    dyn(v, (1<<v.size())-1, dic, goal);
    for(const auto&p :dic){
        for(const auto&q : p.second){
            delete q.second;
        }
    }
}
int main(int argc, char* argv[]){
    T1_START = std::chrono::high_resolution_clock::now();
    std::vector<size_t> v;
    for(size_t i = 1;i<argc-1;++i){
        v.push_back(atoi(argv[i]));
    }
    size_t goal = atoi(argv[argc-1]);
    solve(v,goal);
    return 0;
}

ca carbure mieux, mais bon, pas fantastique tjs
Code: Tout sélectionner
g++ compte.cpp -O3 -std=c++11 && ./a.out 1 2 213 8 9 18 107 82 90 12 1000000
14 ms:(((107)+(18))*(8))*((((90)+(12))*(9))+(82))
49 ms:(((((90)+(12))*(9))+(82))*(8))*((107)+(18))
71 ms:(((((90)+(12))*(9))+(82))*((107)+(18)))*(8)
531 ms:(((82)*(((18)+(12))+(8)))+(9))*((213)+(107))
1274 ms:((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107))
5891 ms:(((((90)*(2))+(107))+(213))*((82)+(18)))*((12)+(8))
6103 ms:(((82)+(18))*((12)+(8)))*((((90)*(2))+(107))+(213))
6298 ms:(((((90)*(2))+(107))+(213))*((12)+(8)))*((82)+(18))
//note: les deux echantillons en dessous sont pa normaux car 8 et 2 intervertis KO
8500 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(2))+(8)
8674 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(8))+(2)
27690 ms:(((((213)+(90))*(12))*(2))+(((82)+(9))*(8)))*((107)+(18))
41297 ms:((((107)+(18))*(8))*(1))*((((90)+(12))*(9))+(82))
41714 ms:((((((90)+(12))*(9))+(82))*(8))*(1))*((107)+(18))
41933 ms:((((((90)+(12))*(9))+(82))*((107)+(18)))*(1))*(8)
41995 ms:((((((90)+(12))*(9))+(82))*((107)+(18)))*(8))*(1)
48108 ms:((((82)*(((18)+(12))+(8)))+(9))*(1))*((213)+(107))
48481 ms:((((82)*(((18)+(12))+(8)))+(9))*((213)+(107)))*(1)
54872 ms:((((((90)*(8))+(107))*(9))+((213)*(12)))+(1))*((82)+(18))
56937 ms:(((((((90)+(82))*(18))+(12))+(9))+(8))*(1))*((213)+(107))
58687 ms:(((((((90)*(8))+(213))*((107)+(12)))+(82))*(9))+(1))+(18)
59906 ms:((((((((107)+(18))+(8))*(90))+(12))+(213))*(82))+(1))+(9)
62689 ms:((((((((107)+(18))+(8))*(90))+(12))+(213))*(82))+(9))+(1)
62689 ms:(((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107)))*(1)
68894 ms:(((107)+(18))*(8))*(((90)*(9))+((((82)+(12))+(1))*(2)))
72313 ms:(((107)+(18))*(8))*(((82)*((9)+(1)))+((90)*(2)))
72441 ms:((((107)*((9)+(1)))+((90)*(2)))*(8))*((82)+(18))
72524 ms:((((82)*((9)+(1)))+((90)*(2)))*(8))*((107)+(18))
72763 ms:((((82)*((9)+(1)))+((90)*(2)))*((107)+(18)))*(8)
76787 ms:((((90)*(9))+((((82)+(12))+(1))*(2)))*(8))*((107)+(18))
80036 ms:((((90)*(9))+((((82)+(12))+(1))*(2)))*((107)+(18)))*(8)
86046 ms:((((213)+(90))*(((12)*(2))+(9)))+(1))*((82)+(18))
87991 ms:((((82)*((18)+(1)))*(2))+(9))*((213)+(107))
90986 ms:((((((90)+(82))+(1))*(18))+(9))+(2))*((213)+(107))

------EDIT 2: fix du bug des dupplicate (je prenais pas le plus petit terme)
Code: Tout sélectionner
#define PLUS_OP -1
#define TIME_OP -2
#define SUBS_OP -3
#define DIVI_OP -4
#include <vector>
#include <map>
#include <sstream>
#include <iostream>
#include <chrono>
#include <bitset>

auto T1_START = std::chrono::high_resolution_clock::now();
class Tree{
public:
    Tree(int op, int val=0, const Tree* left=NULL, const Tree* right=NULL):
        _op(op),
        _val(val),
        _left(left),
        _right(right){
        if(op >= 0){
            _val = op;
            _rightVal = op;
        }else{
            _val = val;
            if(op == SUBS_OP || op == DIVI_OP){
                _rightVal = -right->_val;
            }else{
                _rightVal = right->_val;
            }
        }
    }
    int _op;
    size_t _val;
    int _rightVal;
    const Tree* _left;
    const Tree* _right;
    std::string toString()const{
        if(_op >= 0){
            std::stringstream oss;
            oss<<_op;
            return oss.str();
        }
        std::stringstream oss;
        char symbol;
        if(_op==-1){
            symbol = '+';
        }else if(_op==-2){
            symbol = '*';
        }else if(_op==-3){
            symbol = '-';
        }else if(_op==-4){
            symbol = '/';
        }
        oss<<"("<<_left->toString()<<")"<<symbol<<"("<<_right->toString()<<")";
        return oss.str();
    }
    bool isMul()const{
        return _op >= 0 || _op == TIME_OP || _op == DIVI_OP;
    }
    bool isAdd()const{
        return _op >= 0 || _op == PLUS_OP || _op == SUBS_OP;
    }
    static bool isAddSubOk(const Tree*a, const Tree*b){
        if(a->isAdd()){
            return a->_rightVal >= b->_val && b->isMul();
        }
        return a->_val >= b->_val && b->isMul();
    }
    static bool isMulDivOk(const Tree*a, const Tree*b){
        if(a->isAdd()){
            return a->_val >= b->_val && b->isAdd();
        }
        return a->_rightVal >= b->_val && b->isAdd();
    }
};
typedef std::map<size_t, std::map<size_t, Tree*>> Dic;
void dump(const std::string& s, const Dic &d){
    std::cout<<s<<std::endl;
    for(const auto& p: d){
        std::cout<<p.first<<std::endl;
        for(const auto& v: p.second){
            std::cout<<"\t"<<v.first<<":"<<v.second->toString()<<std::endl;
        }
    }
}
void dump(const std::string& s, const size_t &l){
    std::bitset<sizeof(l)> b(l);
    std::cout<<s<<" "<<b<<std::endl;
}
void print_goal(const std::string& s){
    auto t2 = std::chrono::high_resolution_clock::now();
      std::cout<<(std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - T1_START).count()/1000000)
      << " ms:"
      << s
      <<std::endl;
}
void dump(const Tree* t, const std::string& prefix = ""){
    if(t->_op >= 0){
        std::cout<<prefix<<t->_op<<std::endl;
        return;
    }
    std::string sign;
    if(t->_op==-1){sign="+";}
    if(t->_op==-2){sign="*";}
    if(t->_op==-3){sign="-";}
    if(t->_op==-4){sign="/";}
    std::cout<<"prefix"<<" val:" << t->_val<<" rv:"<<t->_rightVal<<" op:"<<sign<<std::endl;
    std::cout<<prefix<<"left"<<std::endl;
    dump(t->_left, prefix+" ");
    std::cout<<prefix<<"right"<<std::endl;
    dump(t->_right, prefix+" ");
}
void store_plus(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    if(!Tree::isAddSubOk(l.second,r.second)){
        return;
    }
    const auto& res = l.first+r.first;
    m[res] = new Tree(PLUS_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_subs(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first-r.first;
    if(!Tree::isAddSubOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(SUBS_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_time(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first*r.first;
    if(!Tree::isMulDivOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(TIME_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
void store_divi(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
    const auto& res = l.first/r.first;
    if(!Tree::isMulDivOk(l.second,r.second)){
        return;
    }
    m[res] = new Tree(DIVI_OP, res, l.second, r.second);
    if(res == goal){
        print_goal(m[res]->toString());
    }
}
size_t MAX_CALLS = 0;
void dyn(const std::vector<size_t>& v, size_t mask, Dic& dic, size_t goal){
    if(dic.find(mask)!=dic.end())return;
    dic[mask];
    const auto& n = v.size();
    size_t ones = (1<<n)-1;;
    size_t umask = mask^ones;
    for(size_t left = 1; left<ones; ++left){
        size_t right = left^(ones);
        size_t subl = left & mask;
        size_t subr = right & mask;
        if(subl && subr && (umask&left)==0){ //the partition<left, right> lies in mask
            dyn(v, subl, dic, goal);
            dyn(v, subr, dic, goal);
            //dump("bl", subl);
            //dump("br", subr);
            for(const auto& l: dic[subl]){
                for(const auto& r: dic[subr]){
                    if(l.first>r.first){
                        store_plus(dic[mask], l,r,goal);
                        store_time(dic[mask], l,r,goal);
                        store_subs(dic[mask], l,r,goal);
                        if(r.first!=0 && l.first % r.first == 0){
                            store_divi(dic[mask], l,r,goal);
                        }
                    }
                }
            }
        }
    }

}

void solve(const std::vector<size_t>& v, const int &goal){
    Dic dic;
    for(size_t i=0;i<v.size(); ++i){
        size_t mask = 1 << i;
        dic[mask][v[i]] = new Tree(v[i]);
    }
    dyn(v, (1<<v.size())-1, dic, goal);
    for(const auto&p :dic){
        for(const auto&q : p.second){
            delete q.second;
        }
    }
}
int main(int argc, char* argv[]){
    T1_START = std::chrono::high_resolution_clock::now();
    std::vector<size_t> v;
    for(size_t i = 1;i<argc-1;++i){
        v.push_back(atoi(argv[i]));
    }
    size_t goal = atoi(argv[argc-1]);
    solve(v,goal);
    return 0;
}

Code: Tout sélectionner
496 ms:(((((90)+(12))*(9))+(82))*((107)+(18)))*(8)
4343 ms:(((82)*(((18)+(12))+(8)))+(9))*((213)+(107))
10998 ms:((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107))
12364 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))-(8))+(18)
14384 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(18))-(8)
17337 ms:(((((90)*(12))-(82))+(2))*((107)+(18)))*(8)
19205 ms:(((107)+(18))*(((12)*(9))-(8)))*((82)-(2))
19280 ms:((((107)*((82)-(9)))*(8))+(12))*((18)-(2))
20551 ms:(((((90)+(8))*(9))-(82))*((107)+(18)))*((12)-(2))
20753 ms:((((82)+(9))*((90)-(2)))-(8))*((107)+(18))
23724 ms:((((((82)*(2))-(90))*(12))*(9))+(8))*((107)+(18))
26098 ms:(((((((107)+(9))*(12))-(2))*(90))-(82))-(18))*(8)
26286 ms:((((((18)*(12))+(107))*((90)+(82)))*(9))*(2))-(8)
32908 ms:(((((213)-(90))*(9))-(107))*((82)+(18)))*((12)-(2))
38228 ms:((((((90)*(18))-(12))*(2))-(82))-(9))*((213)+(107))
46279 ms:((((107)*(18))+(12))*(((213)*(2))+(90)))-(8)
48683 ms:((((213)+((90)*(2)))+(107))*((82)+(18)))*((12)+(8))
49848 ms:((((((213)-(90))*((107)-(8)))+(18))*(82))-(2))+(12)
58503 ms:((((((213)-(90))*((107)-(8)))+(18))*(82))+(12))-(2)
64804 ms:((((107)*(82))-(2))*(((213)-(90))-(9)))-(8)
66677 ms:((((82)*(12))*(9))-((107)*(8)))*(((213)-(90))+(2))
73155 ms:((((((213)+(9))*(90))+(12))+(8))*((107)-(82)))*(2)
73249 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(8))+(2)
81106 ms:((((((213)+(9))*(90))+(12))+(8))/(2))*((82)+(18))
81553 ms:((((((90)*(9))+(213))+(18))*(12))+(8))*((82)-(2))
84636 ms:(((((213)+((12)*(9)))+(2))*((90)+(82)))*(18))-(8)
85712 ms:((((((213)+(9))*(90))+(12))+(8))*((82)+(18)))/(2)
89265 ms:(((((213)-(18))-(8))*(107))-(9))*((((82)-(12))*(2))-(90))
^C


sensiblement moins de solutions (29 vs 35) pour 1m30s, il _faudrait_ que je fasse une instance plus petite pour être sûr que je rate rien, mais bon, je pense que le cut de l'associativité est correct
Code: Tout sélectionner
    static bool isAddSubOk(const Tree*a, const Tree*b){
        if(a->isAdd()){
            return a->_rightVal >= b->_val && b->isMul();
        }
        return a->_val >= b->_val && b->isMul();
    }
    static bool isMulDivOk(const Tree*a, const Tree*b){
        if(a->isAdd()){
            return a->_val >= b->_val && b->isAdd();
        }
        return a->_rightVal >= b->_val && b->isAdd();
    }
la vie est une fête :)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 16 Oct 2017, 09:39

je met de côté l'exactitude (..),

je note avant que joublie de ma nuit...
un autre pb est que le lookup dans la map est pas top pour deux raisons:
1-pb mémoire (ca swappe)
2-temps dacces

pr 1, on finit de tte manière par atteindre la limite. dc il faut arriver à "switcher" de map par rapport à la récursion courante
de fait, ne plus considérer dic[mask] mais plutot arriver à générer le swap des valeures mémoires ns même?
Vu qu'on va de submask en submask, j'ai envie de regarder quelle taille représente un submask
de manière à voir quel est le plus gros submask que je peux tenir en mémoire. (genre nb max darrangements etc)
pour son mask parent, à chaque changement de submask, je load un autre dic en mémoire

etape2.1: autant réutiliser les etnrées de deux submasks "frères" (même boucle): je peux récupérer le submask courant, et y enlever ttes les valeurs générées par la présence des bits de mon ancien submask qui sont pas dans mon submask courant

etape2.2: lorsque je génère mes submasks, j'ai envie d'avoir dans l'ordre des submasks "proches" de manière à pouvoir réutiliser au max mon cache (au lieu daller betement de 1 à 1<<n-1)
la vie est une fête :)

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Défi: le compte est bon

par pascal16 » 24 Oct 2017, 23:04

J'avais pas retrouvé la dicussion la semaine passée.

[url]http://eternitygames.free.fr/LeCompteEstBon.html#Premier Algorithme (récursif)[/url]

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Défi: le compte est bon

par pascal16 » 06 Sep 2018, 22:00

avec le premier algo en C++ porté en C# et les switch(op) enlevés :

1+2=3
3*213=639
639+9+18=666

90*12=1080
1080+82=1162
1162*107=124334

124334+66 = 125000

125000*8=1 000 000

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 15 Sep 2018, 00:03

je viens d'avoir une idée...

tjs sur cette histoire de groupe additif et groupe multiplicatif
(rappel,
dans un groupe additif, on impose les + d'abord, les - ensuite, et les nombres par ordre decroissants
dans un groupe multiplicatif, pareil mais avec * puis /
)

avec 10nb, on a (max) 9 opérations
par ex (notation qui se lit de gauche à droite, pas de prio des opérateurs)
++***++-/
qui signifie par ex
13+2+1
(13+2+1)*(3*2*2)
[(13+2+1)*(3*2*2)]+(6+4-5)
[[(13+2+1)*(3*2*2)]+(6+4-5) ] /6
on simplifie la notation avec A et M (les groupes additifs, multiplicatifs)
AMAM

L'idée c'est de générer ts les arbres d'opérateures puis pr chaque arbre de le remplir ac toutes les permut de nombres possibles
Jusque là rien n'est mieux: on a rien rajouté de plus que les cut sur associativité, commutativité
(si ce n'est l'attribution des nombres aux groupes (on peut un peu optimiser si on trie le tableau))

MAIS vu que maintenant pour une combi donnée on connait la fin des opérations, on peut cutter si le goal peut ou pas être atteint

par ex: pour le dernier groupe au sait que sa valeur maximale est m (si on prends les plus gros nombres pr * et plus petit pour /)
de fait, pour une permute donnée
si le goal est G
on sait que AMA doit etre supérieur à G/m (sinon le goal peut pas être atteint) et ya pas besoin de calculer la valeur du dernier groupe pour la permute donnée

pareil pour bound par en dessous

ca serait bien si on pouvait de la même manière aggréger AM (de la partie droite) et ainsi de suite mais ca m'air l'air délicat
pour choisir où privilégier les gros coeffs pour +* et petits pour -/
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Défi: le compte est bon

par Ben314 » 15 Sep 2018, 00:37

J'ai fini par retrouver (au fond d'un repertoire pourri...) le truc que j'avais fait il y a 5 ans qui fonctionne "par groupe" (donc quasi aucune redondance dans les calculs) :
Code: Tout sélectionner
#include <stdio.h>
#include <stdlib.h>

#define NbMax 20

int NbPla, Plaque[NbMax];
signed char Util[NbMax]; //  0=non utilisé; 1=addition/soustraction; 2=multiplication/division

int NbLop,Lop[3*NbMax], NbLopSol,LopSol[3*NbMax];
// Liste des opérations Code=(0x10000 si mult/div + 0x100.Nb_Plaques + Nb_Add/Mult) puis liste

int Prof,Atrouver,EcartMin,NbPlaMax;

int NbCalcul,NbSol,NbTrouve[10000],test[NbMax];

//============================================================================================================

void Affiche(int *Tb, int NbTb )
{ int k,i,nb,nb2,R;
//  nb=(Tb[0]>>8)&0xFF; nb2=Tb[0]&0xFF;
//  for(i=0;i<NbTb-1;i++) printf("%d , ",Tb[i]); printf("%d [%d,%d]\n",Tb[i],nb,nb2);
  k=0; do
  { nb=(Tb[k]>>8)&0xFF; nb2=Tb[k]&0xFF;
    if((Tb[k]&0x10000)==0)
    { k++; R=Tb[k++]; printf("%d",R);
      for(i=1;i<nb2;i++) { R+=Tb[k]; printf(" + %d",Tb[k++]);}
      for(   ;i<nb ;i++) { R-=Tb[k]; printf(" - %d",Tb[k++]);}
      printf(" = %d ; ",R);
    }
    else
    { k++; R=Tb[k++]; printf("%d",R);
      for(i=1;i<nb2;i++) { R*=Tb[k]; printf(" x %d",Tb[k++]);}
      for(   ;i<nb ;i++) { R/=Tb[k]; printf(" / %d",Tb[k++]);}
      printf(" = %d ; ",R);
    }
  }
  while(k<NbTb);
  printf("[%d",Plaque[0]); for(i=1;i<NbPla;i++) printf(",%d",Plaque[i]);
  printf("] [%d",Util[0]); for(i=1;i<NbPla;i++) printf(",%d",Util[i]); printf("]");
  //scanf("%d",&i);
  printf("\n");
}

//============================================================================================================

void SousEnsemble(int *Nb, int k, int max, int m);

void ListeSomme(void)
// Cherche toutes les façons d'écrire NbPla = 1.Nb[1]+2.Nb[2]+3.Nb[3]+...+imax.Nb[imax] 
{ int i,imax,Nb[NbMax];
  Nb[1]=NbPla; for(i=2;i<=NbPla;i++) Nb[i]=0; imax=2;
  do
  { if(Nb[1]>=2){ Nb[1]-=2; Nb[2]++;}
    else
    { for(i=2;Nb[i]==0;i++);
      if((Nb[1]==1)||(Nb[i]>=2)){ Nb[1]+=i*(Nb[i]-1)-1; Nb[i]=0; Nb[i+1]++;}
      else{ Nb[1]=i-1; Nb[i]=0; for(i++;Nb[i]==0;i++); Nb[1]+=i*(Nb[i]-1); Nb[i]=0; Nb[i+1]++;}
      if(i==imax) imax++;
    }
//    test[Prof]++;
//    if((test[1]==1)&&(test[2]>17)&&(test[2]<22))
//    { char c=' '; printf("%d =",NbPla);
//      for(i=1;i<=NbPla;i++) if(Nb[i]){ printf("%c%dx%d ",c,Nb[i],i); c='+';} else printf("  .  ");
//      printf("\n"); //scanf("%d",&i);
//    }
    SousEnsemble(Nb,imax,NbPla-1,2);
  }
  while(Nb[NbPla]==0);
}

void SousEnsemble(int *Nb, int k, int max, int m)
// Cherche un sous ensemble à k éléments de {0..max} dont le maximum est >=k.Nb[k]-1 ; m=N° de l'appel
{ int i,j,k2,j1,E[NbMax],P[NbMax],T1,T2,R; signed char U[NbMax],S[NbMax],OK;
  for(i=0;i<k-1;i++) E[i]=i; E[k-1]=k*Nb[k]-1; if(k<NbMax) E[k]=-1;
  Nb[k]--; if(Nb[k]>0) k2=0; else { k2=k-1; while((k2>1)&&(Nb[k2]==0)) k2--; }
  do
  { if(Prof<2) OK=1; else
    { j1=2-(Prof&1); j=0; for(i=0;i<k;i++) if(Util[E[i]]!=j1) j++;
      OK=(j<2);
    } 
    if(OK)
    { for(i=0,j=j1=E[0];j<NbPla;j++) if(j==E[i]){       P[i]=Plaque[j]; U[i]    =Util[j];  i++;}
                                     else       { Plaque[j1]=Plaque[j]; Util[j1]=Util[j]; j1++;}
      for(i=0;i<k;i++) S[i]=0;
      do
      { if((Prof&1)==0)
        { T1=T2=0; j1=0; for(i=0;i<k;i++) if(S[i]){ T1+=P[i]; j1++;} else T2+=P[i];
          if(T1>T2){ R=T1-T2; OK=1; i=0;} else if(T2>T1){ R=T2-T1; OK=2; i=0;} else OK=0;
        }
        else
        { T1=T2=1; j1=0; OK=1; for(i=0;i<k;i++){ if((j=P[i])==1) OK=0; if(S[i]){ T1*=j; j1++;} else T2*=j; }
          if(OK) if(T1%T2==0){ R=T1/T2; i=1<<16;} else if(T2%T1==0){ R=T2/T1; OK=2; i=1<<16;} else OK=0;
        }
        if(OK)
        { j=NbLop; if(OK==1)
          { Lop[j++]=i+(k<<8)+j1; j1+=j; for(i=0;i<k;i++) if(S[i]) Lop[j++]=P[i]; else Lop[j1++]=P[i];}
          else
          { j1=k-j1; Lop[j++]=i+(k<<8)+j1; j1+=j; for(i=0;i<k;i++) if(S[i]) Lop[j1++]=P[i]; else Lop[j++]=P[i];}
          NbLop+=k+1; NbPla-=k-1; Plaque[NbPla-1]=R; Util[NbPla-1]=1+(Prof&1);
          for(i=NbPla-2;(i>=0)&&(Util[i]==0);i--);
          if((k2==1)&&(i==-1))
          { if((abs(R-Atrouver)<EcartMin)||((abs(R-Atrouver)==EcartMin)&&(NbPla>NbPlaMax)))
            { EcartMin=abs(R-Atrouver); NbPlaMax=NbPla; NbLopSol=NbLop;
              for(i=0;i<NbLop;i++) LopSol[i]=Lop[i];
            }
            NbCalcul++; //if(R<1000) NbTrouve[R]++; // Pour tests...
            if(R==Atrouver){ NbSol++; printf("%d)  ",NbSol); Affiche(Lop,NbLop); }
          }
          if(k2==0) SousEnsemble(Nb,k,E[k-1]-k,m+1);
          else if(k2>1) SousEnsemble(Nb,k2,NbPla-m,m+1);
          else if(NbPla>=2){Prof++; ListeSomme(); Prof--;}
          NbPla+=k-1; NbLop-=k+1;
        }
        for(i=k-1;S[i]!=0;i--) S[i]=0; S[i]=1;
      }
      while(S[0]==0);
      for(i=k-1,j=NbPla-1,j1=NbPla-k-1;j>=E[0];j--)
        if(j==E[i]){ Plaque[j]=P[i];       Util[j]=U[i];      i--;}
        else       { Plaque[j]=Plaque[j1]; Util[j]=Util[j1]; j1--;}
    }
    for(i=0;(i+1<k)&&(E[i+1]==E[i]+1);i++);
    E[i]++; for(j=0;j<i;j++) E[j]=j;
  }
  while(E[k-1]<=max);
  Nb[k]++;
}


int NbLop,Lop[3*NbMax], NbLopSol,LopSol[3*NbMax];
// Liste des opérations Code=(0x10000 si mult/div + 0x100.Nb_Plaques + Nb_Add/Mult) puis liste

int Prof,Atrouver,EcartMin,NbPlaMax;

//============================================================================================================

int main()
{ int i,j,deb;
  NbPla=10;
  Plaque[0]=1;
  Plaque[1]=2;
  Plaque[2]=213;
  Plaque[3]=8;
  Plaque[4]=9;
  Plaque[5]=18;
  Plaque[6]=107;
  Plaque[7]=82;
  Plaque[8]=90;
  Plaque[9]=12;
  Atrouver=1000000;
  EcartMin=10000; NbLop=0; for(i=0;i<NbPla;i++) Util[i]=0;
  NbCalcul=NbSol=0; for(i=0;i<1000;i++) NbTrouve[i]=0; for(i=0;i<NbMax;i++) test[i]=0;
  Prof=0; ListeSomme(); printf("-------------------------------------------------------------------------\n");
  Prof=1; ListeSomme(); //-> ne fait aucune addition préalable
  printf("NbCalcul = %d\n",NbCalcul);
  Affiche(LopSol,NbLopSol);
  /*for(j=0;j<20;j++)
  { deb=1;
    for(i=100;i<999;i++)
      if(NbTrouve[i]==j) if(deb) { printf("%2d : %d",j,i); deb=0; } else printf(",%d",i);
    if(!deb) printf("\n");
  }
*/
}

Mais ça doit être passablement illisible (comme d'hab...)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 15 Sep 2018, 11:51

j'ai pris le tps de compiler #cowboy
ton algo run bcp puls vite: 30s 22 sol

Code: Tout sélectionner
Mais ça doit être passablement illisible (comme d'hab...)

lol

peux tu expliquer dans le gros SousEnsemble?
j'ai essayé de lire un peu mais jpense qu'il me faudrait au moins un weekend pour décrypter :(
la vie est une fête :)

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Défi: le compte est bon

par pascal16 » 18 Sep 2018, 10:43

Je repasse de temps en temps voir mon algo .
j'essaie de plus de faire qu'il trouve toutes les solutions, les plus simples en premier puis les autres, pas comme la récursivité basique.
Pour n=6, il va très vite, me sort plein de solutions parasites
Pour n=10, il met 3h, me sort plein de solutions parasites (4400 ) et finalement m'a oublié des solutions suite à un copier-colle mal fait.
Je vai essayer un anti-parasite...
Modifié en dernier par pascal16 le 18 Sep 2018, 14:59, modifié 1 fois.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Défi: le compte est bon

par Ben314 » 18 Sep 2018, 13:57

fatal_error a écrit:Peux tu expliquer dans le gros SousEnsemble?
j'ai essayé de lire un peu mais jpense qu'il me faudrait au moins un weekend pour décrypter :(
Vu que ça fait je sais pas combien d'années que j'ai tapé le bidule, ben... je peine pas mal à retrouver comment ça marche.

Le principe est (relativement) simple.
Au départ, tu as ton ensemble de (par exemple) 10 plaques {P0,P1,P2,...,P9}
PROFONDEUR 1 :
- Tu regarde toute les possibilités de partitionner cet ensemble en sous ensembles (dont au moins un sous ensemble contient 2 éléments). Une des possibilités, c'est par exemple { {P1} , {P2} , {P5} , {P8}, {P0,P7} , {P3,P4,P6,P9} }.
Ici, il n'y a aucune notion d'ordre :
{ {P1} , {P2} , {P5} , {P8}, {P0,P7} , {P3,P4,P6,P9} } = { {P2} , {P8}, {P7,P0} , {P1} , {P4,P6,P3,P9} , {P5}}
- Pour chacun des sous ensemble ayant ayant au moins 2 élément, tu regarde toute les façons de le couper en deux (avec éventuellement une des deux parties vides) par exemple, tu coupe {P0,P7} en {P7,P0}+ensemble vide pour signifier que ce que tu va faire ensuite, c'est P0+P7 et tu coupe {P3,P4,P6,P9} en {P3,P6}+{P4,P9} pour signifier que ce que tu va faire ensuite, c'est (P3+P6)-(P4+P9) ou bien (P4+P9)-(P3+P6) si P3+P6>P4+P9.
- Une fois tout ça choisi, tu considère le nouvel ensemble {Q1,Q2,Q3,Q4,Q5,Q6} avec
Q1=P1 ; Q2=P2 ; Q3=P5 ; Q4=P8 ; Q5=P0+P7 ; Q6=(P3+P6)-(P4+P9) (par exemple).
PROFONDEUR 2 :
Tu recommence à faire exactement la même chose partant de {Q1,Q2,Q3,Q4,Q5,Q6} (partition puis coupage en deux) mais cette fois avec des multiplications/divisions et en vérifiant que le résultat des divisions donne un nombre entier. Parmi les différent cas possible, tu aurais par exemple {R1,R2,R3,R4} avec R1=Q2 ; R2=Q5 ; R3=Q6 ; R4=Q1*Q4/ Q3 (avec en rouge ceux qui sont des "nouveaux calculs" et pas de simple recopie d'éléments)
PROFONDEUR 3 :
Partant de {R1,R2,R3,R4} tu recommence à chercher toutes les partitions possible, MAIS, tu ne garde que celles où, dans les partie non réduite à un élément, il y a au moins un des éléments qui a été modifié le coup précédent (i.e. qui est "en rouge"). Le but, c'est de ne pas considérer de groupement du style {R1,R2} vu que R1+R2=Q2+Q5=P2+P0+P7 qui est un regroupement qui aurai déjà pu être fait à la profondeur 1.
PROFONDEUR 4 :
Idem profondeur 3, mais avec des multiplié/divisé à la place des +/-.
etc...

Et évidement, à chaque fois que tu fait un calcul, par exemple (P3+P6)-(P4+P9) ou Q1*Q4/ Q3, tu compare le résultat avec le "résultat final à obtenir" et, s'il est égal à ce résultat (ou bien s'il est plus proche que ce que tu as trouvé précédemment), tu enregistre quelque part la suite de calculs qui à mené à ce résultat. Cela oblige, dans le processus récursif, à avoir accès en permanence à la liste des opérations qui ont mené à "l'état actuel" (sans être obligé de "remonter" dans la récursivité vu qu'on veut pouvoir la continuer).
Modifié en dernier par Ben314 le 19 Sep 2018, 08:25, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Défi: le compte est bon

par fatal_error » 18 Sep 2018, 23:29

Slt ben,

Ts clair! Thx

Donc il reste pe tester si a un moment donne plus aucune descente ne pourra mener aux resultat

Jessairai de tester si je trouve de la motivation/rouille sufisamment : D
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21479
Enregistré le: 11 Nov 2009, 23:53

Re: Défi: le compte est bon

par Ben314 » 19 Sep 2018, 08:30

Sauf erreur (je rappelle que j'arrive pas a me relire moi même...), tel qu'il est (dans le post précédent), le programme est récursif et ne s'arrête que lorsqu'il a énuméré absolument tout les cas de figure.
Et il affiche toutes les solutions qu'il trouve au fur et à mesure, ce qui permet de voir qu'il n'y a quasiment pas de redondance (i.e. deux solution distincte pour le programme qui en fait sont les même à quelques permutations près).

Si j'ai du temps (par exemple les prochaine vacances), je regarderais si j'arrive pas à faire un code plus lisible.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Défi: le compte est bon

par pascal16 » 22 Sep 2018, 15:59

Je viens de voir un algo hyper rapide, même pour 10 plaques respectant les règles du compte est bon.

Le gars a en fait enregistré dans un BbD toute une série de résultats et va simplement rechercher les solutions déjà trouvées avec au pire quelques calculs.

Le problème, c'est que c'est pas facilement transposable à 10 plaquettes avec des nombres quelconques. Même si on s'approche des log de recherche de nombres premiers qui, au bout d'un certains temps, voient la création de la liste de tous le nombres premier comme accélération du calcul.

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Défi: le compte est bon

par pascal16 » 20 Oct 2018, 19:22


 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite