Peter
Peter Campbell Smith

All good things

Weekly challenge 199 — 9 January 2023

Week 199: 9 Jan 2023

Task 1

Task — Good pairs

You are given a list of integers, @list. Write a script to find the total count of Good Pairs. A pair (i, j) is called good if list[i] == list[j] and i < j.

Examples


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

There are 4 good pairs found as below:
(0,3)
(0,4)
(3,4)
(2,5)

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

Example 3
Input: @list = (1,1,1,1)
Output: 6

Good pairs are below:
(0,1)
(0,2)
(0,3)
(1,2)
(1,3)
(2,3)

Analysis

If @list contains $n entries then the obvious way to do this is:

for $i (0 .. $n - 1) {
    for $j ($i + 1 .. $n) {
        if ($list[$i] == $list[$j]) {
            -- we have an answer
        }
    }
}

Doing the loops like this ensures that we have tested all possible values of $i, $j where $i < $j.

The test for $list[$i] == $list[$j] is performed
($n - 1) ** 2 / 2 times, but it is not obvious to me that there is a more efficient way of doing this.

Try it 

Try running the script with any input:



example: 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-09
# PWC 199 task 1

use v5.28;
use utf8;
use warnings;

# You are given a list of integers, @list. Write a script to find the total count of Good Pairs. 
# A pair (i, j) is called good if list[i] == list[j] and i < j.

my (@tests, $test, @list, $i, $j, $count, $rubric);
@tests = ([1, 2, 3, 1, 1, 3], [1, 2, 3], [1, 1, 1, 1], [1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1]);

# loop over tests
for $test (@tests) {
    
    # initialise
    @list = @$test; 
    $count = 0;
    $rubric = '';
    
    # loop over first candidate
    for $i (0 .. scalar(@list) - 2) {
        
        # loop over second candidate
        for $j ($i + 1 .. scalar(@list) - 1) {
            
            # check for goodness
            if ($list[$i] == $list[$j]) {
                $count ++;
                $rubric .= qq[($i, $j) - both equal $list[$i]\n];
            }
        }
    }
    
    # report
    say qq[Input:  (] . join(', ', @list). qq[)\nOutput: $count];
    say $rubric ? qq[Good pairs are:\n$rubric] : '';
}

Output


Input:  (1, 2, 3, 1, 1, 3)
Output: 4
Good pairs are:
(0, 3) - both equal 1
(0, 4) - both equal 1
(2, 5) - both equal 3
(3, 4) - both equal 1

Input:  (1, 2, 3)
Output: 0

Input:  (1, 1, 1, 1)
Output: 6
Good pairs are:
(0, 1) - both equal 1
(0, 2) - both equal 1
(0, 3) - both equal 1
(1, 2) - both equal 1
(1, 3) - both equal 1
(2, 3) - both equal 1

Input:  (1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1)
Output: 7
Good pairs are:
(0, 5) - both equal 1
(0, 10) - both equal 1
(1, 6) - both equal 3
(2, 7) - both equal 5
(3, 8) - both equal 7
(4, 9) - both equal 9
(5, 10) - both equal 1

 

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