My Lava Lamp Pulsates in Harmony with the String Section

Wherein we measure our shared traits and, absorbing the commonalities with our neighbors, grow our communities ever larger, with togetherness striving towards oneness.

THE WEEKLY CHALLENGE – PERL & RAKU #92

---

episode one:
“Sympathetic Vibrations”

---

Task 1

Isomorphic Strings

Submitted by: Mohammad S Anwar

You are given two strings $A and $B.

Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.

Example 1:

Input: $A = "abc"; $B = "xyz"
Output: 1

Example 2:

Input: $A = "abb"; $B = "xyy"
Output: 1

Example 3:

Input: $A = "sum"; $B = "add"
Output: 0

Method

From the link provided: “Two strings are isomorphic if one-to-one mapping is possible for every character of the first string to every character of the second string.” The site then provides an example of isomorphism, with the two strings “ACAB” and “XCXY”.

Being acutely aware, at this point, of how the ambiguities arising from written speech can confound seemingly innoculous definitions, I immediately set to consider exactly what was being asked of us.

Specifically, what do we mean by a “one-to-one” mapping?

Generally, this means there exists a function that for every character in string A, outputs one and only one character from string B. Such a function is known as an injective function.

But there is a second qualifier buried in the wording: “every character of the second string”. We will take this to mean that there are no characters in string B that are not mapped to by some character in string A. Such a function is called “surjective”.

The two terms are not exclusive: a function that is both injective and surjective is known as “bijective”. This is what is being referred to; the relationship is also known as “one-to-one onto”.

Or so it seems. Although not stated, the positions of the characters within the strings are important to the correspondence. For example, what of the two strings “abb” and “yyx”? If “a” maps to “x” and “b” maps to “y” these would seems to fit the definition. A little sleuthing suggests it does not, however, and so the definition should be amended to “if at each position in the first string a bijective mapping can be made to the character in the corresponding position in the second string”. That seems to cover it.

The terms “injection”, “surjection” and “bijection” apply to sets, and the difference is that we are addressing ordered sets here. The language can still be used, but requires qualification. Now we’re almost done, but not quite.

When we speak of a function that maps A → B, what of B → A? Is it the same function? It is the same hash? A bijective function is known as “invertable”, that is the one-to-one correspondence goes both ways, but the function inverted is not likely to be the same mapping, except in trivial cases such

∀ x : f(x) = x

The inverted function will be related, but the output of the first function, when fed to the second, will return the original input from the first. If we were to give the original input to the second function, the output would not be immediately predictable. So we will need to keep track of the second function, the inverse, as well.

So with definitions out of the way, how do we do this?

PERL 5 SOLUTION

We need to walk the first string position by position. At a given index, if the character has not been seen yet, we will need to add it to a hash that points to the the corresponding letter in string B. If that letter has already been seen in that string, then it has already been allocated to another and this love affair is over. If the letter in the first string has been seen, then the mapping is validated to be pointing to the same letter that it was before. If not, again we fail. To do either of these steps we will require the characters in the second string to become keys in a second hash, so that we can check for their existence.

Working across, we assume success unless we fail by one of the two methods. If we get to the end, then we’re good to go: the required mapping exists and the two strings are isometric.

We don’t even need to store the values for the invert function hash — we won’t need to actually use the function. The logic demands that to establish a new key-value pair for the forward mapping both values need to be heretofore unseen, so a simple check for existence of the invert hash key is all we need from it. This is akin to determining existence in a set, the set of already allocated characters.

use warnings;
use strict;
use feature ":5.26";

sub check_iso {
    my ($str_A, $str_B) = @_;
    return 0 if length $str_A != length $str_B;

    my (%forward, %invert);
    for (0..length $str_A) {
        my $char_A = substr $str_A, $_, 1;
        my $char_B = substr $str_B, $_, 1;

        ## key already in invert
        return 0 if exists $invert{$char_B} and not exists $forward{$char_A};

        ## key in forward matches char B
        if (exists $forward{$char_A} ) {
            return 0 if $forward{$char_A} ne $char_B;
        }
        else {             ## make new key
            $forward{$char_A} = $char_B;
            $invert{$char_B}  = undef;
        }
    }
    return 1;
}

raku solution

In Raku we can use a SetHash type, which allows us to use set operators, like ∈, element of. It’s cool to do programming with proper math symbols, if a bit awkward to input. I like it.

unit sub MAIN (Str $A = 'xxy', Str $B = 'aab') ;

say 0 and exit if $A.chars != $B.chars;

my %forward;
my %invert = SetHash.new;

for 0..$A.chars {
    my $ch-A = $A.substr($_,1);
    my $ch-B = $B.substr($_,1);

    say 0 and exit if $ch-B ∈ %invert and not %forward{$ch-A}:exists;

    if %forward{$ch-A}:exists {
        say 0 and exit if %forward{$ch-A} ne $ch-B;
    }
    else {
        %forward{$ch-A} = $ch-B;
        %invert{$ch-B} = Nil;
    }
}

say 1;

---

episode two:
“Turn On Your Love Light”

---

task 2

Insert Interval

Submitted by: Mohammad S Anwar

You are given a set of sorted non-overlapping intervals and a new interval.

Write a script to merge the new interval to the given set of intervals.

Example 1:

Input $S = (1,4), (8,10); $N = (2,6)
Output: (1,6), (8,10)

Example 2:

Input $S = (1,2), (3,7), (8,10); $N = (5,8)
Output: (1,2), (3,10)

Example 3:

