Perl Weekly Challenge: Week 367
Challenge 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"
I wondered if I could solve this one as a one-liner and sure enough Raku rose to the occasion.
We start by getting the input from the first command-line argument; it is split
into individual digits with .comb(), Then .sort() places all the 1s before the 0s.
.reverse() then puts all 0s before the 1s. .rotate() takes the last element of the
digits array and places it at the front. Now we have the maximum odd binary number and
all that remains is to .join() it back into a string and print it out with .say().
@*ARGS[0].comb.sort.reverse.rotate.join.say
Perl can do it too albeit a bit more lengthily. Most Raku operations have a direct
Perl counterpart and we can emulate .rotate() with push() and shift().
@s = (reverse sort split //, shift); push @s, shift @s; say join q{}, @s
Challenge 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".
I love date and time related problems but as I have said on this blog many times you have to be really careful about the many edge cases and it is better to use a tried and tested module rather than to try and roll your own code for this purpose. My go to library for date and time stuff is Time::Piece which is part of the Perl standard distribution.
We get the start and end times for both events from four command-line arguments and
parse them into Time::Piece objects using the strptime() static constructor.
my ($start1, $end1, $start2, $end2) =
map { Time::Piece->strptime($_, "%H:%M") } @ARGV[0 .. 3];
Now to see if the two events intersect, all we need to do is see if the start of event 1 is before the end of event 2 and the start of event 2 is before the end of event 1 and print
true or false as appropriate. (The 0+ is to prevent a warning about say().)
say 0+($start1 < $end2 && $start2 < $end1) ? 'true' : 'false';
This works for the first four examples but fails on the fifth. There event 1 straddles a day boundary; the start time seems to be greater than the end time because it is actually on the previous day. Our code does not take this into consideration. (I told you there are edge cases.)
This is my 2nd attempt.
In the previous code, we only used strptime() to parse hours and minutes, totally
omitting month, dsy and years. So the newly created Time::Piece objects "fill in
the blanks" with default values January, 01 and 1970. This is the start date or "epoch"
of the POSIX time-handling functions that Time::Piece ultimately relies on. There is no
previous day before then.
My solution was to create the Time::Piece objects with the month January and
the date 2nd (the year still defaults to 1970 but we don't mind about that.)
my ($start1, $end1, $start2, $end2) =
map { Time::Piece->strptime("01 02 $_", "%m %d %H:%M") } @ARGV[0 .. 3];
Now if the start time of event 1 is greater than the end time, we subtract
ONE_DAY from it. This is a constant found in the Time::Seconda module so we have to use Time::Seconds; at the beginning of our code.
ONE_DAY represents 86,400 seconds which due to the oddities of timekeeping may or may not
actually be one day but it is near enough for most purposes. Now the date of the
event is January 01 once again and the start time will properly be less than the end time.
if ($start1 > $end1) {
$start1 -= ONE_DAY;
}
Although it is not necessary for the examples above, for completenesses sake, we do the same for event 2.
if ($start2 > $end2) {
$start2 -= ONE_DAY;
}
The final line is the same as in the first version.
say 0+($start1 < $end2 && $start2 < $end1) ? 'true' : 'false';
Rakus' DateTime class is suprisingly lacking in features compared to Perls' offerings.
It has most of what we need though.
The main thing we need to provide ourselves is a `ONE_DAY constant.
constant ONE_DAY = 86_400;
Note we are initializing our DateTime objects using the ISO8601 format.
my ($start1, $end1, $start2, $end2) =
($s1, $e1, $s2, $e2).map({ DateTime.new("1970-01-02T$($_):00Z") });
Math with fates and times is done using Duration objects.
if $start1 > $end1 {
$start1 -= Duration.new(ONE_DAY);
}
if $start2 > $end2 {
$start2 -= Duration.new(ONE_DAY);
}
In order to get proper comparisons, we have to convert the DateTime objects to Instants.
say ($start1.Instant < $end2.Instant && $start2.Instant < $end1.Instant);