Task — Odd string

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.

Examples

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

We are given a list of strings, such as:

"adc", "wzy", "abc"

From each of these strings we are to form a 'difference array', which contains the alphabetical distance of each letter in the string from the preceding one. So for "adc" the difference array is (3, -1) because 'd' is 3 letters after 'a' in the alphabet, and c is 1 letter before 'd'.

Mohammad suggests that we do this by assigning 0 to 'a', 2 to 'b' and so on, but as we are only concerned by differences we can simply use the ASCII values of the characters, which Perl provides in the function ord().

We are then to told that all of the strings except one have the same difference array, and asked to find the one that does not. Curiously, perhaps, that is mildly challenging, but here is the solution I adopted.

First, let's represent the difference array not as an array but as a string. So for "adc" I am forming the difference array as the string '3, -1'. Let's call that the difference string. So now I'm going through all the strings in the list, and for each one $s I create a difference string $diff, and then with each difference string I do this:

$seen{$diff} .= qq[$s=];

The '=' is simply a separator, because I am concatenating all the '$s=' that have the same $diff into a single member of %seen. It will end up looking like this:

$seen{'3, -1'} -> 'adc=wzy='
$seen{'1, 1'}  -> 'abc='

I then loop over the elements of %seen and look for the value that matches:

$seen{$s} =~ m|^([^=]*)=$|

or in words, a value that starts with a run of characters not containing '=' followed by '=' followed by nothing else. If you look at the values of %seen shown above, you'll see that the only one that matches that pattern (ie having a single '=') is the odd one out.

This only works if Mohammad's assertions are correct, that is, there is only one odd man, all the strings are the same length and only contain lower case a-z letters. I could (and would in 'real life') have tested that those assumptions were correct.

Try it 

Try running the script with any input:

Your @s =

example: 'abc', 'def', 'ghi', 'zzz'

⤡

#!/usr/bin/perl

# Peter Campbell Smith - 2022-11-28
# PWC 193 task 2

use v5.28;
use utf8;
use warnings;

my (@tests, $test, @s, $i, $j, $diff, %seen, $s, $input);

@tests = (["adc", "wzy", "abc"], ["aaa", "bob", "ccc", "ddd"], ['abcd', 'defg', 'hijk', 'fred'],
    ['abcdefghij', 'bcdefghijk', 'bcdefghijj', 'nopqrstuvw']);

for $test (@tests) {
    
    # initialise
    @s = @$test;
    %seen = ();
    $input = '';
    $input .= qq["$_", ] for @s;
    say qq[\nInput:  \@s = (] . substr($input, 0, -2) . ')';
    
    # loop over strings in list
    for ($i = 0; $i < scalar @s; $i ++) {
        
        # calculate difference
        $diff = '';
        for $j (0 .. length($s[0]) - 2) {
            $diff .= ord(substr($s[$i], $j + 1, 1)) - ord(substr($s[$i], $j, 1)) . ', ';
        }
        $seen{$diff} .= qq[$s[$i]=];
    }
    
    # find the one which has been seen only once
    for $s (keys %seen) {
        say qq[Output: "$1"] if $seen{$s} =~ m|^([^=]*)=$|;
    }
}

Output

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

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

Input:  @s = ("abcd", "defg", "hijk", "fred")
Output: "fred"

Input:  @s = ("abcdefghij", "bcdefghijk", "bcdefghijj", "nopqrstuvw")
Output: "bcdefghijj"