searchA

function getNumeroPadres(possibilidade) {
    const padres = String(possibilidade).substring(0,3);
    const numPadres = padres.split('').reduce((p, n) => p + (n === '1' ? 1 : 0), 0)

    return numPadres
}
function getNumeroCanibais(possibilidade) {
    const canibais = String(possibilidade).substring(3,6);
    const numCanibais = canibais.split('').reduce((p, n) => p + (n === '1' ? 1 : 0), 0);
    return numCanibais;
}
function temPossibilidadeEquivalente (possibilidade, possibilidades) {
    return possibilidades.some((combinacao) => {
        const numPadresCombinacao = getNumeroPadres(combinacao);
        const numCanibaisCombinacao = getNumeroCanibais(combinacao);

        const numPadresNovaPossibilidade = getNumeroPadres(possibilidade);
        const numCanibaisNovaPossibilidade = getNumeroCanibais(possibilidade);

        return (numPadresCombinacao === numPadresNovaPossibilidade && numCanibaisCombinacao === numCanibaisNovaPossibilidade)
    })
}
function gerarPossibilidadesAdicao2 (config) {
    const splitted = config.split('');
    const possibilidades = [];

    for (let index = 0; index < splitted.length; index++) {
        if (splitted[index] === '0') {
            const aux = [...splitted];
            aux[index] = '1';

            for (let index2 = 0; index2 < aux.length; index2++) {
                if (index !== index2 && aux[index2] === '0') {
                    const aux2 = [...aux];
                    aux2[index2] = '1';
                    const newPossibilidade = aux2.join('');
                    if (!possibilidades.includes(newPossibilidade) && !temPossibilidadeEquivalente(newPossibilidade, possibilidades)) {
                        possibilidades.push(newPossibilidade);
                    }
                }

            }
        }
    }
    return possibilidades;
}
function gerarPossibilidadesAdicao1 (config) {
    const splitted = config.split('');
    const possibilidades = [];

    const numTotal = splitted.reduce((p,n) => p+ (n === '1' ? 1 : 0), 0);

    if (numTotal <= 5) {
        for (let index = 0; index < splitted.length; index++) {
            if (splitted[index] === '0') {
                const aux = [...splitted];
                aux[index] = '1'
                const newConfig = String(aux.join(''));
                if (!temPossibilidadeEquivalente(newConfig, possibilidades)) {
                    possibilidades.push(newConfig);
                }
            }
        }
    }

    return possibilidades;
}
function gerarPossibilidadesRemocao2 (config) {
    // itera tudo e para aqueles que forem 1 adiciona 0 nele mesmo e itera todos os outros


    const splitted = config.split('');
    const possibilidades = [];

    for (let index = 0; index < splitted.length; index++) {
        if (splitted[index] === '1') {
            const aux = [...splitted];
            aux[index] = '0';

            for (let index2 = 0; index2 < aux.length; index2++) {
                if (index !== index2 && aux[index2] === '1') {
                    const aux2 = [...aux];
                    aux2[index2] = '0';
                    const newPossibilidade = aux2.join('');
                    if (!possibilidades.includes(newPossibilidade) && !temPossibilidadeEquivalente(newPossibilidade, possibilidades)) {
                        possibilidades.push(newPossibilidade);
                    }
                }

            }
        }
    }
    return possibilidades;

}
function gerarPossibilidadesRemocao1 (config) {
    const splitted = config.split('');
    const possibilidades = [];

    const numTotal = splitted.reduce((p,n) => p+ (n === '1' ? 1 : 0), 0);

    if (numTotal <= 5) {
        for (let index = 0; index < splitted.length; index++) {
            if (splitted[index] === '1') {
                const aux = [...splitted];
                aux[index] = '0'
                const newConfig = String(aux.join(''));
                if (!temPossibilidadeEquivalente(newConfig, possibilidades)) {
                    possibilidades.push(newConfig);
                }
            }
        }
    }

    return possibilidades;
}
function gerarPossibilidades (config, vaiParaEsquerda) {
    const adicao2 = gerarPossibilidadesAdicao2(config);
    const adicao1 = gerarPossibilidadesAdicao1(config);
    const remocao2 = gerarPossibilidadesRemocao2(config);
    const remocao1 = gerarPossibilidadesRemocao1(config);
    const possibilidades =[]

    if (vaiParaEsquerda) {
        possibilidades.push(...[...adicao2, ...adicao1])
    } else {
        possibilidades.push(...[...remocao2, ...remocao1])
    }

    return possibilidades;
}
function peneira (possibilidades) {
    const possibilidadesValidas = [];
    for (const possibilidade of possibilidades) {
        const numPadres = getNumeroPadres(possibilidade);
        const numCanibais = getNumeroCanibais(possibilidade);

        if (numCanibais === numPadres || (numPadres > numCanibais && numPadres === 3) || (numCanibais > numPadres && numPadres === 0)) {
            possibilidadesValidas.push(possibilidade)
        }
    }
    return possibilidadesValidas;
}
const estadosGerados = ['111111'];
function gerarNodo (nodo, pos) {
    if (pos === 30) return;
    const possibilidadesValidas = peneira(gerarPossibilidades(nodo.estado, pos % 2), pos % 2)

    for (const possibilidade of possibilidadesValidas) {
        const novoNodo = {
            estado: possibilidade,
            caminhos: []
        }

        if (!estadosGerados.includes(novoNodo.estado)) {
            if (possibilidade === '000000') {
                nodo.caminhos.push(novoNodo)
            } else {
                estadosGerados.push(novoNodo.estado)
                nodo.caminhos.push(novoNodo)

                gerarNodo(novoNodo, pos+1)
            }
        }

    }
}
function pegarMelhorCaminho(nodo) {
    let melhor = {
        qtd: 99,
        index: null
    };
    for (let index = 0; index < nodo.caminhos.length; index++) {
        const caminho = nodo.caminhos[index];
        const qtd = caminho.estado.split('').reduce((p, n) => p+ (n==='1' ? 1 : 0), 0)

        if (qtd < melhor.qtd) {
            melhor.qtd = qtd;
            melhor.index = index;
        }
        if (qtd === 0) {
            return nodo.caminhos[melhor.index].estado
        }
    }
    return pegarMelhorCaminho(nodo.caminhos[melhor.index])
}
const inicio = {
    estado: '111111',
    caminhos: [],
}
gerarNodo(inicio, 0)
console.log('\n', pegarMelhorCaminho(inicio));
require('fs').writeFile('nodes', JSON.stringify(inicio, null, 2), () => {})
// printar(inicio)