March 14, 2014

Longest Common Sub Path

By Mohammed Abualrob Algorithms and Data Structures 0 Comments

Problem

Given an input text file with format as in the following example:

/foo/bar/x/1/2
/foo/bar/x/3
/foo/bar/x/4/5/6

/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

# 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

# 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

8 BIT AVENUE

Longest Common Sub Path

More from my site

About Author

Mohammed Abualrob

Add a Comment