RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved bit rearrangement and range overlaps. (Note that this ends today.)

Task 1: Max Odd Binary

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.

The highest value string will be the one that shuffles all the 1s into the highest (leftmost) places.

The highest value odd string will be like that, but the lowest value 1 has to be in the last place.

So the output will be

• "1" × (count of ones, minus 1)
• "0" × (count of zeroes)
• "1"

In Raku:

sub maxoddbinary($a) {

Count the 1s and 0s. (We don't care about the order they arrive in.)

    my $ones = 0;
    my $zeroes = 0;
    for $a.comb -> $c {
        if ($c eq '0') {
            $zeroes++;
        } elsif ($c eq '1') {
            $ones++;
        }
    }

If we didn't get at least one 1, bail out.

    if ($ones < 1) {
        return '';
    }

Otherwise, assemble the string:

    my $out = '';

All but one of the ones.

    $out ~= '1' x ($ones - 1);

All the zeroes.

    $out ~= '0' x $zeroes;

The final one.

    $out ~= '1';
    $out;
}

Task 2: Conflict Events

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.

I treat this problem as a range intersection: two ranges overlap if the start of each comes before or at the end of the other. The ranges here are quantised into minutes, and ex2 demonstrates that if one end equals the other's start this is not an overlap, so "10:00 to 12:00" becomes 600 to 719 minutes (inclusive).

The fiddly bit is time ranges that span midnight, and I resolve this by making each span a list of lists. If the overall event doesn't span midnight there's just one item, as above; otherwise the first span runs from start to midnight, and the second from midnight to end.

Then I just check each range from the first span against each range from the second span, returning true for any overlap.

Crystal:

Here's a parser to convert a single time ("xx:yy") into a minute count.

def parsetime(t)
  p = t.split(":")
  p[0].to_i * 60 + p[1].to_i
end

def conflictevents(a, b)

r is the list of events, each containing a list of spans, each span itself being a list.

  r = Array(Array(Array(Int32))).new

Look at each event specification.

  [a, b].each do |t|

Get the start and end times out of it.

    st = parsetime(t[0])
    en = parsetime(t[1])

If it doesn't span midnight,

    if st < en

add a single numerical span.

      r.push([[st, en - 1]])

Otherwise, add two separate spans.

    else
      r.push([
               [st, 1440 - 1],
               [0, en - 1]
             ])
    end
  end

Look at each span in the first event

  r[0].each do |ra|

and each span in the second event. (Yeah, O(n²), but we're only making a maximum of four comparisons.)

    r[1].each do |rb|

If there is an overlap, immediately return true.

      if ra[0] <= rb[1] && rb[0] <= ra[1]
        return true
      end
    end
  end

If we got all the way through without an overlap, return fqlse.

  false
end

Full code on codeberg.