The weekly challenge 296 - Task 2: Matchstick Square

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-296/#TASK2
 3 #
 4 # Task 2: Matchstick Square
 5 # =========================
 6 #
 7 # You are given an array of integers, @ints.
 8 #
 9 # Write a script to find if it is possible to make one square using the sticks
10 # as in the given array @ints where $ints[ì] is the length of ith stick.
11 #
12 ## Example 1
13 ##
14 ## Input: @ints = (1, 2, 2, 2, 1)
15 ## Output: true
16 ##
17 ## Top: $ints[1] = 2
18 ## Bottom: $ints[2] = 2
19 ## Left: $ints[3] = 2
20 ## Right: $ints[0] and $ints[4] = 2
21 #
22 ## Example 2
23 ##
24 ## Input: @ints = (2, 2, 2, 4)
25 ## Output: false
26 #
27 ## Example 3
28 ##
29 ## Input: @ints = (2, 2, 2, 2, 4)
30 ## Output: false
31 #
32 ## Example 4
33 ##
34 ## Input: @ints = (3, 4, 1, 4, 3, 1)
35 ## Output: true
36 #
37 ############################################################
38 ##
39 ## discussion
40 ##
41 ############################################################
42 #
43 # First, we calculate the sum of all elements in the array. If that
44 # isn't divisible by 4, we can return false right away. Otherwise, we
45 # divide it by 4. Then we produce all permutations of the array
46 # (Algorithm::Combinatorics has a nice iterator for that). If it is
47 # possible to make a square from the matches, one at least one permutation of
48 # the array will be lined up such that subsequent numbers sum up to one
49 # fourth of the overall sum, so we will look out for such a case. If we
50 # find it, just return true. If we don't, then at the end after producing
51 # all possible permutations, we can return false.
52 
53 use strict;
54 use warnings;
55 use List::Util qw(sum0);
56 use Algorithm::Combinatorics qw(permutations);
57 
58 matchstick_square(1, 2, 2, 2, 1);
59 matchstick_square(2, 2, 2, 4);
60 matchstick_square(2, 2, 2, 2, 4);
61 matchstick_square(3, 4, 1, 4, 3, 1);
62 matchstick_square(4, 3, 3, 2, 2, 2, 2, 2, 2, 2);
63 matchstick_square(4, 3, 3, 2, 2, 2, 2, 2, 2);
64 
65 sub matchstick_square {
66    my @ints = @_;
67    print "Input: (" . join(", ", @ints) . ")\n";
68    my $sum = sum0(@ints);
69    if($sum % 4) {
70       return print("Output: false\n");
71    }
72    $sum /= 4;
73    my $iter = permutations(\@ints);
74    OUTER: while(my $p = $iter->next) {
75       my $s = 0;
76       foreach my $elem (@$p) {
77          $s += $elem;
78          if($s > $sum) {
79             next OUTER;
80          }
81          if($s == $sum) {
82             $s = 0;
83          }
84       }
85       if($s == 0) {
86          return print "Output: true\n";
87       }
88    }
89    print "Output: false\n";
90 }