Perl Weekly Challenge 92, Part 1

Isomorphic Strings

Part 1 of this weeks challenge reads:

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.

Algorithm Overview

If we define a relation which maps the nth character of the string $A to nth character of $B, we need to determine whether is a bijection. For that to happen, the following things need to be true:

1. Both and its inverse, are total.
2. .

We can split the latter condition into two:

1. (this ensures that the same character is mapped to the same value).
2. , where is the domain of , and is the image of . This means that we have as many different characters that are mapped as we have different characters mapped onto.

Checking that and are total is checked by testing that the length of $A and the length of $B are equal.

Checking that the we map the same character to the same value, we can check by iterating over the characters of $A remembering which value they are mapped to, and returning 0 if we find a case where it is mapped to a different value.

Checking that the domain and image are of the same size we can do by taking the mapping we created above, reversing it, and checking we have the same number of keys.

Solution

Perl

sub solve;
my @lines = <>;
say $_ ? 1 : 0 for map {solve @lines [$_ - 1, $_]} grep {$_ % 2} keys @lines;
exit;

This reads all the input into an array @array, then for each pair of lines (containing $A and $B), we call the subroutine solve which returns true if the strings are isomorphic, and false otherwise.

sub solve ($A, $B) {
    return 0 unless length ($A) == length ($B);      # 1)
    my @A = split // => $A;
    my @B = split // => $B;
    my %mapping;
    foreach my $i (keys @A) {
        my $A = $A [$i];
        my $B = $B [$i];
        return 0 if $B ne ($mapping {$A} //= $B);    # 2)
    }
    my %reverse = reverse %mapping;
    keys %reverse == keys %mapping;                  # 3)
}

We first check whether both functions are total by checking the lengths of the strings — if unequal 0 is returned (# 1)).

We then split the strings into individual characters, and iterate over the resulting arrays. We track in a hash (%mapping) which character maps to which other character — if a character is mapped to more one character, we return false (# 2)).

Finally, we check the domain and image have the same size, returning true if they are, and false otherwise. (# 3)).

Find the full program on GitHub.