The weekly challenge 306 - Task 2: Last Element

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-306/#TASK2
  3 #
  4 # Task 2: Last Element
  5 # ====================
  6 #
  7 # You are given a array of integers, @ints.
  8 #
  9 # Write a script to play a game where you pick two biggest integers in the
 10 # given array, say x and y. Then do the following:
 11 #
 12 #   a) if x == y then remove both from the given array
 13 #   b) if x != y then remove x and replace y with (y - x)
 14 #
 15 # At the end of the game, there is at most one element left.
 16 #
 17 # Return the last element if found otherwise return 0.
 18 #
 19 ## Example 1
 20 ##
 21 ## Input: @ints = (3, 8, 5, 2, 9, 2)
 22 ## Output: 1
 23 ##
 24 ## Step 1: pick 8 and 9 => (3, 5, 2, 1, 2)
 25 ## Step 2: pick 3 and 5 => (2, 2, 1, 2)
 26 ## Step 3: pick 2 and 1 => (1, 2, 2)
 27 ## Step 4: pick 2 and 1 => (1, 2)
 28 ## Step 5: pick 1 and 2 => (1)
 29 #
 30 ## Example 2
 31 ##
 32 ## Input: @ints = (3, 2, 5)
 33 ## Output: 0
 34 ##
 35 ## Step 1: pick 3 and 5 => (2, 2)
 36 ## Step 2: pick 2 and 2 => ()
 37 #
 38 ############################################################
 39 ##
 40 ## discussion
 41 ##
 42 ############################################################
 43 #
 44 # There is a bit of ambiguity in the description that is clarified
 45 # by the examples: if there are multiple elements of different value,
 46 # but also multiple elements that are as big as the maximum element,
 47 # then pick one of the biggest values and one of the second biggest,
 48 # NOT two of the biggest. So from (2, 2, 1, 2) pick 2 and 1, not
 49 # 2 and 2.
 50 # With that clarified, we can now implement the whole thing: Search
 51 # the two biggest values in the array, then handle them as layed out
 52 # in the rules.
 53 #
 54 
 55 use v5.36;
 56 
 57 last_element(3, 8, 5, 2, 9, 2);
 58 last_element(3, 2, 5);
 59 
 60 sub last_element(@ints) {
 61    say "Input: (" . join(",", @ints) . ")";
 62    while(@ints) {
 63       if(1 == scalar(@ints)) {
 64          say "Output: " . $ints[0];
 65          return;
 66       }
 67       my ($max1, $max2) = @ints[0..1];
 68       if($max1 < $max2) {
 69          ($max1, $max2) = ($max2, $max1);
 70       }
 71       foreach my $i (2..$#ints) {
 72          if($ints[$i] > $max1) {
 73             ($max1, $max2) = ($ints[$i], $max1);
 74          } elsif ($max1 == $max2) {
 75             $max2 = $ints[$i];
 76          } else {
 77             if($ints[$i] > $max2 && $ints[$i] < $max1) {
 78                $max2 = $ints[$i];
 79             }
 80          }
 81       }
 82       if($max1 == $max2) {
 83          # remove two occurences of $max1
 84          my @tmp = ();
 85          my $removed = 0;
 86          foreach my $elem (@ints) {
 87             if($elem == $max1 && $removed < 2) {
 88                $removed++;
 89                next;
 90             }
 91             push @tmp, $elem;
 92          }
 93          @ints = @tmp;
 94       } else {
 95          # remove max2, replace max1 with max1-max2
 96          my @tmp = ();
 97          my $new = $max1 - $max2;
 98          my $removed = 0;
 99          my $replaced = 0;
100          foreach my $elem (@ints) {
101             if($elem == $max1 && ! $removed) {
102                $removed = 1;
103                next;
104             }
105             if($elem == $max2 && ! $replaced) {
106                push @tmp, $new;
107                $replaced = 1;
108                next;
109             }
110             push @tmp, $elem;
111          }
112          @ints = @tmp;
113       }
114    }
115    say "Output: 0";
116 }