PWC 367 Overlapping Oddities

Task 1, Maximum Odd Binary

It's the week of the Artemis 2 mission to the moon, and we have a problem about odd numbers. I'd call that a Space Oddity.

Task Description

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.

• Example 1: Input: $str = "1011", Output: "1101"
• Example 2: Input: $str = "100", Output: "001"
• Example 3: Input: $str = "111000", Output: "110001"
• Example 4: Input: $str = "0101",Output: "1001"
• Example 5: Input: $str = "1111", Output: "1111"

Task Cogitation

To be as large as possible, a binary number must have all its 1s in the most-significant bits. To be odd, the least significant bit must be a one. So, what has to happen is that all the 1s shift to the left, one shifts to the right, and all the zeroes form a space between them.

I see three possible solutions:

• Sort: sort the bits so that the 1s are on the left, the 0s on the right, and then rotate a 1 into the right-most position.
• Split: make a pass over the bits, creating a pile of 1s and a pile of 0s. Form the required output string from the piles.
• Count: There's no need to move the bits around. Count how many 1s there are. Conjure a string of 1s, and a string of 0s.

Task Implementation

Solution 1: Sorting

sub mobSort($str)
{
    my @bits = sort { $b cmp $a } split(//, $str);
    push @bits, shift @bits;
    return join("", @bits);
}

Notes:

• Sort in descending order to put 1s on the left
• Rotate by taking the bit on the left and pushing it onto the right.

Solution 2: Splitting

sub mobSplit($str)
{
    my @bit = ( "", "" );
    $bit[$_] .= $_ for split //, $str;

    substr($bit[1], -1, 0, $bit[0]);
    return $bit[1];
}

Notes:

• I want a group of 0s and a group of 1s. That's an array of size two, conveniently indexed by [0] and [1].
• For each 0 or 1, append to its string.
• To form the output, use the four-argument form of substr, which replaces a substring. In the string of 1s, insert the string of 0s just before the zero-length string in front of the last bit.

Solution 3: Counting

sub mobCount($str)
{
    my $n = length($str);
    my $zero = ($str =~ tr/0/0/);

    return ("1" x ($n-$zero-1)) . ("0" x $zero) . ("1");
}

Notes:

• The output will be the same length as the input.
• The number of zeroes can be counted by the Perl FAQ idiom of using the tr/// operator -- it returns the number of substitutions.
• Now we know how any 1s and 0s we need, so replicate them appropriately.

Task Benchmark

It's too trivial a problem to be concerned about performance, but let's benchmark it anyway.

               Rate   sorting splitting  counting
sorting    128205/s        --      -28%      -95%
splitting  178571/s       39%        --      -93%
counting  2500000/s     1850%     1300%        --

I'm not surprised that sorting is slowest (it's an O(n_log_n) algorithm). I am a little surprised how much faster counting is.

Task 2, Conflict Events

Task Description

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.

• Example 1:
  • Input: @event1 = ("10:00", "12:00") @event2 = ("11:00", "13:00")
  • Output: true
  • Both events overlap from "11:00" to "12:00".
• Example 2:
  • Input: @event1 = ("09:00", "10:30") @event2 = ("10:30", "12:00")
  • Output: false
  • Event1 ends exactly at 10:30 when Event2 starts. Since the problem defines intersection as non-empty, exact boundaries touching is not a conflict.
• Example 3:
  • Input: @event1 = ("14:00", "15:30") @event2 = ("14:30", "16:00")
  • Output: true
  • Both events overlap from 14:30 to 15:30.

• Example 4:

  • Input: @event1 = ("08:00", "09:00") @event2 = ("09:01", "10:00")
  • Output: false
  • There is a 1-minute gap from "09:00" to "09:01".

• Example 5:

  • Input: @event1 = ("23:30", "00:30") @event2 = ("00:00", "01:00")
  • Output: true
  • They overlap from "00:00" to "00:30".

Task Cogitation

The string form of time is annoying to work with. The first thing to do is to convert the time to a minute of the day. As we learned last week, there are 1440 minutes in a day. And as we learned long ago, there are 525,600 minutes in a year, but that's not relevant. Stay focused.

Once we have the times converted, then we have a problem in detecting overlapping ranges. I know how to do that. The examples highlight the edge cases.

Example 5 throws a curve: the ranges can cross midnight. There will be math involving modulo operators.

I'm going to break this down into small pieces.

Task Solution

What I'm going for is: does the range of event 1 overlap with the range of event 2? That means I need a function to see if ranges overlap, which means I need a function to convert times to ranges, which means I need functions to convert time strings to numbers. Let's pop that stack.

Subtask: Time conversion

Very straightforward. I'm assuming times have been validated and are in the specified format.

sub toMinute($hhmm)
{
    my ($h, $m) = split(":", $hhmm);
    my $minute = $m + 60 * $h;
    return $minute;
}

Subtask: Event range

Here's where we isolate the problem of spanning midnight. We figure out how long the event is, using a 24-hour clock modulo operation. Then, replace the beginning of the range by subtracting the duration from the end. That means we might get a negative number for the beginning, but that's okay -- it represents a time before midnight.

sub toRange($minBeg, $minEnd)
{
    my $duration = ($minEnd - $minBeg) % 1440;
    return [ $minEnd - $duration, $minEnd ];
}

Subtask: Range overlap

Given two ranges, whether they overlap depends on where their edges line up.

I like use enum as a way to introduce a little readability. It's a very efficent module, and quite flexible.

sub isOverlap($range1, $range2)
{
    use enum qw( BEG=0 END=1 );
    return $range1->[END] > $range2->[BEG]
        && $range1->[BEG] < $range2->[END];
}

Composition of the solution

sub isConflict($event1, $event2)
{
    return isOverlap(toRange( map { toMinute($_) } $event1->@* ),
                     toRange( map { toMinute($_) } $event2->@* ) );
}

Given all the pieces, the solution falls into place.

• map { toMinute() " -- convert the time strings into pairs of numbers that we can do arithmetic with.
• toRange( map {} ) - convert pairs of points in time into ranges that might span midnight.
• isOverlap(...) - the answer is the result of checking for range overlap.