The weekly challenge 389 - Task 2: ZigZag Subarray

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-389/#TASK2
  3 #
  4 # Task 2: ZigZag Subarray
  5 # =======================
  6 #
  7 # You are given an array of integers.
  8 #
  9 # Write a script to find the length of the longest contiguous subarray where
 10 # the numbers alternate between strictly increasing and strictly decreasing (a
 11 # ZigZag pattern).
 12 #
 13 ##  A sequence of numbers $A = [a0, a1, …, ak]$ with length $k >= 1 is
 14 ##  considered a ZigZag sequence if every adjacent pair alternates direction:
 15 #
 16 # a_0 < a_1 > a_2 < a_3 > ...
 17 # OR
 18 # a_0 > a_1 < a_2 > a_3 < ...
 19 #
 20 # NOTE: A single element (length 1) or any two distinct elements (length 2) are
 21 # automatically valid ZigZag sequences. Equal adjacent numbers (e.g., 5, 5)
 22 # break the pattern.
 23 #
 24 ## Example 1
 25 ##
 26 ## Input: @nums = (9, 4, 2, 10, 7, 8, 8, 1, 9)
 27 ## Output: 5
 28 ##
 29 ## ZigZag subarray: (4, 2, 10, 7, 8)
 30 #
 31 ## Example 2
 32 ##
 33 ## Input: @nums = (1, 7, 4, 9, 2, 5)
 34 ## Output: 6
 35 ##
 36 ## ZigZag subarray: (1, 7, 4, 9, 2, 5)
 37 #
 38 ## Example 3
 39 ##
 40 ## Input: @nums = (1, 2, 3, 4, 5)
 41 ## Output: 2
 42 ##
 43 ## ZigZag subarray: (1, 2)
 44 #
 45 ## Example 4
 46 ##
 47 ## Input: @nums = (4, 4, 4)
 48 ## Output: 1
 49 #
 50 ## Example 5
 51 ##
 52 ## Input: @nums = (10, 20, 15, 12, 18)
 53 ## Output: 3
 54 ##
 55 ## ZigZag subarray: (10, 20, 15)
 56 #
 57 ############################################################
 58 ##
 59 ## discussion
 60 ##
 61 ############################################################
 62 #
 63 # We check all possible subarrays. We keep track of the maximum length
 64 # of the zigzag subarrays.
 65 
 66 use v5.36;
 67 
 68 zigzag_subarray(9, 4, 2, 10, 7, 8, 8, 1, 9);
 69 zigzag_subarray(1, 7, 4, 9, 2, 5);
 70 zigzag_subarray(1, 2, 3, 4, 5);
 71 zigzag_subarray(4, 4, 4);
 72 zigzag_subarray(10, 20, 15, 12, 18);
 73 
 74 sub zigzag_subarray(@nums) {
 75     say "Input: (" . join(", ", @nums) . ")";
 76     my $max_length = 0;
 77     foreach my $i (0..$#nums) {
 78         foreach my $j ($i..$#nums) {
 79             my $n = is_zigzag_subarray(@nums[$i..$j]);
 80             $max_length = $n if $n > $max_length;
 81         }
 82     }
 83     say "Output: $max_length";
 84 }
 85 
 86 sub is_zigzag_subarray(@array) {
 87     return 1 if scalar(@array) == 1;
 88     my $count = 1;
 89     my $last_one = "X";
 90     foreach my $i (1..$#array) {
 91         if($array[$i-1] > $array[$i]) {
 92             return 0 if $last_one eq ">";
 93             $count++;
 94             $last_one = ">";
 95         } elsif ($array[$i-1] < $array[$i]) {
 96             return 0 if $last_one eq "<";
 97             $count++;
 98             $last_one = "<";
 99         } else {
100             return 0;
101         }
102     }
103     return $count;
104 }