RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved lots of combinatorial searches. (Note that this closes today.)

Both of these problems are best solved with combinatorics. I could have done task 1 in the languages that don't have a readily available combination generator as a fixed depth task (nested for loops), and task 2 ditto with proper combination and permutation generators, but I've done both of these before, I know I can do them (because I've coded up both of these algorithms for my PostScript utility libraries) and this week I lacked enthusiasm for doing it again. So no JavaScript, Kotlin or Lua this time, though eventually I'll probably write the relevant library functions for them (also cartesian product maybe).

Task 1: Shortest Time

You are given a list of time points, at least 2, in the 24-hour clock format HH:MM.

Write a script to find out the shortest time in minutes between any two time points.

We did full time-date parsing in challenge 178 task 2, but this is just hour-and-minute stuff.

Ruby:

def shortesttime(n)
  dl = 1440

Convert each time to a number of minutes past midnight.

  ni = []
  for x in n do
    ni.push(x[0..1].to_i * 60 + x[3..4].to_i)
  end

For each combination of two times, calculate the time difference in both directions (i.e. A to B and B to A, crossing midnight if necessary).

  o = []
  ni.combination(2) do |p|
    d = (p[0] - p[1]).abs
    o.push(d)
    o.push(dl - d)
  end

And return the smallest value.

  return o.min
end

Task 2: Array Pairings

You are given an array of integers having even number of elements..

Write a script to find the maximum sum of the minimum of each pairs.

This was rather fun to work out. Here it is in Raku:

sub arraypairing(@n) {

Make sure we do have an even number of elements.

    my $nl = @n.elems;
    if ($nl % 2 == 1) {
        return 0;
    }
    my $hl = $nl div 2;
    my @out;

Split the array in half in every possible way (combination generator on the array's indices, so that I can easily generate the half that's excluded from the combination too). This does twice as much work as it needs to: it'll generate [a, b] leaving [c, d] and [c, d] leaving [a, b]. I suspect it would have made sense to generate pa based on the combinations on the range of indices from 1 to nl-1, then add index zero to it.

    for [0 .. $nl-1].combinations($hl) -> @px {
        my @pa = map {@n[$_]},@px;
        my $ps = @px.Set;
        my @pb = map {@n[$_]}, grep {$ps{$_}:!exists}, (0 .. $nl-1);

Now @pa and @pb are disjoint lists each consisting of half the entries. Now we take every possible pairing between the two, by working through the permutations of @pa, and add up the values of the minimum of each pair.

        for @pa.permutations -> @pp {
            my $s = 0;
            for (0 .. $hl-1) -> $i {
                $s += min(@pp[$i], @pb[$i]);
            }
            @out.push($s);
        }
    }

Then return the largest one. (As in task 1, if I were working on large data sets I'd just store a single value, out = max(out, s).)

    return max(@out);
}

Full code on github.