//===========================================================================
// Listings of four k-ary de Bruijn sequences generated via known
// greedy approaches
//
// Programmed by Joe Sawada, 2017,  udpdated for debruijnsequence.org 2020
//===========================================================================
#include<stdio.h>
#include<stdlib.h>
#define N_MAX 46    // Max memory available for k=2 on my mac

int n,k,a[N_MAX+1];
long long int power[N_MAX], total;

//------------------------------------------------------
void Print(int v) {
    
    printf("%d", v);
    total++;
}
//------------------------------------------------------
long long int GetNum() {
    long long int sum=0,i;
    
    for (i=1; i<=n; i++) sum += power[i-1] * a[i];
    return sum;
}
//------------------------------------------------------
int Visit(long long int v, char *visited) {
    long long int dec;

    a[n] = v;
    dec = GetNum();
    if (visited[dec] == 0) {
        visited[dec] = 1;
        Print(v);
        return 1;
    }
    return 0;
}
//------------------------------------------------------
// Greedily add the LARGEST value possible
//------------------------------------------------------
void GreedyMax(char *visited) {
    int i;
    
    // Seed string (very important)
    for (i=1; i<=n; i++) a[i] = 0;
    
    while (1) {
        for (i=1; i<n; i++) a[i] = a[i+1];
        for (i=k-1; i>=0; i--) if (Visit(i,visited)) break;
        if  (i < 0) return;
    }
}
//------------------------------------------------------
// Greedily add the SMALLEST value possible
//------------------------------------------------------
void GreedyMin(char *visited) {
    int i;
    
    // Seed string (very important)
    for (i=1; i<=n; i++) a[i] = k-1;
    
    while (1) {
        for (i=1; i<n; i++) a[i] = a[i+1];
        for (i=0; i<=k-1; i++) if (Visit(i, visited)) break;
        if  (i == k) return;
    }
}
//---------------------------------------------------------------
// Greedily try the SAME as the last bit then decrement (mod k)
//---------------------------------------------------------------
void GreedySame(char *visited) {
    int i,last;
    
    // Seed string of sequence (very important). When k=3 seed is ...012012012
    a[n] = k-1;
    for (i=n-1; i>=1; i--) a[i] = (a[i+1]-1+k)%k;
    
    // The last bit of the seed starts the sequence
    Visit(a[n], visited);
    
    while (1) {
        last = a[n];
        for (i=1; i<n; i++) a[i] = a[i+1];
        for(i=0; i<=k-1; i++) if (Visit((last-i+k) % k, visited)) break;
        if (i == k) return;
    }
}
//------------------------------------------------------
// Greedily increment the value of the last bit (mod k)
// When binary, this is prefer OPPOSITE
//------------------------------------------------------
void GreedyOpposite(char *visited) {
    int i,last,seen[k],same=1;
    
    // Tracking for special case
    for (i=1; i<k; i++) seen[i] = 0;
    
    // Initial string of sequence 0^n (very important)
    for (i=1; i<=n; i++) a[i] = 0;
    Visit(a[n], visited);
    
    while (1) {
        last = a[n];
        for (i=1; i<n; i++) a[i] = a[i+1];
        
        // Special case when suffix is x^{n-1} where x > 0
        if (last > 0 && same >= n-1 && seen[last] >= k-1) {
            if (same == n-1) Visit(a[n], visited);
            else Visit(last-1, visited);
        }
        else {
            for(i=0; i<=k-1; i++) if (Visit((last + i+1) % k, visited)) break;
            if (i == k) return;
        }
        
        // Track information for special case
        if (a[n] == last) same++;
        else same = 1;
        if (same >= n-1) seen[a[n]]++;
    }
}
//------------------------------------------------------
// Greedily try to first append 1 + a[n-1] + a[n] (mod 2)
//------------------------------------------------------
void GreedyXNOR(char *visited) {
    int i,z,g;
    
    // Initial string of sequence 011011... (very important)
    for (i=1; i<=n; i++) if (i % 3 == 1) a[i] = 0; else a[i] = 1;
    Visit(a[n], visited);
    
    while (1) {
        g = (1 + a[n-1] + a[n]) % 2;
        for (i=1; i<n; i++) a[i] = a[i+1];
        
        if (z == n) Visit(0, visited);  /// SPECIAL CASE
        else {
            if (Visit(g, visited)) {}
            else if (Visit(1-g, visited)) {}
            else return;
        }
            
        if (a[n] == 0) z++;  // Track information for special case
        else z = 1;
    }
}
//------------------------------------------------------
int main() {
    int i,option;
    char *visited;
    
    printf(" -----------------------------------------\n");
    printf(" Greedy de Bruijn sequence constructions\n");
    printf(" -----------------------------------------\n");
    printf(" 1. Prefer largest \n");
    printf(" 2. Prefer smallest \n");
    printf(" 3. Prefer opposite  \n");
    printf(" 4. Prefer same   \n");
    printf(" 5. Xnor (binary only)  \n\n");
    
    printf(" Enter selection #: ");      scanf("%d", &option);
    printf(" Enter length n: ");         scanf("%d", &n);
    if (option < 5) { printf(" Enter alphabet size k: ");  scanf("%d", &k); }
    else k=2;
    printf("\n");
    
    // Initialize visited strings to 0
    power[0] = 1;
    for (i=1; i<=n; i++) power[i] = k * power[i-1];
    visited = (char *) malloc(sizeof(char) * power[n]);
    for (int i=0; i<power[n]; i++) visited[i] = 0;
    
    total = 0;
    if (option == 1) GreedyMax(visited);
    if (option == 2) GreedyMin(visited);
    if (option == 3) GreedyOpposite(visited);
    if (option == 4) GreedySame(visited);
    if (option == 5) GreedyXNOR(visited);
    printf("\n\nTOTAL = %lld\n", total);
}