Unix Cd Command with Symbolic Link Resolution

Let's understand what we're being asked to do. We have a current working directory (like /foo/bar) and a cd command (like ../boo or /boo), and we need to compute the final path after executing the command.

Tracing through examples:

• From /foo/bar, command boo → append to current path → /foo/bar/boo
• From /foo/bar, command /boo → absolute path (starts with /) → /boo
• From /foo/bar, command ../boo → go up one level (..), then down to boo → /foo/boo
• From /foo/bar, command boo/././doe → append boo, . means stay (no change), . again (no change), then doe → /foo/bar/boo/doe

Important constraints: We need to handle symbolic links (shortcuts that point to other directories) and detect cycles (when following links creates an infinite loop). We also need to handle redundant slashes like //foo///bar (should be treated as /foo/bar).

Edge cases to consider: What if we try to go up from root (/..)? What if the path has trailing slashes (/foo/bar/)? What if a symbolic link points to itself or creates a cycle? What if the command is just . or ..?

A file path is essentially a sequence of directory names separated by slashes. We can break the path into components and process them one by one.

Special components like . (current directory) and .. (parent directory) modify our position in the directory tree. The key insight is that .. means 'go back one level' - this is a last-in, first-out operation where we need to undo the most recent directory we entered.

By treating the path as a sequence of operations (enter directory, go back, stay), we can use a data structure that naturally supports adding and removing from the end.

For symbolic links, we need to track which paths we've visited while resolving links. If we encounter the same path twice, we've found a cycle and should stop to avoid infinite loops.

Think of navigating directories like building a tower of blocks:

• Each directory name adds a block to the top
• The .. command removes the top block (go back one level)
• The . command does nothing (stay at current level)
• An absolute path (starting with /) means clear all blocks and start fresh

For symbolic links, imagine following a trail of breadcrumbs. If you ever see the same landmark twice, you're walking in circles and need to stop.

Use a stack-based approach to manage directory traversal. Split the path into components by '/' delimiter. For each component: if it's a regular directory name, push it onto the stack; if it's '..', pop from the stack (go up one level); if it's '.', do nothing (stay at current level). Handle absolute paths by clearing the stack first. For symbolic links, use depth-first search with a visited set to track paths and detect cycles. Join the final stack contents with '/' to produce the resolved path.

def cd_command(currentPath, command):
    """
    Simulate Unix cd command with path resolution.
    Handles relative paths (. and ..), absolute paths, and symbolic links with cycle detection.
    """
    # Define symbolic link mappings for testing
    symlinks = {
        '/usr/local': '/usr',
        '/home/user/docs': '/home/user/documents',
        '/var/log': '/var/logs',
        '/tmp/link': '/tmp'
    }
    
    def normalize_path(path):
        """Remove redundant slashes and trailing slashes."""
        # Replace multiple slashes with single slash
        while '//' in path:
            path = path.replace('//', '/')
        # Remove trailing slash unless it's root
        if len(path) > 1 and path.endswith('/'):
            path = path[:-1]
        return path
    
    def resolve_path(base_path, target_path, visited):
        """Resolve path with symbolic link handling and cycle detection using DFS."""
        # Normalize the target path
        target_path = normalize_path(target_path)
        
        # Determine if absolute or relative path
        if target_path.startswith('/'):
            # Absolute path - start from root
            working_path = target_path
        else:
            # Relative path - combine with current path
            working_path = base_path + '/' + target_path
        
        # Normalize combined path
        working_path = normalize_path(working_path)
        
        # Check for cycle in symbolic link resolution
        if working_path in visited:
            return "Error: Symbolic link cycle detected at " + working_path
        
        # Add current path to visited set for cycle detection
        visited.add(working_path)
        
        # Split path into components for stack-based traversal
        components = working_path.split('/')
        
        # Initialize stack for directory traversal
        stack = []
        
        # Process each component
        for component in components:
            # Skip empty components (from leading/trailing slashes)
            if component == '' or component == '.':
                # Current directory - do nothing
                continue
            elif component == '..':
                # Parent directory - pop from stack if not empty
                if stack:
                    stack.pop()
            else:
                # Regular directory - push onto stack
                stack.append(component)
        
        # Build resolved path from stack
        if not stack:
            resolved = '/'
        else:
            resolved = '/' + '/'.join(stack)
        
        # Check if resolved path is a symbolic link
        if resolved in symlinks:
            # Follow symbolic link recursively with DFS
            link_target = symlinks[resolved]
            return resolve_path(resolved, link_target, visited)
        
        return resolved
    
    # Normalize current path
    currentPath = normalize_path(currentPath)
    
    # Initialize visited set for cycle detection
    visited = set()
    
    # Resolve the path with symbolic link handling
    result = resolve_path(currentPath, command, visited)
    
    return result

• Stack-based path traversal: Use a stack to manage directory components when processing paths - push directories onto the stack and pop for '..' operations. This naturally handles nested directory structures and makes backtracking trivial, perfect for any hierarchical navigation problem.
• Tokenization before processing: Split paths by '/' delimiters and process each component individually rather than manipulating the raw string. This cleanly handles edge cases like redundant slashes ('/foo//bar'), trailing slashes, and makes '.' and '..' logic straightforward to implement.
• Cycle detection with visited set: When resolving symbolic links, maintain a visited set of paths encountered during the current resolution chain. Before following a symlink, check if the target is already in the set - this prevents infinite loops in circular symlink references.
• Absolute vs relative path handling: Always check if a path starts with '/' to determine if it's absolute or relative. For absolute paths, clear your stack and start fresh; for relative paths, build upon the current directory stack. Missing this distinction causes incorrect path resolution.
• Normalization through reconstruction: After processing all path components with the stack, reconstruct the final path by joining stack elements with '/' and prepending '/'. This ensures a canonical format regardless of input variations (multiple slashes, dots, etc.).
• Real-world file system operations: This pattern directly applies to implementing file system utilities, URL path resolution in web servers, package dependency resolution, and any system requiring hierarchical namespace navigation with shortcuts or aliases.