The Weekly Challenge - 249 (December 25th 2023)

Task #1: Equal Pairs

You are given an array of integers with even number of elements.

Write a script to divide the given array into equal pairs such that:

Each element belongs to exactly one pair.
The elements present in a pair are equal.

Example 1

Input:  @ints = (3, 2, 3, 2, 2, 2)
Output: (2, 2), (3, 3), (2, 2)

There are 6 elements in @ints.
They should be divided into 6 / 2 = 3 pairs.
@ints is divided into the pairs (2, 2), (3, 3), and (2, 2) satisfying all the conditions.

Example 2

Input: @ints = (1, 2, 3, 4)
Output: ()

There is no way to divide @ints 2 pairs such that the pairs satisfy every condition.

Solution

As we need to know if we have equal pairs the first thing we do is count each number.. this is the classic $C{$_}++ for construction which is synonymous with Perl coding tests!

We then look for an odd entry in that list (we could use List::Util‘s first function – but because it is built in grep is generally faster.

If there is we just return an empty list, otherwise we generate the required result. For each value we just $C{$_}/2 copies of [$_,$_].

We may have been tempted to use the x operator, BUT the following do different things.

( [$T,$T] ) x ($C{$T}/2) – makes one copy of [$T,$T] and repeats it
map { [$T,$T] } 1..$C{$T}/2 – makes a number of individual copies of [$T,$T]

The latter I think is less likely to cause a hiccup further down the lines!!

249-equal_pairs.pl - perl
          sub equal_pairs {

  my(%C,$t);

  $C{$_}++ for @_;        ## Collect counts

                          ## Return if any counts are odd

  [ map { $t=$_;          

          map { [$t,$t] } ## Make "n/2" copies of [X,X]

          1 .. $C{$t}/2

        }       

    keys %C ]             ## For each value..

Task #2: DI String Match

Find a permutation of the integers [0 .. length(s)] such that for each character s[i] in the string:

s[i] == 'I' ⇒ perm[i] < perm[i + 1]
s[i] == 'D' ⇒ perm[i] > perm[i + 1]

Example 1

Input: $str = "IDID"
Output: (0, 4, 1, 3, 2)

Example 2

Input: $str = "III"
Output: (0, 1, 2, 3)

Example 3

Input: $str = "DDI"
Output: (3, 2, 0, 1)

Solution

How do we chose the next number…

If the next symbol is a “D” then we can guarantee the next number satisfies the criteria if we chose the largest number available;
If the second symbol is a “I” then we can guarantee the next number satisfies the criteria if we chose the smallest number available;

This gives the fomulae below.

We use two variables $n, $x to track min and max – values remaining. At the end both $n & $x contain the same value.

249-di_string_match.pl - perl
          sub DI_string_match {

  my( $n, $x ) = ( 0, length $_[0] );

  map( { 'I' eq $_ ? $n++ : $x-- } split //, $_[0] ), $n

}

About The Weekly Challenge

The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.

These are posted at:

https://theweeklychallenge.org/