Generación de IPs válidas con backtracking en C++

¿Cómo solucionar el problema de restaurar direcciones IP?

Bienvenidos a esta clase donde abordaremos la solución al problema de restaurar direcciones IP utilizando una lista de números. El reto consiste en insertar puntos en los lugares adecuados para crear todas las direcciones IP posibles, tomando en cuenta lo que constituye una IP válida. Este no es un proceso trivial, ya que las direcciones IP siguen un formato específico y hay ciertos valores considerados inválidos. Vamos a desgranar este problema y propondremos una solución empleando backtracking.

¿Qué es lo que hace válida una dirección IP?

Primero, debemos entender las características que definen una IP válida. Para validar si un segmento de nuestro número puede formar parte de una IP, consideramos las siguientes condiciones:

• No deben haber ceros a la izquierda, excepto cuando el número es "0".
• El valor numérico debe estar en el rango de 0 a 255.

Para implementar esta validación, creamos una función auxiliar dedicada a comprobar si un segmento es válido conforme a estas reglas.

bool esValido(const std::string& num) {
    if (num.length() == 0) return false;
    if (num.length() > 1 && num[0] == '0') return false;
    int valor = stoi(num);
    return valor >= 0 && valor <= 255;
}

¿Cómo utilizamos backtracking para generar IPs válidas?

El backtracking nos permite ir generando combinaciones de los números con puntos, explorando diversos caminos y retrocediendo cuando notamos que una combinación no es válida. El objetivo es persistir solo en las rutas que pueden desembocar en una IP válida.

Implementación de la solución

Para ello, realizamos una función recursiva que crea combinaciones de direcciones IP a partir de nuestra entrada. Vamos a controlar el proceso con un índice que rastrea nuestra posición en la cadena y un contador que lleva la cuenta de cuántos segmentos hemos generado.

void crearCombinaciones(const std::string& s, std::vector<std::string>& ipsValidas, int index, int cantidadNum, std::string ipValida) {
    if (cantidadNum > 4) return;
    if (cantidadNum == 4 && index == s.length()) {
        ipsValidas.push_back(ipValida);
    }
    for (int i = 1; i <= 3; i++) {
        if (index + i > s.length()) break;
        std::string num = s.substr(index, i);
        if (esValido(num)) {
            crearCombinaciones(s, ipsValidas, index + i, cantidadNum + 1, ipValida + (cantidadNum ? "." : "") + num);
        }
    }
}

¿Qué nos enseña este problema sobre problemas similares?

Este ejercicio práctico de backtracking es una introducción a cómo enfrentarse a problemas complejos dividiéndolos en subproblemas más manejables. La implementación tiene paralelismos con problemas como el de las N-Reinas en ajedrez, donde se busca colocar N reinas en un tablero sin que se ataquen entre sí. Les dejo el desafío de explorar este problema similar y encontrar soluciones propias.

Al enfrentar este tipo de problemas, la práctica constante y la exploración de estrategias como el backtracking mejorará la forma en que resolvemos problemas algorítmicos. ¡Espero que este contenido te sea de ayuda y sigas motivado en tu camino de aprendizaje!