site.base_url }}/">The Bear's Den -->

The Bear's Den

Enter at your own risk

14 April 2024

Challenge 264

The Greatest Target

Task 1: Greatest English Letter
Task 2: Target Array

Task 1: Greatest English Letter

Submitted by: Mohammad Sajid Anwar

You are given a string, $str, made up of only alphabetic characters [a..zA..Z].

Write a script to return the greatest english letter in the given string.

A letter is greatest if it occurs as lower and upper case. Also letter ‘b’ is greater than ‘a’ if ‘b’ appears after ‘a’ in the English alphabet.

Example 1

Input: $str = 'PeRlwEeKLy'
Output: L

There are two letters E and L that appears as lower and upper.
The letter L appears after E, so the L is the greatest english letter.

Example 2

Input: $str = 'ChaLlenge'
Output: L

Example 3

Input: $str = 'The'
Output: ''

Solution

The task may easily generalized to arbitrary strings and can be solved in a single pass through the string.

Convert the string to its Normalization Form “Canonical Composition”.
Split the string into characters and loop over these.
- Check the General Category properties “Letter uppercase” and “Letter lowercase” and store a corresponding bit in a hash keyed with the case folded character.
- If both cases of the character have been found in the string, choose the new maximum character for the next loop.
Transform the maximum letter found in the loop to upper case.

use strict;
use warnings;
use Unicode::Normalize;
use List::Util 'reduce';

sub gl {
    my %l;
    uc reduce {
        local $_ = $b;
        my $fc = fc;
        ($l{$fc} |= /\p{Ll}/ | /\p{Lu}/ << 1) == 3 && $fc gt $a ?
            $fc :
            $a;
    } '', split //, NFC shift;
}

See the full solution.

Task 2: Target Array

Submitted by: Mohammad Sajid Anwar

You are given two arrays of integers, @source and @indices. The @indices can only contains integers 0 <= i < size of @source.

Write a script to create target array by insert at index $indices[i] the value $source[i].

Example 1

Input: @source  = (0, 1, 2, 3, 4)
       @indices = (0, 1, 2, 2, 1)
Output: (0, 4, 1, 3, 2)

@source  @indices  @target
0        0         (0)
1        1         (0, 1)
2        2         (0, 1, 2)
3        2         (0, 1, 3, 2)
4        1         (0, 4, 1, 3, 2)

Example 2

Input: @source  = (1, 2, 3, 4, 0)
       @indices = (0, 1, 2, 3, 0)
Output: (0, 1, 2, 3, 4)

@source  @indices  @target
1        0         (1)
2        1         (1, 2)
3        2         (1, 2, 3)
4        3         (1, 2, 3, 4)
0        0         (0, 1, 2, 3, 4)

Example 3

Input: @source  = (1)
       @indices = (0)
Output: (1)

Solution

This week’s challenge led me into a series of failures.

Smoke Test

The examples in the task look too friendly. For a better understanding of the basic principles, here is a set of test cases that dig somewhat deeper. Looking at a target array, we may ask at which position a value had been inserted that arrived at a specific target position.

Taking the indices (0, 0, 1, 1, 2) in several arrangements such that the resulting target’s array at indices (2, 3, 4) represent all six permutations of insertion points (0, 1, 2). The source values are selected such that their first digit represents the step at which they enter the game and their second digit the index where they were inserted.

`@source`	`@indices`	`@target`
10 21 32 40 51	0 1 2 0 1	40 51 10 21 32
10 21 30 42 51	0 1 0 2 1	30 51 10 42 21
10 20 32 41 51	0 0 2 1 1	20 51 41 10 32
10 20 31 42 51	0 0 1 2 1	20 51 31 42 10
10 21 30 41 52	0 1 0 1 2	30 41 52 10 21
10 20 31 41 52	0 0 1 1 2	20 41 52 31 10

First Attempt: Sort indices

In my first attempt I tried to solve the task by setting the target elements in the insertion indices’ order and in reverse order within the same insertion index.

The simple PDL line

$s->index(cat($i, -sequence($i))->xchg(0, 1)->qsortveci)

looks easy and solves all of the examples from the task and some more, but it is wrong. It fails all smoke tests. (I had constructed these afterwards).

