What An Unusual String You Have There! Or Are You Just Glad To Meet Me?

Wherein we learn the way of the third wheel…

THE WEEKLY CHALLENGE – PERL & RAKU #193 Task 2

---

“One of the odd enjoyments in life is to be alone in a room full of people. To have them there as unknowing human filler in your wide shot.”

— Henry Rollins

---

Odd String

Submitted by: Mohammad S Anwar

You are given a list of strings of same length, @s.

Write a script to find the odd string in the given list. Use positional value of alphabet starting with 0, i.e. a = 0, b = 1, ... z = 25.

Find the difference array for each string as shown in the example. Then pick the odd one out.

Example 1:

Input: @s = ("adc", "wzy", "abc")
Output: "abc"

Difference array for "adc" => [ d - a, c - d ]
                           => [ 3 - 0, 2 - 3 ]
                           => [ 3, -1 ]

Difference array for "wzy" => [ z - w, y - z ]
                           => [ 25 - 22, 24 - 25 ]
                           => [ 3, -1 ]

Difference array for "abc" => [ b - a, c - b ]
                           => [ 1 - 0, 2 - 1 ]
                           => [ 1, 1 ]

The difference array for "abc" is the odd one.

Example 2:

Input: @s = ("aaa", "bob", "ccc", "ddd")
Output: "bob"

Difference array for "aaa" => [ a - a, a - a ]
                           => [ 0 - 0, 0 - 0 ]
                           => [ 0, 0 ]

Difference array for "bob" => [ o - b, b - o ]
                           => [ 14 - 1, 1 - 14 ]
                           => [ 13, -13 ]

Difference array for "ccc" => [ c - c, c - c ]
                           => [ 2 - 2, 2 - 2 ]
                           => [ 0, 0 ]

Difference array for "ddd" => [ d - d, d - d ]
                           => [ 3 - 3, 3 - 3 ]
                           => [ 0, 0 ]

The difference array for "bob" is the odd one.

ANALYSIS

There are three distinct parts of this puzzle. In order of appearance, firstly we have an two-part encoding scheme, where we take a string as an array of characters, and then convert the letters to a numeric equivalent using a fixed mapping.

In the second phase we take one of these encoded arrays and calculate what is known as a “difference array”, where we note the net change between successive elements, using the numeric encoding we came up with previously.

Lastly we need a way to compare and categorize these difference arrays corresponding to the input strings and find “the odd one out”. Exactly what this last determination means is left without further definition.

We will note, though, that being the odd element out is generally in reference to not being part of any group. It’s my understanding this definition is based in ancient belief systems.

The idea of oddness is very old, going back to Pythagorian mystic mathemeticians, who decided numbers divisible by two were good, and those not were bad. Parity was born. In any collection of items, each element in the set can be paired (good) with another (also good). However with an odd number of elements in the set, one item will be left over (bad). This, then, the unpairable one, would be the odd item. Alone in the world, it is caught driftless, without a moral compass, unable to couple, mate or create more items.

I believe that is the crux of the matter.

Also, apparently the Pythagorean mystics were unaware of parthenogenetic mitosis. I suppose that is to be expected.

Before continuing I will mention that most of what I just wrote is highly speculative as to the origins of even numbers being good and odd bad, a topic I have written about before with varying degrees of seriousness. I find the subject very interesting, albeit odd. See what I did there? The English word “odd” comes from the Old Norse oddi, which curiously refers a triangular point of land, and from that generally a reference to pointy things, and then suddenly a leap to that part in excess of a sum. This in turn was extended to such constructions as “odda-maðr”, meaning the third man in the context of casting a tiebreaker vote. This last semantic twist is singularly limited amongst its similar Germanic variants to only Old Norse, which is in itself interesting.

Germanic traditions had a lot of practical democracy in their communities, relatively speaking, in the management of the social balance. Tacitus describes folk assemblies amongst the tribes in his account Germania from 98 CE, and the Althing legal meeting-ground assembly of Iceland was formed in 930 CE. So the creation of a unique term supporting the action of voting is not in this context surprising.

