Bagging Scorepoints with Raku
[234] Published 29. April 2023.This is my response to The Weekly Challenge #214.
Challenge #214.1: Rank Score
Write a script to rank each score in descending order. First three will get medals i.e. G (Gold), S (Silver) and B (Bronze). Rest will just get the ranking number.
Using the standard model of giving equal scores equal rank, then advancing that number of ranks.
Example 1:
Input: @scores = (1,2,4,3,5)
Output: (5,4,S,B,G)
Score 1 is the 5th rank.
Score 2 is the 4th rank.
Score 4 is the 2nd rank i.e. Silver (S).
Score 3 is the 3rd rank i.e. Bronze (B).
Score 5 is the 1st rank i.e. Gold (G).
Input: @scores = (8,5,6,7,4)
Output: (G,4,B,S,5)
Score 8 is the 1st rank i.e. Gold (G).
Score 4 is the 4th rank.
Score 6 is the 3rd rank i.e. Bronze (B).
Score 7 is the 2nd rank i.e. Silver (S).
Score 4 is the 5th rank.
Input: @list = (3,5,4,2)
Output: (B,G,S,4)
Input: @scores = (2,5,2,1,7,5,1)
Output: (4,S,4,6,G,S,6)
We need a
way of counting the frequency of each score, and the Raku Bag
type is a good choice here.
A Bag is a sort-of-hash formed from an array where the keys are the distinct values, and the value is the frequency. E.g.
> say <1 1 2 3 x x x x x>.Bag.hash;
{1 => 2, 2 => 1, 3 => 1, x => 5}
Coercing it to a hash makes life easier for us, as we can use it as a traditional hash, but is not really necessary.
See
docs.raku.org/type/Bag
for more information about the Bag type.
#! /usr/bin/env raku
unit sub MAIN (*@scores where @scores.elems > 0
&& all(@scores) ~~ UInt, # [1]
:v(:$verbose));
my %freq = @scores>>.Int.Bag; # [2]
my @sort = @scores.sort.squish.reverse; # [3]
say ": Frequency: { %freq.raku }" if $verbose;
my %gold = (1 => 'G', 2 => 'S', 3 => 'B'); # [4]
my %rank; # [5]
for @sort -> $score # [6]
{
state $rank = 1; # [7]
%rank{$score} = %gold{$rank} // $rank; # [8]
say ": Score $score with rank: %rank{$score} and frequency: %freq{$score}"
if $verbose;
$rank += %freq{$score}; # [9]
}
say "(" ~ @scores.map({ %rank{$_} }).join(",") ~ ")"; # [10]
[1] At least one element (in this slurpy array), and all
the values must be of the UInt (Unsigned Int) type.
See
docs.raku.org/type/UInt for
more information about the Uint type.
[2] Get the frequency, via Bag and coerce the result to a hash
courtesy of the % sigil in the assignment. Also note the coersion
of the values to integers, so that verbose mode does not report the pesky
IntStr type.
[3]
The scores, without duplicates, with the highest first.
Note the use of the fast(ish) squish to remove duplicates that
come together, whereas the general unique will work on unorted
data (at a higher computational cost).
See
docs.raku.org/routine/squish
for more information about squish.
See
docs.raku.org/routine/unique
for more information about unique.
[4] The mapping of the G (Gold), S (Silver) and B (Bronze) letters to the ranks 1, 2 and 3.
[5] The rank of each score will end up here.
[6] Iterate over the scores (unique, and the highest first).
[7] A state variable for the rank of the current
score. We start at 1 (Gold).
See
docs.raku.org/syntax/state for
more information about the variable declarator state.
[8] The rank of the current score, looking it up in the hash
(for values 1, 2 or 3), using // to default to the numeric value.
See
docs.raku.org/routine/$SOLIDUS$SOLIDUS
for more information about the Defined Or operator //.
[9] Add the frequency to the rank, so that we are redy for the next iteration (the next score).
[10] Print the result, mapping each score to the rank (with map).
Running it:
$ ./rank-scores 1 2 4 3 5
(5,4,S,B,G)
$ ./rank-scores 8 5 6 7 4
(G,4,B,S,5)
$ ./rank-scores 3 5 4 2
(B,G,S,4)
$ ./rank-scores 2 5 2 1 7 5 1
(4,S,4,6,G,S,6)
Looking good.
With verbose mode:
$ ./rank-scores -v 1 2 4 3 5
: Frequency: {"1" => 1, "2" => 1, "3" => 1, "4" => 1, "5" => 1}
: Score 5 with rank: G and frequency: 1
: Score 4 with rank: S and frequency: 1
: Score 3 with rank: B and frequency: 1
: Score 2 with rank: 4 and frequency: 1
: Score 1 with rank: 5 and frequency: 1
(5,4,S,B,G)
$ ./rank-scores -v 8 5 6 7 4
: Frequency: {"4" => 1, "5" => 1, "6" => 1, "7" => 1, "8" => 1}
: Score 8 with rank: G and frequency: 1
: Score 7 with rank: S and frequency: 1
: Score 6 with rank: B and frequency: 1
: Score 5 with rank: 4 and frequency: 1
: Score 4 with rank: 5 and frequency: 1
(G,4,B,S,5)
$ ./rank-scores -v 3 5 4 2
: Frequency: {"2" => 1, "3" => 1, "4" => 1, "5" => 1}
: Score 5 with rank: G and frequency: 1
: Score 4 with rank: S and frequency: 1
: Score 3 with rank: B and frequency: 1
: Score 2 with rank: 4 and frequency: 1
(B,G,S,4)
$ ./rank-scores -v 2 5 2 1 7 5 1
: Frequency: {"1" => 2, "2" => 2, "5" => 2, "7" => 1}
: Score 7 with rank: G and frequency: 1
: Score 5 with rank: S and frequency: 2
: Score 2 with rank: 4 and frequency: 2
: Score 1 with rank: 6 and frequency: 2
(4,S,4,6,G,S,6)
Challenge #214.2: Collect Points
You will perform a series of removal operations. For each operation, you remove from the list N (one or more) equal and consecutive numbers, and add to your score N × N.
Determine the maximum possible score.
Example 1:
Input: @numbers = (2,4,3,3,3,4,5,4,2)
Output: 23
We see three 3's next to each other so let us remove that first and
collect 3 x 3 points.
So now the list is (2,4,4,5,4,2).
Let us now remove 5 so that all 4's can be next to each other and
collect 1 x 1 point.
So now the list is (2,4,4,4,2).
Time to remove three 4's and collect 3 x 3 points.
Now the list is (2,2).
Finally remove both 2's and collect 2 x 2 points.
So the total points collected is 9 + 1 + 9 + 4 => 23.
Input: @numbers = (1,2,2,2,2,1)
Output: 20
Remove four 2's first and collect 4 x 4 points.
Now the list is (1,1).
Finally remove the two 1's and collect 2 x 2 points.
So the total points collected is 16 + 4 => 20.
Input: @numbers = (1)
Output: 1
Input: @numbers = (2,2,2,1,1,2,2,2)
Output: 40
Remove two 1's = 2 x 2 points.
Now the list is (2,2,2,2,2,2).
Then reomove six 2's = 6 x 6 points.
Note that the first version of my program works with the four examples, but it does not work for all variants of input values. We will get back to that.
The general idea of this program is to collect all the unique values
and their frequencies (in [4]), then iterate over them (in [5], and
note the sort so that we get the same order each time
we run the program), and checking if all the instances of that value
(in [6]) are adjacent (in [8]). If so, remove them (in [9]) and
update the score (in [10]).
This is done in a loop, as long as we have values left. The first
example shows why we need this loop, with three iterations (of
the while loop) to get rid of all the numbers.
The first iteration starts with the whole array. The first row (the grey
boxes) is the current numbers, and the second row (the blue boxes) is
the values and their frequencies. The third row starts with a «2», the
first value in the inner for loop. We locate he first «2»;
there should be two of them, but they are not adjacent (highlighted with
red). The next value is «3», and here we locate all three adjacent to
each other (highlighted with green). We remove them, and get the
all-yellow row below. The next value is «4», but the three of them are
not adjacent. The final value is «5», of which there is only one.
It is removed.
The second while iteration has two distinct values only,
but we cannot remove the «2»s. The «4»s are adjacent, and are removed.
The third and final while iteration removes the «2»s, and we
are done as we have removed all the numbers.
#! /usr/bin/env raku
unit sub MAIN (*@numbers where @numbers.elems > 0
&& all(@numbers) ~~ Numeric, # [1]
:v(:$verbose));
my $score = 0; # [2]
while (@numbers.elems) # [3]
{
my %freq = @numbers.Bag; # [4]
for %freq.keys.sort -> $value # [5]
{
my $freq = %freq{$value}; # [6]
my $index = @numbers.first($value, :k); # [7]
if all(@numbers[$index .. $index + $freq -1]) eq $value # [8]
{
sink @numbers.splice($index, $freq); # [9]
$score += $freq * $freq; # [10]
say ": Removed the value $value ($freq items, at index: $index .. \
{ $index + $freq -1}). New score: $score" if $verbose;
}
}
}
say $score; # [11]
[1] A slurpy array, with at least one element. All the
elements must be numeric (smartmatching against the Numeric
type).
See
docs.raku.org/routine/Numeric
for more information about Numeric.
[2] The score, starting at zero.
[3] As long as we have numbers left in the array. (We are going to remove them.)
[4] Get the frequency of each distinct value in the input, as a hash.
[5] Iterate over the distinct values, in sorted order to ensure the same order each time we run the program.
[6] The frequency of the current value.
[7] Get the index of the first occurence (the name
first should be self describing) of the current value.
See
docs.raku.org/routine/first
for more information about first.
[8] Get an array slice (the [from .. to] part),
with the same size as the frequency of the current value. Then we check if
all those values are equal to the current value with an all
junction. Note the string comparison (eq) instead of numeric
comparison (==), to make it easier to rewrite the program to
support non-numeric values as well - if we were to be so inclined at a later
date.
[9]
If it is, we remove those repeating values (with
splice). This will return the removed values, and we get explicit
rid of them with sink.
See
docs.raku.org/routine/splice
for more information about splice.
See
docs.raku.org/routine/sink for
more information about sink.
[10] Adjust the score, by adding the squared number of values removed.
[11] Print the score.
Running it:
$ ./collect-points 2 4 3 3 3 4 5 4 2
23
$ ./collect-points 1 2 2 2 2 1
20
$ ./collect-points 1
1
$ ./collect-points 2 2 2 1 1 2 2 2
40
Looking good.
With verbose mode:
$ ./collect-points -v 2 4 3 3 3 4 5 4 2
: Removed the value 3 (3 items, at index: 2 .. 4). New score: 9
: Removed the value 5 (1 items, at index: 3 .. 3). New score: 10
: Removed the value 4 (3 items, at index: 1 .. 3). New score: 19
: Removed the value 2 (2 items, at index: 0 .. 1). New score: 23
23
$ ./collect-points -v 1 2 2 2 2 1
: Removed the value 2 (4 items, at index: 1 .. 4). New score: 16
: Removed the value 1 (2 items, at index: 0 .. 1). New score: 20
20
$ ./collect-points -v 1
: Removed the value 1 (1 items, at index: 0 .. 0). New score: 1
1
$ ./collect-points -v 2 2 2 1 1 2 2 2
: Removed the value 1 (2 items, at index: 3 .. 4). New score: 4
: Removed the value 2 (6 items, at index: 0 .. 5). New score: 40
40
Now to data that breaks this approach:
$ ./collect-points 1 2 1 2
^C
The program will run forever, without removing values.
The next version detects this situation, without doing anything with it - except bailing out with a suitable error message:
File: collect-points-last
#! /usr/bin/env raku
unit sub MAIN (*@numbers where @numbers.elems > 0
&& all(@numbers) ~~ Numeric,
:v(:$verbose));
my $score = 0;
while (@numbers.elems)
{
my %freq = @numbers.Bag;
my $size = @numbers.elems; # [1]
for %freq.keys.sort -> $value
{
my $freq = %freq{$value};
my $index = @numbers.first($value, :k);
if all(@numbers[$index .. $index + $freq -1]) eq $value
{
sink @numbers.splice($index, $freq);
$score += $freq * $freq;
say ": Removed the value $value ($freq items, at index: $index .. \
{ $index + $freq -1}). New score: $score" if $verbose;
}
}
last if @numbers.elems == $size; # [2]
}
say "ERROR: Unable to reduce: @numbers[]" if @numbers.elems; # [3]
say $score;
[1] The size of the array, before iterating over the unique values left.
[2] Exit the while loop if the array has the same size as before the for loop, tellingf us that it was unable to remove any values.
[3] Print the remaining values.
Running it with the values that caused an infinite loop:
$ ./collect-points-last -v 1 2 1 2
ERROR: Unable to reduce 1 2 1 2
0
Another one, where we get a partial result before it reaches the infinite loop:
$ ./collect-points-last -v 1 2 1 2 3 3 3 3 4 4 4 4 5 6 7 6
: Removed the value 3 (4 items, at index: 4 .. 7). New score: 16
: Removed the value 4 (4 items, at index: 4 .. 7). New score: 32
: Removed the value 5 (1 items, at index: 4 .. 4). New score: 33
: Removed the value 7 (1 items, at index: 5 .. 5). New score: 34
: Removed the value 6 (2 items, at index: 4 .. 5). New score: 38
ERROR: Unable to reduce 1 2 1 2
38
This is quite easy to fix, actually.
File: collect-points-cheat
#! /usr/bin/env raku
unit sub MAIN (*@numbers where @numbers.elems > 0
&& all(@numbers) ~~ Numeric,
:v(:$verbose));
my $score = 0;
my %freq; # [1]
my $cheat = False; # [2]
while (@numbers.elems)
{
$cheat # [3]
?? ( $cheat = False ) # [3a]
!! ( %freq = @numbers.Bag ); # [3b]
my $size = @numbers.elems;
for %freq.keys.sort -> $value
{
my $freq = %freq{$value};
my $index = @numbers.first($value, :k);
if all(@numbers[$index .. $index + $freq -1]) eq $value
{
sink @numbers.splice($index, $freq);
$score += $freq * $freq;
say ": Removed the value $value ($freq items, at index: $index .. \
{ $index + $freq -1}). New score: $score" if $verbose;
}
}
if @numbers.elems == $size # [4]
{
my $val = %freq.keys.sort({ %freq{$_} }).first; # [5]
%freq{$val}--; # [6]
$cheat = True; # [7]
say ": Enable cheat mode on value $val" if $verbose;
}
}
say "ERROR: Unable to reduce @numbers[]" if @numbers.elems; # [8]
say $score;
[1] This variable is now global, so that we kan keep the previous value between iterations - as required by cheat mode.
[2] Cheat mode is off by default.
[3] Has cheat mode been enabled? If so, unset it (ready for the next iteration) [3a] and keep the old frequency hash. If not, compute the frequency hash again [3b].
[4] The last (in the previous program) has been replaced
by a block.
[5] Get the value with the lowest frequency. There can be more than one, and this will then give one of them.
[6] Reduce the count frequency count for the chosen value.
[7] Enable cheat mode, so that the next iteration uses the modifed frequency count. This is done to unlock a stalemate. Note that it may take several iterations for this to help, but it will help.
[8] I have kept this one, just to be sure...
Running it on the previously unresolved values:
$ ./collect-points-cheat -v 1 2 1 2
: Enable cheat mode on value 1
: Removed the value 1 (1 items, at index: 0 .. 0). New score: 1
: Removed the value 1 (1 items, at index: 1 .. 1). New score: 2
: Removed the value 2 (2 items, at index: 0 .. 1). New score: 6
6
$ ./collect-points-cheat -v 1 2 1 2 3 3 3 3 4 4 4 4 5 6 7 6
: Removed the value 3 (4 items, at index: 4 .. 7). New score: 16
: Removed the value 4 (4 items, at index: 4 .. 7). New score: 32
: Removed the value 5 (1 items, at index: 4 .. 4). New score: 33
: Removed the value 7 (1 items, at index: 5 .. 5). New score: 34
: Removed the value 6 (2 items, at index: 4 .. 5). New score: 38
: Enable cheat mode on value 1
: Removed the value 2 (1 items, at index: 1 .. 1). New score: 39
: Removed the value 1 (2 items, at index: 0 .. 1). New score: 43
: Removed the value 2 (1 items, at index: 0 .. 0). New score: 44
44
This looks reasonable...
Note that I cannot guarantee that the result will be correct (as in the highest possible score), though.
And that's it.