Second Attempt: Efficient sort

The process description “smells” like an insertion sort with an effort of $\mathcal{O}(n^2)$.

The process’ efficiency could be improved if we were able to efficiently compare the target positions of a pair of “indices” and apply an efficient sort based on the pairwise compare.

Taking an index as the pair $(p, i)$ with $p$ as the step number and $i$ as the insertion index, we may compare two indices $(p_1, i_1)$ and $(p_2, i_2)$.

$p \diagdown i$	$i_1 < i_2$	$i_1 = i_2$	$i_1 > i_2$
$p_1 < p_2$	?	$<$	$<$
$p_1 > p_2$	$>$	$>$	?

Two symmetric cases are problematic:

An element inserted at a smaller position in an earlier step may have move rightwards when the second element is inserted
An element inserted at a higher position in a later step may fall behind an earlier inserted element as this may have moved rightwards.

The relation between such two insertions does not only depend on the steps in between, but also on the steps before as these set up the environment.

Abandoning this approach, too.

Third Attempt: Follow the recipe

So finally I fell back to implementing the given recipe.

There are some pitfalls. The main issues to consider:

There may be holes in the target array - while filling or even finally.
On insertion of a new element, an existing block of data needs to be shifted
Holes will not be shifted.
When shifting a block, a trailing hole may be filled joining two blocks of data.
When inserting an element into a hole, two blocks of data may be joined.

To handle the blocks efficiently, two extra arrays are in use: @begin and @end. For each index in the target array @target, these two arrays hold the begin and end indices of the element’s block. The @end array is used to determine the block that has to be shifted when an element shall be inserted at an already filled position.

If the shift causes a hole to be filled, the whole left part receives a new end index. Here the @begin array springs into action as it provides the start index for the block to be updated.

Example

An example, showing the arrays in action with . as empty fields:

@source =  (1, 2, 3, 4, 5, 6)
@indices = (0, 2, 1, 0, 5, 3)

@source  @indices  @target       @begin        @end
1        0         (1)           (1)           (1)
2        2         (1 . 2)       (0 . 2)       (0 . 2)
3        1         (1 3 2)       (0 0 0)       (2 2 2)
4        0         (4 1 3 2)     (0 0 0 0)     (3 3 3 3)
5        5         (4 1 3 2 . 5) (0 0 0 0 . 5) (3 3 3 3 . 5)
6        3         (4 1 3 6 2 5) (0 0 0 0 0 0) (5 5 5 5 5 5)

There is nothing to be shifted for source items 1, 2, 3. Item 3 joins two blocks.
For item 4 we identify the block @target[0..2] to be shifted to @target[1 .. 3]
Item 5 creates a new singleton block
For item 6 we identify the block @target[3..3] to be shifted to @target[4 .. 4], joining the two blocks.

Here is the implementation:

use strict;
use warnings;
use experimental 'signatures';

sub target_array ($source, $indices) {
    my @source = @$source;
    my (@target, @begin, @end);
    # Loop over indices
    for my $i (@$indices) {
        # Get the corresponding source element
        my $s = shift @source;
        # Shift an existing block and store its new end
        if (defined(my $ei = $end[$i])) {
            @target[$i + 1 .. $ei + 1] = @target[$i .. $ei];
            $end[$i] = $ei + 1;
        }
        # Begin of block: existing or new
        my $b = $begin[$i] // $i;
        # Possibly join a preceding block
        $b = $begin[$b - 1] if $b > 0 && defined $begin[$b - 1];
        # End of block: existing or new
        my $e = $end[$i] // $i;
        # Possibly join a subsequent block
        $e = $end[$e + 1] if defined $end[$e + 1];
        # Update new block begin and end
        @end[$b .. $e] = ($e) x ($e + 1 - $b);
        @begin[$b .. $e] = ($b) x ($e + 1 - $b);
        # Store the current item
        $target[$i] = $s;
    }
    \@target;
}

See the full solution.

\(p \diagdown i\)	\(i_1 < i_2\)	\(i_1 = i_2\)	\(i_1 > i_2\)
\(p_1 < p_2\)	?	\(<\)	\(<\)
\(p_1 > p_2\)	\(>\)	\(>\)	?