under engineered

Longest absolute file path

Problem #

The question gives us the input in the form of a file path

input #

dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext

which represents the following

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

output #

The length of absolute length of the longest file path. This includes:

So for the above input example, the answer would be adding up the length of dir -> subdir2 -> file.txt

Solution #

The directory structure looks like the classic folder structure on our laptops, where each file is nested under a folder and folders in turn can be in other folders/directory.

Before you run off to start parsing the string as a tree like structure, I'd urge you to hold-your-horses. There's very less ROI (return on investment)

The files are located directly under the directory one level up, and each path is separated by \n.

So that's our #1 hint. Process each path one by one - split by \n

pro-tip: \t and \n are single characters

If you're to closely look at the file path, you get each level or nesting one by one. For example, the below path would be three separate strings and not one if you split by \n.

dir                 (level 0)
    subdir2          (level 1)
        file.txt     (level 2)

=> ['dir', '\tsubdir2', '\t\tfile.txt']

You get the level by counting the \t character.

determining the longest path #

The following should probably do it :P

how to calculate the length #

(cost calculation figure)

dir                (level 0)
<-3->                           3
    subdir2        (level 1)
    <-1 + 7->                   3 + 8 = 11    
        file.txt   (level 2)
        <-1 + 8->               11 + 9 = 20

** 1 is added at both level 1,2 for the nesting

translating into code #

The below code is written in Go, as I wanted to learn this for a long time and this will probably teach me at least 10% :P

Go code is very terse, and readable like English

processing the input and splitting it by \n #

func lengthLongestPath(input string) int {
    lines := strings.Split(input, "\n")

    // iterating over lines one by one
    for _, eachLine := range lines {
        // calculate the cost of line
    }
}

calculating cost #

cost of item = self cost + prev level cost

I'll also have to store the cost of each level so that it can be used to calculate the cost of subsequent levels. (using a map)

func lengthLongestPath(input string) int {
    maxCost := 0
    lines := strings.Split(input, "\n")
    costMap := make(map[int]int)

    for _, eachLine := range lines {
        // count the `\t` in the line
        tabs := strings.Count(eachLine, "\t")

        // calculate the cost of each line
        cost := len(eachLine) - tabs + costMap[tabs - 1] + nestingCost(tabs)

        // save the cost for future use
        costMap[tabs] = cost

        if strings.Contains(eachLine, ".") {
            // do this only if it's a file
            if maxCost < cost {
                maxCost = cost
            }
        }
    }

    return maxCost
}

func nestingCost(tabs int) int {
    if tabs == 0 {
        return 0
    }
    return 1
}

In the above code, all the magic is in the line which calculates the cost

cost := len(eachLine) - tabs // self cost
    + costMap[tabs - 1]      // prev level cost
    + nestingCost(tabs)      // nesting cost either 0 or 1

If you're scratching your head and wondering what's going on in there, let me break it down.

practise #

discuss on twitter, because why not?