Perl Weekly Challenge: Conflicting Every Odd

Posted on by

Perl Weekly Challenge 367‘s tasks are “Max Odd Binary” and “Conflict Events”. Since my wife won’t let me forget I’m part of “the Phil Collins set”1, let’s lean into it and say this week’s musical theme is Against All Odds.

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.

Example 1

Input: $str = "1011"
Output: "1101"

"1101" is max odd binary (13).

Example 2

Input: $str = "100"
Output: "001"

"001" is max odd binary (1).

Example 3

Input: $str = "111000"
Output: "110001"

Example 4

Input: $str = "0101"
Output: "1001"

Example 5

Input: $str = "1111"
Output: "1111"

Approach

Example 2 really gives away the approach: for any number to be odd, there must be a 1 in the ones place. Then, to make the number as maximal as possible, the remaining 1s need to be shifted as far to the left as possible. So let’s split the bits into an array, sort them so the 1s are first, then shift off the first 1 and push it on the end of the array and rejoin it into a string.

Raku

I was hoping to be able to do this in one line, but I couldn’t think how to shift off the first 1 and push it to the end without assigning the list of bits to a variable.

sub maxOddBinary($str) {
  my @bits = $str.comb.sort.reverse;
  @bits.push(@bits.shift).join;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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"

Perl

Perl got a line longer because I couldn’t chain the shift/push with the join.

sub maxOddBinary($str) {
  my @bits = reverse sort split //, $str;
  push @bits, shift @bits;
  join '', @bits;
}

View the entire Perl script for this task on GitHub.

Python

The Python built-in reversed returns a list_reverseiterator object, which isn’t a list that we can pop off of or append to, so we need to call list to convert the iterator to a list.

def max_odd_binary(mystr):
  bits = list(reversed(sorted([ b for b in mystr ])))
  bits.append(bits.pop(0))
  return ''.join(bits)

View the entire Python script for this task on GitHub.

Elixir

The core of the Elixir solution is Kernel.hd/1 and Kernel.tl/1, which return the head (first element) of a list and the tail (the list without its head) of a list.

  def max_odd_binary(str) do
    bits = str |> String.graphemes |> Enum.sort |> Enum.reverse
    {head, bits} = {hd(bits), tl(bits)}
    bits ++ [head] |> Enum.join
  end

View the entire Elixir script for this task on GitHub.

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.

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".

Approach

Ok, we’re going to make the assumption that @event2 is always later than @event1. That’s the only way Example 5 makes sense: if @event2 were earlier, then there would be no overlap—@event2 would finish 23 hours before @event1 started. But because it says they do overlap, then the midnight start time for @event2 is only 30 minutes later than the start time for @event1.

So, with that assumption out of the way, we only really need to examine the end time for @event1 and the start time for @event2. If the end time of the first is strictly greater than the start time of the second, they overlap. We can do this by stripping the colons out of the times, converting them to integers, and comparing them.

Raku

Like I did last week, I’m using the Str method .subst to remove the colon, and because I’m using Raku’s numeric greater than operator (>) the strings are coerced into numeric values before the comparison.

sub conflict(@event1, @event2) {
  my $end   = @event1[1].subst(":");
  my $start = @event2[0].subst(":");
  $end > $start;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @event1 = ("10:00", "12:00")
       @event2 = ("11:00", "13:00")
Output: True

Example 2:
Input: @event1 = ("09:00", "10:30")
       @event2 = ("10:30", "12:00")
Output: False

Example 3:
Input: @event1 = ("14:00", "15:30")
       @event2 = ("14:30", "16:00")
Output: True

Example 4:
Input: @event1 = ("08:00", "09:00")
       @event2 = ("09:01", "10:00")
Output: False

Example 5:
Input: @event1 = ("23:30", "00:30")
       @event2 = ("00:00", "01:00")
Output: True

Perl

For the Perl solution, I’m doing a little trick where you can use a variable assignment as an lvalue that’s passed into a function. Usually, I see this done when changing a variable via a regular expression:

(my $copy = $str) =~ s/\\/\\\\/g;

The assignment of the value of $str to $copy is done first, and then $copy is used as the target for the regex substitution, leaving $str unchanged. Then, I’m passing the lvalue into substr and replacing the third character (the array is 0-indexed) with the empty string.

sub conflict($event1, $event2) {
  substr((my $end   = $event1->[1]), 2, 1, "");
  substr((my $start = $event2->[0]), 2, 1, "");
  $end > $start ? 'True' : 'False';
}

View the entire Perl script for this task on GitHub.

Python

Of course, Python doesn’t have automatic type coercion, so we have to explicitly convert the starting and ending values to int.

def conflict(event1, event2):
  end   = int(event1[1].replace(":", ""))
  start = int(event2[0].replace(":", ""))
  return end > start

View the entire Python script for this task on GitHub.

Elixir

As soon as I started this task, I knew that I wanted to use the feature in Elixir where, when a function is expecting a list, you can break it out into the hd and tl of the array by writing [head | tail]. Of course, I forgot that the tail of a list is a list itself, so on line 8 I originally was piping stop |> replace(":", ""). But when I did that, I got the following error:

    The following arguments were given to String.replace/4:

        # 1
        ["12:00"]

        # 2
        ":"

        # 3
        ""

        # 4
        []

D’oh! The first argument to String.replace/4 is a string, not a list. So I changed stop to hd(stop) (which gave me the string that’s the one element in the list) and all was well.

Oh, and I had to rename the end variable to stop because end is a reserved word in Elixir.

import String, except: [to_charlist: 1] # keep Kernel.to_charlist/1

def conflict([_ | stop], [start | _]) do
  stop  = hd(stop) |> replace(":", "") |> to_integer
  start = start    |> replace(":", "") |> to_integer
  stop > start
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-367/packy-anderson

  1. David Bowie, later in life, described his mid-80s albums—Let’s Dance, Tonight and Never Let Me Down—as not his best work, and dismissed them as “appealing to the Phil Collins set.”

    Let’s Dance is my favorite Bowie album, and my wife never lets me forget it. ↩︎

Leave a Reply