March 14, 2014
Longest Common Sub Path
Problem
Given an input text file with format as in the following example:
1 2 3 |
/foo/bar/x/1/2 /foo/bar/x/3 /foo/bar/x/4/5/6 |
print the number of sub directory levels that are common to all paths in the file. In this case it is /foo/bar/x so the count is 3
Solution
Here is a sample python code to implement that
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
# Preallocate a list of lists # Each child list represent a column # For example the first one contains the root directory name of each path # The second list contains the second subdirectory of each path # and so on. I am assuming the max number of nested directories is 4 columns = [[] for c in range(4)] # Row index i = 0 # For each none empty line in the file for row in [l for l in open('input.txt') if l != '\n']: # Column index j = 0 # 1. Remove white space and new line characters # 2. Split line using / as separator # 3. Filter out empty tokens for dir in [dir for dir in row.rstrip().split( '/') if dir]: # Append directory name to the corresponding column columns[j].append(dir) # Go to next column j = j + 1 # Go to the next row i = i + 1 # For each column check if all directory names are the same # stop on the first mismatch and print the number count = 0 for c in columns: # Check if all elements in the column are unique # If all elements are the same then the set length is # just 1 and also the number of columns in the list # should be the same as the number of rows in the file if len(set(c)) == 1 and len(c) == i: count = count + 1 else: # Stop on first mismatch break # Print columns to get an idea if the script is doing the right # thing print columns # Print the max number of common directory paths print count |