PDLS (Cassidoo) #2: Resolución de enlaces simbólicos en un sistema de archivos falso

Enlaces simbólicos, ciclos y el arte de la resolución

Un enorme agradecimiento a Cassidy Williams y su fantástico boletín Cassidoo por el acertijo de esta semana. El problema se siente como navegar por un laberinto de atajos: dado un diccionario que representa un sistema de archivos (rutas como claves, valores que son null para un archivo real o una cadena que apunta a otra ruta), escribe una función que resuelva una ruta hasta su destino real. Si una cadena de enlaces simbólicos forma un ciclo, regresas null. Sencillo en la superficie, pero lleno de trampas sutiles.

En esta publicación construiremos desde cero: un enfoque recursivo ingenuo, luego una solución iterativa con detección de ciclos y finalmente una versión óptima limpia usando un conjunto de visitados. En el camino exploraremos las matemáticas de los grafos funcionales, discutiremos la complejidad temporal y espacial, y produciremos código Python que realmente puedas usar. Y sí, le daremos a Cassidy el crédito que merece.

El enunciado del problema (tal como se da)

"Se te da un sistema de archivos representado como un objeto donde las claves son rutas absolutas y los valores son null (archivo/directorio real) o una cadena (un enlace simbólico que apunta a otra ruta). Escribe una función que resuelva una ruta dada hasta su destino real, siguiendo los enlaces simbólicos en el camino. Si una cadena de enlaces simbólicos forma un ciclo, regresa null."

Ejemplo (en notación de objeto de JavaScript, pero usaremos diccionarios de Python):


const fs = {
  "/a": "/b",
  "/b": "/c",
  "/c": null,
  "/loop1": "/loop2",
  "/loop2": "/loop1",
  "/real": null,
  "/alias": "/real",
};

resolvePath(fs, "/a");      // "/c"
resolvePath(fs, "/alias");  // "/real"
resolvePath(fs, "/loop1");  // null
resolvePath(fs, "/real");   // "/real"

Nuestra tarea: implementar resolve_path(fs, path) en Python.

Reescribiendo en términos más simples

Imagina un mapa del tesoro donde cada ubicación es el tesoro (null / archivo real) o contiene una nota que dice "ve a esta otra ubicación". Tu tarea: seguir las notas hasta que llegues al tesoro o te des cuenta de que estás caminando en círculos. Si encuentras el tesoro, regresa su nombre. Si detectas un bucle (regresas a un lugar que ya visitaste), regresa None (que es el null de Python).

La entrada es un diccionario (mapa hash) donde las claves son cadenas (rutas como "/a") y los valores son None (que significa "soy un archivo real") u otra cadena (que significa "soy un enlace simbólico, ve allí"). La función debe ser pura: no modifica el diccionario, solo lo lee.

De ingenuo a óptimo: tres enfoques

Enfoque 1: Seguidor recursivo (el más simple pero riesgoso)

La traducción más directa: si la ruta actual apunta a un archivo real (fs[path] is None), regresa la ruta. Si apunta a otra ruta, llama a la función nuevamente en ese destino. Si la ruta no está en el diccionario (caso extremo), podríamos regresar None o lanzar un error; pero dado el enunciado del problema, asumimos que todos los enlaces simbólicos apuntan a claves existentes.

El problema obvio: la profundidad de recursión. Si tienes una cadena de 1000 enlaces simbólicos, el límite de recursión de Python (generalmente 1000) se romperá. Además, los ciclos causan recursión infinita a menos que los detectemos.


def resolve_path_recursive(fs, path):
    """
    Resolución recursiva ingenua. Vulnerable a desbordamiento de pila y bucles infinitos.
    """
    if path not in fs:
        return None  # O lanza KeyError, pero la especificación asume claves válidas.
    target = fs[path]
    if target is None:
        return path
    # Paso recursivo
    return resolve_path_recursive(fs, target)

Esto funciona para los casos simples, pero falla en ciclos (RecursionError) y cadenas profundas (RecursionError otra vez). No está listo para producción.

Enfoque 2: Iterativo con detección de ciclos usando un conjunto de visitados

Podemos transformar la recursión en un bucle. Mantén un conjunto de rutas que ya hayamos visto en la cadena de resolución actual. Si alguna vez encontramos una ruta que ya está en el conjunto, significa que estamos a punto de repetirnos: existe un ciclo. Regresa None. De lo contrario, sigue caminando hasta que llegues a un archivo real (null) o una entrada faltante.


