by Arne Sommer

# Bagging Scorepoints with Raku

 Published 29. April 2023.

This is my response to The Weekly Challenge #214.

## Challenge #214.1: Rank Score

You are given a list of scores (>=1).

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). ``` Example 2: ```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. ``` Example 3: ```Input: @list = (3,5,4,2) Output: (B,G,S,4) ``` Example 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.

File: rank-scores ```#! /usr/bin/env raku unit sub MAIN (*@scores where @scores.elems > 0 && all(@scores) ~~ UInt, #  :v(:\$verbose)); my %freq = @scores>>.Int.Bag; #  my @sort = @scores.sort.squish.reverse; #  say ": Frequency: { %freq.raku }" if \$verbose; my %gold = (1 => 'G', 2 => 'S', 3 => 'B'); #  my %rank; #  for @sort -> \$score #  { state \$rank = 1; #  %rank{\$score} = %gold{\$rank} // \$rank; #  say ": Score \$score with rank: %rank{\$score} and frequency: %freq{\$score}" if \$verbose; \$rank += %freq{\$score}; #  } say "(" ~ @scores.map({ %rank{\$_} }).join(",") ~ ")"; #  ```

 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.

 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.

 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`.

 The mapping of the G (Gold), S (Silver) and B (Bronze) letters to the ranks 1, 2 and 3.

 The rank of each score will end up here.

 Iterate over the scores (unique, and the highest first).

 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`.

 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 `//`.

 Add the frequency to the rank, so that we are redy for the next iteration (the next score).

 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 are given a list of numbers.

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. ``` Example 2: ```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. ``` Example 3: ```Input: @numbers = (1) Output: 1 ``` Example 4: ```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 ), then iterate over them (in , 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 ) are adjacent (in ). If so, remove them (in ) and update the score (in ).

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.

File: collect-points ```#! /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; #  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; } } } say \$score; #  ```

 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`.

 The score, starting at zero.

 As long as we have numbers left in the array. (We are going to remove them.)

 Get the frequency of each distinct value in the input, as a hash.

 Iterate over the distinct values, in sorted order to ensure the same order each time we run the program.

 The frequency of the current value.

 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`.

 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.

 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`.

 Adjust the score, by adding the squared number of values removed.

 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; #  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; #  } say "ERROR: Unable to reduce: @numbers[]" if @numbers.elems; #  say \$score; ```

 The size of the array, before iterating over the unique values left.

 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.

 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; #  my \$cheat = False; #  while (@numbers.elems) { \$cheat #  ?? ( \$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 #  { my \$val = %freq.keys.sort({ %freq{\$_} }).first; #  %freq{\$val}--; #  \$cheat = True; #  say ": Enable cheat mode on value \$val" if \$verbose; } } say "ERROR: Unable to reduce @numbers[]" if @numbers.elems; #  say \$score; ```

 This variable is now global, so that we kan keep the previous value between iterations - as required by cheat mode.

 Cheat mode is off by default.

 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].

 The `last` (in the previous program) has been replaced by a block.

 Get the value with the lowest frequency. There can be more than one, and this will then give one of them.

 Reduce the count frequency count for the chosen value.

 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.

 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.