Défi: le compte est bon

Discutez d'informatique ici !
Avatar de l’utilisateur
anthony_unac
Vétéran
Messages: 946
Enregistré le: 30 Juin 2007, 00:31

Re: Défi: le compte est bon

par anthony_unac » 10 Nov 2016, 22: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: 5774
Enregistré le: 22 Nov 2007, 13:00

Re: Défi: le compte est bon

par fatal_error » 13 Oct 2017, 20: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: 17859
Enregistré le: 11 Nov 2009, 22:53

Re: Défi: le compte est bon

par Ben314 » 13 Oct 2017, 21: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: 5774
Enregistré le: 22 Nov 2007, 13:00

Re: Défi: le compte est bon

par fatal_error » 13 Oct 2017, 22: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: 5774
Enregistré le: 22 Nov 2007, 13:00

Re: Défi: le compte est bon

par fatal_error » 14 Oct 2017, 19: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: 17859
Enregistré le: 11 Nov 2009, 22:53

Re: Défi: le compte est bon

par Ben314 » 14 Oct 2017, 21: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: 5774
Enregistré le: 22 Nov 2007, 13:00

Re: Défi: le compte est bon

par fatal_error » 14 Oct 2017, 23: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: 5774
Enregistré le: 22 Nov 2007, 13:00

Re: Défi: le compte est bon

par fatal_error » 16 Oct 2017, 08: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 Complexe
Messages: 2558
Enregistré le: 01 Mar 2017, 13: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, 22:04

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

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

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

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