Killing Numbers with Raku

This is my response to The Weekly Challenge #210.

Challenge #210.1: Kill and Win

Input: @int = (2, 3, 1)
Output: 6

First we delete 2 and that would also delete 1 and 3. So the maximum
points we get is 6.

Input: @int = (1, 1, 2, 2, 2, 3)
Output: 11

First we delete 2 and that would also delete both the 1's and the 3.
Now we have (2, 2).

Then we delete another 2 and followed by the third deletion of 2. So
the maximum points we get is 11.

#! /usr/bin/env raku

unit sub MAIN (*@int where @int.elems > 0 && @int.all ~~ UInt,  # [1]
               :v($verbose));

my $min = @int.min + 1;                                         # [2]
my $max = @int.max - 1;                                         # [3]

my $score = -Inf;                                               # [4]
my $target;                                                     # [5]

for $min .. $max -> $value                                      # [6]
{ 
  my $sum = @int.grep({ $value -1 <= $_ <= $value +1 }).sum;    # [7]
  
  if $sum > $score                                              # [8]
  {
    $target = $value;                                           # [8a]
    $score  = $sum;                                             # [8b]
    say ": + $value with sum $sum" if $verbose;
  }
  elsif $verbose
  {
    say ": - $value with sum $sum";
  }
  
}

say $score;                                                     # [9]

[1] Ensure at least one element, and they must be of the UInt (Unsiged Int) type. Negative values would play havoc with the sum, so I have decided to make them illegal. Zero could have been illegal as well, but not with this type.

See docs.raku.org/type/UInt for more information about the Uint type.

[2] We are (in [6]) iterating over all the possible choices for the number to kill. Here we get the lowest value, which is one above the minimum in the array - as the minimum is included in the elimination anyway by the +/- 1 rule.

[3] The highest value in the iteration (in [6]).

[4] The higest score, starting at the absolute minimum.

[5] The value that we killed to get the highest score.

[6] Iterate over the possible values.

Note that we could optimise here. If we have large gaps between the values, we would get a lot of iterations doing nothing. E.g. «1,1,1000,1000» would iterate over all the values from 2 to 999, and only the first and last one would make any sense. We could remove dumplicates, replace all the values with the one below and above, remove duplicates again, and iterate over that list. Fell free to amend the program to do so..

[7] Get the sum. We use grep to get the value itself, and the one below and above - zero, one or more of each. Then we use sum to get the sum.

[8] Do we have a new maximum? If so, save the killed value [8a] and the score [8b].

[9] Print the maximum.

Running it:

$ ./kill-and-win 2 3 1
6

$ ./kill-and-win 1 1 2 2 2 3
11

Looking good.

With verbose mode:

$ ./kill-and-win -v 2 3 1
: + 2 with sum 6
6

$ ./kill-and-win -v 1 1 2 2 2 3
: + 2 with sum 11
11

That was not very exciting...

Let us try with a greater span in the numbers:

$ ./kill-and-win -v 1 2 3 4 5 6 7 8 9 10
: + 2 with sum 6
: + 3 with sum 9
: + 4 with sum 12
: + 5 with sum 15
: + 6 with sum 18
: + 7 with sum 21
: + 8 with sum 24
: + 9 with sum 27
27

$ ./kill-and-win -v 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12
: + 2 with sum 16
: - 3 with sum 0
: - 4 with sum 0
: - 5 with sum 0
: - 6 with sum 0
: - 7 with sum 0
: - 8 with sum 0
: - 9 with sum 0
: - 10 with sum 0
: - 11 with sum 12
16

Challenge #210.2: Number Collision

Input: @list = (2, 3, -1)
Output: (2, 3)

The numbers 3 and -1 collide and -1 explodes in the end. So we are left
with (2, 3).

Input: @list = (3, 2, -4)
Output: (-4)

The numbers 2 and -4 collide and 2 explodes in the end. That gives us
(3, -4). Now the numbers 3 and -4 collide and 3 explodes. Finally we
are left with -4.

Input: @list = (1, -1)
Output: ()

The numbers 1 and -1 both collide and explode. Nothing left in the end.

I assume that zero is regarded as positive, or non-negative if we are pedantic.

If we consider the values as an array, which they are when we write a program at least, then we do not have to move positive values to the right at all. We can move negative values to the left only, and that will suffice.

We are starting at index 0, comparing the current value - the one at that index, called left, and shown as yellow - and the one at the right side of it, called right, and shown as red (collision) or green (no collision)). We increase the index (according to rules described below), until we have reached the end. Then we have the result.

The rule of collision applies if the left value is positive, and the right on is negative. We have three variants, shown here at an arbitrary position in the array (by the «...» indicating zero or nmore values).