def resolve_path_iterative(fs, path):
    """
    Resolución iterativa con detección de ciclos usando un conjunto de visitados.
    Regresa la ruta real o None si se detecta un ciclo.
    """
    seen = set()
    current = path
    while current in fs:
        if current in seen:
            # Ciclo detectado
            return None
        seen.add(current)
        target = fs[current]
        if target is None:
            # Archivo / directorio real
            return current
        # De lo contrario, sigue el enlace simbólico
        current = target
    # Si salimos del bucle porque current no está en fs, es una condición de error.
    # Según la especificación del problema, asumimos que todos los enlaces son válidos, pero defensivamente:
    return None

Esto ya es mucho mejor. Sin límite de recursión, detección explícita de ciclos, tiempo lineal en la longitud de la cadena de enlaces simbólicos. Pero hay un matiz: el problema espera que si la ruta inicial es un archivo real (apunta a null), regresemos esa misma ruta. Nuestro código hace eso.

Enfoque 3: Óptimo con salida temprana y seguimiento de ruta (la forma final)

La solución anterior ya es óptima en términos de complejidad temporal: O(L) donde L es la longitud de la cadena (o el número de nodos únicos visitados antes de un ciclo). Sin embargo, podemos hacer una pequeña mejora: en lugar de almacenar un conjunto genérico de nodos visitados, también podríamos almacenar el orden de recorrido, pero no lo necesitamos. El conjunto de visitados es suficiente. El código anterior es limpio y rápido.

Pero espera: hay un error sutil en algunos casos extremos. ¿Qué pasa si el diccionario contiene una clave que mapea a una cadena que no existe como clave? Según el enunciado del problema, asumimos que la entrada está bien formada, pero el código robusto podría manejar eso regresando None. Además, ¿qué pasa con los auto-bucles? "/self": "/self" sería detectado por la detección de ciclos inmediatamente.

Produzcamos la versión final, pulida, con comentarios y manejo de errores.


def resolve_path(fs, path):
    """
    Resuelve una ruta de enlace simbólico hasta su destino real.
    
    Parámetros:
    fs (dict): Un diccionario que mapea rutas absolutas a None (archivo real)
               o una cadena (destino del enlace simbólico).
    path (str): La ruta inicial a resolver.
    
    Regresa:
    str o None: La ruta real si se encuentra, None si se detecta un ciclo o la
                ruta lleva a un destino inválido.
                 
    Ejemplo:
    >>> fs = {"/a": "/b", "/b": None, "/loop": "/loop"}
    >>> resolve_path(fs, "/a")
    '/b'
    >>> resolve_path(fs, "/loop")
    None
    """
    if path not in fs:
        # Ruta no está en el sistema de archivos: tratar como faltante, también podría lanzar excepción.
        return None
    
    visited = set()
    current = path
    
    while current in fs:
        if current in visited:
            # Ciclo detectado
            return None
        visited.add(current)
        target = fs[current]
        if target is None:
            # Llegamos a un archivo real
            return current
        # Seguir el enlace simbólico
        current = target
    
    # Si salimos porque current no está en fs, es un enlace roto.
    return None

Esta es la implementación que enviaremos. Es concisa, eficiente y maneja ciclos con elegancia.

El modelo matemático: grafos funcionales

El diccionario del sistema de archivos se puede ver como una función parcial f: P → P ∪ {⊥}, donde P es el conjunto de cadenas de ruta y ⊥ representa un archivo real (null). Para cada ruta p que es un enlace simbólico, f(p) = q donde q es otra ruta. Para archivos reales, f(p) = ⊥.

Partiendo de una ruta inicial p0, generamos una secuencia: p0, p1, p2, ... donde p_{i+1} = f(p_i) siempre que f(p_i) sea una cadena (no ⊥). Esta secuencia:

Termina en un archivo real: encontramos algún p_k tal que f(p_k) = ⊥, y regresamos p_k.
Entra en un ciclo: existen i < j tales que p_i = p_j, y para todo k ≥ i, la secuencia se repite. Como f es determinista, una vez que revisitamos un nodo estamos en un bucle infinito. Detectamos esto y regresamos None.
Lleva a una clave faltante: si algún f(p_i) es una cadena que no está en el dominio de f, la cadena se rompe. Defensivamente regresamos None.

Esta es exactamente la estructura de un grafo funcional (un grafo dirigido donde cada nodo tiene grado de salida como máximo 1). La detección de ciclos en grafos funcionales es un problema clásico de ciencias de la computación. El enfoque del conjunto de visitados es esencialmente un método de "marcar y barrer": marcamos los nodos a medida que los recorremos, y si encontramos un nodo marcado, tenemos un ciclo.

