Perl Weekly Challenge 112: Canonical Path

We will split the input on slashes, leaving us an array of directory and file names. We copy this array to a new array, with the following exceptions:

• We skip empty components, and components of the form ..
• A component of the form .. is not only skipped, but we also delete the last element of the new array.

We have the input in $_. First, we split into components:

my @parts = split /\/+/;

Now we build a new array, @parts2:

foreach my $part (@parts) {
    next if $part eq "." || $part eq "";
    if ($part eq "..") {
        pop @parts2;
        next;
    }
    push @parts2 => $part;
}

And we print it:

say "/" . join "/" => @parts2;

Find the full program on GitHub.

AWK will split the input for us. By default on whitespace, but we can tell it to split on slashes:

BEGIN {
    FS="/"
}

AWK doesn't have a pop function, so we just keep track of how many elements we have in an array path:

delete path
j = 0                            # Tracks the number of parts in
                                 # the canonical part.
for (i = 1; i <= NF; i ++) {     # Loop over directory parts
    if ($i == "") {              # Skip empty parts
        continue;
    }
    if ($i == ".") {             # Skip current directory
        continue;
    }
    if ($i == "..") {            # Back up to parent directory
        if (j > 0) {
            j --
        }
        continue;
    }
    path [j] = $i                # Copy
    j ++
}

We can now print the canonical path. If we just have a root directory, we have to special case it:

if (j == 0) {                    # Root directory
    print "/"
}
else {                           # Print parts, preceeded by a /
    for (k = 0; k < j; k ++) {
        printf "/%s", path [k]
    }
    print ""
}

Find the full program on GitHub.

The bash solution isn't very different from the AWK solution:

IFS="/"

while read -a i_parts
do    declare -a o_parts
      j=0
      for ((i = 0; i < ${#i_parts[@]}; i ++))
      do  if [ "X${i_parts[$i]}" == "X" ]       # Skip empty parts
          then continue
          fi
          if [ "X${i_parts[$i]}" == "X." ]      # Skip current directory
          then continue
          fi
          if [ "X${i_parts[$i]}" == "X.." ]     # Back up to parent directory
          then if ((j > 0))
               then ((j --))
               fi   
               continue
          fi
          o_parts[$j]=${i_parts[$i]}            # Copy part
          ((j ++))
      done  
      if  ((j == 0))
      then echo "/"                             # Root directory
      else for ((k = 0; k < j; k ++))           # Canonical path
           do  printf "/%s" ${o_parts[$k]}
           done
           echo
      fi
done

Our C solution is different. We won't be splitting the input into components. Instead, we first "eliminate" components: current directories, and parents directories together with the preceeding component. We do this by overwriting those components with slashes.

Once we have to this, we copy the result to the output, skipping over any subsequent slashes.

The input path is in a variable char * line, as its length in size_t str_len:

First the eliminating of parts:

line [str_len - 1] = '/';    /* Replacing trailing newline with slash */
for (size_t i = 0; i < str_len; i ++) {
    if (line [i] == '.' && line [i - 1] == '/') {
        /* Component starts with a . */
        if (line [i + 1] == '/') {
            line [i] = '/';  /* Current directory */
            continue;
        }
        else {
            if (line [i + 1] == '.' && line [i + 2] == '/') {
                /* Parent directory. */
                /* First wipe this component */
                line [i]     = '/';
                line [i + 1] = '/';
                /* Then wipe the previous component, if any. */
                /* First, skip the slashes */
                size_t j = i - 1;
                while (j && line [j] == '/') {
                    j --;
                }
                /* Now, erase exactly one component */
                while (j && line [j] != '/') {
                    line [j] = '/';
                    j --;
                }
            }
        }
    }
}

Now we remove any trailing slashes:

while (str_len > 1 && line [str_len - 1] == '/') {
    str_len --;
}

Printing, skipping any subsequent slashes:

bool slash = false;
for (size_t i = 0; i < str_len; i ++) {
    if (line [i] == '/') {
        if (slash) {
            continue;
        }
        slash = true;
    }
    else {
        slash = false;
    }
    printf ("%c", line [i]);
}
printf ("\n");

Find the full program on GitHub.

We have the input path in a variable line. First we split on slashes. Except that Lua doesn't have a split function, so we capture anything which is not a slash.

local parts = {}
for part in line : gmatch ("[^/]+") do
    table . insert (parts, part)
end

Creating the second array:

local parts2 = {}   
for index, part in ipairs (parts) do
    if part == "." then    -- Current directory -> skip
        goto continue
    end
    if part == ".." then   -- Parent direction -> pop from new structure
        table . remove (parts2)
        goto continue
    end
    table . insert (parts2, part)  -- Else, copy
    ::continue::
end

Note that Lua doesn't have a next, so we use a goto to jump to the end of the loop.

Print the result:

print ("/" .. table . concat (parts2, "/"))

Find the full program on GitHub.

The input path is in a variable _:

let parts = _ . split (/\/+/)              // Split on slash.
let parts2 = [] 
parts . every (_ => {
    if (_ == "." || _ == "") {             // Skip current directory,
        return true                        // and empty parts.
    }
    if (_ == "..") {                       // Pop parent directory.
        parts2 . pop ()
        return true 
    }
    parts2 . push (_)                      // Copy part.
    return true
})
console . log ("/" + parts2 . join ("/"))  // Print result.

Find the full program on GitHub.

line contains our input path:

parts  = line . rstrip () . split ("/")   # Split input on / 
parts2 = []
for part in parts:   
    if part == "" or part == ".":         # Skip empty parts,
        continue                          # and current directory.
    if part == "..":                      # Pop parent directory
        if len (parts2):
            parts2 . pop ()
        continue    
    parts2 . append (part)                # Else, append.
print ("/" + "/" . join (parts2))         # Print result.

Find the full program on GitHub.

parts = line . strip() . split (/\/+/)
parts2 = []
parts . each do
    | part |
    if part == "" or part == "."   # Skip empty parts and current directory
        next
    end
    if part == ".."                # Remove parent directory
        parts2 . pop
        next
    end
    parts2 . push (part)           # Add part
end
puts ("/" + parts2 . join("/"))    # Print result