This week's tasks are about length, so let's cue up the Eagles Long Run album from 1979 and get to work.

Task 1: Longest Repeating Character

Task Description

You are given a string str and an integer k > 0. Write a script to choose any character of str and change it to another character. You may perform this operation up to k times. Return the length of the longest reachable substring of a single letter.

  • Example 1: Input: $str = "AAAAA", $k = 2

    • Output: 5
    • Every character in the string is already the same letter "A". The maximum operations allowed (k = 2) do not even need to be used. The entire string of length 5 is already the longest valid substring.

  • Example 2: Input: $str = "ABCDE", $k = 4

    • Output: 5
    • All 5 characters in the string are distinct. The most frequent character occurs only 1 time. To turn the entire string into a single repeated character, we need to replace 5 - 1 = 4 characters. Since k = 4, we can replace "B","C","D", and "E" with "A" to form "AAAAA".

  • Example 3: Input: $str = "AAABBBBAA", $k = 1`

    • Output: `5
    • If we target "A", we could change the "B" in "AAAB" (k=1 replacement) to get length 4 ("AAAA"). If we target "B", we can pick the substring "BBBBA" and change the single trailing "A" to "B" (k=1 replacement) to form "BBBBB", which gives a length of 5. Targeting "B" gives better result than targeting "A".

  • Example 4: Input: $str = "ABACADA", $k = 2

    • Output: 5
    • Look at the substring [0..4] which is "ABACA" (length 5). In this window, "A" appears 3 times, and there are 2 non-"A" characters ("B" and "C"). With k = 2, we can replace "B" and "C" with "A" to form "AAAAA".
    • Look at the substring [2..6] which is "ACADA" (length 5). Here, "A" appears 3 times, and non-"A" characters ("C" and "D") count to 2. Replacing them gives "AAAAA".
    • In both cases, the maximum valid length is 5.

  • Example 5: Input: $str = "BAAABAAAA", $k = 1

    • Output: 8
    • The string has two groups of "A"s separated by a single "B" ("AAABAAAA"). We can replace the character 4 "B" with an "A" to get a sequence of 8 "A".

The thought process

There seem to be a lot of combinations to work through. Something easier would be to take every character in turn and see how long of a streak we can make of that character. There's no prize being awarded for being frugal with substitutions, so let's just do k substitutions every time and see where we land.

Some code 

