Camel
Peter
Peter Campbell Smith

Arrays and arrays

Weekly challenge 310 — 24 February 2025

Week 310: 24 Feb 2025

Task 1

Task — Arrays intersection

You are given a list of arrays of integers. Write a script to return the common elements in all the arrays.

Examples


Example 1
Input: $list = ( [1, 2, 3, 4], [4, 5, 6, 1], 
   [4, 2, 1, 3] )
Output: (1, 4)

Example 2
Input: $list = ( [1, 0, 2, 3], [2, 4, 5] )
Output: (2)

Example 3
Input: $list = ( [1, 2, 3], [4, 5], [6] )
Output: ()

Analysis

This is interesting in that it is trickier to find what isn't there than what is there. So after some trial and lack of success I settled on the following algorithm:

  • Loop over each $value in the first array
  • Look to see if $value appears in each other array
  • If it does, add it to the output array and replace it in the input array with 1e6 (see below for the reason)

The challenge statement is silent on what is expected if a number appears more than once in any array. I took the view that if a number appears multiple times in every array, then we report the minimum number of times that it appears. So for example if the arrays are
(1, 2, 5, 2, 6, 2, 3), (4, 2, 2) I report (2, 2), as there are 2 - and no more - 2s in each array.

The reason for replacing the matched value with 1e6 is so that it isn't there to be matched with a second (etc) ocurrence of the same number in the first array.

The examples also lack 0 or negative numbers although the task statement just says 'integers'. If duplicated, 0 and negative numbers are not allowed, there is an alternative solution:

  • Loop over each value $v in each array, incrementing $count[$v] for each
  • Output all the $v values where $count[$v] equals the number of arrays.

And lastly, I also toyed with making the arrays into strings with a separator - like ~2~3~4~5~ - and using regular expressions to check for the presence of each value in the first array. That can handle 0 and negative values, but not (easily) repeated values.

Try it 

Try running the script with any input:



example: [1, 2, 3], [2, 3, 4, 5]

Script


#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-02-24
use utf8;     # Week 310 - task 1 - Arrays intersection
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

arrays_intersection([1, 2, 3, 4], [4, 5, 6, 1], [4, 2, 1, 3]);
arrays_intersection([1, 0, 2, 3], [2, 4, 5]);
arrays_intersection([1, 2, 3], [4, 5], [6]);
arrays_intersection([-31, 56, 22, 0, -99], [-31, 56, 100, 423], [-99, 0, 56, -31]);
arrays_intersection([2, 2, 2, 2, 2], [2, 2, 2]);
arrays_intersection([1, 2, 3, 4, 5]);

sub arrays_intersection {
    
    my (@arrays, $value, $missing, $a, $v, @input, @output, @other, $i);
    
    # input
    @arrays = @_;
    $input[$_] = '[' . join(', ', @{$arrays[$_]}) . ']' for 0 .. $#arrays;
    say qq[\nInput:  \@list = (] . join(', ', @input) . ')';
    
    # loop over numbers in first array
    for $value (@{$arrays[0]}) {
        $missing = 0;
    
        # loop over the other arrays
        A: for $a (1 .. $#arrays) {
    
            # loop over values in the other array
            @other = @{$arrays[$a]};
            for $i (0 .. $#other) {
                
                # match - zap it to prevent re-use
                if ($value == $other[$i]) {
                    $arrays[$a]->[$i] = 1e6;
                    next A;
                }
            }
            
            # no match
            $missing = 1;
        }
        push @output, $value unless $missing;
    }
    say qq[Output: (] . join(', ', sort @output) . ')';
}

Output


Input:  @list = ([1, 2, 3, 4], [4, 5, 6, 1], [4, 2, 1, 3])
Output: (1, 4)

Input:  @list = ([1, 0, 2, 3], [2, 4, 5])
Output: (2)

Input:  @list = ([1, 2, 3], [4, 5], [6])
Output: ()

Input:  @list = ([-31, 56, 22, 0, -99], 
   [-31, 56, 100, 423], [-99, 0, 56, -31])
Output: (-31, 56)

Input:  @list = ([2, 2, 2, 2, 2], [2, 2, 2])
Output: (2, 2, 2)

Input:  @list = ([1, 2, 3, 4, 5])
Output: (1, 2, 3, 4, 5)

 

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