Task — Number collision

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.

Analysis

Let's consider an example:
12, -2, -9, -6, -12, 10, 6, 1, 1, -12, 14

The only places where an collision occurs are where a positive (+ve) number is followed by a negative (-ve) number - for example 12, -2 and 1, -12. The collision has three possible outcomes: the +ve number dies, the -ve number dies or both die.

It seems simplest to repeatedly work along the array looking for these collision sites and deleting as specified in the challenge until a pass leaves it unchanged. This means that all the -ve numbers (if any) are now at the left hand end and the +ve ones (if any) are at the right.

From a practical viewpoint, I set dead entries to zero, and then at the end of each pass I use

to eliminate any zeroes. I can then stop looking when a pass results in no change to the length of the list.

Try it 

Script

#!/usr/bin/perl

use v5.16;       # The Weekly Challenge - 2023-03-27
use utf8;        # Week 210 task 2 - Number collision
use strict;      # Peter Campbell Smith
use warnings;    # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($j, @list);

number_collision(2, 3, -1);
number_collision(3, 2, -4);
number_collision(1, -1);
number_collision(1, -1, 2, -2, 4, -4);
number_collision(12, -2, -9, -6, -12, 10, 6, 1, 1, -12, 14);

for $j (0 .. 10) {
    $list[$j] = int(rand(15)) - 7;
}
number_collision(@list);


sub number_collision {
    
    my (@list, $last, $size, $j, $k);
    
    # loop over all the numbers, setting them to 0 if they die
    @list = @_;
    while (1) {
        
        # loop over values
        $size = scalar @list;
        for $j (0 .. $size - 2) {
            
            # skip unless this is +ve and next is -ve
            $k = $j + 1;
            next unless ($list[$j] > 0 and $list[$k] < 0);
            
            # same absolute value - both die
            if (abs($list[$j]) == abs($list[$k])) {
                $list[$j] = $list[$k] = 0;
                
            # this kills next
            } elsif (abs($list[$j]) < abs($list[$k])) {
                $list[$j] = 0;
                
            # next kills this
            } else {
                $list[$k] = 0;
            }   
        }
        
        # eliminate zeroes and exit if nothing's changed
        @list = grep { $_ != 0 } @list;
        last if scalar @list == $size;
    }

    # show results
    say qq[\nInput:  \@list = (] . join(', ', @_) . q[)];
    say qq[Output: (] . join(', ', @list) . qq[)];
}

Output

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

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

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

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

Input:  @list = (12, -2, -9, -6, -12, 10, 6, 1, 1, -12, 14)
Output: (-12, 14)

Input:  @list = (5, 5, -3, 7, 6, -7, 4, 7, 3, -6, 7)
Output: (5, 5, 4, 7, 7)