#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>

enum element_type { INPUT, NAND };

struct element {
    enum element_type type;
    int a;
    int b;
};

struct element_stack {
    struct element** data;
    int top;
    int size;
};

struct element_stack* sCreate(int size) {
    struct element_stack* e = malloc(sizeof(struct element_stack));
    e->data = malloc(sizeof(struct element*)*size);
    e->size = size;
    e->top = 0;
}

int sPush(struct element_stack* stack,struct element* e) {
    //printf("Pushed %d %d %d\n", e->a, e->b, stack->top);
    if(stack->top == stack->size) return 1;
    stack->data[stack->top] = e;
    stack->top++;
}

struct element* sPop(struct element_stack* stack) {
    if(stack->top == 0) return NULL;
    stack->top--;
    struct element* e = stack->data[stack->top];
    //printf("Popped %d %d %d\n", e->a, e->b, stack->top);
    return e;
}

struct element* sGet(struct element_stack* stack, int index) {
    if(index < 0 || index >= stack->top) return NULL;
    return stack->data[index];
}

void sFree(struct element_stack* stack) {
    free(stack->data);
    free(stack);
}

void sPrint(struct element_stack* stack) {
    for(int i = 0; i < stack->top; i++) {
        struct element* e = sGet(stack,i);
        if(e->type == INPUT) {
            printf("%d: INPUT %d\n",i,e->a);
        } else {
            printf("%d: NAND %d %d\n",i,e->a,e->b);
        }
    }
}

struct element* sFind(struct element_stack* stack, struct element* pattern) {
    for(int i = 0; i<stack->top; i++) {
        struct element* e = stack->data[i];
        if(e->type == pattern->type && e->a == pattern->a && e->b == pattern->b) {
            return e;
        }
    }
    return NULL;
}

struct truth_table {
    int z;
    int* in;
};

int test_truth_table( struct element_stack* stack, const struct truth_table te) {
    int* netvalues = malloc(sizeof(int)*stack->top);
    int inputs = 0;
    for(int i = 0; i < stack->top; i++) {
        struct element* e = sGet(stack,i);
        if(e->type == INPUT) {
            netvalues[i] = te.in[e->a];
            if(inputs <= e->a) inputs = e->a+1;
        } else if(e->type == NAND) {
            if(netvalues[e->a] == 1 && netvalues[e->b] == 1) {
                netvalues[i] = 0;
            } else {
                netvalues[i] = 1;
            }
        }
    }
    int result = netvalues[stack->top-1];

    free(netvalues);
    if(result == te.z) {
        return 1;
    } else {
        return 0;
    }
}

int buildnet( struct element_stack* stack, int inputs, int nands, const struct truth_table* tt ) {
    if(stack->top == inputs+nands) {
        //sPrint(stack);
        for(int i = 0; i < (1 << inputs); i++) {
            if(!test_truth_table(stack, tt[i] )) {
                return 0;
            }
        }
        return 1;
    } else {
        struct element* e = malloc(sizeof(struct element));
        e->type = NAND;
        sPush(stack,e);
        for(int a = 0; a < stack->top-1; a++) {
            e->a = a;
            for(int b = a; b < stack->top-1; b++) {
                e->b = b;
                struct element* f = sFind(stack,e);
                if(f != NULL && f != e) continue;
                if(buildnet(stack, inputs, nands, tt)) {
                    return 1;
                }
            }
        }
        assert(sPop(stack) == e);
        free(e);
        return 0;
    }
}

struct element_stack* findnet( int inputs, int nands, const struct truth_table* tt ) {
    struct element_stack* stack = sCreate(inputs+nands);
    // Add inputs to stack
    for(int i = 0; i < inputs; i++) {
        struct element* e = malloc(sizeof(struct element));
        e->type = INPUT;
        e->a = i;
        e->b = 0;
        sPush(stack,e);
    }

    if(buildnet(stack, inputs, nands, tt)) {
        return stack;
    } else {
        while(stack->top > 0) {
            free(sPop(stack));
        }
        sFree(stack);
        return NULL;
    }
}


int main( int argc, char *argv[] ) {
    /*const struct truth_table tt[16] = {
        { .in = {0,0,0,0}, .z = 0 },
        { .in = {0,0,0,1}, .z = 0 },
        { .in = {0,0,1,0}, .z = 0 },
        { .in = {0,0,1,1}, .z = 0 },
        { .in = {0,1,0,0}, .z = 1 },
        { .in = {0,1,0,1}, .z = 1 },
        { .in = {0,1,1,0}, .z = 1 },
        { .in = {0,1,1,1}, .z = 0 },
        { .in = {1,0,0,0}, .z = 1 },
        { .in = {1,0,0,1}, .z = 0 },
        { .in = {1,0,1,0}, .z = 1 },
        { .in = {1,0,1,1}, .z = 1 },
        { .in = {1,1,0,0}, .z = 1 },
        { .in = {1,1,0,1}, .z = 1 },
        { .in = {1,1,1,0}, .z = 1 },
        { .in = {1,1,1,1}, .z = 1 }
    };*/

    /*const struct truth_table tt[4] = {
        { .in = {0,0}, .z = 0 },
        { .in = {0,1}, .z = 1 },
        { .in = {1,0}, .z = 1 },
        { .in = {1,1}, .z = 0 }
    };*/

    int inputs, z;
    printf("number of inputs: ");
    scanf("%d",&inputs);
    struct truth_table* tt = malloc( sizeof(struct truth_table) * (1<<inputs) );

    for(int v = 0; v < (1<<inputs); v++) {
        tt[v].in = malloc(sizeof(int)*inputs);
        for(int n = inputs-1; n >= 0; n--) {
            tt[v].in[inputs-n-1] = ((v>>n)&1);
            printf("%d ",tt[v].in[inputs-n-1]);
        }
        printf(" => ");
        scanf("%d",&z);
        if(z != 0) z = 1;
        tt[v].z = z;
    }

    struct element_stack* result;
    for(int nands = 1; nands <= 20; nands++) {
        printf("-- Trying to find solution for %d NANDS\n",nands);
        result = findnet(inputs,nands,tt);
        if(result != NULL) break;
        printf("No solution\n");
    }

    if(result != NULL) {
        sPrint(result);
    } else {
        printf("No result.\n");
    }

    for(int v = 0; v < (1<<inputs); v++) {
        free(tt[v].in);
    }
    free(tt);

	return 0;
}