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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.