Supprimer quelques bits et compter

26

Considérez toutes les 2^ndifférentes chaînes binaires de longueur net supposez n > 2. Vous êtes autorisé à supprimer exactement les b < n/2bits de chacune des chaînes binaires, en laissant des chaînes de longueur n-brestantes. Le nombre de chaînes distinctes restantes dépend des bits que vous supprimez. En supposant que votre objectif est de laisser le moins de chaînes différentes restantes possible, ce défi consiste à écrire du code pour calculer combien vous pouvez en laisser en fonction de n.

Exemple, n=3et b = 1. Vous ne pouvez laisser que les deux chaînes 11et 00.

Pour n=9et b = 1,2,3,4nous avons70,18,6,2

Pour n=8et b = 1,2,3nous avons40,10,4

Pour n=7et b = 1,2,3nous avons20,6,2

Pour n=6et b = 1,2nous avons12,4

Pour n=5et b = 1,2nous avons6,2

Cette question a été posée à l'origine par moi en 2014 sous une forme différente sur MO .

Entrée et sortie

Votre code doit prendre un entier net produire un seul entier pour chaque valeur de bdépart b = 0et d'augmentation.

But

Votre score est le plus élevé npour lequel votre code se termine pour tous b < n/2en moins d'une minute sur mon PC basé sur Linux. En cas de bris d'égalité, le plus gros de bvotre code arrive pour les plus gros ngains communs . En cas de bris d'égalité sur ce critère aussi, le code le plus rapide pour les plus grandes valeurs de net bdécide. Si les temps sont dans une seconde ou deux l'un de l'autre, la première réponse publiée l'emporte.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue de bibliothèque que vous aimez. Parce que je dois exécuter votre code, cela aiderait s'il était gratuit (comme dans la bière) et fonctionnait sous Linux.

Anush
la source
Je suppose en b > 0tant qu'exigence d'entrée supplémentaire? Ou serait- n=3il b=0simplement sorti 2^ncomme résultat?
Kevin Cruijssen
@KevinCruijssen Il devrait en 2^neffet sortir .
Anush
En outre, vous dites que l'entrée est un simple net un seul b, mais le score est le plus élevé npour lequel le code se termine b < n/2en moins d'une minute. Ne serait-il pas préférable d'avoir une seule entrée ndans ce cas et de produire tous les résultats pour 0 <= b < n/2? Ou devrions-nous fournir deux programmes / fonctions: l'un prenant deux entrées net b, et l'autre ne prenant que l'entrée net la sortie de tous les résultats dans la plage 0 <= b < n/2?
Kevin Cruijssen
2
Eh bien, j'avais déjà voté pour votre défi, alors je ne peux pas le refaire. :) Bien que je ne sache pas comment calculer cela efficacement (les algorithmes O efficaces étaient quelque chose pour lesquels j'ai toujours été mauvais .. et l'un des rares sujets de l'informatique que j'ai dû refaire quelques fois), il semble que un défi très intéressant. Je suis curieux de voir quelles réponses les gens trouvent.
Kevin Cruijssen
2
Y a-t-il un exemple de travail? Ce serait un bon point de départ, à la fois en termes de justesse, mais aussi de comparaison de vitesse.
maxb

Réponses:

6

Python 2.7 / Gurobi n = 9

Cette solution est une utilisation très simple du solveur ILP de Gurobi pour les problèmes booléens à nombres entiers (MIP).

La seule astuce consiste à supprimer la symétrie dans le complément à 1 pour réduire de moitié la taille des problèmes.

En utilisant la licence "gratuite" à durée limitée de Gurobi LLC, nous sommes limités à 2000 contraintes, mais résoudre 10 del 1 est bien en dehors du délai de 60 secondes de toute façon sur mon ordinateur portable.

from gurobipy import *
from itertools import combinations

def mincover(n,d):
    bs = pow(2,n-1-d)
    m = Model()
    m.Params.outputFlag = 0
    b = {}
    for i in range(bs):
      b[i] = m.addVar(vtype=GRB.BINARY, name="b%d" % i)
    m.update()
    for row in range(pow(2,n-1)):
      x = {}
      for i in combinations(range(n), n-d):
        v = 0
        for j in range(n-d):
          if row & pow(2,i[j]):
            v += pow(2,j)
        if v >= bs:
          v = 2*bs-1-v
        x[v] = 1
      m.addConstr(quicksum(b[i] for i in x.keys()) >= 1)
    m.setObjective(quicksum(b[i] for i in range(bs) ), GRB.MINIMIZE)
    m.optimize()
    return int(round(2*m.objVal,0))

