Perl Weekly Challenge: Empty Substrings and Empty Spaces

Posted on by

Perl Weekly Challenge 372‘s tasks are “Rearrange Spaces” and “Largest Substring”.

The music connection is very train of thought and tenuous. This morning, my wife linked me a short of The Lakes Brass Quintet playing a polka arrangement of Empty Chairs at Empty Tables from Les Misérables. Yet in my head, I was repeating the incorrect lyric “empty chairs and empty spaces“. So now, when I think spaces, all I can think of is this.

You’re welcome.

Task 1: Rearrange Spaces

You are given a string text of words that are placed among number of spaces.

Write a script to rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximised. If you can’t distribute, place the extra spaces at the end. Finally return the string.

Example 1

Input: $str = "  challenge  "
Output: "challenge    "

We have 4 spaces and 1 word. So all spaces go to the end.

Example 2

Input: $str = "coding  is  fun"
Output: "coding  is  fun"

We have 4 spaces and 3 words (2 gaps). So 2 spaces per gap.

Example 3

Input: $str = "a b c  d"
Output: "a b c d "

We have 4 spaces and 4 words (3 gaps). So 1 space per gap and 1 remainder.

Example 4

Input: $str = "  team      pwc  "
Output: "team          pwc"

We have 10 spaces and 2 words (1 gap). So 10 spaces per gap.

Example 5

Input: $str = "   the  weekly  challenge  "
Output: "the    weekly    challenge "

We have 9 spaces and 3 words (2 gaps). So 4 spaces per gap and 1 remainder.

Approach

We’ve had problems before where we pull out space separated words, so the new twist here is we have to count up the whitespace and then distribute it evenly. Basically, once we have the count of whitespace ($s) and words ($w), if there’s more than one word, we do an integer division int($s/($w-1)) to determine how many spaces we put between words, and modulo division ($s % ($w-1)) to determine how many spaces go at the end.

Raku

I go back and forth between using .split(/\s+/, :skip-empty) and .comb(/\S+/) to extract words from strings.

