// Cuánto crece la expresión al eliminar estados: growth [K_MÁXIMO]
// Para cada k construye el DFA de k estados de los múltiplos de k en binario (el de la
// semana 1 con k = 3), elimina sus estados en el orden r0, r1, … y en el orden inverso, y
// cuenta los nodos de la expresión que sale.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "dfa.h"
#include "gnfa.h"
#include "regex.h"

// El estado rI dice que el valor de lo leído deja resto I al dividir entre k.
// Leer el bit b cambia el valor v por 2v + b.
static Dfa multiples_of(int k) {
    Dfa m;
    m.alphabet = {'0', '1'};
    for (int i = 0; i < k; i++) {
        m.states.push_back("r" + std::to_string(i));
    }
    m.start = "r0";
    m.accept = {"r0"};
    for (int i = 0; i < k; i++) {
        m.delta[{m.states[i], '0'}] = m.states[(2 * i) % k];
        m.delta[{m.states[i], '1'}] = m.states[(2 * i + 1) % k];
    }
    check_dfa(m);
    return m;
}

int main(int argc, char** argv) {
    int max_k = (argc == 2) ? std::stoi(argv[1]) : 8;
    std::cout << " k   estados   nodos (r0 primero)   nodos (r0 al final)\n";
    for (int k = 2; k <= max_k; k++) {
        Dfa m = multiples_of(k);
        std::vector<std::string> forward = m.states;
        std::vector<std::string> backward(m.states.rbegin(), m.states.rend());
        std::size_t a = size(to_regex(m, forward));
        std::size_t b = size(to_regex(m, backward));
        std::cout.width(2);
        std::cout << k;
        std::cout.width(10);
        std::cout << k;
        std::cout.width(21);
        std::cout << a;
        std::cout.width(22);
        std::cout << b << '\n';
    }
}
