I’ve been doing the Weekly
Challenges. The
latest
involved quinelikes and list processing. (Note that this ends today.)
Task 1: Self Spammer
Write a program which outputs one word of its own script / source
code at random. A word is anything between whitespace, including
symbols.
Clearly this is an allied trade to the quine (a program that produces
its own source). And I can see the value of this kind of game. But
it's really not my style, so I didn't play.
Task 2: Order Game
You are given an array of integers, @ints
, whose length is a power of 2.
Write a script to play the order game (min and max) and return the
last element.
Examples explain that "the order game (min and max)" consists of
running a sliding window of 2 along the list, and taking either the
lower or the higher value in alternation. This is done repeatedly
until there is only one value left.
One could probably do this in place with splice operations, but it
seemed more straightforward to have one list for reading and one for
writing. For example in Perl (using the slightly clumsy slideatatime
from List::MoreUtils
):
sub ordergame($a) {
Initialise my working copy of the list.
my @p = @{$a};
While there are at least two entries left,
while (scalar @p > 1) {
Make a new (output) list and initialise the flip-flop.
my @q;
my $mm = 1;
Iterate over the overlapping pairs of list elements.
my $dd = slideatatime 1, 2, @p;
while (my @j = $dd->()) {
Take minimum or maximum and flip the state.
if (scalar @j == 2) {
if ($mm) {
push @q, min(@j);
} else {
push @q, max(@j);
}
$mm = 1 - $mm;
}
}
Finally, copy the output list to the working copy, and ultimately
return the sole entry.
@p = @q;
}
return $p[0];
}
I'm rather fond of the PostScript implementation. It uses the same
algorithm as above, but instead of having two explicitly-named lists,
it uses the stack to build up the output list and then assigns it to
the working copy. (My rotor
is inspired by Raku's, but doesn't
return partial groups.)
/ordergame {
0 dict begin
/p exch def
{
p length 1 le {
exit
} if
/mm true def
[
p 2 -1 rotor {
aload pop
mm {
min
} {
max
} ifelse
/mm mm not def
} forall
] /p exch def
} loop
p 0 get
end
} bind def
Full code on
github.