I’ve been doing the Weekly
Challenges. The
latest
involved breaking lists into groups and building a numerical sequence. (Note that this ends today.)
Task 1: Equal Pairs
You are given an array of integers with even number of elements.
Write a script to divide the given array into equal pairs such that:
a) Each element belongs to exactly one pair. b) The elements present
in a pair are equal.
The simple solution seems to me to take the input list, sort it, then
consume it two at a time and make sure each pair of values fits. (If
not, bail out with an empty list.) Most languages have some sort of
"take two items off the list at a time" functionality, usually called
something like "chunk", and the ones that don't have for
loops with
a step.
Kotlin:
fun shortestdistance(a0: List<Int>): List<List<Int>> {
if (a0.size % 2 != 0) {
return emptyList<List<Int>>()
}
var a = ArrayList(a0)
a.sort()
var out = ArrayList<List<Int>>()
for (t in a.chunked(2)) {
if (t[0] != t[1]) {
return emptyList<List<Int>>()
}
out.add(listOf(t[0], t[0]))
}
return out.toList()
}
Python:
def equalpairs(a0):
a = a0
a.sort()
out = []
for i in range(0, len(a), 2):
if a[i] != a[i+1]:
return []
out.append([a[i], a[i]])
return out
Task 2: DI String Match
You are given a string s, consisting of only the characters "D" and
"I".
Find a permutation of the integers [0 .. length(s)] such that for
each character s[i] in the string: s[i] == 'I' ⇒ perm[i] < perm[i +
1] s[i] == 'D' ⇒ perm[i] > perm[i + 1]
In other words: arrange 0..len(s)
such that each entry after the first is
higher ("I") or lower ("D") than the previous one.
The most enjoyable part of this was working out an algorithm. I ended
up using powers of two; say my first value is 16, then the next can be
16+8 or 16-8, then ±4, etc. Then I map the sorted order of those
values to 0..len(s)
, and use that to create the output.
Perl:
sub distringmatch($a) {
my $v = 1 << (length($a) - 1);
my $wv = $v << 1;
my @out = ($wv);
My first value is always in the mid-point of the potential range.
foreach my $c (split '', $a) {
For each character, add or subtract the current delta value.
if ($c eq 'I') {
$wv += $v
} else {
$wv -= $v;
}
Then halve the delta value and store the current working value.
$v >>= 1;
push @out, $wv;
}
Build a separate list that's all those values in order.
my @r = sort{$::a <=> $::b} @out;
Create a hash to map list values to index values.
my %c = map {$r[$_] => $_} (0..$#r);
Return the index values in that order.
return [map{$c{$_}} @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.