I’ve been doing the Weekly
Challenges. The
latest
involved exhaustive searching and an iterative process. (Note that
this ends today.)
Task 1: Odd Sum
You are given an array of positive integers, @ints.
Write a script to return the sum of all possible odd-length
subarrays of the given array. A subarray is a contiguous subsequence
of the array.
This is easy in languages that have a windowing function. (In
languages that don't, I write one.) Raku:
sub oddsum(@a) {
Start by summing the individual elements. No need to go through the
overhead of windowing for that.
my $out = @a.sum;
Start with 3-sequences.
my $l = 3;
Loop if it'll fit in the array.
while ($l <= @a.elems) {
Build each subsequence and add its sum to the total.
for @a.rotor($l => -($l - 1)) -> @s {
$out += @s.sum;
}
Go to the next odd-numbered sequence.
$l += 2;
}
$out;
}
Task 2: Last Element
You are given a array of integers, @ints.
Write a script to play a game where you pick two biggest integers in
the given array, say x and y. Then do the following:
a) if x == y then remove both from the given array
b) if x != y then remove x and replace y with (y - x)
At the end of the game, there is at most one element left.
Return the last element if found otherwise return 0.
The trick for me was to realise that I should remove both elements,
and then add the replacement if needed.
PostScript:
/lastelement {
0 dict begin
b is my working copy of the input list.
/b exch def
{
Inside the loop, sort it.
/b b quicksort def
Pop off the two highest entries.
/b
b apop.right /f exch def
apop.right /s exch def
def
If they aren't equal, push on the difference.
f s gt {
/b b f s sub apush.right def
} if
If we have no entries left return zero.
b length 0 eq {
0
exit
} if
If we have one entry left, return it.
b length 1 eq {
b 0 get
exit
} if
Otherwise continue forever.
} loop
end
} bind def
Full code on
github.