DEV Community

Simon Green
Simon Green

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay