#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int value(int w, int h)
{
    return w + 3*h - 4;
}

int inverse(int x)
{
    return 3*(x%3) + x/3;
}

bool st[9][9][9][9];
int st3[9][9][9];
struct
{
    int top;
    int left;
    int right;
    int bottom;
} stc[9][9];

void initialize_st(int i1, int i2, int i3, int i4)
{
    st[i1][i2][i3][i4] = true;
    stc[i1][i2].top++;
    stc[i1][i3].left++;
    stc[i2][i4].right++;
    stc[i3][i4].bottom++;
}

void remove_st(int i1, int i2, int i3, int i4)
{
    if (st[i1][i2][i3][i4])
    {
        st[i1][i2][i3][i4] = false;
        stc[i1][i2].top--;
        stc[i1][i3].left--;
        stc[i2][i4].right--;
        stc[i3][i4].bottom--;
    }
}

#define DEPTH 5

struct VariantTransition;

struct Variant
{
    Variant(char *_pattern, Variant *_next) : next(_next), from_trans(0), to_trans(0) { strcpy(pattern, _pattern); }
    ~Variant();
    char pattern[DEPTH+1];
    VariantTransition *from_trans;
    VariantTransition *to_trans;
    Variant *next;
};

struct VariantTransition
{
    VariantTransition(Variant *_from, Variant *_to)
    {
        from = _from;
        if (from->to_trans != 0)
            from->to_trans->ref_prev_to = &next_to;
        next_to = from->to_trans;
        from->to_trans = this;
        ref_prev_to = &from->to_trans;

        to = _to;
        if (to->from_trans != 0)
            to->from_trans->ref_prev_from = &next_from;
        next_from = to->from_trans;
        to->from_trans = this;
        ref_prev_from = &to->from_trans;
    }
    ~VariantTransition()
    {
        if (next_from != 0)
            next_from->ref_prev_from = ref_prev_from;
        *ref_prev_from = next_from;
        if (next_to != 0)
            next_to->ref_prev_to = ref_prev_to;
        *ref_prev_to = next_to;
    }
    Variant *from;
    VariantTransition **ref_prev_from;
    VariantTransition *next_from;
    Variant *to;
    VariantTransition **ref_prev_to;
    VariantTransition *next_to;
};

Variant::~Variant()
{ 
    while (from_trans != 0)
        delete from_trans;
    while (to_trans != 0)
        delete to_trans;
    delete next;
}

Variant* insert(Variant **ref_var, char *pattern)
{
    for (; *ref_var != 0; ref_var = &(*ref_var)->next)
    {
        int cmp = strcmp((*ref_var)->pattern, pattern);
        if (cmp == 0)
            return (*ref_var);
        if (cmp > 0)
            break;
    }
    *ref_var = new Variant(pattern, *ref_var);
    return (*ref_var);
}

int compare(Variant *left, Variant *right)
{
    for (; left != 0 && right != 0; left = left->next, right = right->next)
    {
        int c = strcmp(left->pattern, right->pattern);
        if (c != 0)
            return c;
    }
    return left == 0 && right == 0 ? 0 : left == 0 ? -1 : 1;
}

struct StateList;

struct State
{
    State(char _first, Variant *_variants, State *_next)
      : first(_first), variants(_variants), next(_next), nr_before(0), processed(false), 
        same_as(0), non_circular(false), reach_all(false), under(0), nr_valid_under(0)
    { 
        for (int i = 0; i < 9; i++) next_state[i] = 0;
    }
    int nr;
    int nr_before;
    char first;
    Variant *variants;
    bool processed;
    State *next_state[9];
    State *same_as;
    State *uniqueState()
    {
        if (this == 0)
            return 0;
        if (same_as == 0)
            return this;
        same_as = same_as->uniqueState();
        return same_as;
    }
    bool non_circular;
    bool reach_all;
    bool s1, s2;

    StateList* under;
    int nr_valid_under;

    State *next;
};

struct StateList
{
    StateList(State* _state) : state(_state), valid(true), next(0) {}
    ~StateList() { delete next; }
    State* state;
    bool valid;
    StateList* next;
};

