The weekly challenge 396 - Task 2: Trionic Array

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-396/#TASK2
  3 #
  4 # Task 2: Trionic Array
  5 # =====================
  6 #
  7 # You are given an array of integer.
  8 #
  9 # Write a script to return true if the given array is Trionic otherwise return
 10 # false.
 11 #
 12 ## An array is trionic if there exist indices 0 < p < q < n − 1 such that
 13 ## arr[0…p] is strictly increasing, arr[p…q] is strictly decreasing, and
 14 ## arr[q…n − 1] is strictly increasing.
 15 #
 16 ## Example 1
 17 ##
 18 ## Input: @arr = (1, 3, 5, 4, 2, 6, 8)
 19 ## Output: true
 20 ##
 21 ## Choose p = 2 and q = 4
 22 ## $arr[0..2] = (1, 3, 5) (strictly increasing)
 23 ## $arr[2..4] = (5, 4, 2) (strictly decreasing)
 24 ## $arr[4..6] = (2, 6, 8) (strictly increasing)
 25 ##
 26 ## Valid indices: 0 < p (2) < q (4) < n-1 (6).
 27 #
 28 ## Example 2
 29 ##
 30 ## Input: @arr = (1, 4, 4, 2, 1, 3, 5)
 31 ## Output: false
 32 ##
 33 ## The first segment (1, 4, 4) contains duplicate adjacent values, so it is not
 34 ## strictly increasing.
 35 ## No valid p and q exist to satisfy all three strictly monotonic conditions.
 36 #
 37 ## Example 3
 38 ##
 39 ## Input: @arr = (2, 10, 3, 1, 9)
 40 ## Output: true
 41 ##
 42 ## Choose p = 1 and q = 3.
 43 ## $arr[0..1] = (2, 10)    (strictly increasing)
 44 ## $arr[1..3] = (10, 3, 1) (strictly decreasing)
 45 ## $arr[3..4] = (1, 9)     (strictly increasing)
 46 #
 47 ## Example 4
 48 ##
 49 ## Input: @arr = (1, 2, 3, 4, 3, 2, 1)
 50 ## Output: false
 51 ##
 52 ## This is a standard mountain array (strictly increasing, then strictly
 53 ## decreasing).
 54 ## There is no second valley (q) that transitions back into a strictly
 55 ## increasing third segment before reaching the end of the array.
 56 #
 57 ## Example 5
 58 ##
 59 ## Input: @arr = (1, 3, 6, 4, 2, 7, 8, 4)
 60 ## Output: false
 61 #
 62 ############################################################
 63 ##
 64 ## discussion
 65 ##
 66 ############################################################
 67 #
 68 # Keeping state of whether we are in the first increasing, the
 69 # decreasing or the second increasing part, we move through the
 70 # array, bailing out on all error conditions that we meet. In
 71 # the end, we return true only if our state indicates we are in
 72 # the second increasing state.
 73 
 74 use v5.36;
 75 
 76 sub trionic_array(@arr) {
 77     say "Input: (" . join(", ", @arr) . ")";
 78     my $trio = 0;
 79     foreach my $i (0..$#arr-1) {
 80         if($trio == 0) {
 81             next if $arr[$i+1] > $arr[$i];
 82             # if we don't strictly increase at the first position, then
 83             # we can bail out in error
 84             return say "Output: false" if $i == 0;
 85             # if we're not strictly in/decreasing, then we can bail
 86             # out as well
 87             return say "Output: false" if $arr[$i+1] == $arr[$i];
 88             # Now we're strictly decreasing
 89             $trio = 1;
 90         } elsif ($trio == 1) {
 91             next if $arr[$i+1] < $arr[$i];
 92             # if we're not strictly in/decreasing, then we can bail out
 93             return say "Output: false" if $arr[$i+1] == $arr[$i];
 94             # now we're strictly increasing again
 95             $trio = 2;
 96         } else {
 97             next if $arr[$i+1] > $arr[$i];
 98             # if we're not strictly increasing, then we can bail out
 99             return say "Output: false";
100         }
101     }
102     return say "Output: true" if $trio == 2;
103     say "Output: false";
104 }
105 
106 trionic_array(1, 3, 5, 4, 2, 6, 8);
107 trionic_array(1, 4, 4, 2, 1, 3, 5);
108 trionic_array(2, 10, 3, 1, 9);
109 trionic_array(1, 2, 3, 4, 3, 2, 1);
110 trionic_array(1, 3, 6, 4, 2, 7, 8, 4);