RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved array hunting and re-permuting. (Note that this ends today.)

Task 1: Contiguous Array

You are given an array of binary numbers, @binary.

Write a script to return the maximum length of a contiguous subarray with an equal number of 0 and 1.

The main trick with this one is evaluating from largest to smallest possible answer, which lets me exit early when I find one that's valid, rather than tracking a running highest-answer-found while going through all possibilities.

Python:

def contiguousarray(a):

Count down length values (even numbers only)

  for l in reversed(range(2, len(a) + 1, 2)):

Iterate over valid start points.

    for start in range(len(a) - l + 1):

Since the values can only be 0 or 1, slice and sum to check validity.

      end = start + l
      if sum(a[start:end]) * 2 == l:
        return l
  return 0

Task 2: Semi-Ordered Permutation

You are given permutation of $n integers, @ints.

Write a script to find the minimum number of swaps needed to make the @ints a semi-ordered permutation.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.

A permutation is called semi-ordered if the first number is 1 and the last number equals n.`You are ONLY allowed to pick adjacent elements and swap them.

This can obviously be solved by exploratory swapping, but an easier approach occurred to me. The lowest value at index S has to be moved left S times to arrive at 0; the highest value at index E has to be moved right (length - E - 1) times to arrive at the end. Add those values to give a number of swaps. If the highest value is before the lowest in the initial setup, then one of the necessary swaps will move both values towards their goals, so subtract one from the total.

Raku:

sub semiorderedpermutation(@a) {

Get the length.

    my $en = @a.elems;

Get the start and end indices.

    my $s = 1;
    my $e = $en - 1;
    for @a.kv -> $i, $n {
        if ($n == 1) {
            $s = $i;
        }
        if ($n == $en) {
            $e = $i;
        }
    }

Work out total moves.

    my $r = $s + ($en - 1 - $e);

Subtract 1 if there's a swap that brings 1 before N.

    if ($s > $e) {
        $r--;
    }
    $r;
}

Full code on github.