# RogerBW's Blog

The Weekly Challenge 206: Array Time! 05 March 2023

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).

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 - p).abs
o.push(d)
o.push(dl - d)
end
``````

And return the smallest value.

``````  return o.min
end
``````

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.