// This code correspond to the algorithm described in section 4 of the article // "How far away must forced letters be so that squares are still avoidable?" // It should be compiled with c++11 or higher and optimization O3 wich gives: // g++ lemma_7.cpp -O3 -lgmp-lgmpxx -o // where is the size of the alphabet // that is, for testing the first statement of Theorem 9 one could do: // g++ lemma_7.cpp -O3 -DTEST3 -o testing_3.out // ./ testing_3.out #include #include #include #include #include using namespace std; #ifdef TEST3 #define P 61 #define sA 3 #define N 320 array, 28> W;// we keep the mirrors of the elements of W array f={4,19,19,19,22,22,22,28,28,28,36,36,36,50,50,50,63,63,63,88,88,88,118,118,118,148,148,148}; void initW(){ int t=0; W[t++]=vector(9,-1); for(int i=19; i<=27;i++) for(int a=0; a<3; a++){ W[t]=vector(i,-1); W[t++][0]=a; } } #elif defined TEST4 #define P 18 #define sA 4 #define N 96 array, 21> W;// we keep the mirrors of the elements of W array f={2,5,5,5,5,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8}; void initW(){ int t=0; W[t++] = vector(1,-1); for(int a=0; a(4,-1); W[t][1] = a; t++; } for(int a=0; a(6,-1); W[t][0]=a; W[t][3]=b; t++; } } } #elif defined TEST6 #define P 12 #define sA 6 #define N 96 array, 43> W;// we keep the mirrors of the elements of W array f; void initW(){ int t=0; W[t] = vector(1,-1); f[t++] = 3; for(int a=0; a(3,-1); W[t][1] = a; f[t++]=6; } for(int a=0; a(4,-1); W[t][0]=a; W[t][2]=b; f[t++]=6; } } } #endif class optstring:bitset{ public: using bitset::operator[]; // [0]...[7] is the size of the string in binary // [8]...[N-1] is the mirror of the string // letter i of the mirror image is [8+2i]+2*[8+2i+1] if sA <= 4 or [8+2i]+2*[8+2i+1]+4*[8+2i+1] if 4 < sA <= 8 optstring():bitset(){} void Cut(){// find g(f(u)) int n = size(); for(int i=0; i= 2*P-3) return; } } void pop_back() { setsize(size()-1); } int size() const{// return the size int n=0; for(int i=0; i<7; i++){ n += ((*this)[i]?1:0)<(){// a copie of s with a at the end (so a starts the mirror image) int n = s.size(); setsize(n+1); (*this)[8] = a%2; (*this)[9] = a/2; for(int i=8; i<8+2*n; i++) (*this)[i+2]=s[i]; } int back() const{//return the last letter of the mirror (so the first letter of the word) int n=size()-1; return ((*this)[n*2+8]?1:0)+((*this)[n*2+9]?2:0); } optstring& operator += (int c){ //catenation of a letter at the end of the mirror image int n = size(); (*this)[n*2+8]=(c%2); (*this)[n*2+9]=(c/2); setsize(n+1); return *this; } optstring& operator++(int){ //add 1 to the last letter int n=size()-1; (*this)[n*2+9] = (*this)[n*2+9] | (*this)[n*2+8]; (*this)[n*2+8] = !(*this)[n*2+8]; return *this; } friend bool operator< (const optstring& x, const optstring& y){ //any kind of comparator is fine //we need one to manipulate set in time O(log(n)) int n= x.size(); if(ny.size()) return false; for (int i = 8; i < 8+2*n; i++) { if (x[i] && !y[i]) return false; if (!x[i] && y[i]) return true; } return false; } bool hasSquareLast()const{//return true if there is a square that contains the last letter int s = size(); for(int p = 1; p*2<=s; p++){//p = period of the possible square bool isrep = true; for(int j=0; j=1; i--){ bool possiblePeriod = true; for(size_t j=0; j+i(){// a copie of s with a at the end (so a starts the mirror image) int n = s.size(); setsize(n+1); (*this)[8] = a%2; (*this)[9] = (a/2)%2; (*this)[10] = (a/4); for(int i=8; i<8+3*n; i++) (*this)[i+3]=s[i]; } int back() const{//return the last letter of the mirror (so the first letter of the word) int n=size()-1; return ((*this)[n*3+8]?1:0)+((*this)[n*3+9]?2:0)+((*this)[n*3+10]?4:0); } optstring& operator += (int c){ //catenation of a letter at the end of the mirror image int n = size(); (*this)[n*3+8]=(c%2); (*this)[n*3+9]=(c/2)%2; (*this)[n*3+10]=(c/4); setsize(n+1); return *this; } optstring& operator++(int){ //add 1 to the last letter int n=size()-1; (*this)[n*3+10] = (*this)[n*3+10] | ((*this)[n*3+8]&(*this)[n*3+9]); (*this)[n*3+9] = ((*this)[n*3+9] & (~(*this)[n*3+8])) | ((~(*this)[n*3+9]) & (*this)[n*3+8]); (*this)[n*3+8] = ~(*this)[n*3+8]; return *this; } friend bool operator< (const optstring& x, const optstring& y){ //any kind of comparator is fine //we need one to manipulate set in time O(log(n)) int n= x.size(); if(ny.size()) return false; for (int i = 8; i < 8+3*n; i++) { if (x[i] && !y[i]) return false; if (!x[i] && y[i]) return true; } return false; } bool hasSquareLast()const{//return true if there is a square that contains the last letter int s = size(); for(int p = 1; p*2<=s; p++){//p = period of the possible square bool isrep = true; for(int j=0; j=1; i--){ bool possiblePeriod = true; for(int j=0; j+i & listwords){// find the set of non-empty square free words w such that g(f(w))=w optstring w; w+=0; while(true){ if(!w.hasSquareLast()){ if(w.size()<2*P-3 && !w.noNeedToComplete()){ w += 0; }else{ listwords.push_back(w); while(w.size() > 0 && w.back() >= sA-1) w.pop_back(); if (w.size() == 0) return; w++; } }else{ while(w.size() > 0 && w.back()>= sA-1) w.pop_back(); if (w.size() == 0) return; w++; } } } size_t getIndex(vector& listwords, optstring& e){// dichotomic search of e in listwords size_t lb=0, ub=listwords.size()-1; while(lb& listwords, vector >& graph){//compute the edges of the graph for(size_t i=0; i< listwords.size(); i++){ if(i%2000000==0) cout<< i<<" vertices done out of "<< listwords.size()<<" ( "<<100*double(i)/double(listwords.size())<< "% )"< >& graph){//remove all the vertices with P_{i,d,G[X]}(v) worstOutDeg(graph.size(),0);//contains P_{i,d,G[X]} vector worstOutDegNew(graph.size(),0); vector valid(graph.size(),true); bool todo = true; while(todo){//if we removed vertices in the last round, we need to do at least one more round todo = false; // this is the dynamic algorithm computing P_{i,d,G[X]} for(size_t w=0; w listwords; find(listwords); cout <<"There are "<< listwords.size()<<" vertices in g(f(R_P))."<> graph(listwords.size()); getGraph(listwords, graph); vector().swap(listwords); cout<<"Graph found."<