sub task($str, $k) { my $longest = 1; my $strlen; while ( ($strlen = length($str)) > 0 && $strlen > $longest ) { # Shift left-most character off str my $c = substr($str, 0, 1, ""); # Make as many substitutions as possible my $copy = $str; $copy =~ s/[^$c]/$c/ for 1 .. $k; # Check the length of repeated first character $copy =~ m/^($c+)/; my $run = 1 + length($1 // ""); $longest = $run if $run > $longest; } return $longest; }

The body of the loop is to consider the first character of the string, chop it off, and continue until the string is empty or we can't beat the longest value. The four-argument version of substr simplifies it for us -- it returns the first character, and the fourth argument effectively removes it by replacing it with an empty string.

We want to modify the string, so we'll operate on a copy. In the copy, we substitute the first k characters that aren't $c. We may end up doing too much in this step, but, meh.

To check the length, do a regular expression match for repetitions of $c at the beginning of $copy. Capture the match and check its length. The +1 is there to account for $c.

Task 2: Longest Absolute Path

Task Description

You are given a filesystem as string. Write a script to return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

dir - subdir1 - file1.ext - subsubdir1 - subdir2 - subsubdir2 - file2.ext

The above filesystem can be represented as below:

"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

  • Example 1: Input: $fs = "dir\n\tsubdir1\n\t\tsubsubdir1\n\tsubdir2"

    • Output: 0
    • There are no files in the system (a file must contain a . character separating a name and extension). Since there are no files, the answer is 0.

  • Example 2: Input: $fs = "file1.txt\nfile2.ext\na.png"

    • Output: 9
    • All entries are located at root depth (0 tabs). Found File paths:
      • "file1.txt" (length = 9)
      • "file2.ext" (length = 9)
      • "a.png" (length = 5)

  • Example 3: Input: $fs = "my documents\n\tproject v1.0\n\t\tnotes v1.txt\n\timage.png"

    • Output: 38
    • Notice project v1.0 is a directory (it has children beneath it), while notes v1.txt and image.png are files. Found File Paths:
      • "my documents/project v1.0/notes v1.txt" (length = 38)
      • "my documents/image.png" (length = 22)

  • Example 4: Input: $fs = "root\n\ta\n\t\tb\n\t\t\tc.txt\n\td\n\t\te.txt"

    • Output: 14
    • Found File Paths:
      • "root/a/b/c.txt" => 4 + 1 + 1 + 1 + 1 + 1 + 5 = 14
      • "root/d/e.txt" => 4 + 1 + 1 + 1 + 5 = 12

  • Example 5: Input: $fs = "a\n\tb\n\t\tc\n\t\t\td\n\t\t\t\te.txt\n\tvery_long_directory_name\n\t\tf.txt"

    • Output: 32
    • Found File Paths:
      • "a/b/c/d/e.txt" => 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 5 = 13
      • "a/very_long_directory_name/f.txt" => 1 + 1 + 24 + 1 + 5 = 32

The thought process

The examples clarify some of the specification. The / separators in the path are to be counted. A path must end at a file; the definition of a file seems to be a string containing a . with nothing under it.

This is a tree, so let's tree. We'll want to create a tree structure out of the string, and then walk through the tree looking for files and counting string lengths.

A tree is a recursive structure, where a node names a file or directory, and contains links to the children under it. I've done this before using classes, and I shall do it again.

The textual form with significant leading tabs is somewhat awkward (shades of Python). We'll have to note the context to see if we're moving up or down the tree while processing the text.

Let's tree

A little bit of object-oriented design. Let's assume we have a recursive tree that consists of Node objects. Besides a constructor, the class should have methods to

  • add a child node
  • test whether a node is a file
  • walk through the tree looking for the longest path.

Building the tree will require us to move up the tree, as well as down, so it will be useful for a node to remember its parent. A well-formed input string will only tab over one level at a time while going down the tree, but it might jump back more than one level as in Example 5, so we should record the depth of a node at the time it's placed into the tree.

Here's a Node class that can build a tree. I'll come back to the body of the methods. The :reader attribute on the fields generate accessors, and the child nodes are tracked in an array of @children.

use feature 'class'; no warnings "experimental::class"; class Node { field $name :param :reader; field $depth :param :reader = 0; field $parent :param :reader = undef; field @children; method addChild($name) { ... } method isFile() { ´... } method findLongest() { ... } }

Let's parse

Having Node in my pocket, I can proceed to building the tree.

I start the tree by giving it a root with a zero-length name. It will get default parameters, which means that it goes at depth 0 and has no parent.

The $node variable will be a cursor that points at the node we're currently working on. Additions to the tree will be relative to it; hence it starts by pointing at $root.

Now we need to parse that awkward input string. Newline separators give us the name of a node, and the leading tabs tell us where to go in the tree. If the indent increases, we have a child node; if it decreases, we need to back up; if it stays the same, we have a sibling.

sub task($fs) { my $node = my $root = Node->new(name => ""); # Build a tree structure from the input text. for my $line ( split(/\n/, $fs) ) { # Split on tab characters tells us how far down the tree # we are by creating empty fields. The name is the last # element in the split. my @level = split(/\t/, $line); my $name = $level[-1]; if ( @level > $node->depth() ) # Descending deeper { $node = $node->addChild($name); } elsif ( @level == $node->depth() ) # Sibling at same level { $node = $node->parent->addChild($name); } else # Indent decreased, move back up the tree { $node = $node->parent while ( $node->depth >= @level ); $node = $node->addChild($name); } } return $root->findLongest(); }

Notes:

  • @level is the result of splitting a line on tabs. It will contain empty elements for leading tabs, and the name text in its last element. Using it in scalar context will give us the depth of a node, without introducing another variable, but with a tiny bit of obfuscation.
  • When the indent decreases, we need to move the $node cursor back up to the correct parent. This is why the depth and parent fields exist in the Node class.

The tree-building code

Back to the Node class. There's really only one method needed to build the tree: addChild. To add a child, we construct a new Node object, bumping its depth and recording its parent. It goes into the @children array.

 method addChild($name) { my $c = Node->new(name => $name, depth => $depth +1, parent => $self); push @children, $c; return $c; }

The searching function

Finally, we arrive at looking for the path length. It's going to be a breadth-first search among the children. Each child goes onto a queue, and then we process elements until we run out of queue. If we hit a file, we're at the bottom of the tree, so check the path length. To make that possible, we tag each queue element with the length up to that point.

method findLongest() { my $longest = 0; my @queue = ( [$self, -1] ); while ( defined(my $x = shift @queue) ) { my ($node, $sofar) = $x->@*; if ( $node->isFile ) { my $len = $sofar + length($node->name); $longest = $len if $len > $longest; next; } for my $child ( $node->getChildren->@* ) { # Add 1 for the / separator push @queue, [ $child, $sofar + 1 + length($node->name) ]; } } return $longest; }

Notes:

  • Each element in the @queue is a reference to a pair: the node, and the accumulated path length up to the node.
  • The first thing in the queue is the root node. The length at this point is -1, because we don't want to count a separator here. Later, as we push children onto the queue, we'll add 1 to count the / separator, and that will make the accounting correct at the root.
  • As we take things off the queue, we'll check if the node is a file. If it is, we can check the total path length. The Node class method for testing for file is to see if there are no children, and . character exists in the name: 
method isFile() { return @children == 0 && index($name, ".") >= 0 }
  • If it's not a file, then we'll push all the children onto the queue, incrementing the path length by this node's name plus a separator.
  • We need an accessor to get the @children list of another Node object. My accessor returns a reference, to avoid an array copy.

Wrap-up

There's a little more code than usual in this task solution. The whole thing is on GitHub. There's extra stuff there, including overloading the "" string operator to make it easy to dump a tree for debugging, as well as the unit tests.