Un enfoque matemático alternativo es el algoritmo de detección de ciclos de Floyd (tortuga y liebre), que usa O(1) de memoria extra en lugar de O(L). Pero dado que es poco probable que las cadenas de enlaces simbólicos sean astronómicamente largas, el conjunto de visitados es más simple y legible. Para completar, aquí te mostramos cómo podrías implementar el algoritmo de Floyd:


def resolve_path_floyd(fs, path):
    """
    Detección de ciclos usando el algoritmo de la tortuga y la liebre de Floyd.
    Usa O(1) de espacio extra pero dos apuntadores.
    """
    def next_node(p):
        # regresa la siguiente ruta o None si es archivo real o falta
        if p not in fs:
            return None
        val = fs[p]
        if val is None:
            return None
        return val
    
    tortoise = path
    hare = path
    
    # Fase 1: detectar ciclo
    while True:
        tortoise = next_node(tortoise)
        hare = next_node(next_node(hare)) if hare is not None else None
        if hare is None or tortoise is None:
            # No hay ciclo, llegamos a un archivo real o enlace roto
            break
        if tortoise == hare:
            # Ciclo detectado
            return None
    
    # Fase 2: encontrar el destino real sin ciclo
    # En realidad, si no hay ciclo, solo seguimos hasta None
    current = path
    visited = set()  # todavía necesitamos visitados para evitar bucles infinitos? No, porque ya sabemos que no hay ciclo.
    # Pero cuidado: Floyd solo nos dice que hay un ciclo, no dónde comienza si queremos el archivo real.
    # Para nuestro propósito, es más simple reutilizar el conjunto de visitados iterativo. Floyd es excesivo.
    # Así que nos quedamos con la versión anterior.
    return resolve_path_iterative(fs, path)  # respaldo

Dada la claridad del conjunto de visitados, mantendremos ese como nuestra solución canónica.

Análisis de complejidad

Sea L el número de nodos distintos visitados durante la resolución (la longitud de la cadena hasta la terminación o detección de ciclos). En el peor caso, L podría ser hasta el número total de enlaces simbólicos en el diccionario (digamos N). El algoritmo:

Complejidad temporal: O(L) porque cada paso realiza búsquedas en el diccionario e inserciones/verificaciones en el conjunto en tiempo constante.
Complejidad espacial: O(L) para el conjunto de visitados. En el peor caso, L = N, entonces O(N) de memoria adicional.

Si la memoria es una preocupación (por ejemplo, miles de millones de enlaces simbólicos), la variante de Floyd reduciría el espacio a O(1), pero a costa de la legibilidad. Para contextos de entrevista, el conjunto de visitados es perfectamente aceptable y esperado.

Probando la solución (con los ejemplos proporcionados)

Escribamos algunos casos de prueba para asegurar la corrección.


def test_resolve_path():
    fs = {
        "/a": "/b",
        "/b": "/c",
        "/c": None,
        "/loop1": "/loop2",
        "/loop2": "/loop1",
        "/real": None,
        "/alias": "/real",
        "/self": "/self",      # auto-bucle
        "/broken": "/missing", # enlace roto
    }
    
    assert resolve_path(fs, "/a") == "/c"
    assert resolve_path(fs, "/alias") == "/real"
    assert resolve_path(fs, "/loop1") is None
    assert resolve_path(fs, "/real") == "/real"
    assert resolve_path(fs, "/self") is None
    assert resolve_path(fs, "/broken") is None  # destino faltante
    assert resolve_path(fs, "/nonexistent") is None
    
    print("¡Todas las pruebas pasaron!")

if __name__ == "__main__":
    test_resolve_path()

Ejecutar esto debería mostrar "¡Todas las pruebas pasaron!"

Casos extremos y trampas

Diccionario vacío: Si fs está vacío, cualquier ruta se resuelve a None (ya que la ruta no está en fs). Es consistente.
La ruta apunta directamente a None: Debería regresar la ruta misma (archivo real). Nuestro código hace eso porque target es None y regresamos current.
Ciclo de longitud 1: Una clave que se mapea a sí misma. Se detecta inmediatamente cuando vemos que current ya está en el conjunto de visitados.
Cadena que termina en una clave faltante: Regresamos None, que es un valor predeterminado sensato. El enunciado del problema no especificó este escenario, pero el código robusto lo maneja.
Cadenas muy largas: Sin recursión, por lo que el desbordamiento de pila es imposible.