I think it stands to reason you will find similar patterns surrounding the concept of oddness evolving spontaneously back with the creation of numbers themselves, as a natural extension of grouping objects, and original time-frame for that origin of that meaning to be lost in prehistory.

Ancient numero-analytical mysticism aside, however, we do have a real, immediate problem in front of us now, with the vagaries in the specifics of this concept of displaced oddness. We will need to address that. The numerological rabbit-hole will be there waiting for us later.

I think the eseential quality here is not a number’s not-evenness but rather the ungrouped aspect. It thus doesn’t matter what the makeup is of any larger groupings our candidate is not a part of — these need not be only pairings but may be of any size greater than one. The only criterium is that within the set of all such objects the one under inspection remains unique.

Another question is what if there is more than one unique element? Yea, well… who knows? Seriously, there is no explicit statement that there can and will be only one. We have only the inference we can gather from the tense of the text to “pick the odd one out”. Not, honestly, a lot to go on, rigorously speaking.

In fact, choosing random equal length words as input would be more suited to a task of actually finding words with equal difference sets than locating a single odd one out. Random difference sets would statistically be predominantly different by a wide margin. We will have to assume then that the input comes structured in a specific way, but that said we have no idea where these lists come from.

The last part of the puzzle needed to finish the challenge is a method of performing a deep numeric analysis of arrays to test for equality, disallowing any multiples found from further consideration. In short, we need some sort of a unique filter for arrays, only allowing things through that there are only one of. Limiting the values to integers as we have done will make this a little easier, but obviously a simple test for equality won’t just work. The arrays will need to be processed in some manner to be compared.

METHOD

Breaking the task down as we have done will require three routines and some sort of framework to call them.

The initial encoding is pretty straightforward, and possibly could be rolled up inline with the later processing, but for clarity we will keep it separate for now. This whole process is in danger of becoming compliated enough already without making the code unnecessarily dense.

Likewise the function for creating an array of deltas from and encoded array will get its own subroutine.

As we’re looking for strings without matching difference arrays, these relationships are linked within a hash table. We can then iterate through the pairs and count the frequencies of the various difference arrays by constructing a unique stringified key from the data. This is accomplished by separating the integers with a non-numeric character — we will select a colon for the job. At the same time we’ll construct another lookup hash using these stringified difference keys to point back around to their original string antecedents.

“But wait!” You might say. “Those stringified keys aren’t unique! You’ll overwrite the strings! Won’t anyone think of the children!”

Sure, sure, but calm down. Geez. This is a very good point. “The thing is” we respond: “We don’t care.”

As we know, any overwritten values will never be used anyway as they will refer to non-unique differences. So please settle down. Everything is going to be all right.

A consequence of doing things this way is it becomes straightforward to allow for multiple unique strings. So we’re going to do that, with the results returned as an array.

PERL 5 SOLUTION

my @s = @ARGV;
@s == 0 and @s = ("aaa", "bob", "ccc", "ddd", 'ray');

say for odd_man_out( @s );


sub odd_man_out ( @strings ) {
## a procedural wrapper for find_unique_strings(), setting up the correct input
    my %input_hash;
    $input_hash{$_} = difference_array( encode($_) ) for @strings;
    
    return find_unique_strings( %input_hash );
}

sub find_unique_strings( %string_hash ) {
## given a hash of strings to their difference arrays, 
## finds all strings with a difference map frequency of 1 and returns them
    my %freq;
    my %rev_lookup;     ## %freq keys to original strings
    while ( my ($str, $arr) = each %string_hash ) {
        my $key = join ':', $arr->@*;
        $freq{$key}++;
        $rev_lookup{$key} = $str;
    }
    
    my @singles = grep { $freq{$_} == 1 } keys %freq;
    return map { $rev_lookup{$_} } @singles;
}

sub difference_array ( $aref ) {
## given an array of numeric elements, compute and return the 
## array of differences between successive elements
    my @out;
    push @out, $aref->[$_] - $aref->[$_-1] for 1..$aref->$#*;
    return \@out;
}

sub encode ( $str ) {
## convert a string into an array of digits, mapped to the 
## lowercase alphabet starting at 0.
## a => 0, b => 1, ... z => 25
    return [ map { ord($_)-97 } split '', lc($str) ]
}