Bob Lied

Posted on Feb 26

PWC 362 Echo Chamber

#perl #pwc #perlweeklychallenge

The musical accompaniment must obviously be Pink Floyd's Echoes.

The Task

You are given a string containing lowercase letters.

Write a script to transform the string based on the index position of each character (starting from 0). For each character at position i, repeat it i + 1 times.

Example 1
- Input: "abca"
- Output: "abbcccaaaa"
Index 0: "a" -> repeated 1 time -> "a"
Index 1: "b" -> repeated 2 times -> "bb"
Index 2: "c" -> repeated 3 times -> "ccc"
Index 3: "a" -> repeated 4 times -> "aaaa"

The Thoughts, Both Profound and Superficial

A string transformation problem, an ideal domain for Perl. There are at least three approaches I can see.

Treat it as a regular expression problem, substituting each character for n copies of itself. It wouldn't be Perl if at least one of the more-than-one-way-do-its didn't have more punctuation than letters.
Treat it as a list problem. Separate the string into a list of characters and map each list element into n copies of itself.
Treat it as a string generation problem. Build a new string out of bits of the original.

In any case, the linchpin is going to be the repetition operator, x.

The Solutions

A Regular Expression Substition

sub echoRE($str)
{
    use English;
    return $str =~ s/(.)/$1 x $LAST_MATCH_END[1]/ger;
}

Several features of Perl regular expressions come into play.

We need to do some math in the substitution to replicate the characters. To put executable code into the substitution, we use the /e flag.
We need the index of the character we're replacing. Perl regular expressions have many useful side effects that are available in special variables. When using a capture group, the indexes of the beginning and end of the matching text are available in the @- and @+ special array variables.
The default result of a s///g global substitution is the number of replacements made, which can be useful in some contexts, but not this one. The /r flag changes the behavior so that it results in the modified string instead.
I'm conceding a tiny bit to readability. use English lets me use $LAST_MATCH_END in place of $+.

Here's the breakdown of willing the regular expression into existence:

s///gr -- It's going to be a global substituion (every character), and we want the result.
s/(.)//gr -- Capture every character, no matter what it is.
s/(.)/$1 x .../gre -- Replicate the captured character the appropriate number of times. Add the e flag to execute this expression.
s/(.)/$1 x $+[1]/gre -- After a visit to the Perl references (just to spite AI, I used an actual book of genuine paper), we find that the offset of the captured character is in the @- and @+ special variables. Using @+ (end of the match) instead of @- takes care of the index+1 annoyance.
As evidenced by the step above, I can't remember the special variables, so I add use English to get the name LAST_MATCH_END.

A List Solution

sub echoMap($str)
{
    return join "", map { substr($str, $_-1, 1) x $_} 1 .. length($str)
}

This solution turns each character into a longer string of repeated characters. It maps indexes into a corresponding string of the correct length.

A String-building solution

sub echoStr($str)
{
    my $result = "";
    for my ($i, $c) ( indexed split(//, $str) )
    {
        $result .= ($c x ($i+1));
    }
    return $result;
}

A variation on the list processing, this one builds a string with repeated concatenation. Instead of building a list with map and then join-ing it into a result, this one goes straight to the string.

split gives me the individual characters as a list. It's more efficient than repeated calls to substr.

Since we need both the character and its index, I relied on my favorite variation of the for loop using indexed to conveniently give me variable names.

The Comparison

As always, I'm curious about the relative efficiency of the solutions. Here's a benchmark result:

           Rate    regex  mapjoin splitstr
regex    2365/s       --     -43%     -57%
mapjoin  4118/s      74%       --     -25%
splitstr 5469/s     131%      33%       --

I'm a little surprised that regular expressions didn't fare better. I hypothesize that the addition of executable code in the substitution is a significant cost.

I'm not surprised that string building won. Iterating over lists and manipulating strings are a core strength of Perl, and those operations have no doubt been optimized to heck over the decades.

DEV Community