perl logo Perl logo (Thanks to Olaf Alders)

The weekly challenge 336 - Task 1: Equal Group

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-336/#TASK1
  3 #
  4 # Task 1: Equal Group
  5 # ===================
  6 #
  7 # You are given an array of integers.
  8 #
  9 # Write a script to return true if the given array can be divided into one or
 10 # more groups: each group must be of the same size as the others, with at least
 11 # two members, and with all members having the same value.
 12 #
 13 ## Example 1
 14 ##
 15 ## Input: @ints = (1,1,2,2,2,2)
 16 ## Output: true
 17 ##
 18 ## Groups: (1,1), (2,2), (2,2)
 19 #
 20 #
 21 ## Example 2
 22 ##
 23 ## Input: @ints = (1,1,1,2,2,2,3,3)
 24 ## Output: false
 25 ##
 26 ## Groups: (1,1,1), (2,2,2), (3,3)
 27 #
 28 #
 29 ## Example 3
 30 ##
 31 ## Input: @ints = (5,5,5,5,5,5,7,7,7,7,7,7)
 32 ## Output: true
 33 ##
 34 ## Groups: (5,5,5,5,5,5), (7,7,7,7,7,7)
 35 #
 36 #
 37 ## Example 4
 38 ##
 39 ## Input: @ints = (1,2,3,4)
 40 ## Output: false
 41 #
 42 ############################################################
 43 ##
 44 ## discussion
 45 ##
 46 ############################################################
 47 #
 48 # You can create matching groups if all the numbers of integers of the same
 49 # value are divisible by a common prime. So we check if we find a common prime
 50 # factor: for each prime, check if it is a divisor of the number and count that,
 51 # and if a prime happens to appear as often as there are distinct numbers in
 52 # the input array, we can return "true". If in the end, this wasn't the case
 53 # for any prime from our list, we return "false".
 54 
 55 use v5.36;
 56 use List::Util qw(max);
 57 
 58 equal_group(1,1,2,2,2,2);
 59 equal_group(1,1,1,2,2,2,3,3);
 60 equal_group(5,5,5,5,5,5,7,7,7,7,7,7);
 61 equal_group(1,2,3,4);
 62 
 63 sub equal_group( @ints ) {
 64     say "Input: (" . join(", ", @ints) . ")";
 65     my $numbers;
 66     foreach my $i (@ints) {
 67         $numbers->{$i}++;
 68     }
 69     my $biggest = max( map { $numbers->{$_} } keys %$numbers );
 70     my @primes;
 71     foreach my $n (2..$biggest) {
 72         push @primes, $n if is_prime($n);
 73     }
 74     my $primes_found;
 75     foreach my $n (keys %$numbers) {
 76         foreach my $prime (@primes) {
 77             $primes_found->{$prime}++ unless $numbers->{$n} % $prime;
 78         }
 79     }
 80     foreach my $f (keys %$primes_found) {
 81         return say "true" if $primes_found->{$f} == scalar(keys %$numbers);
 82     }
 83     return say "false";
 84 }
 85 
 86 
 87 ### From the solution of the weekly challenge 223:
 88 sub is_prime {
 89    my $num = shift;
 90    return 0 if $num == 1;
 91    my $divider = 2;
 92    while($divider <= sqrt($num)) {
 93       if(int($num/$divider) == $num/$divider) {
 94          return 0;
 95       }
 96       $divider++;
 97    }
 98    return 1;
 99 }
100