Weekly Challenge 297

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Contiguous Array

Task

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.

My solution

Two relatively straight forward task this week. This is good, cause I'm still on holiday! For this task, I start with the variable max_length which is the length of the array. If this is an odd number, I reduce the value by one as we are only interested in an even number of items.

I have an loop that counts from max_length to 2, removing 2 from the length variable each time. I then have an inner loop called start that starts at zero and ends at the length of the array minus the length value. I check if the sum of the integers between start and start + length is half the value of length. This would indicate that we have the same number of zeros and ones.

If I find no solution, I return 0

def contiguous_array(binary: list) -> str:
    max_length = len(binary)
    if max_length % 2:
        max_length -= 1

    for length in range(max_length, 0, -2):
        for start in range(len(binary) - length + 1):
            if sum(binary[start:start+length+1]) == length // 2:
                return length

    return 0

Examples

$ ./ch-1.py 0 1 0
2

$ ./ch-1.py 0 0 0 0 0
0

$ ./ch-1.py 0 1 0 0 1 0
4

Task 2: Semi-Ordered Permutation

Task

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.

My solution

I start this task by computing the following values.

• last_index is the index (position) of the last value. This is the length of the array minus 1.
• min_index is the index of the first minimum value in the array.
• max_index is the index of the last maximum value in the array.

If min_index is greater than max_index, then we have an offset value of 1 as one less move is require when we cross over the two values.

The number of moves to get the minimum value to the first position is min_index. The number of moves to get the maximum value to the last position is last_index - max_index (minus 1 if there is a cross over).

def semi_ordered_permutation(ints: list) -> int:
    last_index = len(ints) - 1
    min_index = ints.index(min(ints))
    max_index = last_index - ints[::-1].index(max(ints))


    offset = 1 if  max_index < min_index else 0
    return min_index + last_index - max_index - offset 

Examples

$ ./ch-2.py 2 1 4 3
2

$ ./ch-2.py 2 4 1 3
3

$ ./ch-2.py 1 2 3 4 5
0