#include <cstdio>
#include <iostream>

using namespace std;

const int INPUT_LENGTH = 5;
int input[(1 << INPUT_LENGTH)][INPUT_LENGTH];
int output[INPUT_LENGTH];
int test_output[(1 << INPUT_LENGTH)][INPUT_LENGTH];

struct State {
    int next_state[2];
    int output[2];
};

const int MAX_STATES = 10;
int combinations[MAX_STATES];
State states[MAX_STATES];
int curr_state = 0;
int total_states = 0;

void print_automata_format_info() {
    cout << "Automata info format:\n";
    cout << "(state, input) -> (new_state, output)\n";
}

void print_automata() {
    // (state, input) -> (new_state, output)
    cout << "States:\n";
    for (int i = 0; i < total_states; i++) {
        cout << "(" << i << ", 0) -> (" << states[i].next_state[0] << ", " << states[i].output[0] << ")\n";
        cout << "(" << i << ", 1) -> (" << states[i].next_state[1] << ", " << states[i].output[1] << ")\n";
    }
    cout << '\n';
}

void generate_input() {
    for (int i = 0; i < (1 << INPUT_LENGTH); i++) {
        int mask = 1 << (INPUT_LENGTH - 1);
        for (int j = INPUT_LENGTH - 1; j >= 0; j--) {
            input[i][j] = (mask & i) ? 1 : 0;
            mask >>= 1;
        }
    }
}

void generate_verified_output() {
    for (int i = 0; i < (1 << INPUT_LENGTH); i++) {
        for (int j = 0; j < INPUT_LENGTH; j++) {
            if (j == 0 || j == 1) {
                test_output[i][j] == 0;
                continue;
            }

            // do AND
            if (input[j] == 0) {
                test_output[i][j] = input[i][j - 2] & input[i][j - 1];
            }

            // do XOR
            if (input[i][j] == 1) {
                test_output[i][j] = input[i][j - 2] ^ input[i][j - 1];
            }
        }
    }
}

void generate_output(int idx) {
    for (int j = 0; j < INPUT_LENGTH; j++) {
        output[j] = states[curr_state].output[idx][input[j]];
        curr_state = states[curr_state].next_state[idx][input[j]];
    }
}

bool verify_output(int idx) {
    for (int j = 0; j < INPUT_LENGTH; j++) {
        if (output[j] != test_output[idx][j]) {
            return false;
        }
    }

    return true;
}

void verify_automata() {
    for (int i = 0; i < (1 << INPUT_LENGTH); i++) {
        curr_state = 0;

        generate_output(i);

        if (verify_output(i) == false) {
            return;
        }
    }

    cout << "Automata found\n";
    print_automata();
}

void try_all_outputs(int idx) {
    if (total_states == idx) {
        for (int i = 0; i < total_states; i++) {
            states[i].output[0] = combinations[i] & 1;
            states[i].output[1] = combinations[i] >> 1;
        }

        verify_automata();
        return;
    }

    combinations[idx] = 0;
    try_all_outputs(idx + 1);
    combinations[idx] = 1;
    try_all_outputs(idx + 1);
    combinations[idx] = 2;
    try_all_outputs(idx + 1);
    combinations[idx] = 3;
    try_all_outputs(idx + 1);
}

void generate_automatas(int state_idx) {
    if (state_idx == total_states) {
        try_all_outputs(0);
        return;
    }

    for (int i = 0; i < total_states; i++) {
        states[state_idx].next_state[0] = i;
        for (int j = 0; j < total_states; j++) {
            states[state_idx].next_state[1] = j;
            generate_automatas(state_idx + 1);
        }
    }
}

int main() {
    generate_input();
    generate_verified_output();

    print_automata_format_info();

    total_states = 4;

    generate_automatas(0);
};