Perl Weekly Challenge: The Power of String

Posted on by

With Perl Weekly Challenge 349‘s tasks being “Power String” and “Meeting Point”, I had a tough music choice. I could have given you Kansas from the 70s, but my high school/college years were the 80s, so I had to go with my heart and give you The Power of Love by Huey Lewis & The News.

Don’t need no credit card to ride this train.

Task 1: Power String

You are given a string.

Write a script to return the power of the given string.

The power of the string is the maximum length of a non-empty substring that contains only one unique character.

Example 1

Input: $str = "textbook"
Output: 2

Breakdown: "t", "e", "x", "b", "oo", "k"
The longest substring with one unique character is "oo".

Example 2

Input: $str = "aaaaa"
Output: 5

Example 3

Input: $str = "hoorayyy"
Output: 3

Breakdown: "h", "oo", "r", "a", "yyy"
The longest substring with one unique character is "yyy".

Example 4

Input: $str = "x"
Output: 1

Example 5

Input: $str = "aabcccddeeffffghijjk"
Output: 4

Breakdown: "aa", "b", "ccc", "dd", "ee", "ffff", "g", "h", "i", "jj", "k"
The longest substring with one unique character is "ffff".

Approach

Once I excised Huey Lewis from my brain, I heard something else: “And sure enough Johnny’s got his finger on the power… …the power… the power window.” But that’s a story for another time1.

There are probably clever ways to do this, but I’m going to just process the string character-by-character, keeping track of what single character sequences I find, and then spit out the length of the longest one found. Really, unless I’m spitting out the breakdown, I don’t need to track the sequences, just the length of the longest one.

Raku

Not much to say about the Raku implementation.

sub powerString($str) {
  my $longest = 0;
  my @chars   = $str.comb;
  my $last    = @chars.shift;
  my $count   = 1;
  for @chars -> $current {
    if ($current eq $last) { # same as last char
      $count++;
    }
    else { # character has changed
      if ($count > $longest) {
        $longest = $count;
      }
      $count = 1;
      $last  = $current;
    }
  }
  if ($count > $longest) { # last sequence is longest
    $longest = $count;
  }
  return $longest;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "textbook"
Output: 2

Example 2:
Input: $str = "aaaaa"
Output: 5

Example 3:
Input: $str = "hoorayyy"
Output: 3

Example 4:
Input: $str = "x"
Output: 1

Example 5:
Input: $str = "aabcccddeeffffghijjk"
Output: 4

Perl

The only difference between the Perl and Raku versions are on lines 6 and 9.

sub powerString($str) {
  my $longest = 0;
  my @chars   = split //, $str;
  my $last    = shift @chars;
  my $count   = 1;
  foreach my $current ( @chars ) {
    if ($current eq $last) { # same as last char
      $count++;
    }
    else { # character has changed
      if ($count > $longest) {
        $longest = $count;
      }
      $count = 1;
      $last  = $current;
    }
  }
  if ($count > $longest) { # last sequence is longest
    $longest = $count;
  }
  return $longest;
}

View the entire Perl script for this task on GitHub.

Python

The Python solution is shortest mostly because of the lack of block terminators. The Perl solution, without the } lines, would be the exact same length.

def power_string(mystr):
  longest = 0
  chars   = [ c for c in mystr ]
  last    = chars.pop(0)
  count   = 1
  for current in chars:
    if current == last: # same as last char
      count += 1
    else: # character has changed
      if count > longest:
        longest = count
      count = 1
      last  = current
  if count > longest:
    longest = count # last sequence is longest
  return longest

View the entire Python script for this task on GitHub.

Elixir

And though it may not look like it, this is the exact same algorithm. On line 21, hd(chars) handles pulling the first character off the array and tl(chars) passing rest of the array into the loop, which is implemented by the recursive power_string/4 function. Lines 11-12 increment count if the character is the same as the last one, and lines 14-15 update the longest variable if we’ve found a longer sequence, and then resetting count to 1 and last to current. Lines 4-5 are the condition when the last sequence is the longest one.

  def power_string([], _, count, longest) when count > longest,
    do: count # last sequence is longest
  def power_string([], _, _, longest),
    do: longest

  def power_string([current | chars], last, count, longest) do
    cond do
      current == last -> # same as last char
        power_string(chars, last, count+1, longest)
      true -> # character has changed
        longest = if count > longest, do: count, else: longest
        power_string(chars, current, 1, longest)
    end
  end

  def power_string(str) do
    chars = String.graphemes(str)
    power_string(tl(chars), hd(chars), 1, 0)
  end

View the entire Elixir script for this task on GitHub.

Task 2: Meeting Point

You are given instruction string made up of U (up), D (down), L (left) and R (right).

Write a script to return true if following the instruction, you meet (0,0) at any point along the sequence.

Example 1

Input: $path = "ULD"
Output: false