Por qué esta pregunta es interesante

La pregunta de Cassidy evalúa varios conceptos fundamentales: recursión vs iteración, detección de ciclos, búsquedas en diccionarios y pensamiento en casos extremos. Refleja la resolución de enlaces simbólicos del mundo real en sistemas operativos (aunque esos son más complejos con permisos y puntos de montaje). En entrevistas, es una excelente manera de evaluar si un candidato recurre a la recursión sin considerar los límites de la pila, y si recuerda detectar ciclos.

Además, es un ejemplo perfecto de un problema de recorrido de grafos disfrazado de problema de sistema de archivos. Una vez que ves el grafo funcional, la solución se vuelve clara.

Enfoques alternativos de la comunidad

He visto a algunos desarrolladores implementar esto usando un bucle while con un contador (por ejemplo, limitar a 1000 pasos) como una detección de ciclos pobre. Eso es frágil. Otros usan una lista para registrar el orden de visita y verifican if current in path_list, que es O(L) por verificación, haciendo que todo el algoritmo sea O(L^2). El conjunto de visitados da verificaciones O(1).

También hay una técnica de dos apuntadores (tortuga y liebre) que usa espacio O(1). Aunque elegante, es más difícil de explicar en una entrevista a menos que estés preparado. El conjunto de visitados es el punto medio ideal.

Poniéndolo todo junto: la respuesta final

Aquí está la función Python completa, lista para usar, con cadena de documentación y comentarios.


def resolve_path(fs, path):
    """
    Resuelve una ruta de enlace simbólico hasta su destino real.
    
    La función sigue enlaces simbólicos hasta que llega a un archivo real
    (el valor es None) o detecta un ciclo. Si se encuentra un ciclo, regresa None.
    
    Args:
        fs (dict): Un diccionario que mapea rutas de cadena a None (archivo real)
                   o una cadena (destino del enlace simbólico).
        path (str): La ruta inicial a resolver.
    
    Regresa:
        str o None: La ruta real resuelta, o None si se detecta un ciclo
                     o la ruta lleva a un destino inválido.
    
    Complejidad temporal: O(L) donde L es la longitud de la cadena de enlaces simbólicos.
    Complejidad espacial: O(L) para el conjunto de visitados.
    """
    if path not in fs:
        return None  # la ruta no existe en el sistema de archivos
    
    visited = set()
    current = path
    
    while current in fs:
        if current in visited:
            # Ya estuvimos aquí antes -> ciclo
            return None
        visited.add(current)
        target = fs[current]
        
        if target is None:
            # Llegamos a un archivo/directorio real
            return current
        # De lo contrario, seguir el enlace simbólico
        current = target
    
    # Si salimos del bucle porque current no es una clave en fs,
    # el enlace simbólico apunta a una ruta inexistente.
    return None

Conclusión

Hemos viajado desde una solución recursiva ingenua a través de una versión iterativa consciente de ciclos hasta una implementación óptima y limpia. Las ideas clave: tratar el sistema de archivos como un grafo funcional, usar un conjunto para registrar nodos visitados y preferir siempre la iteración sobre la recursión para cadenas sin límite. La pregunta de Cassidy nos recuerda que incluso los problemas aparentemente simples pueden ocultar complejidad, y que un enfoque metódico produce código robusto.

Gracias nuevamente a Cassidy Williams por la inspiración. Si disfrutaste este desglose, revisa su boletín para más desafíos semanales. ¡Feliz codificación, y que tus enlaces simbólicos nunca formen ciclos!

Referencias y lecturas adicionales

Grafo funcional (Wikipedia) — Antecedentes matemáticos para mapear nodos a como máximo un sucesor.
Detección de ciclos (algoritmos de Floyd y Brent) — Alternativas eficientes en espacio al conjunto de visitados.
Comando readlink de GNU — Resolución de enlaces simbólicos en el mundo real en Unix.

¿Aún no tienes suficiente de lumænaut? Lee esto...

Puliendo LeetCode — Día 2: Suma de Dos Números — acarreo de primaria en listas enlazadas: recorre una cadena paso a paso, mantén un poco de estado y cuida los casos extremos al final.
Los 8 paradigmas de algoritmos — ocho modelos mentales que repetirás en problemas, entrevistas y código de producción.
Así funciona el bucle del videojuego — el latido de un fotograma: actualizar, renderizar y una temporización estable en lenguaje sencillo.