The weekly challenge 297 - Task 1: Contiguous Array

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-297/#TASK1
 3 #
 4 # Task 1: Contiguous Array
 5 # ========================
 6 #
 7 # You are given an array of binary numbers, @binary.
 8 #
 9 # Write a script to return the maximum length of a contiguous subarray with an
10 # equal number of 0 and 1.
11 #
12 ## Example 1
13 ##
14 ## Input: @binary = (1, 0)
15 ## Output: 2
16 ##
17 ## (1, 0) is the longest contiguous subarray with an equal number of 0 and 1.
18 #
19 ## Example 2
20 ##
21 ## Input: @binary = (0, 1, 0)
22 ## Output: 2
23 ##
24 ## (1, 0) or (0, 1) is the longest contiguous subarray with an equal number of 0 and 1.
25 #
26 ## Example 3
27 ##
28 ## Input: @binary = (0, 0, 0, 0, 0)
29 ## Output: 0
30 #
31 ## Example 4
32 ##
33 ## Input: @binary = (0, 1, 0, 0, 1, 0)
34 ## Output: 4
35 #
36 ############################################################
37 ##
38 ## discussion
39 ##
40 ############################################################
41 #
42 # For all possible sub-arrays of the input array, check whether
43 # the number of ones and zeroes is the same. If it is and the
44 # length of the subarray is bigger than the current maximum, set
45 # a new maximum. If the length of the sub-array is shorter than
46 # the current maximum, we can short-circuit the whole operation
47 # a little as well.
48 
49 use strict;
50 use warnings;
51 
52 contiguous_array(1, 0);
53 contiguous_array(0, 1, 0);
54 contiguous_array(0, 0, 0, 0, 0);
55 contiguous_array(0, 1, 0, 0, 1, 0);
56 
57 sub contiguous_array {
58    my @binary = @_;
59    print "Input: (" . join(", ", @binary) . ")\n";
60    my $max = 0;
61    foreach my $i (0..$#binary) {
62       foreach my $j ($i+1..$#binary) {
63          my $len = $j + 1 - $i;
64          next if $len < $max;
65          my $zero = 0;
66          my $one = 0;
67          foreach my $k ($i..$j) {
68             if($binary[$k] == 0) {
69                $zero++;
70             } else {
71                $one++;
72             }
73          }
74          if($zero == $one) {
75             $max = $len;
76          }
77       }
78    }
79    print "Output: $max\n";
80 }