(-1,1) <- (0,1)
   |        ^
   v        |
(-1,0)    (0,0)

Example 2

Input: $path = "ULDR"
Output: true

 (-1,1) <- (0,1)
    |        ^
    v        |
 (-1,0) -> (0,0)

Example 3

Input: $path = "UUURRRDDD"
Output: false

(0,3) -> (1,3) -> (2,3) -> (3,3)
  ^                          |
  |                          v
(0,2)                      (3,2)
  ^                          |
  |                          v
(0,1)                      (3,1)
  ^                          |
  |                          v
(0,0)                      (3,0)

Example 4

Input: $path = "UURRRDDLLL"
Output: true

(0,2) -> (1,2) -> (2,2) -> (3,2)
  ^                          |
  |                          v
(0,1)                      (3,1)
  ^                          |
  |                          v
(0,0) <- (1,0) <- (1,1) <- (3,0)


Example 5
Input: $path = "RRUULLDDRRUU"
Output: true

(0,2) <- (1,2) <- (2,2)
  |                 ^
  v                 |
(0,1)             (2,1)
  |                 ^
  v                 |
(0,0) -> (1,0) -> (2,1)

Approach

Again, there may be a clever way to do this, but I’m just going to take the straightforward approach: maintain an $x and $y variable each initialized to 0, then when I encounter U $y++, when I encounter D $y--, when I encounter R $x++ and when I encounter L $x--. This is perfect for a case statement.

Raku

In Raku, that’s given / when. There’s also a standalone when that works mostly like an if, except that after executing the code specified by the when, all code to the end of the enclosing block is skipped (so it’s fortunate I don’t have any code I need to run between lines 13 and 14. If I did, I would have just used if.

sub meetingPoint($path) {
  my ($x, $y) = (0, 0);
  for $path.comb() -> $step {
    given $step {
      when "U" { $y++ }
      when "D" { $y-- }
      when "R" { $x++ }
      when "L" { $x-- }
    }
    return True when $x == 0 && $y == 0;
  }
  return False;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $path = "ULD"
Output: False

Example 2:
Input: $path = "ULDR"
Output: True

Example 3:
Input: $path = "UUURRRDDD"
Output: False

Example 4:
Input: $path = "UURRRDDLLL"
Output: True

Example 5:
Input: $path = "RRUULLDDRRUU"
Output: True

Perl

Perl doesn’t have a case statement, but there’s an old pattern that I think comes from the camel book (I’m away from home at the moment, so I can’t look that up) (I found something like it on perl.com) where you use a foreach statement with a single value and regex matches to look like a case statement:

foreach ($variable) {
  /val1/ && do {
    ...
    last;
  };
  /val2/ && do {
    ...
    last;
  };
  /val3/ && do {
    ...
    last;
  };
  do { # default
    ...
  };
}

Fortunately, I’ve already got a foreach statement in the code, so I can easily borrow elements from that pattern to accomplish what I need. I don’t need the last statements because I’m not looking to skip over everything until the end of the foreach block: the regex matches will ensure that only the operation for the current letter will be executed, and then at the end of the foreach, we want to run the test to see if we’re back a 0,0.

sub meetingPoint($path) {
  my ($x, $y) = (0, 0);
  foreach (split //, $path) {
    /U/ && do { $y++; };
    /D/ && do { $y--; };
    /R/ && do { $x++; };
    /L/ && do { $x--; };
    return 'true' if $x == 0 && $y == 0;
  }
  return 'false';
}

View the entire Perl script for this task on GitHub.

Python

In Python, what we want is match / case. Also, we can test x and y together by testing them as a tuple.

def meeting_point(path):
  x, y = 0, 0
  for step in path:
    match step:
      case "U": y += 1
      case "D": y -= 1
      case "R": x += 1
      case "L": x -= 1
    if (x, y) == (0, 0): return True
  return False

View the entire Python script for this task on GitHub.

Elixir

In Elixir, it’s a case statement. Note how on lines 13-16, I use a second case statement to test the tuple that I’m passing around of {x, y} to see if it matches {0, 0}; if it matches, I return true, if it doesn’t, I make the recursive call to process the next step (as usual, if I want to potentially bail out of a looping operation early in Elixir, I want to be using recursion to do my looping).

def meeting_point([], {_, _}), do: false

def meeting_point([step | path], {x, y}) do
  {x, y} = case step do
    "U" -> {x, y + 1}
    "D" -> {x, y - 1}
    "R" -> {x + 1, y}
    "L" -> {x - 1, y}
  end
  case {x, y} do
    {0, 0} -> true
    _ -> meeting_point(path, {x, y})
  end
end

def meeting_point(path) do
  meeting_point(String.graphemes(path), {0, 0})
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-349/packy-anderson

  1. Johnny’s Camaro, David Wilcox, 2018. ↩︎

Leave a Reply