int compare(State *left, char first, Variant *variants)
{
    if (left->first < first)
        return -1;
    if (left->first > first)
        return 1;
    return compare(left->variants, variants);
}

State *all_states = 0;


State* insertState(char first, Variant *variants, bool before)
{
    State **state_ref = &all_states;
    for (; *state_ref != 0; state_ref = &(*state_ref)->next)
    {
        int cmp = compare((*state_ref), first, variants);
        if (cmp == 0)
        {
            if (before)
                (*state_ref)->nr_before++;
            // copy VariantTransition
            Variant* target = (*state_ref)->variants;
            for (Variant* source = variants; source != 0; source = source->next, target = target->next)
                for (VariantTransition* trans = source->from_trans; trans != 0; trans = trans->next_from)
                    new VariantTransition(trans->from, target);
            delete variants;
            return (*state_ref);
        }
        if (cmp > 0)
            break;
    }
    *state_ref = new State(first, variants, *state_ref);
    if (before)
        (*state_ref)->nr_before++;
    return (*state_ref);
}


void buildInit(int i1, int i2, int depth, char *pattern, Variant **ref_variants)
{
    if (depth == DEPTH)
    {
        insert(ref_variants, pattern);
        return;
    }
    for (int i3 = 0; i3 < 9; i3++)
        for (int i4 = 0; i4 < 9; i4++)
            if (st[i3][i4][i1][i2])
            {
                pattern[depth] = i4 + 'A';
                buildInit(i3, i4, depth+1, pattern, ref_variants);
            }
}

void buildNext(int i1, int i2, int depth, char *prev_pattern, char *pattern, Variant **ref_variants, Variant *from)
{
    if (depth == DEPTH)
    {
        Variant* to = insert(ref_variants, pattern);
        new VariantTransition(from, to);
        return;
    }
    int i3 = prev_pattern[depth] - 'A';
    for (int i4 = 0; i4 < 9; i4++)
        if (st[i3][i4][i1][i2])
        {
            pattern[depth] = i4 + 'A';
            buildNext(i3, i4, depth+1, prev_pattern, pattern, ref_variants, from);
        }
}

