The weekly challenge 245 - Task 2: Largest of Three

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-245/#TASK2
 3 #
 4 # Task 2: Largest of Three
 5 # ========================
 6 #
 7 # You are given an array of integers >= 0.
 8 #
 9 # Write a script to return the largest number formed by concatenating some of
10 # the given integers in any order which is also multiple of 3. Return -1 if
11 # none found.
12 #
13 ## Example 1
14 ##
15 ## Input: @ints = (8, 1, 9)
16 ## Output: 981
17 ##
18 ## 981 % 3 == 0
19 #
20 ## Example 2
21 ##
22 ## Input: @ints = (8, 6, 7, 1, 0)
23 ## Output: 8760
24 #
25 ## Example 3
26 ##
27 ## Input: @ints = (1)
28 ## Output: -1
29 #
30 ############################################################
31 ##
32 ## discussion
33 ##
34 ############################################################
35 #
36 # While all examples in the description use single-digit numbers,
37 # there is nothing that would require this. So in order to catch all
38 # solutions, we need all possible permutations of all subsets of the
39 # array and of the numbers created out of those we need the biggest
40 # one that is divisible by 3.
41 
42 use strict;
43 use warnings;
44 use Algorithm::Combinatorics qw(permutations subsets);
45 
46 largest_of_three(8, 1, 9);
47 largest_of_three(8, 6, 7, 1, 0);
48 largest_of_three(1);
49 largest_of_three(8, 60, 7);
50 largest_of_three(80, 6, 7);
51 
52 sub largest_of_three {
53    my @ints = @_;
54    print "Input: (" . join(", ", @ints) . ")\n";
55    my $result;
56    my $iter = subsets(\@ints);
57    while(my $s = $iter->next) {
58       next unless @$s;
59       my $iter2 = permutations($s);
60       while(my $p = $iter2->next) {
61          my $num = join("", @$p);
62          next unless $num;
63          next unless $num % 3 == 0;
64          $result = $num unless defined $result;
65          $result = $num if $num > $result;
66       }
67    }
68    if(defined $result) {
69       print "Output: $result\n";
70    } else {
71       print "Output: -1\n";
72    }
73 }
74