Peter
Peter Campbell Smith

Pairs and ups and downs

Weekly challenge 249 — 25 December 2023

Week 249: 25 Dec 2023

Task 1

Task — Equal pairs

You are given an array of integers with even number of elements. Write a script to divide the given array into equal pairs such that:

  1. Each element belongs to exactly one pair.
  2. The elements present in a pair are equal.

Examples


Example 1
Input: @ints = (3, 2, 3, 2, 2, 2)
Output: (2, 2), (3, 3), (2, 2)

There are 6 elements in @ints.
They should be divided into 6 / 2 = 3 pairs.
@ints is divided into the pairs (2, 2), (3, 3), and 
(2, 2) satisfying all the conditions.

Example 2
Input: @ints = (1, 2, 3, 4)
Output: ()

There is no way to divide @ints into pairs such that the 
pairs satisfy every condition.

Analysis

There are a number of ways to approach this, but I ended up with making a single pass through @ints and for each element $j, if $seen{$j} existed, I deleted it and if it didn't exist, I created it.

So at the end, if there was anything left in %seen then at least one number existed in @ints an odd number of times and thus couldn't be paired. If @ints was empty, then all the numbers could be paired.

To provide the required output, I built it up each time I deleted a value from %seen.

Try it 

Try running the script with any input:



example: 1, 2, 3, 4, 2, 3, 1, 4

Script


#!/usr/bin/perl

use v5.26;    # The Weekly Challenge - 2023-12-25
use utf8;     # Week 249 task 1 - Equal pairs
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

equal_pairs(1, 2, 3, 4, 1, 2, 3, 4);
equal_pairs(1, 2, 3, 4, 1, 2, 3);
equal_pairs(77, 23, 45, 12, 23, 99, 99, 12, 77, 45, 12, 12);

sub equal_pairs {
    
    my ($j, %seen, $result);
    %seen = ();
    
    # loop over supplied integers
    for $j (@_) {
        
        # seen one unpaired already, so this is an answer
        if ($seen{$j}) { 
            $result .= qq[($j, $j), ];
            delete $seen{$j};
            
        # note that we are looking for a mate
        } else {
            $seen{$j} = 1;
        }
    }
    
    # output answers: if success then %seen will be empty
    say qq[\nInput:  \@ints = (] . join(', ', @_) . ')';
    say qq[Output: ] . (scalar keys %seen ? 'not possible' : substr($result, 0, -2));
}
    

Output


Input:  @ints = (1, 2, 3, 4, 1, 2, 3, 4)
Output: (1, 1), (2, 2), (3, 3), (4, 4)

Input:  @ints = (1, 2, 3, 4, 1, 2, 3)
Output: not possible

Input:  @ints = (77, 23, 45, 12, 23, 99, 99, 12, 77, 45, 12, 12)
Output: (23, 23), (99, 99), (12, 12), (77, 77), (45, 45), (12, 12)

 

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