void findStates()
{
    char pattern[DEPTH+1];
    pattern[DEPTH] = '\0';

    // initialize states
    for (int i1 = 0; i1 < 9; i1++)
        for (int i2 = 0; i2 < 9; i2++)
        {
            Variant *variants = 0;
            buildInit(i1, i2, 0, pattern, &variants);
            if (variants != 0)
                insertState(i2+'A', variants, false);
        }
        
    // Expand all states
    for (;;)
    {
        State *state = all_states;
        while (state != 0 && state->processed)
            state = state->next;
        if (state == 0)
            break;
        for (int i2 = 0; i2 < 9; i2++)
        {
            Variant *variants = 0;
            for (Variant *variant = state->variants; variant != 0; variant = variant->next)
                buildNext(state->first - 'A', i2, 0, variant->pattern, pattern, &variants, variant);
            if (variants != 0)
                state->next_state[i2] = insertState(i2+'A', variants, true);
        }
        state->processed = true;
    }

    int nr_states = 0;
    for (State* state = all_states; state != 0; state = state->next)
        if (state->nr_before > 0)
            state->nr = ++nr_states;
    
    // Incremental removal of unreachable variants in both directions
    for (int removed = -1; removed != 0;)
    {
        removed = 0;
        for (State* state = all_states; state != 0; state = state->next)
            for (Variant* variant = state->variants; variant != 0; variant = variant->next)
            {
                if (variant->to_trans == 0)
                    while (variant->from_trans != 0)
                    {
                        delete variant->from_trans;
                        removed++;
                    }
                if (variant->from_trans == 0)
                    while (variant->to_trans != 0)
                    {
                        delete variant->to_trans;
                        removed++;
                    }
            }
        //printf("Loop %d\n", removed);
    }        

    // Calculate possible states under each state
    for (State *state = all_states; state != 0; state = state->next)
        if (state->nr_before > 0 && state->same_as == 0)
        {
            StateList **ref_under = &state->under;
            for (State *state_under = all_states; state_under != 0; state_under = state_under->next)
                if (state_under->nr_before > 0 && state_under->same_as == 0)
                {                
                    bool fits = true;
                    for (Variant *variant_under = state_under->variants; variant_under != 0; variant_under = variant_under->next)
                    {
                        char pattern[DEPTH+1];
                        pattern[0] = state_under->first;
                        for (int i = 0; i < DEPTH-1; i++)
                            pattern[i+1] = variant_under->pattern[i];
                        pattern[DEPTH] = '\0';
                        
                        bool found = false;
                        for (Variant *variant = state->variants; variant != 0; variant = variant->next)
                        {
                            int cmp = strcmp(variant->pattern, pattern);
                            if (cmp < 0)
                                continue;
                            found = cmp == 0;
                            break;
                        }
                        if (!found)
                        {
                            fits = false;
                            break;
                        }
                    }
                    if (fits)
                    {
                        *ref_under = new StateList(state_under);
                        ref_under = &(*ref_under)->next;
                        state->nr_valid_under++;
                    }
                }
        }

    // Check for all under states there is a possible continuation for all next states
    for (bool go = true; go;)
    {
        go = false;
        for (State *state = all_states; state != 0; state = state->next)
            if (state->nr_before > 0 && state->same_as == 0)
                for (StateList* under = state->under; under != 0; under = under->next)
                    if (under->valid)
                    {
                        State* under_state = under->state;
                        bool found = false;
                        for (int i = 0; i < 9 && !found; i++)
                        {
                            State* next_state = state->next_state[i]->uniqueState();
                            if (next_state != 0)
                            {
                                for (int i2 = 0; i2 < 9 && !found; i2++)
                                {
                                    State* under_next_state = under_state->next_state[i2]->uniqueState();
                                    if (under_next_state != 0)
                                        for (StateList* next_under = next_state->under; next_under != 0; next_under = next_under->next)
                                            if (next_under->valid && next_under->state == under_next_state)
                                            {
                                                found = true;
                                                break;
                                            }
                                }
                            }
                        }
                        if (!found)
                        {
                            under->valid = false;
                            go = true;
                            state->nr_valid_under--;
                        }
                    }
    }
    for (State *state = all_states; state != 0; state = state->next)
        if (state->nr_before > 0 && state->same_as == 0 && state->nr_valid_under == 0)
            printf("State %d%c has not valid under\n", state->nr, state->first);     
}

#define WIDTH 40
#define HEIGHT 40

bool validUDTile(State* s1, State* s2, State* s3, State* s4)
{
    return st[s3->first-'A'][s4->first-'A'][s1->first-'A'][s2->first-'A'];
}