sub rearrange($str) {
  my @words  = $str.comb(/\S+/);
  my $spaces = $str.comb(/\s/).elems;
  my $w = @words.elems - 1;
  if ($w == 0) {
    return @words[0] ~ (" " x $spaces);
  }
  else {
    my $between = $spaces div $w;
    my $end     = $spaces  %  $w;
    return @words.join(" " x $between) ~ (" " x $end);
  }
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: $str = "coding  is  fun"
Output: "coding  is  fun"

Example 3:
Input: $str = "a b c  d"
Output: "a b c d "

Example 4:
Input: $str = "  team      pwc  "
Output: "team          pwc"

Example 5:
Input: $str = "   the  weekly  challenge  "
Output: "the    weekly    challenge "

Perl

Originally, I wrote line 6 as 

  (my $spaces = $str) =~ s/\S+//g; $spaces = length($spaces);

because Perl regex substitutions return the number of substitutions, but then I remembered the /r option on Perl regex substitutions, which returns a copy of the string with the substitutions and leaves the original string unmodified.

sub rearrange($str) {
  my @words  = split " ", $str;
  my $spaces = length($str =~ s/\S+//gr);
  my $w = @words - 1;
  if ($w == 0) {
    return $words[0] . (" " x $spaces);
  }
  else {
    my $between = int($spaces / $w);
    my $end     =     $spaces % $w;
    return join(" " x $between, @words) . (" " x $end);
  }
}

View the entire Perl script for this task on GitHub.

Python

Here’s another example of my writing something and then discovering a better way to do it. Initially, I was going to write the div/mod like I did in Raku & Perl:

    between = spaces // w
    end     = spaces  % w

But as I was looking for the documentation for the // operator, I discovered there’s a single function that will do both for me: divmod.

import re

def rearrange(string):
  words  = string.split()
  spaces = len(re.sub(r'\S+', '', string))
  w = len(words) - 1
  if w == 0:
    return words[0] + (' ' * spaces)
  else:
    between, end = divmod(spaces, w)
    return (' ' * between).join(words) + (' ' * end)

View the entire Python script for this task on GitHub.

Elixir

And writing the Elixir solution last, I was affected by how I’d done it in Python, hence writing line 11 with a tuple instead of on two separate lines. Special call-outs to two functions I don’t use much, String.duplicate/2 and Kernel.then/2. I’m also using the & shorthand for anonymous functions.

def rearrange(str) do
  words  = str |> String.split(" ", trim: true)
  spaces = Regex.replace(~r/\S+/, str, "") |> String.length
  w = length(words) - 1
  if w == 0 do
    hd(words) <> String.duplicate(" ", spaces)
  else
    {between, final} = {div(spaces,w), rem(spaces, w)}
    words |> Enum.join(String.duplicate(" ", between))
          |> then(&(&1 <> String.duplicate(" ", final)))
  end
end

View the entire Elixir script for this task on GitHub.

Task 2: Largest Substring

You are given a string.

Write a script to return the length of the largest substring between two equal characters excluding the two characters. Return -1 if there is no such substring.

Example 1

Input: $str = "aaaaa"
Output: 3

For character "a", we have substring "aaa".

Example 2

Input: $str = "abcdeba"
Output: 5

For character "a", we have substring "bcdeb".

Example 3

Input: $str = "abbc"
Output: 0

For character "b", we have substring "".

Example 4

Input: $str = "abcaacbc"
Output: 4

For character "a", we have substring "bca".
For character "b", we have substring "caac".
For character "c", we have substring "aacb".

Example 5

Input: $str = "laptop"
Output: 2

For character "p", we have substring "to".

Approach

The problem definition says we should return -1 if there’s no substring, but example 3 shows returning 0. I’m going to do this, because it means I don’t have to treat no substring as a special case.

This feels like we want to use a regex, but I need to be careful… more in my Raku description.

Raku

First I tried testing my regex in Raku’s REPL:

$ raku
Welcome to Rakudo™ Star v2025.11.
Implementing the Raku® Programming Language v6.d.
Built on MoarVM version 2025.11.

To exit type 'exit' or '^D'
[0] > for ["aaaaa", "abcdeba", "abbc", "abcaacbc", "laptop"] -> $str {
* say $str ~~ /(.) {} :my $c = $0; (.*) ($c)/;
* }
｢aaaaa｣
 0 => ｢a｣
 1 => ｢aaa｣
 2 => ｢a｣
｢abcdeba｣
 0 => ｢a｣
 1 => ｢bcdeb｣
 2 => ｢a｣
｢bb｣
 0 => ｢b｣
 1 => ｢｣
 2 => ｢b｣
｢abcaa｣
 0 => ｢a｣
 1 => ｢bca｣
 2 => ｢a｣
｢ptop｣
 0 => ｢p｣
 1 => ｢to｣
 2 => ｢p｣
[0] >

I pulled the regex with the capture available within the regex pretty much directly from the Raku documentation. But notice: the fourth example only matches the 3-character match, not either of the four character matches. That’s when I realized I didn’t want to rely on the regex to identify the two equal characters, since it would just pick the first it found, not the one yielding the largest substring. But there was something I could use to identify all the characters that could bracket any such substrings: a Bag.

[0] > for ["aaaaa", "abcdeba", "abbc", "abcaacbc", "laptop"] -> $str {
* say "STR: $str";
* for $str.comb.Bag.pairs.grep({ .value > 1 }).map({ .key }) -> $c {
* print "  $c: ";
* say $str ~~ /$c (.*) $c/;
* } }
STR: aaaaa
  a: ｢aaaaa｣
 0 => ｢aaa｣
STR: abcdeba
  a: ｢abcdeba｣
 0 => ｢bcdeb｣
  b: ｢bcdeb｣
 0 => ｢cde｣
STR: abbc
  b: ｢bb｣
 0 => ｢｣
STR: abcaacbc
  a: ｢abcaa｣
 0 => ｢bca｣
  b: ｢bcaacb｣
 0 => ｢caac｣
  c: ｢caacbc｣
 0 => ｢aacb｣
STR: laptop
  p: ｢ptop｣
 0 => ｢to｣
[0] >

All I have to do is loop over the keys of the bag and keep track of which one, when used in the regex, matches the largest substring.

sub largest($str) {
  my $max = 0;
  my @explain;
  my @chars = $str.comb.Bag.pairs
            .grep({ .value > 1 }) # filter out single chars
            .map({ .key });       # return just the chars
  for @chars -> $c {
    $str ~~ /$c (.*) $c/;
    $max = max($max, $0.chars);
    @explain.push(
      qq[For character "$c", we have substring "$0".]
    );
  }
  $max ~ "\n\n" ~ @explain.join("\n")
}

View the entire Raku script for this task on GitHub.

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

For character "a", we have substring "aaa".

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

For character "a", we have substring "bcdeb".
For character "b", we have substring "cde".

Example 3:
Input: $str = "abbc"
Output: 0

For character "b", we have substring "".

Example 4:
Input: $str = "abcaacbc"
Output: 4

For character "a", we have substring "bca".
For character "c", we have substring "aacb".
For character "b", we have substring "caac".

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

For character "p", we have substring "to".

Perl

Rather than filtering the hash in the statement on line 9, I figured it was easier to just loop over the key/value pairs and immediately next if the value wasn’t greater than 1.

use List::AllUtils  qw( max );
use List::MoreUtils qw( frequency );

sub largest($str) {
  my $max = 0;
  my @explain;
  my %chars = frequency split //, $str;
  foreach my ($c, $f) ( %chars ) {
    next unless $f > 1; # filter out single chars
    $str =~ /$c (.*) $c/x;
    $max = max($max, length($1));
    push @explain,
      qq[For character "$c", we have substring "$1".];
  }
  $max . "\n\n" . join("\n", @explain)
}

View the entire Perl script for this task on GitHub.

Python

As usual, I mistakenly used re.match on line 12 instead of re.search, and I wondered for a minute or two why my script was breaking on the second example, where I was trying to match a pattern that didn’t start at the beginning of the string.

from collections import Counter
import re

def largest(string):
  maxval = 0
  explain = []
  for c,v in Counter([ c for c in string ]).items():
    if v <= 1: continue # filter out single chars
    pattern = re.compile(f'{c}(.*){c}')
    m = pattern.search(string)
    maxval = max(maxval, len(m[1]))
    explain.append(
      f'For character "{c}", we have substring "{m[1]}".'
    )
  return str(maxval) + "\n\n" + "\n".join(explain)

View the entire Python script for this task on GitHub.

Elixir

For the Elixir solution, I learned about a function that was new to me: Enum.reject/2, which is to Enum.filter/2 in Elixir what unless is to if in Raku/Perl; instead of returning a list of elements where the function returns true, it returns a list of elements where the function returns false, thus rejecting the elements it’s true for.

The hd(tl(x)) construction returns the second element in the list. Since Regex.run/3 returns a list of the matched string followed by any captures, the captured substring would be the second element of that list.

def largest(str) do
  {explain, max} = str
  |> String.codepoints |> Enum.frequencies
  |> Enum.reject(fn {_, v} -> v <= 1 end) # filter out single chars
  |> Enum.reduce({[], 0}, fn {c, _}, {explain, max} ->
    pattern = Regex.compile!("#{c}(.*)#{c}")
    substr = hd(tl(Regex.run(pattern, str)))
    {
      explain ++ [ "For character \"#{c}\", " <>
                   "we have substring \"#{substr}\"." ],
      Enum.max([max, String.length(substr)])
    }
  end)
  "#{max}\n\n" <> Enum.join(explain, "\n")
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/challenge-372-packy-anderson/challenge-372/packy-anderson

Leave a Reply