| 02 April 2026 | Challenge 367 |
Odd Events
Task 1: Max Odd Binary
Submitted by: Mohammad Sajid Anwar
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"
Solution
One obvious approach:
- count the ones in the string
- take one less than the counted number of ones
- append as many zeroes as there are in the string
- append a one
Perl
use strict;
use warnings;
use experimental 'signatures';
sub max_odd_binary ($str) {
my $ones = $str =~ tr/1//;
die unless $ones;
'1' x ($ones - 1) . '0' x (length($str) - $ones) . '1';
}
See the full solution to task 1.
J
max_odd_binary =: # ('101' #~ <:@] , - , 1:) +/@('1'&=)
echo max_odd_binary '1011'
See the full solution.
Task 2: Conflict Events
Submitted by: Mohammad Sajid Anwar
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".
Solution
There is an ambiguity in this task. For an event having the same start and end time there are two possible interpretations:
- it has a zero length or
- it spans a whole day.
Both interpretations seem to be valid, though they lead to different results in edge cases. Here I’ll presume the second interpretation as this will turn out to be convenient in the following.
First subtask: parse input times.
Multiply the hours by 60, add the minutes and take the result modulo 1440.
This gives a relaxed interpretation of times, as "02:30" and "25:90" will be regarded as valid and treated equivalently.
And it gives the first motivation to consider ("00:00", "00:00") as a full day: it is identical to
("00:00", "24:00").
Second subtask: identify conflicts.
Each event has a duration that is the difference between its end time and its start time modulo 1440 with zero shifted to 1440.
Furthermore, we define two complementary events that have the same start times but exchanged end times.
There are two cases how events may conflict:
- they share one common time interval, this includes the case where one event is contained in the other
- they share two common intervals, where one events starts and ends within the other, but wrapping around.
In the first case the duration sum of the primary events equals the duration sum of the complementary events. The duration of an arbitrary complementary event is therefore less than the duration sum of the primary events.
In the second case the duration sum of the primary events exceeds 1440 min. As a single event’s duration cannot exceed 1440 min, both complementary events’ durations are less than the primary events’ duration sum.
In both cases the duration of an arbitrary complementary event is less than the duration sum of the primary events.
On the other hand, when the primary events do not conflict, then at least one of the complementary events includes the primary events completely and as these do not overlap, its duration is not shorter than the primary events’ duration sum. With the the second interpretation from above, this is true for both complementary events, even if the primary events are adjacent.
Putting everything together and presuming the second interpretation from above:
Two events are conflicting if and only if the sum of their durations is greater than the duration of an arbitrary complementary event.
The resulting formula looks a bit too simple and I doubted more than once that it were correct. But whatever new edge case I thought of where the formula could fail, it proved right.
Please leave a comment if you have a case where this approach fails.
Examples:
| Primary | 03:00 - 18:00 |
09:00 - 15:00 |
|
| Durations | 900 min |
360 min |
1260 min |
| Complementary | 03:00 - 15:00 |
09:00 - 18:00 |
|
| Durations | 720 min |
540 min |
< |
| Primary | 03:00 - 15:00 |
09:00 - 18:00 |
|
| Durations | 720 min |
540 min |
1260 min |
| Complementary | 03:00 - 18:00 |
09:00 - 15:00 |
|
| Durations | 900 min |
360 min |
< |
| Primary | 03:00 - 21:00 |
18:00 - 09:00 |
|
| Durations | 1080 min |
900 min |
1980 min |
| Complementary | 03:00 - 09:00 |
18:00 - 21:00 |
|
| Durations | 360 min |
180 min |
< |
| Primary | 03:00 - 09:00 |
18:00 - 21:00 |
|
| Durations | 360 min |
180 min |
720 min |
| Complementary | 03:00 - 21:00 |
18:00 - 09:00 |
|
| Durations | 1080 min |
900 min |
>= |
Perl
Straight implementation of the described approach.
use strict;
use warnings;
use experimental 'signatures';
sub dur ($event) {
($event->[1] - $event->[0]) % (24 * 60) || 24 * 60;
}
sub conflict_events ($event1, $event2) {
my @events =
map [map {
my ($h, $m) = split /:/;
(60 * $h + $m) % (24 * 60);
} @$_
], $event1, $event2;
dur($events[0]) + dur($events[1]) > dur([$events[0][0], $events[1][1]]);
}
See the full solution to task 2.
J
The distinction is in the vectorized calculations. With a little fantasy you may recognize the similarity to the Perl solution.
NB. convert 'hh:mm hh:mm' to (min min)
event =: >@((24 * 60)&|@((24 60)&#.) L:0)@(> L:1)@(". L:0)@(':'&cutopen L:0)@(' '&cutopen)
NB. "x dur y" calculates the duration between x and y
dur =: (24*60)"_^:(0&=)@((24*60)&|)@-~
NB. check two events - given as a 2x2 matrix of minutes - for conflicts
conflict =: +/@:(dur/"1) > dur/@((<0 1)&|:)
echo conflict event@>"0 '10:00 12:00';'11:00 13:00'
See the full solution.