void generateRandomRTL()
{
    srand (time(NULL));

    int nr_opt, s;
    
    State* line[WIDTH];

    // Generate first sequence
    nr_opt = 0;
    for (State *state = all_states; state != 0; state = state->next)
        if (state->nr_before > 0 && state->same_as == 0)
            nr_opt++;
    s = rand() % nr_opt;
    for (State *state = all_states; state != 0; state = state->next)
        if (state->nr_before > 0 && state->same_as == 0)
        {
            if (s == 0)
            {
                line[0] = state;
                break;
            }
            s--;
        }

    printf("\"");
    printf("%c", line[0]->first);
    
    for (int i = 1; i < WIDTH; i++)
    {
        nr_opt = 0;
        for (int n = 0; n < 9; n++)
            if (line[i-1]->next_state[n] != 0)
                nr_opt++;
        s = rand() % nr_opt;
        for (int n = 0; n < 9; n++)
            if (line[i-1]->next_state[n] != 0)
            {
                if (s == 0)
                {
                    line[i] = line[i-1]->next_state[n]->uniqueState();
                    break;
                }
                s--;
            }
        printf("%c", line[i]->first);
    }
    printf("\",\n");
    
    // Generate next sequences
    for (int j = 1; j < HEIGHT; j++)
    {
        // Fill unders
        StateList* unders[WIDTH];
        for (int i = 0; i < WIDTH; i++)
        {
            unders[i] = 0;
            int count = 0;
            StateList** ref_under = &(unders[i]);
            for (StateList* under = line[i]->under; under != 0; under = under->next)
                if (under->valid)
                {
                    bool valid = i == 0;
                    if (!valid)
                        for (StateList* prev_under = unders[i-1]; prev_under != 0 && !valid; prev_under = prev_under->next)
                            for (int i4 = 0; i4 < 9 && !valid; i4++)
                                if (   prev_under->state->next_state[i4]->uniqueState() == under->state
                                    && validUDTile(line[i-1], line[i], prev_under->state, under->state))
                                    valid = true;
                    if (valid)
                    {
                        *ref_under = new StateList(under->state);
                        ref_under = &(*ref_under)->next;
                        count++;
                    }
                }
        }

        char outputline[WIDTH+1];
        outputline[WIDTH] = '\0';
        State* corner = 0;
        nr_opt = 0;
        for (StateList* under = unders[WIDTH-1]; under != 0; under = under->next)
            nr_opt++;
        if (nr_opt == 0)
        {
            printf("\nError: no option\n");
            return;
        }
        s = rand() % nr_opt;            
        for (StateList* under = unders[WIDTH-1]; under != 0; under = under->next)
        {
            if (s == 0)
            {
                corner = line[WIDTH-1];
                line[WIDTH-1] = under->state;
                break;
            }
            s--;
        }
        outputline[WIDTH-1] = line[WIDTH-1]->first;

        for (int i = WIDTH-2; i >= 0; i--)
        {
            nr_opt = 0;
            for (StateList* under = unders[i]; under != 0; under = under->next)
            {
                bool valid = false;
                for (int i4 = 0; i4 < 9; i4++)
                    if (   under->state->next_state[i4]->uniqueState() == line[i+1]
                        && validUDTile(line[i], corner, under->state, line[i+1]))
                    {
                        valid = true;
                        break;
                    }
                
                if (valid)
                    nr_opt++;
            }
            if (nr_opt == 0)
            {
                printf("\nError: no option for %d\n", i);
                return;
            }
            s = rand() % nr_opt;                        
            for (StateList* under = unders[i]; under != 0 && s >= 0; under = under->next)
                if (under->valid)
                {
                    bool valid = false;
                    for (int i4 = 0; i4 < 9; i4++)
                        if (   under->state->next_state[i4]->uniqueState() == line[i+1]
                            && validUDTile(line[i], corner, under->state, line[i+1]))
                        {
                            valid = true;
                            break;
                        }
                    if (valid)
                    {
                        if (s == 0)
                        {
                            corner = line[i];
                            line[i] = under->state;
                            break;
                        }
                        s--;
                    }
                }
            outputline[i] = line[i]->first;
        }
        for (int i = 0; i < WIDTH; i++)
            delete unders[i];
        printf("\"%s\",\n", outputline);
    }
}

