This is my response to The Weekly Challenge #367.
Input: $str = "1011"
Output: "1101"
"1101" is max odd binary (13).
Input: $str = "100"
Output: "001"
"001" is max odd binary (1).
Input: $str = "111000"
Output: "110001"
Input: $str = "0101"
Output: "1001"
Input: $str = "1111"
Output: "1111"
We get the highest possible value by placing all the 1s before the 0s. An odd number is achieved by placing a 1 at the very end. As the input number has at least 1 of them (the 1s), we can take the leftmost value and insert it at the right.
File: max-odd-binary
#! /usr/bin/env raku
subset Binary1 where /^<[01]>+$/ && /1/; # [1]
unit sub MAIN (Binary1 $binary, :v($verbose)); # [2]
my @digits = $binary.comb.sort: -*; # [3]
say ": Digits sorted: { @digits.join(", ") }" if $verbose;
@digits.push: @digits.shift; # [4]
say ": Digits w/trailing 1: { @digits.join(", ") }" if $verbose;
my $result = @digits.join; # [5]
say ": \"$result\" is max odd binary ({ $result.parse-base(2) })"
if $verbose;
say $result; # [6]
[1] A Custom type for the binary input, with at least one 1 in it.
[2] Apply the custom type on the input.
[3] Get the digits in reversed sorted order, i.e. with all the 1s (one
or more of them) before the 0s (zero or more of them). The -* sorts
on the negative version of each value, so we do not have to reverse
the result.
[4] Get the first element (which is a 1, with shift) and move it
to the end. (with push) This gives us an odd number (as the rightmost
digit in a binary value has the decimal value of 1, if set).
[5] Glue the digits together again,
[6] and print the result.
Running it:
$ ./max-odd-binary 1011
1101
$ ./max-odd-binary 100
001
$ ./max-odd-binary 111000
110001
$ ./max-odd-binary 0101
1001
$ ./max-odd-binary 1111
1111
Looking good.
With verbose mode:
$ ./max-odd-binary -v 1011
: Digits sorted: 1, 1, 1, 0
: Digits w/trailing 1: 1, 1, 0, 1
: "1101" is max odd binary (13)
1101
$ ./max-odd-binary -v 100
: Digits sorted: 1, 0, 0
: Digits w/trailing 1: 0, 0, 1
: "001" is max odd binary (1)
001
$ ./max-odd-binary -v 111000
: Digits sorted: 1, 1, 1, 0, 0, 0
: Digits w/trailing 1: 1, 1, 0, 0, 0, 1
: "110001" is max odd binary (49)
110001
$ ./max-odd-binary -v 0101
: Digits sorted: 1, 1, 0, 0
: Digits w/trailing 1: 1, 0, 0, 1
: "1001" is max odd binary (9)
1001
$ ./max-odd-binary -v 1111
: Digits sorted: 1, 1, 1, 1
: Digits w/trailing 1: 1, 1, 1, 1
: "1111" is max odd binary (15)
1111
Input: @event1 = ("10:00", "12:00")
@event2 = ("11:00", "13:00")
Output: true
Both events overlap from "11:00" to "12:00".
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.
Input: @event1 = ("14:00", "15:30")
@event2 = ("14:30", "16:00")
Output: true
Both events overlap from 14:30 to 15:30.
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".
Input: @event1 = ("23:30", "00:30")
@event2 = ("00:00", "01:00")
Output: true
They overlap from "00:00" to "00:30".
A custom grammar seems like a good fit here. See e.g. this Grammar Tutorial for a good explanation.
File: conflict-event
#! /usr/bin/env raku
unit sub MAIN ($event1, $event2, :v($verbose)); # [1]
grammar Event # [2]
{
token TOP { <hhmm> <space> <hhmm> } # [3]
token hhmm { <hh> <colon> <mm> } # [4]
token space { \s } # [5]
token colon { ":" } # [6]
token hh { <[01]> <[0..9]> | 20 | 21 | 22 | 23 } # [7]
token mm { <[012345]> <[0..9]> } # [8]
}
my $e1 = Event.parse($event1); # [9]
my $e2 = Event.parse($event2); # [9a]
die "Illegal syntax in 1. event" unless $e1; # [10]
die "Illegal syntax in 2. event" unless $e2; # [10a]
my $start1 = $e1<hhmm>[0]<hh> * 60 + $e1<hhmm>[0]<mm>; # [11]
my $stop1 = $e1<hhmm>[1]<hh> * 60 + $e1<hhmm>[1]<mm>; # [11a]
my $start2 = $e2<hhmm>[0]<hh> * 60 + $e2<hhmm>[0]<mm>; # [12]
my $stop2 = $e2<hhmm>[1]<hh> * 60 + $e2<hhmm>[1]<mm>; # [12a]
if $start1 > $start2 # [13]
{ # [13a]
($start1, $stop1, $start2, $stop2) = ($start2, $stop2, $start1, $stop1);
say ": Swapped event 1 & 2 so that 1 starts first" if $verbose;
}
my $overnight1 = $start1 > $stop1; # [14]
my $overnight2 = $start2 > $stop2; # [14a]
if $verbose
{
say ": Event1: $start1 - $stop1 Overnight:$overnight1";
say ": Event2: $start2 - $stop2 Overnight:$overnight2";
}
if $overnight1 == $overnight2 == True # [15]
{
say True; # [15a]
}
elsif $overnight1 == $overnight2 == False # [16]
{
say $start2 < $stop1; # [16a]
}
elsif $overnight1 == True # [17]
{
say ( $stop1 > $start2 || $start1 < $stop2 ); # [17a]
}
elsif $overnight2 == True # [18]
{
say ( $stop2 > $start1 || $start2 < $stop1 ); # [18a]
}
[1] The two event strings without constraints. That will be done in [9] and [9a]. See the "Running it" section for the string syntax.
[2] A custom grammer for an event.
[3] The starting token must have the name «TOP». It cntains two time values separated by a space.
See docs.raku.org/syntax/token for more information about token.
[4] The time value token.
[5] The actual space,
[6] and colon.
[7] The hour value,
[8] and the minute value.
[9] Apply the grammer on the event string(s) with parse.
See docs.raku.org/routine/parse for more information about parse.
[10] Get the start and stop [10a] times for the first event, as minutes past midnight.
[11] Ditto for the second event.
[12] Swap the events if required, so that the first one is the first to start. This makes the conflict checks easier.
[13] Check if the events are overnight events
[14] If both events are overnight, we have a conflict.
[15] If none are overnight, we have a conflict if the second one starts before the end of the first one.
[16] If the first one (only) is overnight, we have a conflict if the first one ends before the start of second one - or the first one starts before the end of the second one.
[16] If the second one (only) is overnight; the same logic as above. Swap the events in the checks.
Running it:
$ ./conflict-event "10:00 12:00" "11:00 13:00"
True
$ ./conflict-event "09:00 10:30" "10:30 12:00"
False
$ ./conflict-event "14:00 15:30" "14:30 16:00"
True
$ ./conflict-event "08:00 09:00" "09:01 10:00"
False
$ ./conflict-event "23:30 00:30" "00:00 01:00"
True
Looking good.
With verbose mode:
$ ./conflict-event -v "10:00 12:00" "11:00 13:00"
: Event1: 600 - 720 Overnight:False
: Event2: 660 - 780 Overnight:False
True
$ ./conflict-event -v "09:00 10:30" "10:30 12:00"
: Event1: 540 - 630 Overnight:False
: Event2: 630 - 720 Overnight:False
False
$ ./conflict-event -v "14:00 15:30" "14:30 16:00"
: Event1: 840 - 930 Overnight:False
: Event2: 870 - 960 Overnight:False
True
$ ./conflict-event -v "08:00 09:00" "09:01 10:00"
: Event1: 480 - 540 Overnight:False
: Event2: 541 - 600 Overnight:False
False
$ ./conflict-event -v "23:30 00:30" "00:00 01:00"
: Swapped event 1 & 2 so that 1 starts first
: Event1: 0 - 60 Overnight:False
: Event2: 1410 - 30 Overnight:True
True
And that's it.