C1 shows what happens if the absolute value of the right value is higher than the left value: We remove the left value, and keep the index.

C2 shows what happens if the absolute value of the right value is the same as the left value: We remove both values, and decrease the index by one. This is a backtrack, indexwise.

C3 shows what happens if the absolute value of the right value is lower than the left value: We remove the right value, and keep the index.

If we do not have a collision (N1, N2 or N3), we just increase the index by one.

Let us do an example:

1. The array of values
2. At index 0: No collision, so add 1 to the index
3. At index 1. Still no collision, so add 1 to the index
4. At index 2. Still no collision, so add 1 to the index yet again
5. At index 3: Collision. Rule C1 applies, so remove the left value and subtract 1 from the index
6. At index 2: Collision: Rule C1 apllies yet again, so we do as above
7. At index 1: Collision: Rule C1 apllies yet again
8. At index 0: No right value, so we are finished

Let us jump the gun, and show the verbose output of the program when we give it this array:

$ ./number-collision -v 1 2 3 4 -5
: 1,2,3,4,-5 index 0 
: 1,2,3,4,-5 index 1 
: 1,2,3,4,-5 index 2 
: 1,2,3,4,-5 index 3 < Remove 4 at index 3 -> 1,2,3,-5
: 1,2,3,-5 index 2 < Remove 3 at index 2 -> 1,2,-5
: 1,2,-5 index 1 < Remove 2 at index 1 -> 1,-5
: 1,-5 index 0 < Remove 1 at index 0 -> -5
(-5)

Then the program:

#! /usr/bin/env raku

unit sub MAIN (*@list where @list.elems > 0 && @list.all ~~ Int,  # [1]
               :v($verbose));

my $index = 0;                      # [2]

loop                                # [3]
{
  last unless @list.elems;          # [4]
  last if $index == @list.end;      # [5]

  my $left  = @list[$index];        # [6]
  my $right = @list[$index +1];     # [7]

  print ": { @list.join(",") } index $index " if $verbose;

  if $left >= 0 && $right < 0       # [8]
  {
    if $left > $right.abs           # [9]
    {
      @list.splice($index+1,1);     # [9a]
      say "> Remove $right at index {$index+1} -> { @list.join(",") }"
        if $verbose;
    }
    elsif $left < $right.abs        # [10]
    {
      @list.splice($index,1);       # [10a]
      say "< Remove $left at index $index -> { @list.join(",") }"
        if $verbose;
      $index-- unless $index == 0;  # [10b]
    }
    else                            # [11]
    {
      @list.splice($index,2);       # [11a]
      say " = Remove $left and $right at index $index and { $index +1 } -> \
        { @list.join(",") }" if $verbose; 
      $index-- unless $index == 0;  # [11b]
    }
  }
  else                              # [12]
  {  
    say "" if $verbose;
    $index++;                       # [12a]
  }
}

say "({ @list.join(",") })";        # [13]

[1] Ensure that all the values (of which there are at lerast 1) are integers.

[2] We start at iondex 0.

[3] An eternal loop. (We could have added [4] and/or [5] in a conditional while loop instead, but this way mat ve considered more readable.

[4] We are finished when the list is empty, as it is in the third example.

[5] We are finished when the index is at the end (i.e. that it does not have a right value; see [7]).

[6] The left value.

[7] The right value.

[8] Do we have a collision?

[9] Yes, check for the C1 rule. If it is satisfied, we use splice to get rid of the loosing value [9b].

See docs.raku.org/routine/splice for more information about splice.

[10] Yes, check for the C3 rule. If that one is satisfied, we get rid of the loosing value [10a] and we adjust the index to the left (unless we are at the start) [10b].

[11] Yes, the C3 rule. Get rid of both values [11a] and adjust the index to the left (again, unless we are at the start [11b].

[12] No (no collision). Adjust the index to the right.

[13] print the reulting list, which may be empty.

Running it:

$ ./number-collision 2 3 -1
(2,3)

$ ./number-collision 3 2 -4
(-4)

$ ./number-collision 1 -1
()

Looking good.

Even better with verbose mode:

$ ./number-collision -v 2 3 -1
: 2,3,-1 index 0 
: 2,3,-1 index 1 > Remove -1 at index 2 -> 2,3
(2,3)

$ ./number-collision -v 3 2 -4
: 3,2,-4 index 0 
: 3,2,-4 index 1 < Remove 2 at index 1 -> 3,-4
: 3,-4 index 0 < Remove 3 at index 0 -> -4
(-4)

$ ./number-collision -v 1 -1
: 1,-1 index 0  = Remove 1 and -1 at index 0 and 1 -> 
()

And that's it.