for n in range(4,10):
    for d in range((n//2)+1):
        print n, d, mincover(n,d)

MISE À JOUR + CORR: 10,2 a une taille de solution optimale 31 (voir par exemple) Gurobi montre qu'aucune solution symétrique de taille 30 n'existe (retourne un problème irréalisable). modèles d'entiers 0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255ou0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255

Jayprich
la source
Vous avez battu le record de la "prime infinie réclamée la plus rapide"?
user202729
Je ne vois aucune prime ici, que voulez-vous dire?
jayprich
@ user202729 Oui .. Je l'ai réglé trop bas. J'aurais dû le mettre à n = 10 :)
Anush
En fait, le résoudre à n = 9 n'est pas une chose facile. C'est pourquoi OP utilise une bibliothèque existante (qui est censée être meilleure qu'une solution manuscrite, comme la mienne).
user202729
1
Merci @ChristianSievers Je vois MO affirmer que 10,2 n'a que des optima asymétriques que je ne peux ni réfuter ni vérifier. Si je supprime le raccourci d'hypothèse de symétrie qui fonctionne jusqu'à n = 9, il s'avère que Gurobi peut toujours résoudre jusqu'à n = 9 dans le temps requis.
jayprich
3

C ++, n = 6

Force brute avec quelques petites optimisations.

#include<cassert>
#include<iostream>
#include<vector>

// ===========
/** Helper struct to print binary representation.
`std::cout<<bin(str,len)` prints (str:len) == the bitstring 
represented by last (len) bits of (str).
*/
struct bin{
    int str,len;
    bin(int str,int len):str(str),len(len){}
};
std::ostream& operator<<(std::ostream& str,bin a){
    if(a.len)
        return str<<bin(a.str>>1,a.len-1)<<char('0'+(a.str&1));
    else if(a.str)
        return str<<"...";
    else
        return str;
}
// ===========

/// A patten of (len) bits of ones.
int constexpr pat1(int len){
    return (1<<len)-1;
}

// TODO benchmark: make (res) global variable?

/**Append all distinct (subseqs+(sfx:sfxlen)) of (str:len) 
with length (sublen) to (res).
*/
void subseqs_(
    int str,int len,int sublen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    // std::cout<<"subseqs_ : str = "<<bin(str,len)<<", "
    // "sublen = "<<sublen<<", sfx = "<<bin(sfx,sfxlen)<<'\n';

    assert(len>=0);

    if(sublen==0){ // todo remove some branches can improve perf?
        res.push_back(sfx);
        return;
    }else if(sublen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }else if(sublen>len){
        return;
    }

    if(str==0){
        res.push_back(sfx);
        return;
    }

    int nTrail0=0;
    for(int ncut;str&&nTrail0<sublen;

        ++nTrail0,
        ncut=__builtin_ctz(~str)+1, // cut away a bit'0' of str
        // plus some '1' bits
        str>>=ncut,
        len-=ncut
    ){
        ncut=__builtin_ctz(str)+1; // cut away a bit'1' of str
        subseqs_(str>>ncut,len-ncut,sublen-nTrail0-1,
            sfx|1<<(sfxlen+nTrail0),sfxlen+nTrail0+1,
            res
        ); // (sublen+sfxlen) is const. TODO global var?
    }

    if(nTrail0+len>=sublen) // this cannot happen if len<0
        res.push_back(sfx);
}

std::vector<int> subseqs(int str,int len,int sublen){
    assert(sublen<=len);
    std::vector<int> res;
    if(__builtin_popcount(str)*2>len){ // too many '1's, flip [todo benchmark]
        subseqs_(pat1(len)^str,len,sublen,0,0,res);
        int const p1sublen=pat1(sublen);
        for(int& r:res)r^=p1sublen;
    }else{
        subseqs_(str,len,sublen,0,0,res);
    }
    return res;
}

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

/** Append all distinct (supersequences+(sfx:sfxlen)) of (str:len)
with length (suplen) to (res).
Define (a) to be a "supersequence" of (b) iff (b) is a subsequence of (a).
*/
void supseqs_(
    int str,int len,int suplen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    assert(suplen>=len);

    if(suplen==0){
        res.push_back(sfx);
        return;
    }else if(suplen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }

    int nTrail0; // of (str)
    if(str==0){
        res.push_back(sfx);
        // it's possible that the supersequence is '0000..00'
        nTrail0=len;
    }else{
        // str != 0 -> str contains a '1' bit ->
        // supersequence cannot be '0000..00'
        nTrail0=__builtin_ctz(str);
    }
    // todo try `nTrail0=__builtin_ctz(str|1<<len)`, eliminates a branch
    // and conditional statement

    for(int nsupTrail0=0;nsupTrail0<nTrail0;++nsupTrail0){
        // (nsupTrail0+1) last bits of supersequence matches with 
        // nsupTrail0 last bits of str.
        supseqs_(str>>nsupTrail0,len-nsupTrail0,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    int const strMatch=str?nTrail0+1:len; 
    // either '1000..00' or (in case str is '0000..00') the whole (str)

    for(int nsupTrail0=suplen+strMatch-len;nsupTrail0-->nTrail0;){
        // because (len-strMatch)<=(suplen-1-nsupTrail0),
        // (nsupTrail0<suplen+strMatch-len).

        // (nsupTrail0+1) last bits of supersequence matches with
        // (strMatch) last bits of str.
        supseqs_(str>>strMatch,len-strMatch,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    // todo try pulling constants out of loops
}

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

int n,b;
std::vector<char> done;
unsigned min_undone=0;

int result;
void backtrack(int nchoice){
    assert(!done[min_undone]);
    ++nchoice;
    std::vector<int> supers_s;
    for(int s:subseqs(min_undone,n,n-b)){
        // obviously (s) is not chosen. Try choosing (s)
        supers_s.clear();
        supseqs_(s,n-b,n,0,0,supers_s);
        for(unsigned i=0;i<supers_s.size();){
            int& x=supers_s[i];
            if(!done[x]){
                done[x]=true;
                ++i;
            }else{
                x=supers_s.back();
                supers_s.pop_back();
            }
        }

        unsigned old_min_undone=min_undone;
        while(true){
            if(min_undone==done.size()){
                // found !!!!
                result=std::min(result,nchoice);
                goto label1;
            }
            if(not done[min_undone])
                break;
            ++min_undone;
        }
        if(nchoice==result){
            // backtrack more will only give worse result
            goto label1;
        }

        // note that nchoice is already incremented
        backtrack(nchoice);

        label1: // undoes the effect of (above)
        for(int x:supers_s)
            done[x]=false;
        min_undone=old_min_undone;
    }
}

int main(){
    std::cin>>n>>b;

    done.resize(1<<n,0);
    result=1<<(n-b); // the actual result must be less than that

    backtrack(0);
    std::cout<<result<<'\n';
}

Exécutez localement:

[user202729@archlinux golf]$ g++ -std=c++17 -O2 delbits.cpp -o delbits
[user202729@archlinux golf]$ time for i in $(seq 1 3); do ./delbits <<< "6 $i"; done
12
4
2

real    0m0.567s
user    0m0.562s
sys     0m0.003s
[user202729@archlinux golf]$ time ./delbits <<< '7 1'
^C

real    4m7.928s
user    4m7.388s
sys     0m0.173s
[user202729@archlinux golf]$ time for i in $(seq 2 3); do ./delbits <<< "7 $i"; done
6
2

real    0m0.040s
user    0m0.031s
sys     0m0.009s
user202729
la source
1
Surtout pour encourager les autres à publier leur code s'il est plus rapide que le mien.
user202729
S'il vous plaît? ... (note: Ceci est une instance d'un problème de couverture.)
user202729
1
J'y travaille. Je ne peux tout simplement pas trouver de façon intelligente de le faire. Si personne d'autre ne répond, je mettrai la mienne qui ne peut aller jusqu'à n = 4 jusqu'à présent.
mypetlion