Input $S = (1,5), (7,9); $N = (10,11)
Output: (1,5), (7,9), (10,11)

Method

This task requires us to abstract a sequence of intervals along a one-dimensional line, each distinguished by a start point and an end. Numbers between those marks, inclusive, are considered to be inside the interval, those outside, not. Furthermore, there’s no reason for the numbers to be whole; if a number is greater than or equal to the lower boundary and less than or equal to the upper we’re in, both literally and figuratively. We’ll stick to integers for our examples, but there’s nothing preventing any other real values.

To start we will need a way to abstract our intervals. A 2-tuple array should do the trick. The tuples can then be assembled into a list, as they would be represented on a line.

We start knowing that the intervals do not intersect, and are properly sorted . This is quite helpful in that once we insert our interval correctly into the list, we will only need to resolve the perturbations of this one action, although those may cascade. On insertion, either the interloper will fall before an overlapping interval or after, so if we can figure that out when it goes in we can focus our attention on the right spot. Or alternately there is no overlap at all, a case we must consider as well.

PERL 5 SOLUTION

The task can be broken up into two parts: inserting the interval and resolving any overlaps created.

Inserting is straightforward. All we need to do is iterate through the list of our tuples, comparing in each the first value, the lower bound, against that in our new set. Moving along the list, keeping track of the index as we go, we increment by one until the following element has a higher lower bound than the one going in, and then use splice to do the insertion. This way the newcomer is placed before an element with an equal value, which matters toward the bookkeeping for the next step.

To perform the merging operation, we need to know the indexes of the intervals merged from and to. We know one index will follow the other, but whether the gatecrasher is inserted before the overlap or after remains undetermined. Proper ordering of the lower bounds is essential, but an overlap is created between the upper and lower bounds of two adjacent intervals. So knowing the index where we insert the new tuple, we need to compare the upper bound of the interval before, and, if it is greater or equal, set the index to start merging one less than the index we did the insertion at. We’ll need to retain this number for the next step, the merging itself.

When given an index to start merging, we first need a conditional to determine whether there is in fact an overlap that need to be resolved. We need this because it’s quite possible that our newcomer sits neatly between elements in the old line, requiring no action. When two intervals are determined to overlap, though, we merge the following element into the previous. We know that the lower bound of the first is less than or equal to that of the second, so that value will remain unchanged. The upper bound of the first interval is then set to the greater of the two upper values amongst the two. Once this is done the second interval is spliced out and removed from the list. After the merging process, the list above the index shifts one position downward, and the index for merging remains the same.

Because we don’t know anything about the relationship the upper bound of our newly spliced insert to the values of the rest of the list, we need to repeat the conditional and decide again whether to merge. The new following interval is compared and merged if necessary. Theoretically the upper bound of the merged interval may be beyond that of every element in the list, absorbing them all. We need to continue until the upper bound of the current interval is less than the lower of the next interval – only then can we can stop.

Or it it’s the last interval, we should also stop then, lest we loop forever.

The whole process is quite efficient. We only need to traverse the list once, and then only up to the point where we insert the new interval. Once there, we use that value to determine the merge point, and then loop until the overlap is resolved, after which there is no need to continue the traversal further. We have successfully patched the anomaly in-place. splice may incur a certain penalty for a very long list, but that will be Perl recopying part of the underlying C-array down in the guts, rather than us iterating through things up on top.

================================================================================
Dec 25, 2020 at 3:07:37 AM
~/Code/PWC/92_2_lava_lamp.pl
--------------------------------------------------------------------------------

input:  (1,4) (8,10)
new:    (2,6)
merged: (1,6) (8,10)
ok 1 - ex 1

input:  (1,2) (3,7) (8,10)
new:    (5,8)
merged: (1,2) (3,10)
ok 2 - ex 2

input:  (1,5) (7,9)
new:    (10,11)
merged: (1,5) (7,9) (10,11)
ok 3 - ex 3

---

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:


sub main {
    my ($S, $N) = @_;
    say '';

    say "input:  ", sprint_intervals( $S );
    say "new:    ", sprint_intervals( [$N] );

    my $idx = insert_and_find_merge($S, $N);

    while (1) {
        if (defined $S->[$idx+1] and $S->[$idx][1] >= $S->[$idx+1][0]) {
            merge($S, $idx);
        }
        last if $idx == $S->@* - 1;
        last if $S->[$idx][1] < $S->[$idx+1][0];
    }

    say "merged: ", sprint_intervals( $S );

    return sprint_intervals( $S );   ## for testing purposes
}

sub insert_and_find_merge {
## insert new interval into interval list
## return index of interval to merge with next
## this will either be the insert point or one before
    my ($list, $new) = @_;
    my $idx = 0;
    my $merge;
    while ($idx < $list->@*) {
        last if $list->[$idx][0] >= $new->[0];
        $idx++;
    }
    splice $list->@*, $idx, 0, $new;

    return 0 if $idx == 0;
    return $idx-1 if $list->[$idx-1][1] >= $new->[0];
    return $idx;
}

sub merge {
## given list ref and index, merges index and index + 1
    my ($list, $idx) = @_;
    $list->[$idx][1] = $list->[$idx][1] > $list->[$idx+1][1] ? $list->[$idx][1]
                                                             : $list->[$idx+1][1];
    splice $list->@*, $idx+1, 1;
}

sub sprint_intervals {
## return formatted string
    my $list = shift;
    return  (join ' ', map { "($_->[0],$_->[1])" } $list->@*) ;
}