The Bear's Den

Enter at your own risk

11 April 2025 Challenge 316

Regular Sequences

Task 1: Circular

Submitted by: Mohammad Sajid Anwar

You are given a list of words.

Write a script to find out whether the last character of each word is the first character of the following word.

Example 1

Input: @list = ("perl", "loves", "scala")
Output: true

Example 2

Input: @list = ("love", "the", "programming")
Output: false

Example 3

Input: @list = ("java", "awk", "kotlin", "node.js")
Output: true

Solution

Though the task description from task 1 in week 314 is quite different from this task, there is a very similar solution.

Quoting my post for challenge 314, the solution to this task…

…may be found with a single regex. To this end we join the strings with a character not contained in any of the strings. For simplicity this will be the newline character "\n" in the following, which will not be matched by the dot metacharacter.

The last character of a word may be captured with .*+(?<=(.)). The the beginning of following word starting with this captured character will be matched with \n(?=\1). A complete word chain is then matched by /^(?:.*+(?<=(.))\n(?=\1))*+.*+$/.

The usage of “possessive” quantifiers suppresses backtracking in case of a failing match.

use strict;
use warnings;

sub circular {
    join("\n", @_) =~ /^(?:.*+(?<=(.))\n(?=\1))*+.*+$/;
}

See the full solution to task 1.

Task 2: Subsequence

Submitted by: Mohammad Sajid Anwar

You are given two string.

Write a script to find out if one string is a subsequence of another.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

Example 1

Input: $str1 = "uvw", $str2 = "bcudvew"
Output: true

Example 2

Input: $str1 = "aec", $str2 = "abcde"
Output: false

Example 3

Input: $str1 = "sip", $str2 = "javascript"
Output: true

Solution

Each character in $str1 will be quoted if it represents a regex meta-character and may be followed by zero or more other characters. $str2 is then matched against the result of the first step.

use strict;
use warnings;
use experimental 'signatures';

sub subsequence ($str1, $str2) {
    $str2 =~ ($str1 =~ s/./\Q$&\E.*/gr);
}

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.