int main(int argc, char* argv[])
{
    for (int i1 = 0; i1 < 9; i1++)
        for (int i2 = 0; i2 < 9; i2++) 
        {
            for (int i3 = 0; i3 < 9; i3++)
            {
                for (int i4 = 0; i4 < 9; i4++) 
                    st[i1][i2][i3][i4] = false;
                st3[i1][i2][i3] = 0;
            }
            stc[i1][i2].top = 0;
            stc[i1][i2].left = 0;
            stc[i1][i2].right = 0;
            stc[i1][i2].bottom = 0;
        }

    // empty
    for (int a = 1; a+1 <= 3; a++)
        for (int b = 1; b+1 <= 3; b++)
            initialize_st(value(a, b), value(a+1, b), value(a, b+1), value(a+1, b+1));

    // horizontal
    for (int a = 1; a+1 <= 3; a++)
        for (int b = 1; b <= 3; b++)
            for (int c = 1; c+1 <= 3; c++)
                if (a != 2 || c != 2)
                    initialize_st(value(a, b), value(a+1, b), value(c, 1), value(c+1, 1));

    // vertical
    for (int a = 1; a < 3; a++)
        for (int b = 1; b <= 3; b++)
            for (int c = 1; c+1 <= 3; c++)
                if (a != 2 || c != 2)
                    initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, c+1));

    // T
    for (int a = 1; a+1 <= 3; a++)
        for (int b = 1; b <= 3; b++)
            for (int c = 1; c <= 3; c++)
                initialize_st(value(a, b), value(a+1, b), value(c, 1), value(1, 1));

    // T rotated to the left
    for (int a = 1; a+1 <= 3; a++)
        for (int b = 1; b <= 3; b++)
            for (int c = 1; c <= 3; c++)
                initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, 1));

    // T rotated to the right
    for (int a = 1; a <= 3; a++)
        for (int b = 1; b <= 3; b++)
            if (!(a == 3 && b == 1) && !(a == 1 && b == 3))
                for (int c = 1; c <= 3; c++)
                    if (c != a)
                        for (int d = 1; d+1 <= 3; d++)
                            initialize_st(value(a, b), value(1, d), value(c, 1), value(1, d+1));

    // T upside-down
    for (int a = 1; a <= 3; a++)
        for (int b = 1; b <= 3; b++)
            if (!(a == 3 && b == 1) && !(a == 1 && b == 3))
                for (int c = 1; c <= 3; c++)
                    if (c != a)
                        for (int d = 1; d+1 <= 3; d++)
                            initialize_st(value(b, a), value(1, c), value(d, 1), value(d+1, 1));
    for (bool go = true; go; )
    {
        // Check top versus bottom
        go = false;
        for (int i1 = 0; i1 < 9; i1++)
            for (int i2 = 0; i2 < 9; i2++)
            {
                bool top = stc[i1][i2].top > 0;
                bool bottom = stc[i1][i2].bottom > 0;
                if (top != bottom)
                {
                    go = true;
                }
                if (top && !bottom)
                {
                    for (int i3 = 0; i3 < 9; i3++)
                        for (int i4 = 0; i4 < 9; i4++)
                            remove_st(i1, i2, i3, i4);
                }
                if (bottom && !top)
                {
                    for (int i3 = 0; i3 < 9; i3++)
                        for (int i4 = 0; i4 < 9; i4++)
                            remove_st(i3, i4, i1, i2);
                }
            }
        // Check left versus right
        for (int i1 = 0; i1 < 9; i1++)
            for (int i2 = 0; i2 < 9; i2++)
            {
                bool left = stc[i1][i2].left > 0;
                bool right = stc[i1][i2].right > 0;
                if (left != right)
                    go = true;
                if (left && !right)
                {
                    for (int i3 = 0; i3 < 9; i3++)
                        for (int i4 = 0; i4 < 9; i4++)
                            remove_st(i1, i3, i2, i4);
                }
                if (right && !left)
                {
                    for (int i3 = 0; i3 < 9; i3++)
                        for (int i4 = 0; i4 < 9; i4++)
                            remove_st(i3, i1, i4, i2);
                }
            }
    }

    
    for (int i1 = 0; i1 < 9; i1++)
        for (int i2 = 0; i2 < 9; i2++) 
            for (int i3 = 0; i3 < 9; i3++)
                for (int i4 = 0; i4 < 9; i4++)
                    if (st[i1][i2][i3][i4])
                        st3[i1][i2][i3]++;
                        
    // check if symmetric
    for (int i1 = 0; i1 < 9; i1++)
        for (int i2 = 0; i2 < 9; i2++) 
            for (int i3 = 0; i3 < 9; i3++)
            {
                if (st3[i1][i2][i3] != st3[inverse(i1)][inverse(i3)][inverse(i2)])
                {
                    printf("Not symmetric for %c%c %c\n", i1+'A', i2+'A', i3+'A');
                    return 1;
                }
                for (int i4 = 0; i4 < 9; i4++)
                    if (st[i1][i2][i3][i4] != st[inverse(i1)][inverse(i3)][inverse(i2)][inverse(i4)])
                    {
                        printf("Not symmetric for %c%c %c%c\n", i1+'A', i2+'A', i3+'A', i4+'A');
                        return 1;
                    }
            }
                
    findStates();

    generateRandomRTL();
    
    return 0;
}