Weekly Challenge: Maximum conflict

Weekly Challenge 367

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. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Max Odd Binary

Task

You are given a binary string that has at least one 1.

Write a script to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number and return the resulting binary string. The resulting string can have leading zeros.

My solution

This task requires some number theory to implement the solution.

• To make an odd binary number the last bit (less significant) needs to be a 1.
• To make the largest possible number, the remaining set bits need to be the largest (left / most significant) bits.

The parts of this task are:

1. Use a regular expression to check the input_string variable matches the expected input. It must contain at least one 1 and any number of 0 and 1.
2. Count the number of zeros and ones in the string, stored as the variables zeros and ones respectively.
3. Return a string that was ones-1 ones, zeros zeros and the last one to make it an odd binary.

def max_odd_binary(input_string: str) -> str:
    if not re.search(r'^[01]*1[01]*$', input_string):
        raise ValueError("Input not in expected format")

    zeros = input_string.count("0")
    ones = input_string.count("1")

    return "1" * (ones-1) + "0" * zeros + "1"

The Perl solution follows the same logic. It uses the tr function to count the number of zeros and ones, and the x operator for repetition.

Examples

$ ./ch-1.py 1011
1101

$ ./ch-1.py 100
001

$ ./ch-1.py 111000
110001

$ ./ch-1.py 0101
1001

$ ./ch-1.py 1111
1111

Task 2: Conflict Events

Task

You are given two events start and end time.

Write a script to find out if there is a conflict between the two events. A conflict happens when two events have some non-empty intersection.

My solution

One of the challenges when completing these tasks is achieving the most optimal solutions. Not in terms of performance, but in terms of being the best solution. Usually it is straight forward, I'm not sure if I've hit the mark on this one.

Things get more complicated when one (or both) the times go across midnight. This is the approach I took.

Create a function hm2m to convert a time in HH:MM format to minutes after midnight. It also uses a regular expression to check that the HH:MM is in the correct format and is valid.

def hm2m(t: str) -> int:
    if not re.search(r'^([0-1][0-9]|2[0-3]):[0-5][0-9]$', t):
        raise ValueError("Input is not in the expected format (HH:MM)")

    return int(t[:2]) * 60 + int(t[3:])

Take the supplied events (although the tasks specifies two, more can be provided) and create a range object from the start time to one minute less than the stop time and store it in the event_minutes list. If the start_time is later than end_time I add two range objects, one before midnight (end time = 1440) and after midnight (start time = 0).

def conflict_events(events) -> bool:
    """Determine if there is a conflict between two or more events.

    Params:
        events(list): A list of start and end times in HH:MM format

    Returns:
        bool: Whether two events conflict (occur at the same time)
    """
    event_minutes = []
    for event in events:
        start_minute = hm2m(event[0])
        end_minute = hm2m(event[1])
        if start_minute == end_minute:
            continue

        if end_minute < start_minute:
            event_minutes.extend(
                [range(start_minute, 1440), range(0, end_minute)])
        else:
            event_minutes.append(range(start_minute, end_minute))

The final step is to take the event_minutes ranges, and see if there is any overlap. For this I have a minutes set (hash in Perl). I iterate over each minute in each item in the events_minutes list. If the minute already appears in the minutes set, I return True. If not, I added it to the minutes set, and continue the loop.

If the list is exhausted, I return False as there is no conflict. Lucky you!

    minutes = set()
    for r in event_minutes:
        for minute in r:
            if minute in minutes:
                return True
            minutes.add(minute)

    return False

The Perl solution follows the same logic. The event_minutes array stores an array of start minutes and end minutes, as it does not have a range-like object.

Examples

$ ./ch-2.py 10:00 12:00 11:00 13:00
True

$ ./ch-2.py 09:30 10:30 10:30 12:00
False

$ ./ch-2.py 14:00 15:30 14:30 16:00
True

$ ./ch-2.py 08:00 09:00 09:01 10:00
False

$ ./ch-2.py 23:00 00:30 00:00 01:00
True