Second to None

Wherein we run a race. Not just to be first, but to be out there all alone doing it.

THE WEEKLY CHALLENGE – PERL & RAKU #180 Task 1

---

“We live as we dream — alone. While the dream disappears, the life continues painfully.”

— Joseph Conrad, Heart of Darkness

---

First Unique Character

Submitted by: Mohammad S Anwar

You are given a string, $s.

Write a script to find out the first unique character in the given string and print its index (0-based).

Example 1

Input: $s = "Perl Weekly Challenge"
Output: 0 as 'P' is the first unique character

Example 2

Input: $s = "Long Live Perl"
Output: 1 as 'o' is the first unique character

ANALYSIS

We have another multipart task this week, requiring a combination of separate actions to achieve the goal. I find these hybrid operations interesting, as the focus ultimately falls on the synthesis between the parts, rather than any singular bold insight.

I often say nothing in life is only one thing. The unique attributes of originality rise not from the individual components, but from the particular way the parts are put together. Call it a metaphor for the human condition if you want — you wouldn’t be wrong — but I think a better explanation is found in the way we process complex situations, isolating aspects individually as though they are separate things.

So, in the context of this challenge we need two things: a set of unique characters and a mapping to find where the first instance of each character lies. We then can combine these pieces of information to find the first instance of any unique character.

Neither of the two requirements on its own is particularly difficult to implement. It would be straightforward to iterate across the characters in the string and count the number of instances of each, and when we get to the end of the line those characters with a frequency of only 1 will compose the unique set. We could then look at each candidate and log its first position — the closest to the front wins.

That however would be tedious, and require multiple passes into the string to come to a conclusion. In every case to satisfy the uniqueness quality we will need to examine every character at least once. Can we gather the data we need in that single pass, at least?

Sure. We just need to record the right data when we make it.

There are only so many characters available. Twenty-six letters in the English alphabvet, 127 in ASCII, 256 if we extend the range into 1-byte characters. How many Unicode characters are there now? 15,000? Anyways a lot, but not that many in the great scheme of things. We’re counting character varieties not protons.

METHOD

We’ll use substr to examine each character in turn. We could store everything in a single deep data structure, but as we’ve noted a hash with every character as a key would never be extraordinarily large. And hash lookups are effectively constant anyway, with no regard to scaling. Big, little — the hashes don’t care. And as a basic data type in Perl they are quite quick at doing what they do.

So for clarity instead of something more complex we will just build two hashes. In on the first, we identify whether a character is unique. In the second, we store the position of the first instance of each value.

When examining a candidate character, we first look to find a key in the first, %common hash. If it’s found there we immediately discard the candidate and move on. We don’t care a whit how common a character is, only whether it’s unique or it isn’t.

If it is not found in the %common lookup, we then we turn to the second hash. We’ll call this hash %position, for recording the index of each character’s first occurrence. If the character already exists as a key here, then it’s not unique, and in fact it’s common. We make a new key in the %common hash, delete the entry in the %position hash and move on. On the other hand if we don’t already find it there then the character is, at that moment, still considered unique. We add its position to the %position hash under a new key. You can see now that the %position hash is constantly updated to only contain unique characters.

When we reach the end of the line we’ve gathered everything we need to know. The %position hash contains only unique keys mapped to similarly unique positions — as of course no two characters can hold the same index in a string. To find the smallest position, instead of laboriously sorting the keys by value we can instead just reverse the hash. After all, we know the index positions in the values are unique, so reversed they will make unique keys.

Sorting the keys of this reversed hash yields the smallest numeric position, which can then be looked up to find the character at that location.

PERL 5 SOLUTION

I should note that reversing the hash as the the end is not really necessary. It’s a lot of lookups to perform a sort on the values, but it’s also work to flatten the hash, reverse it and then rebuild it. I do find it conceptually cleaner this way, or maybe I’ve just being clever. Alternately, when explicitly sorting by value:

my ($result) = sort { $position{$a} <=> $position{$b} } keys %position;

we can extract the correct key in one line, which is nice. As they say, there’s more than one way to do it.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';



my $str = shift // 'prophylaxis';

my %common;
my %position;
my $pos = 0;

## pass over string and record data
while ($pos < length $str) {
    my $char = substr $str, $pos++, 1;
    next if $common{$char};
    if ($position{$char}) {
        $common{$char} = 1;
        delete $position{$char};
        next;
    }
    $position{$char} = $pos;
}
%position = reverse %position;  ## magic of a sort

## output value from smallest position, now a key
say $position{ (sort {$a<=>$b} keys %position )[0] };