1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-211/#TASK2
 3 #
 4 # Task 2: Split Same Average
 5 # ==========================
 6 #
 7 # You are given an array of integers.
 8 #
 9 # Write a script to find out if the given can be split into two separate arrays whose average are the same.
10 #
11 ## Example 1:
12 ##
13 ## Input: @nums = (1, 2, 3, 4, 5, 6, 7, 8)
14 ## Output: true
15 ##
16 ## We can split the given array into (1, 4, 5, 8) and (2, 3, 6, 7).
17 ## The average of the two arrays are the same i.e. 4.5.
18 #
19 ## Example 2:
20 ##
21 ## Input: @list = (1, 3)
22 ## Output: false
23 #
24 ############################################################
25 ##
26 ## discussion
27 ##
28 ############################################################
29 #
30 # This is basically a problem on how to create all possible
31 # combinations and checking if any of these allows for the
32 # same average
33 
34 use strict;
35 use warnings;
36 use List::Util qw(sum);
37 
38 split_same_average(1, 2, 3, 4, 5, 6, 7, 8);
39 split_same_average(1, 3);
40 
41 sub split_same_average {
42    my @list = @_;
43    print "Input: (" . join(", ", @list) . ")\n";
44    if(has_matching_split([@list], [], [])) {
45       print "Output: true\n";
46    } else {
47       print "Output: false\n";
48    }
49 }
50 
51 # check if the rest of the current list, with two partially
52 # filled lists from the previous elements, can still be turned
53 # into two lists that have the same average
54 # so we create all possible combinations step by step, if we have
55 # found one we check if it has lead us to two lists of the same
56 # average, and otherwise return a non-true value (which will lead
57 # to the next recursive call)
58 sub has_matching_split {
59    my ($rest, $list1, $list2) = @_;
60    if(@$rest) {
61       # we still have some elements to distribute among the two
62       # lists, so we get the first element of this remainder
63       my $first = shift @$rest;
64       # if by adding this to the first partial list we can achieve
65       # a combination where both lists have the same average, we can
66       # finish searching and return 1
67       if(has_matching_split([@$rest], [@$list1, $first], [@$list2])) {
68          return 1;
69       }
70       # same is true if we can achieve a good combination by adding the
71       # element to the second partial list
72       if(has_matching_split([@$rest], [@$list1], [@$list2, $first])) {
73          return 1;
74       }
75       # if we didn't succeed either way, we can't find any matching combination
76       # that leads to two arrays with the same average, so we return 0
77       return 0;
78    } else {
79       # we have distributed all elements to the two lists, so if both
80       # lists are non-empty and share the same average we have found a
81       # solution
82       if(@$list1 && @$list2 && average(@$list1) == average(@$list2)) {
83          return 1;
84       }
85    }
86    return 0;
87 }
88 
89 # of course we need a helper function to calculate the average of all
90 # elements of a list
91 sub average {
92    my @list = @_;
93    my $count = @list;
94    return undef unless $count;
95    my $sum = sum @list;
96    return $sum / $count;
97 }