Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Clase 41 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Cómo restaurar direcciones IP válidas a partir de una cadena de dígitos?

Crear direcciones IP válidas a partir de una cadena de dígitos es un problema interesante que desafía nuestro entendimiento sobre cómo se estructuran las IPs. Este no es simplemente un ejercicio de orden o eliminación, sino más bien de estructuración según reglas precisas. Dada una cadena S compuesta solo por dígitos, nuestro objetivo es encontrar todas las posibles combinaciones válidas al insertar puntos entre estos dígitos.

¿Qué constituye una dirección IP válida?

Una dirección IP válida se compone de cuatro enteros, cada uno separado por un punto. Cumplen con los siguientes criterios:

Cada entero está en el rango de 0 a 255.
No puede haber ceros a la izquierda en ningún segmento a menos que el segmento sea simplemente "0". Esto significa que "05" y "011" no son válidos, pero "5" y "11" sí lo son.
Solo se utilizan los caracteres numéricos contenidos en la cadena, sin reordenarlos ni eliminarlos.

Ejemplos de direcciones IP válidas e inválidas

A continuación, algunos ejemplos claros para entender mejor las reglas:

Válidas:
- 0.1.2.201
- 192.168.1.1
Inválidas:
- 0.011.255.245: Contiene 011, que tiene un cero a la izquierda.
- 192.168.1.312: 312 es mayor que 255.
- 192.168.1.1@: Contiene un carácter inválido (el arroba).

Ejemplo práctico

Supongamos que se nos da la cadena de dígitos "25525511135". Nuestro objetivo es identificar todas las combinaciones válidas posibles:

Opción 1: 255.255.11.135
Opción 2: 255.255.111.35

Estas son las únicas direcciones IP válidas que pueden construirse a partir de dichos dígitos, ya que cualquier otra combinación violaría las reglas establecidas.

Recomendaciones para afrontar el problema

Para resolver este tipo de problemas, es recomendable:

Descomponer la tarea: Dividir la cadena en segmentos y comprobar cada posible división.
Validar cada segmento: Asegurar que cada grupo de números cumple con el rango permitido (0-255) y que no tenga ceros iniciales no permitidos.
Explorar todas las posibilidades: Utilizar un enfoque que permita generar todas las combinaciones posibles, verificando su validez.

Este ejercicio, además de desafiar nuestra lógica, nos ayuda a entender mejor cómo funcionan las direcciones IP, un conocimiento muy útil en el mundo de la tecnología. Antes de avanzar, te animo a intentar solucionar el problema por ti mismo. Esto fortalecerá tu pensamiento lógico y tus habilidades de programación. ¡Buena suerte y sigue aprendiendo!

Andres Silva Vega

student•

Esta sería mi solución en javascript usando recursividad (las expresiones regulares las construí yo mismo después de hacer un curso de expresiones regulares aquí donde el profesor me pareció un experto):

const combinacionesIp = function (value){
    const regex = /^[0-9]{4,12}$/g
    if(!regex.exec(value)){
        console.error("Cadena no valida. Debe ingresar numeros de 4 a 12 digitos");
        return;
    }
    let respuesta = combinacion_recursiva(value,1);
    return respuesta;
}
const combinacion_recursiva = (value, digito) => {
    const regex_cero = /^0+\d+$/
    if(digito == 4 ){
        let val = parseInt(value);
        if(regex_cero.exec(value) == null && val >= 0 && val < 256){
            return [value];
        }
        return [];
    }
    
    let comb = [];
    let ret = [];
    let numero = 0;
    for (let i = 1; i <= 3; i++) {
        numero = value.substr(0,i);
        if(regex_cero.exec(numero) == null && parseInt(numero) < 256 && parseInt(numero) >= 0){
            ret = combinacion_recursiva(value.substr(i), digito + 1);
            if(ret.length > 0){
                ret.forEach(ele => {
                    comb.push(`${numero}.${ele}`);
                });
            }
        }
    }
    return comb;
}