Usuń niektóre bity i policz

26

Rozważ wszystkie 2^nróżne ciągi binarne długości ni załóż n > 2. Możesz usunąć dokładnie b < n/2bity z każdego z ciągów binarnych, pozostawiając ciągi o długości n-bpozostającej. Liczba pozostałych ciągów znaków zależy od tego, które bity usuwasz. Zakładając, że Twoim celem jest pozostawienie jak najmniejszej liczby różnych ciągów znaków, wyzwaniem jest napisanie kodu, aby obliczyć, jak mało możesz pozostawić jako funkcję n.

Przykład n=3i b = 1. Możesz zostawić tylko dwa ciągi 11i 00.

Za n=9i b = 1,2,3,4mamy70,18,6,2

Za n=8i b = 1,2,3mamy40,10,4

Za n=7i b = 1,2,3mamy20,6,2

Za n=6i b = 1,2mamy12,4

Za n=5i b = 1,2mamy6,2

To pytanie zostało pierwotnie postawione przeze mnie w 2014 r. W innej formie na temat MO .

Wejście i wyjście

Twój kod powinien przyjmować liczbę całkowitą ni wypisywać jedną liczbę całkowitą dla każdej wartości brozpoczynania od b = 0i zwiększania.

Wynik

Twój wynik jest najwyższy, ndla którego Twój kod wypełnia wszystko b < n/2w ciągu minuty na moim komputerze z systemem Linux. W przypadku przerw remisowych, największy bTwój kod otrzyma za wspólne największe nwygrane. W przypadku zerwania remisu również na tym kryterium decyduje najszybszy kod dla największych wartości ni b. Jeśli czasy mieszczą się w sekundach lub dwóch, wygrywa pierwsza opublikowana odpowiedź.

Języki i biblioteki

Możesz użyć dowolnego języka biblioteki, który ci się podoba. Ponieważ muszę uruchomić kod, pomogłoby, gdyby był darmowy (jak w piwie) i działał w Linuksie.

Anush
źródło
Przyjmuję b > 0jako dodatkowy wymóg wejściowy? A może n=3i b=0po prostu wyjście 2^njako wynik?
Kevin Cruijssen
@KevinCruijssen To powinno 2^nrzeczywiście generować .
Anush
Mówisz także, że dane wejściowe są pojedyncze ni pojedyncze b, ale wynik jest największy, ndla którego kod kończy się b < n/2w niecałą minutę. Czy nie byłoby lepiej mieć nw tym przypadku jedno wejście i wyświetlać wszystkie wyniki 0 <= b < n/2? Albo powinniśmy zapewnić dwa programy / funkcje: jedna biorąc dwa wejścia ni b, a jeden biorąc tylko wejście ni wyprowadzanie wszystkie wyniki w zakresie 0 <= b < n/2?
Kevin Cruijssen
2
Cóż, już przegłosowałem twoje wyzwanie, więc nie mogę tego zrobić ponownie. :) Chociaż nie mam pojęcia, jak to skutecznie obliczyć (wydajne algorytmy O były czymś, w czym zawsze byłem zły ... i jednym z niewielu przedmiotów na uczelni IT, które musiałem powtarzać kilka razy), wydaje się, że bardzo interesujące wyzwanie. Jestem ciekawy, jakie odpowiedzi wymyślą ludzie.
Kevin Cruijssen
2
Czy istnieje działający przykład? Byłoby to dobre miejsce do rozpoczęcia, zarówno pod względem poprawności, jak i porównania prędkości.
maxb

Odpowiedzi:

6

Python 2.7 / Gurobi n = 9

To rozwiązanie jest bardzo proste wykorzystanie solvera ILP firmy Gurobi do logicznych problemów mieszanych (MIP).

Jedyną sztuczką jest usunięcie symetrii w uzupełnieniu 1, aby zmniejszyć o połowę rozmiary problemów.

Korzystając z ograniczonej czasowo „darmowej” licencji firmy Gurobi LLC, jesteśmy ograniczeni do 2000 ograniczeń, ale rozwiązanie 10 del 1 jest poza moim 60-sekundowym terminem.

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)

AKTUALIZACJA + CORR: 10,2 ma optymalne rozwiązanie o rozmiarze 31 (patrz np.) Gurobi pokazuje, że nie istnieje symetryczne rozwiązanie o rozmiarze 30 (zwraca problem nieosiągalny) .. [moja próba wykazania asymetrycznej wykonalności w 30 pozostawała niejednoznaczna po 9,5 godziny pracy] np. Bit wzory liczb całkowitych 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 255lub0 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
źródło
Pobiłeś rekord „najszybciej zdobywanej nieskończonej nagrody”?
user202729,
Nie widzę tu żadnej nagrody, co masz na myśli?
jayprich
@ user202729 Tak .. Ustawiłem go za nisko. Powinienem był ustawić na n = 10 :)
Anush
Właściwie rozwiązanie go przy n = 9 nie jest łatwe. Właśnie dlatego OP używa istniejącej biblioteki (która ma być lepsza niż odręczne rozwiązanie, takie jak moja).
user202729,
1
Dzięki @ChristianSievers Widzę, że MO twierdzi, że 10,2 ma tylko asymetryczne optymima, których nie mogę obalić ani zweryfikować. Jeśli usunę skrót do założenia symetrii, który działa do n = 9, okazuje się, że Gurobi wciąż może rozwiązać do n = 9 w wymaganym czasie.
jayprich
3

C ++, n = 6

Brute force z kilkoma drobnymi optymalizacjami.

#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';
}

Uruchom lokalnie:

[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
użytkownik202729
źródło
1
Głównie, aby zachęcić innych do opublikowania swojego kodu, jeśli jest on szybszy niż mój.
user202729
Proszę? ... (uwaga: jest to przykład problemu z ustawioną ochroną.)
user202729
1
Pracuję nad tym. Po prostu nie mogę wymyślić żadnego inteligentnego sposobu na zrobienie tego. Jeśli nikt inny nie opublikuje odpowiedzi, postawię moją, która jak dotąd może sięgać tylko n = 4.
mypetlion