All good things

Weekly challenge 199 — 9 January 2023

Week 199 - 9 Jan 2023

Task 1

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.

Example 1Input: @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 2Input: @list = (1,2,3) Output: 0Example 3Input: @list = (1,1,1,1) Output: 6 Good pairs are below: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3)

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.

#!/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] : ''; }

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain