The weekly challenge 345 - Task 2: Last Visitor

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-345/#TASK2
  3 #
  4 # Task 2: Last Visitor
  5 # ====================
  6 #
  7 # You are given an integer array @ints where each element is either a positive integer or -1.
  8 #
  9 # We process the array from left to right while maintaining two lists:
 10 #
 11 ## @seen: stores previously seen positive integers (newest at the front)
 12 ## @ans: stores the answers for each -1
 13 #
 14 # Rules:
 15 #
 16 ## If $ints[i] is a positive number -> insert it at the front of @seen
 17 ## If $ints[i] is -1:
 18 #
 19 # Let $x be how many -1s in a row we’ve seen before this one.
 20 #
 21 # If $x < len(@seen) -> append seen[x] to @ans
 22 #
 23 # Else -> append -1 to @ans
 24 #
 25 # At the end, return @ans.
 26 #
 27 ## Example 1
 28 ##
 29 ## Input: @ints = (5, -1, -1)
 30 ## Output: (5, -1)
 31 ##
 32 ## @seen = (5)
 33 ## First  -1: @ans = (5)
 34 ## Second -1: @ans = (5, -1)
 35 #
 36 #
 37 ## Example 2
 38 ##
 39 ## Input: @ints = (3, 7, -1, -1, -1)
 40 ## Output: (7, 3, -1)
 41 ##
 42 ## @seen = (3, 7)
 43 ## First  -1: @ans = (7)
 44 ## Second -1: @ans = (7, 3)
 45 ## Third  -1: @ans = (7, 3, -1)
 46 #
 47 #
 48 ## Example 3
 49 ##
 50 ## Input: @ints = (2, -1, 4, -1, -1)
 51 ## Output: (2, 4, 2)
 52 #
 53 #
 54 ## Example 4
 55 ##
 56 ## Input: @ints = (10, 20, -1, 30, -1, -1)
 57 ## Output: (20, 30, 20)
 58 #
 59 #
 60 ## Example 5
 61 ##
 62 ## Input: @ints = (-1, -1, 5, -1)
 63 ## Output: (-1, -1, 5)
 64 #
 65 ############################################################
 66 ##
 67 ## discussion
 68 ##
 69 ############################################################
 70 #
 71 # We just implement the rules as layed out in the exercise.
 72 # We use unshift to add at the beginning of @seen if needed,
 73 # otherwise we check our $x and either add $seen[$x] to @ans
 74 # or we add -1. Don't forget to increment $x of course. And
 75 # reset it to 0 if the number we're looking at is > 0.
 76 
 77 use v5.36;
 78 
 79 
 80 last_visitor(5, -1, -1);
 81 last_visitor(3, 7, -1, -1, -1);
 82 last_visitor(2, -1, 4, -1, -1);
 83 last_visitor(10, 20, -1, 30, -1, -1);
 84 last_visitor(-1, -1, 5, -1);
 85 
 86 sub last_visitor(@ints) {
 87     say "Input: (" . join(", ", @ints) . ")";
 88     my @seen = ();
 89     my @ans = ();
 90     my $x = 0;
 91     foreach my $elem (@ints) {
 92         if($elem > 0) {
 93             $x = 0;
 94             unshift @seen, $elem;
 95         } else {
 96             if($x < scalar(@seen)) {
 97                 push @ans, $seen[$x];
 98             } else {
 99                 push @ans, -1;
100             }
101             $x++;
102         }
103     }
104     say "Output: (" . join(", ", @ans) . ")";
105 }