Peter
Peter Campbell Smith

Flipping members

Weekly challenge 242 — 6 November 2023

Week 242: 6 Nov 2023

Task 1

Task — Missing members

You are given two arrays of integers. Write a script to list the members of each array which are missing from the other array.

Examples


Example 1
Input: @arr1 = (1, 2, 3)
       @arr2 = (2, 4, 6)
Output: ([1, 3], [4, 6])

(1, 2, 3) has 2 members (1, 3) missing in the array (2, 4, 6).
(2, 4, 6) has 2 members (4, 6) missing in the array (1, 2, 3).

Example 2
Input: @arr1 = (1, 2, 3, 3)
       @arr2 = (1, 1, 2, 2)
Output: ([3])

(1, 2, 3, 3) has 2 members (3, 3) missing in the array (1, 1, 2, 2). Since they are same, keep just one.
(1, 1, 2, 2) has 0 member missing in the array (1, 2, 3, 3).

Analysis

This is easily stated and fairly easily solved, but it is harder to come up with a good solution that would work efficiently if the arrays had, thousands of members. In such a case I can think of two approaches:

1 Sort each array and work steadily along both of them in parallel, noting where a value was missinng from either.

2 Use a hash and build $exists{$j} for every $j in @arr2, and then match @arr1 sequentially aginst the hash.

But our arrays are small and I didn't use either of those approaches. Mine simply does this:

for $j (@two) {
  @one = grep { $_ != $j } @one;
}

This iterates $j over the members of @two and creates a new @one which omits any $two[$j]. For this to give the required answer, the arrays have to be made unique, and I used the handy module List::Uniq for that.

And, of course, all of these solutions need to be done again with @arr1 and @arr2 swapped.

Try it 

Try running the script with any input:



example: 1, 2, 3, 4, 5



example: 3, 4, 5, 6, 7

Script


#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-11-06
use utf8;     # Week 242 task 1 - Missing members
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use List::Uniq 'uniq';

missing_members([1, 2, 3], [2, 4, 6]);
missing_members([1, 2, 3, 3], [1, 1, 2, 2]);
missing_members([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 4, 6, 8, 10]);

# make bigger example
my ($j, @arr1, @arr2);
for $j (0 .. 29) {
    push @arr1, int(rand(15) + 1);
    push @arr2, int(rand(15) + 1);
}
missing_members(\@arr1, \@arr2);

sub missing_members {
    
    printf('%sInput:  ([%s], [%s])%s', "\n", join(', ', @{$_[0]}), join(', ', @{$_[1]}), "\n");
    printf('Output: ([%s], [%s])%s', mm($_[0], $_[1]), mm($_[1], $_[0]), "\n");
}

sub mm {
    
    my (@one, @two, $j);
    
    # make each array unique
    @one = uniq(@{$_[0]});
    @two = uniq(@{$_[1]});
    
    # delete from @one anything that occurs in @two
    for $j (@two) {
        @one = grep { $_ != $j } @one;
    }
    
    # and return what's left
    return join(', ', @one);
}
    

Output


Input:  ([1, 2, 3], [2, 4, 6])
Output: ([1, 3], [4, 6])

Input:  ([1, 2, 3, 3], [1, 1, 2, 2])
Output: ([3], [])

Input:  ([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 4, 6, 8, 10])
Output: ([1, 3, 5, 7, 9], [10])

Input:  ([13, 7, 6, 9, 7, 8, 11, 1, 14, 7, 15, 12, 11, 7, 5, 4, 1, 7, 11, 5, 14, 3, 8, 8, 6, 3, 15, 9, 12, 11], 
         [7, 5, 12, 10, 1, 5, 9, 12, 7, 9, 8, 3, 14, 14, 10, 15, 10, 10, 6, 7, 10, 15, 1, 8, 8, 14, 15, 1, 2, 11])
Output: ([13, 4], [10, 2])


 

Any content of this website which has been created by Peter Campbell Smith is in the public domain