RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved date overlaps and combination searches. (Note that this is open until 23 October 2022.)

Task 1: Days Together

Two friends, Foo and Bar gone on holidays seperately to the same city. You are given their schedule i.e. start date and end date.

To keep the task simple, the date is in the form DD-MM and all dates belong to the same calendar year i.e. between 01-01 and 31-12. Also the year is non-leap year. Also both dates are inclusive.

Write a script to find out for the given schedule, how many days they spent together in the city, if at all.

First, of course, we have to convert the text format into a date. (Kotlin, Rust's chrono, and Perl's DateTime all have parsers available; other languages offer regexps or substrings.) The Raku version:

sub s2date($ds) {
    if ($ds ~~ /^(\d+)\-(\d+)$/) {
        return Date.new(year => 2022,
                        month => $1,
                        day => $0);
    }
    die "$ds is not a recognisable date\n";
}

The core calculation is to take the pair of start dates and sort them into starts, and the pair of end dates and sort them into ends. Only two matter: the earlier end date (ends[0]) and the later start date (starts[1]). If ends[0] falls on or after starts[1], then there's an overlap, the size of which is the number of days between them plus 1; otherwise return 0.

sub daystogether(@a,@b) {
    my @starts = [s2date(@a[0]), s2date(@b[0])].sort;
    my @ends = [s2date(@a[1]), s2date(@b[1])].sort;
    if (@ends[0] > @starts[1]) {
        return @ends[0]-@starts[1]+1;
    } else {
        return 0;
    }
}

The other languages are similar.

Task 2: Magical Triplets

You are given a list of positive numbers, @n, having at least 3 numbers.

Write a script to find the triplets (a, b, c) from the given list that satisfies the following rules.

1. a + b > c
2. b + c > a
3. a + c > b
4. a + b + c is maximum.

Some languages have an easily-accessible combination generator: Rust, Ruby, Raku, Perl with Algorithm::Combinatorics and (shown here) Python, so it's just a matter of an exhaustive search.

def magicaltriplets(a):
  out = []
  mv = 0
  for b in combinations(a, 3):
    if b[0] + b[1] > b[2] and b[1] + b[2] > b[0] and b[0] + b[2] > b[1]:
       v = sum(b)
       if v > mv:
         mv = v
         out = b
  return list(reversed(sorted(out)))

For the others, such as Kotlin, I lay out the loops explicitly, but the core is the same:

fun magicaltriplets(a: List<Int>): List<Int> {
    var out = listOf<Int>()
    var mv = 0
    for (ai in 0..a.size-3) {
        for (bi in ai+1..a.size-2) {
            for (ci in bi+1..a.size-1) {
                if (a[ai] + a[bi] > a[ci] &&
                    a[bi] + a[ci] > a[ai] &&
                    a[ai] + a[ci] > a[bi]) {
                    var v = a[ai] + a[bi] + a[ci]
                    if (v > mv) {
                        mv = v
                        out = listOf(a[ai], a[bi], a[ci])
                    }
                }
            }
        }
    }
    return out.sorted().reversed().toList()
}

(Since the examples list only a single triplet, not a list of lists, I calculate only the first maximum value.)

Full code on github.