with Raku

This is my response to The Weekly Challenge #210.

You are given a list of integers.

Write a script to get the maximum points. You are allowed to take out (kill) any integer and remove from the list. However if you do that then all integers exactly one-less or one-more would also be removed. Find out the total of integers removed.

Example 1:

File: /kill-and-win
Write a script to get the maximum points. You are allowed to take out (kill) any integer and remove from the list. However if you do that then all integers exactly one-less or one-more would also be removed. Find out the total of integers removed.

Example 1:

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.

Example 2:
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

You are given an array of integers which can move in right direction if it is positive
and left direction when negative. If two numbers collide then the smaller one will
explode. And if both are same then they both explode. We take the absolute value in
consideration when comparing.

All numbers move at the same speed, therefore any 2 numbers moving in the same direction will never collide.

Write a script to find out who survives the collision.

Example 1:

All numbers move at the same speed, therefore any 2 numbers moving in the same direction will never collide.

Write a script to find out who survives the collision.

Example 1:

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

Example 2:
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.

Example 3:
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:

- The array of values
- At index 0: No collision, so add 1 to the index
- At index 1. Still no collision, so add 1 to the index
- At index 2. Still no collision, so add 1 to the index yet again
- At index 3: Collision. Rule C1 applies, so remove the left value and subtract 1 from the index
- At index 2: Collision: Rule C1 apllies yet again, so we do as above
- At index 1: Collision: Rule C1 apllies yet again
- 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:

File: number-collision#! /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.